65.4. GIN 索引

65.4. GIN 索引
上一页	上一级	Chapter 65. 内置索引访问方法	首页	下一页

65.4. GIN 索引 #

65.4.1. 简介
65.4.2. 内置操作符类
65.4.3. 可扩展性
65.4.4. 实现
65.4.5. GIN 技巧与诀窍
65.4.6. 限制
65.4.7. 示例

65.4.1. 简介 #

GIN 是 Generalized Inverted Index（广义倒排索引）的缩写。GIN 用于处理这样的场景：被索引的项是复合值，而索引需要处理的查询要搜索出现在复合项内部的元素值。例如，项可以是文档，而查询可以是搜索包含特定单词的文档。

我们用项一词指代要被索引的复合值，用键一词指代元素值。 GIN 总是存储并搜索键，而不是项值本身。

GIN 索引存储一组 (键, posting list) 对，其中 posting list 是出现该键的行 ID 的集合。同一行 ID 可以出现在多个 posting list 中，因为一个项可以包含多个键。每个键值只存储一次，因此在同一个键出现很多次的场景下，GIN 索引非常紧凑。

GIN 之所以是广义的，是因为 GIN 访问方法代码不需要了解它所加速的具体操作。它使用为特定数据类型定义的自定义策略。策略定义了如何从被索引的项和查询条件中提取键，以及如何判断包含查询中某些键值的行是否真正满足该查询。

GIN 的一个优点是：它允许由该数据类型领域的专家（而非数据库专家）来开发带有相应访问方法的自定义数据类型。这与使用 GiST 的优点大体相同。

PostgreSQL 中的 GIN 实现主要由 Teodor Sigaev 和 Oleg Bartunov 维护。关于 GIN 的更多信息见他们的网站。

65.4.2. 内置操作符类 #

PostgreSQL 核心发行版包含 Table 65.3 所示的 GIN 操作符类。（Appendix F 中描述的一些可选模块提供了额外的 GIN 操作符类。）

Table 65.3. 内置 GIN 操作符类

Name	Indexable Operators
`array_ops`	`&& (anyarray,anyarray)`
	`@> (anyarray,anyarray)`
	`<@ (anyarray,anyarray)`
	`= (anyarray,anyarray)`
`jsonb_ops`	`@> (jsonb,jsonb)`
	`@? (jsonb,jsonpath)`
	`@@ (jsonb,jsonpath)`
	`? (jsonb,text)`
	`?\| (jsonb,text[])`
	`?& (jsonb,text[])`
`jsonb_path_ops`	`@> (jsonb,jsonb)`
	`@? (jsonb,jsonpath)`
	`@@ (jsonb,jsonpath)`
`tsvector_ops`	`@@ (tsvector,tsquery)`

在 jsonb 类型的两个操作符类中，jsonb_ops 是默认的。jsonb_path_ops 支持的操作符更少，但对这些操作符提供了更好的性能。详情见 Section 8.14.4。

65.4.3. 可扩展性 #

GIN 接口具有很高的抽象层次，只要求访问方法的实现者实现被访问数据类型的语义。GIN 层本身负责并发、日志记录以及树结构的搜索。

要让一个 GIN 访问方法工作起来，只需实现少量用户定义的方法，这些方法定义了树中键的行为，以及键、被索引项和可索引查询之间的关系。简而言之，GIN 把可扩展性与通用性、代码复用以及简洁的接口结合在了一起。

GIN 的操作符类必须提供两个方法：

Datum *extractValue(Datum itemValue, int32 *nkeys, bool **nullFlags)

给定一个待索引的项，返回一个 palloc'd 的键数组。返回的键数量必须存入 *nkeys。如果任何键可以为空，还要 palloc 一个包含 *nkeys 个 bool 字段的数组，把其地址存入 *nullFlags，并按需设置这些空标志。如果所有键都非空，*nullFlags 可以保持 NULL（其初始值）。如果项不包含任何键，返回值可以是 NULL。

Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode)

给定一个要查询的值，返回一个 palloc'd 的键数组；也就是说， query 是某个可索引操作符右侧的值，其左侧是被索引的列。 n 是该操作符在操作符类中的策略号（见 Section 36.16.2）。 extractQuery 通常需要查看 n 来确定 query 的数据类型以及它应使用的键值提取方法。返回的键数量必须存入 *nkeys。如果任何键可以为空，还要 palloc 一个包含 *nkeys 个 bool 字段的数组，把其地址存入 *nullFlags，并按需设置这些空标志。如果所有键都非空，*nullFlags 可以保持 NULL（其初始值）。如果 query 不包含任何键，返回值可以是 NULL。

