GIN索引
介绍
GIN（Generalized Inverted Index）通用倒排索引。设计为处理索引项为组合值的情况，查询时需要通过索引搜索出出现在组合值中的特定元素值。例如，文档是由多个单词组成，需要查询出文档中包含的特定单词。
使用item表示索引的组合值，key表示一个元素值。GIN用来存储和搜索key，而不是item。
GIN索引存储一系列（key，posting list）键值对，这里的posting list是一组出现key的行ID。由于每个item都可能包含多个key，同一个行ID可能会出现在多个posting list中，而每个key值只被存储一次，所以在相同的key在item中出现多次的情况下，GIN索引是非常简洁的。
因为GIN索引的访问方式不需要了解他的运行方式，所以GIN索引是通用的。GIN索引使用为特殊数据类型定义的策略。策略定义了如何从索引选项和查询条件中抽出key，以及如何确定在查询中包含某些key值的行是否实际满足查询条件。
扩展性
GIN索引的接口实现了一个高层次的抽象，要求访问用户仅需要实现被访问数据类型的语义。GIN层自身可以处理并发操作、记录日志、搜索树结构的任务。
定义GIN索引的访问方式所要做的事情就是实现多个用户定义的方法，这些方法定义了键在树中的行为、键与键之间的关系、需要索引的item、能够使用索引的查询。简而言之，GIN索引将扩展性与普遍性、代码重用、清晰的接口结合在了一起。
实现GIN索引的操作符类有如下四个方法：
int compare(Datum a, Datum b)
比较两个key（不是索引的item）然后返回一个小于零、零或大于零的值，分别表示第一个key小于、等于或大于第二个key。NULL不会被传入这个函数。
Datum *extractValue(Datum itemValue, int32 *nkeys, bool**nullFlags)
给定一个要被索引的item，返回一个对应key的数组。返回key的数目必须存储在*nkeys中。如果任何key都可能为NULL，还要分配包含*nkeys个布尔元素的数组，将地址存储到*nullFlags，并且根据需要设置NULL值。
如果所有key都是非NULL，可以让*nullFlags保持为NULL（他的初始值）。如果item不包含任何key，返回值可以为NULL。Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode)
给定一个被查询的值，返回一个对应的key的数组。也就是说，query是可索引操作符右侧的值，而该操作符左侧是被索引的字段。
n是操作符类中操作符的策略号。通常，extractQuery需要参考n来决定query的数据类型以及抽取键值的方法。返回key的个数必须存放在*nkeys中。如果任何key都可能为NULL，还要分配包含*nkeys个布尔元素的数组，将地址存储到*nullFlags，并且根据需要设置NULL值。
如果所有key都是非NULL的，可以让*nullFlags保持为NULL（他的初始值）。如果query不包含任何key，返回值可以为NULL。searchMode是一个输出参数，他允许extractQuery指定一些关于如何执行搜索的细节。如果设置*searchMode为GIN_SEARCH_MODE_DEFAULT（这也是调用函数前此参数的初始化值），只有那些至少返回一个key的item才能被考虑作为候选匹配项。如果设置*searchMode为GIN_SEARCH_MODE_INCLUDE_EMPTY，除了包含至少一个匹配key的item之外，根本不包含任何key的item也被考虑作为候选匹配项。（这个模式对于实现像”是否是子集”这样的操作是有用的）如果设置*searchMode为GIN_SEARCH_MODE_ALL，索引中所有非NULL的item都被考虑作为候选匹配项，不管他们是否匹配返回key中的任何一个。
pmatch是一个允许支持部分匹配的输出参数。如果使用此参数，extractQuery必须分配有*nkeys个布尔元素的数组，并把数组地址保存到*pmatch。如果需要部分匹配相应的key，则数组的每个元素应该设置为TRUE；如果不需要匹配，则设置为FALSE。如果设置*pmatch为NULL，则假设GIN不需要部分匹配。在函数调用前这个值被初始化为NULL，因此，对于不支持部分匹配的操作符类，可以忽略这个参数。
extra_data是一个允许extractQuery以consistent和comparePartial的方式传递额外数据的输出参数。如果使用他，extractQuery必须分配一个包含*nkeys个Pointer元素的数组，并把数组地址保存到*extra_data，然后把他想附加的东西存储到各个独立的指针中。在函数调用前这个值初始化为NULL，因此，对于不需要附加数据的操作符类，可以忽略这个参数。如果设置了*extra_data，那么以consistent方式传递整个数组，使用comparePartial方式传递适当的元素。
bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[])
如果被索引项满足StrategyNumber为n的查询操作符则返回TRUE。这个函数并不直接访问被索引项的值，因为GIN并没有精确的把项目保存下来，但是需要知道从查询中提取的哪些键值出现在给定的被索引项中。check数组的长度是nkeys，这个与query调用extractQuery函数返回的键值的数目相同。如果索引项包含了相应的查询键，check数组中对应的元素值就是TRUE。比如，如果(check[i] TRUE)，那么意味着extractQuery的结果数组的第i个键出现在索引项中。考虑可能会用到consistent方式，原始的query也被作为参数传入进来。与此相同的还有extractQuery函数返回的queryKeys[]和nullFlags[]。extra_data是extractQuery函数返回的额外数据数组，如果没有的话就是NULL。
当extractQuery在queryKeys[]中返回一个NULL的键值，如果被索引项包含NULL键值，相应的check[]中的元素是TRUE。也就是说，check[]的语义很像IS NOT DISTINCT FROM。如果需要知道是通常值匹配还是NULL匹配，consistent函数可以检查相应的nullFlags[]元素。
成功执行后，如果堆元组需要针对查询运算符进行重新检查，*recheck需要设置为TRUE，如果索引测试已经是精确的了，则设为FALSE。也就是说，FALSE的返回值确保堆元组不匹配这个查询；设置*recheck为FALSE的TRUE的返回值确保堆元组匹配这个查询；设置*recheck为TRUE的TRUE的返回值意味着堆元组可能匹配这个查询，因此需要通过直接对照原始索引项对查询运算符进行获取和重新检查。
GIN操作符类可以可选地提供第五个函数。
int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer extra_data)
比较一个部分匹配查询键和一个索引键。返回一个整型值，它的符号代表了不同的含义：小于0意味着索引键不匹配查询，但是索引扫描应该继续；0意味着索引键匹配查询；大于0指示应该终止索引扫描，因为不可能再有更多的匹配。在需要确定何时结束扫描的语义的情况下，这里提供了生成部分一致查询的操作符的策略号n。同样的，extra_data是extractQuery生成的额外数据数组中的相应元素，如果没有对应的元素，则为NULL。NULL的键永远不会被传入这个函数。
为了支持”部分匹配”查询，一个操作符类必须提供comparePartial方法，并且当遇到部分匹配查询时，他的extractQuery方法必须设置pmatch参数。详细信息请参考部分匹配算法。
上面的各种Datum值的实际数据类型根据操作符类的不同而不同。传入到extractValue中的项目值总是操作符类的输入类型，所有的键值类型必须是这个类的STORAGE类型。传入到extractQuery和consistent的query参数的类型是由策略号识别的类成员操作符的右操作数的输入类型。他不需要和项目类型相同，只要可以从中抽取出正确类型的键值。
实现
在内部，GIN索引包含一个在键上构造的B-tree索引，每个键是一个或多个被索引项的一个元素（比如，一个数组的一个成员）。并且页面上每个元组包含了堆指针的B-tree的一个指针（一个posting tree），当列表小到足以和键值一起存储到一个索引元组中时，则是堆指针的一个简单列表（一个posting list）。
多列GIN索引通过在组合值（列号，键值）上建立一个单个的B-tree实现。不同列的键值可以有不同的类型。
GIN快速更新技术
由于倒排索引的本身特性影响，更新一个GIN索引可能会比较慢。插入或更新一个堆行可能导致许多往索引的插入。当对表执行VACUUM后，或者如果待处理实体的列表太大了（大于work_mem），这些实体被使用和初始索引创建时用到的相同的bulk插入方法，移动到主要的GIN数据结构。即使把额外的VACUUM开销算进去，这也大大提升了GIN索引更新的速度。而且，这种额外开销的工作可以通过后台进程而不是前端查询来处理。
这种方法的主要缺点在于搜索时除了常规的索引还必须要扫描待处理实体的列表。因此，大的待处理实体的列表会显著的拖慢搜索。另一个缺点是，虽然大多数更新很快，但是一个导致待处理列表（pending list）变得”太大”的更新将引发一个立即清理，并因此比起其它更新会非常慢。恰当的使用autovacuum可以弱化这两个问题。
如果一致的响应时间（清理实体速度和更新速度的响应时间）比更新速度更重要，可以通过把GIN索引的存储参数FASTUPDATE设置为off而不使用待处理实体。详细请参考12.19.42CREATE INDEX。
部分匹配算法
GIN可以支持”部分匹配”查询。即：查询并不决定单个或多个键的一个精确的匹配，而是，可能的匹配落在一个合理的狭窄键值范围内（根据compare支持函数决定的键值排序顺序）。此时，extractQuery方法并不返回一个用于精确匹配的键值，取而代之的是，返回一个要被搜索的键值范围的下边界，并且设置pmatch为true。然后，使用comparePartial方式扫描这个键值范围。 comparePartial必须为一个相匹配的索引键返回0，如果不匹配但依然在被搜索范围内时返回小于0的值，对超过可以匹配的范围的索引键则返回大于0的值。
GIN提示与技巧
创建vs插入
由于可能要为每个项目插入很多键，所以GIN索引的插入可能比较慢。对于向表中大量插入的操作，我们建议先删除GIN索引，在完成插入之后再重建索引。与GIN索引创建、查询性能相关的GUC参数如下：
maintenance_work_mem
GIN索引的构建时间对maintenance_work_mem的设置非常敏感。
work_mem
往已有的启用了FASTUPDATE的GIN索引的插入操作期间，只要待处理实体列表的大小超过了work_mem，系统就会清理这个列表。为了避免可观察到的响应时间的大起大落，让待处理实体列表在后台被清理是比较合适的（比如通过autovacuum）。前端清理操作可以通过增加work_mem或者执行autovacuum来避免。然而，扩大work_mem意味着如果发生了前端清理，那么他的执行时间将更长。
gin_fuzzy_search_limit
开发GIN索引的主要目的是为了让Vastbase支持高度可伸缩的全文索引，并且常常会遇见全文索引返回海量结果的情形。而且，这经常发生在查询高频词的时候，因而这样的结果集没什么用处。因为从磁盘读取大量记录并对其进行排序会消耗大量资源，这在产品环境下是不能接受的。
为了控制这种情况，GIN索引有一个可配置的返回结果行数上限的配置参数gin_fuzzy_search_limit。缺省值0表示没有限制。如果设置了非零值，那么返回结果就是从完整结果集中随机选择的一部分。