searchMode 是一个输出参数，允许 extractQuery 指定搜索方式的细节。如果 *searchMode 被设为 GIN_SEARCH_MODE_DEFAULT（这是调用前它的初始值），只有与至少一个返回键匹配的项被视为候选匹配项。如果 *searchMode 被设为 GIN_SEARCH_MODE_INCLUDE_EMPTY，那么除了包含至少一个匹配键的项之外，完全不包含任何键的项也被视为候选匹配项。（例如，这个模式对实现 is-subset-of 操作符很有用。）如果 *searchMode 被设为 GIN_SEARCH_MODE_ALL，那么索引中所有非空项都被视为候选匹配项，无论它们是否与任何返回键匹配。（这个模式比另外两种慢得多，因为它实际上需要扫描整个索引，但为了正确实现边角情形可能是必需的。大多数情况下需要这个模式的操作符，多半不是 GIN 操作符类的好候选。）设置该模式所用符号的定义在 access/gin.h 中。

pmatch 是一个输出参数，用于支持部分匹配的情形。要使用它，extractQuery 必须分配一个包含 *nkeys 个 bool 的数组，并把其地址存入 *pmatch。如果对应的键需要部分匹配，数组的每个元素应设为 true，否则设为 false。如果 *pmatch 被设为 NULL，GIN 会认为不需要部分匹配。该变量在调用前被初始化为 NULL，因此不支持部分匹配的操作符类可以简单地忽略这个参数。

extra_data 是一个输出参数，允许 extractQuery 向 consistent 和 comparePartial 方法传递附加数据。要使用它，extractQuery 必须分配一个包含 *nkeys 个指针的数组，把其地址存入 *extra_data，然后把想传递的内容存入各个指针。该变量在调用前被初始化为 NULL，因此不需要额外数据的操作符类可以简单地忽略这个参数。如果 *extra_data 被设置，整个数组会被传给 consistent 方法，而对应的元素会传给 comparePartial 方法。

操作符类还必须提供一个函数来检查被索引的项是否与查询匹配。它有两种形式：布尔型的 consistent 函数和三值型的 triConsistent 函数。 triConsistent 涵盖了两者的功能，因此只提供 triConsistent 就足够了。不过，如果布尔变体的计算成本明显更低，同时提供两者可能更有利。如果只提供布尔变体，某些依赖于在取回全部键之前反驳索引项的优化将被禁用。

bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[])

如果被索引的项满足策略号为 n 的查询操作符（或可能满足，如果返回了 recheck 指示），则返回 true。该函数无法直接访问被索引项的值，因为 GIN 不显式存储项。可用的信息是：从查询中提取的哪些键值出现在给定的被索引项中。 check 数组的长度为 nkeys，与 extractQuery 之前为该 query 值返回的键数量相同。如果被索引项包含对应的查询键，check 数组的对应元素为 true，即若 (check[i] == true)，则 extractQuery 结果数组的第 i 个键存在于被索引项中。原始的 query 值会被传入，以备 consistent 方法需要查看它； extractQuery 之前返回的 queryKeys[] 和 nullFlags[] 数组同样会被传入。 extra_data 是 extractQuery 返回的额外数据数组，若没有则为 NULL。

当 extractQuery 在 queryKeys[] 中返回一个空键时，如果被索引项包含一个空键，则对应的 check[] 元素为 true；也就是说，check[] 的语义类似 IS NOT DISTINCT FROM。如果 consistent 函数需要区分常规值匹配与空值匹配，它可以查看对应的 nullFlags[] 元素。

成功时，如果堆元组需要针对查询操作符重新检查，应把 *recheck 设为 true；如果索引测试是精确的，则设为 false。也就是说，返回 false 保证堆元组不匹配该查询；返回 true 且 *recheck 为 false 保证堆元组匹配该查询；返回 true 且 *recheck 为 true 表示堆元组可能匹配该查询，因此需要取回它，并直接针对最初被索引的项求值查询操作符来重新检查。

GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], Datum queryKeys[], bool nullFlags[])

triConsistent 与 consistent 类似，但 check 向量中不是布尔值，每个键有三种可能的取值：GIN_TRUE、GIN_FALSE 和 GIN_MAYBE。GIN_FALSE 和 GIN_TRUE 的含义与常规布尔值相同，而 GIN_MAYBE 表示该键是否存在是未知的。当出现 GIN_MAYBE 值时，只有当项确定匹配（无论索引项是否包含对应的查询键）时，函数才应返回 GIN_TRUE。同样，只有当项确定不匹配（无论它是否包含 GIN_MAYBE 键）时，函数才必须返回 GIN_FALSE。如果结果依赖于 GIN_MAYBE 条目，即仅凭已知查询键既无法确认也无法反驳匹配，函数必须返回 GIN_MAYBE。

当 check 向量中没有 GIN_MAYBE 值时，返回 GIN_MAYBE 等价于在布尔型 consistent 函数中设置 recheck 标志。

此外，GIN 必须有办法对存储在索引中的键值进行排序。操作符类可以通过指定一个比较方法来定义排序顺序：

int compare(Datum a, Datum b): 比较两个键（而非被索引项！），返回一个小于零、等于零或大于零的整数，分别表示第一个键小于、等于或大于第二个键。空键永远不会被传给这个函数。

或者，如果操作符类没有提供 compare 方法，GIN 会查找索引键数据类型的默认 btree 操作符类，并使用其比较函数。建议只为单一数据类型设计的 GIN 操作符类显式指定比较函数，因为查找 btree 操作符类要耗费一些周期。不过，多态的 GIN 操作符类（例如 array_ops）通常无法指定单一的比较函数。

GIN 的操作符类可以可选地提供以下方法：

int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer extra_data)

把部分匹配查询键与索引键进行比较。返回一个整数，其符号表示结果：小于零表示索引键与查询不匹配，但索引扫描应继续；零表示索引键与查询匹配；大于零表示索引扫描应停止，因为不可能再有匹配了。会传入产生部分匹配查询的操作符的策略号 n，以备判断何时结束扫描需要用到它的语义。此外， extra_data 是 extractQuery 生成的额外数据数组中的对应元素，若没有则为 NULL。空键永远不会被传给这个函数。

void options(local_relopts *relopts)

定义一组控制操作符类行为的用户可见参数。

options 函数会接收一个指向 local_relopts 结构的指针，该结构需要被填充为一组操作符类特定的选项。其他支持函数可以使用 PG_HAS_OPCLASS_OPTIONS() 和 PG_GET_OPCLASS_OPTIONS() 宏来访问这些选项。

由于被索引值的键提取方式和键在 GIN 中的表示方式都是灵活的，它们可能依赖于用户指定的参数。

要支持“部分匹配”查询，操作符类必须提供 comparePartial 方法，并且当遇到部分匹配查询时，其 extractQuery 方法必须设置 pmatch 参数。详情见 Section 65.4.4.2。

上述各种 Datum 值的实际数据类型取决于操作符类。传给 extractValue 的项值始终是操作符类的输入类型，并且所有键值必须属于该类的 STORAGE 类型。传给 extractQuery、 consistent 和 triConsistent 的 query 参数的类型，是由策略号所标识的类成员操作符的右侧输入类型。它不必与被索引类型相同，只要能从中提取出正确类型的键值即可。不过，建议这三个支持函数的 SQL 声明对 query 参数使用操作符类的被索引数据类型，即使实际类型可能因操作符而异。

65.4.4. 实现 #

在内部，GIN 索引包含一棵构建在键之上的 B-tree 索引，其中每个键是一个或多个被索引项的元素（例如数组的成员），并且叶页面中的每个元组要么包含一个指向堆指针 B-tree 的指针（即 “posting tree”），要么在列表小到可以连同键值一起放入单个索引元组时，包含一个简单的堆指针列表（即 “posting list”）。Figure 65.1 展示了 GIN 索引的这些组成部分。

从 PostgreSQL 9.1 开始，空键值也可以被包含在索引中。此外，对于根据 extractValue 判定为空或不包含任何键的被索引项，索引中会包含占位空值。这使得应当找到空项的搜索能够做到这一点。

多列 GIN 索引通过在复合值 (列号, 键值) 之上构建单棵 B-tree 来实现。不同列的键值可以是不同的类型。

Figure 65.1. GIN 内部结构

65.4.4.1. GIN 快速更新技术 #

更新 GIN 索引往往很慢，这是倒排索引的固有性质决定的：插入或更新一个堆行可能导致对索引的多次插入（从被索引项中提取出的每个键一次）。 GIN 能够把这项工作的很大一部分推迟，方法是先把新元组插入一个临时的、未排序的待处理条目列表。当表被清理或自动分析时，或者调用 gin_clean_pending_list 函数时，或者待处理列表超过 gin_pending_list_limit 时，这些条目会被移入主 GIN 数据结构，使用与初始索引创建时相同的大量插入技术。这极大地提高了 GIN 索引的更新速度，即使算上额外的清理开销也是如此。而且，这些开销工作可以由后台进程完成，而不必在前台查询处理中进行。

这种方法的主要缺点是：除了搜索常规索引之外，还必须扫描待处理条目列表，因此大量的待处理条目会显著拖慢搜索。另一个缺点是，虽然大多数更新都很快，但导致待处理列表变得“过大”的那次更新会引发一次立即的清理循环，因此比其他更新慢得多。正确使用 autovacuum 可以把这两个问题都降到最低。

如果稳定的响应时间比更新速度更重要，可以通过关闭 GIN 索引的 fastupdate 存储参数来禁用待处理条目。详情见 CREATE INDEX。

65.4.4.2. 部分匹配算法 #

GIN 可以支持“部分匹配”查询，即查询无法确定一个或多个键的精确匹配，但可能的匹配落在一个相当窄的键值范围内（按 compare 支持方法确定的键排序顺序）。此时 extractQuery 方法不返回要精确匹配的键值，而是返回一个作为待搜索范围下界的键值，并把 pmatch 标志设为 true。然后使用 comparePartial 方法扫描该键范围。comparePartial 对匹配的索引键必须返回零，对仍在待搜索范围内的不匹配键返回小于零，对超出可能匹配范围的索引键返回大于零。

65.4.5. GIN 技巧与诀窍 #

创建与插入

向 GIN 索引插入数据可能很慢，因为每个项很可能会插入很多键。因此，在向表进行批量插入时，建议先删除 GIN 索引，待批量插入完成后再重建。

当为 GIN 启用 fastupdate 时（详情见 Section 65.4.4.1），代价会比未启用时小。但对于非常大的更新，删除并重建索引可能仍是最佳选择。

maintenance_work_mem

GIN 索引的构建时间对 maintenance_work_mem 设置非常敏感；在索引创建期间节省工作内存是不划算的。

gin_pending_list_limit

在向启用了 fastupdate 的现有 GIN 索引连续插入数据的过程中，只要待处理条目列表增长超过 gin_pending_list_limit，系统就会清理该列表。为了避免观测到的响应时间出现波动，最好让待处理列表的清理在后台进行（即通过 autovacuum）。可以通过增大 gin_pending_list_limit 或让 autovacuum 更积极来避免前台清理操作。然而，把清理操作的阈值调大意味着一旦真的发生前台清理，它将耗时更久。

可以通过修改存储参数为单个 GIN 索引覆盖 gin_pending_list_limit，这使得每个 GIN 索引可以有自己的清理阈值。例如，可以只为更新频繁的 GIN 索引增大该阈值，而对其他索引减小。

gin_fuzzy_search_limit

开发 GIN 索引的首要目标是在 PostgreSQL 中支持高度可扩展的全文搜索，而全文搜索经常会返回非常大的结果集。而且，这种情况往往发生在查询包含非常频繁的词时，此时庞大的结果集甚至毫无用处。由于从磁盘读取大量元组并对它们排序可能耗费很长时间，这对生产环境是不可接受的。（注意索引搜索本身非常快。）

为了便于对这类查询进行受控执行，GIN 对返回的行数有一个可配置的软上限：gin_fuzzy_search_limit 配置参数。默认设置为 0（表示没有限制）。如果设置了非零限制，返回的集合就是整个结果集的一个随机抽取的子集。

“软”是指实际返回的结果数量可能与指定限制略有出入，取决于查询以及系统随机数生成器的质量。

根据经验，数千的取值（例如 5000 — 20000）效果良好。

65.4.6. 限制 #

GIN 假定可索引的操作符是严格的。这意味着对空的项值根本不会调用 extractValue（而是自动创建一个占位索引条目），对空的查询值也不会调用 extractQuery （而是假定查询无法满足）。不过要注意，非空复合项或查询值中包含的空键值是受支持的。

65.4.7. 示例 #

PostgreSQL 核心发行版包含前面 Table 65.3 所示的 GIN 操作符类。以下 contrib 模块也包含 GIN 操作符类：

btree_gin: 多种数据类型的 B-tree 等价功能
hstore: 存储 (键, 值) 对的模块
intarray: 对 int[] 的增强支持
pg_trgm: 基于三元组匹配的文本相似度