# 55.2\. 扩展性 传统上，实现一种新的索引访问方法意味着大量的艰苦工作。必须理解数据库的内部工作机制，比如锁的机制和预写日志。 GiST接口有一个高层的抽像，只要求访问方法的实现者实现被访问的数据类型的语意。 GiST层本身会处理并发，日志和搜索树结构等任务。 不要把这个扩展性和其它标准搜索树的扩展性混淆在一起，比如它们所能处理的数据等方面。 比如，PostgreSQL支持可扩展的 B-trees和哈希索引。 这就意味着可以用PostgreSQL在任意你需要的数据类型上建立 B-tree或哈希 。 但是 B-trees 只支持范围谓词(`<`、`=`、`>`),而哈希仅支持相等查询。 所以，如果你用PostgreSQL B-tree 索引了一个图像集，那么你就只能发出类似 "图像 x 和图像 y 相等吗"、"图像 x 是不是比图像 y 小"、"图像 x 是否大于图像 y"这样的查询。 依赖于你在这个环境下定义的"等于"、"小于"、"大于"的含义，上面这些查询可能有意义。 但是，使用一个基于GiST的索引，你可以创建一些方法来提出和领域相关的问题，比如"找出所有马的图像"或者"找出所有曝光过头的图像"。 要让一种GiST访问方法跑起来只要实现几个用户定义方法，这些方法定义了树里面的键字的行为。 当然，为了支持那些怪异的查询，这些方法也会相当怪异，但是对于所有标准的查询(B-tree，R-tree 等)，他们是相当直接的。 简单说，GiST组合了扩展性和通用性，以及代码复用和一个干净的界面。 GiST用的索引操作符类必须提供7个方法，第8个方法是可选的。 索引的正确性通过正确的实现`same`, `consistent`和`union`方法来确保,而索引的效率(大小和速度)依赖于`penalty`和`picksplit`。 剩下的2个方法是`compress`和`decompress`，它们允许索引持有的内部数据和它索引的对象数据的类型不同。 叶子节点的类型必须和被索引数据相同，而其他节点可以是任意C结构(但是，这里仍然必须遵守PostgreSQL中数据类型的规则，对可变大小数据请参考`varlena`)。 如果树的内部数据类型在SQL级别存在，可以在`CREATE OPERATOR CLASS`命令中使用`STORAGE`选项。 可选的第8个方法是`distance`,如果希望操作符类支持排序的扫描（最邻近搜索），就需要提供这个方法。 `consistent` 给定一个索引项`p`和查询值`q`，这个函数决定是否索引项和查询"一致"； 也即是，对任何该索引项代表的行，谓词 "`_indexed_column_``_indexable_operator_` `q`"是否可能为真？ 对叶子索引项这等价于测试索引条件，对内部树节点它指示是否有必要扫描该节点代表的索引子树。 当结果为`true`，必须还要返回`recheck`标志位。这指示了谓词是精确为真还是只是可能为真。 如果`recheck` = `false`，索引已经精确地测试了谓词条件， 如果`recheck`= `true`，相应的行仅仅是一个候选匹配。 这种情况下，系统还将自动对实际的行值进行评价`_indexable_operator_`以检查是否真的匹配。 这一规则允许GiST同时支持无损索引和有损索引。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal) RETURNS bool AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_consistent(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_consistent); Datum my_consistent(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); data_type *query = PG_GETARG_DATA_TYPE_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); /* Oid subtype = PG_GETARG_OID(3); */ bool *recheck = (bool *) PG_GETARG_POINTER(4); data_type *key = DatumGetDataType(entry->key); bool retval; /* * 根据strategy,key和query决定返回值。 * * 使用GIST_LEAF(entry)可以感知函数在索引树的什么位置被调用，比如这在支持=操作符时很方便 * （可以在非叶子节点检查非空的union()和在叶子节点检测等价性)。 */ *recheck = true; /* 如果是精确检查则为假 */ PG_RETURN_BOOL(retval); } ``` 这里`key`是索引中的一个元素，而`query`是要在索引中查找的值。 `StrategyNumber`参数指示要应用操作符类中的哪个操作符， 它必须是`CREATE OPERATOR CLASS`命令指定的操作符编号之一。 依赖于在操作符类中包含的操作符，`query`的数据类型可能和操作符不同，但是上面的骨架代码假设不是这种情况。 `union` 这个方法用于合并树中的信息。输入一个项目的集合，这个函数生成一个代表所有给定项目的新的索引项目。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_union(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_union(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_union); Datum my_union(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GISTENTRY *ent = entryvec->vector; data_type *out, *tmp, *old; int numranges, i = 0; numranges = entryvec->n; tmp = DatumGetDataType(ent[0].key); out = tmp; if (numranges == 1) { out = data_type_deep_copy(tmp); PG_RETURN_DATA_TYPE_P(out); } for (i = 1; i < numranges; i++) { old = out; tmp = DatumGetDataType(ent[i].key); out = my_union_implementation(out, tmp); } PG_RETURN_DATA_TYPE_P(out); } ``` 正如你看到的，这个骨架代码中我们处理了符合`union(X, Y, Z) = union(union(X, Y), Z)`的数据类型。 在GiST支持方法中实现适当的union算法也可以很容易地支持其它不符合这一条件的数据类型。 `union`的实现函数应该返回一个由`palloc()`分配的内存的指针。 不能简单地直接返回输入的东西。 `compress` 把数据项转换为适合在索引页中存储的格式。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_compress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_compress(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* 把entry->key替换为压缩的版本 */ compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); /* 从entry->key填充*compressed_data */ retval = palloc(sizeof(GISTENTRY)); gistentryinit(*retval, PointerGetDatum(compressed_data), entry->rel, entry->page, entry->offset, FALSE); } else { /* 通常不需要对非叶子节点做任何处理 */ retval = entry; } PG_RETURN_POINTER(retval); } ``` 当然，为了压缩叶子节点，你需要把`_compressed_data_type_`适配到特定的数据类型。 根据你的需求，可能还需要关心如何压缩`NULL`值，例如存储为`(Datum) 0`，就像`gist_circle_compress`那样。 `decompress` 与`compress`函数正好相反。 把数据项的索引表现转换为可以被数据库处理的格式。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_decompress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_decompress(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_decompress); Datum my_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); } ``` 上面的骨架代码适合不需要解压缩的场合。 `penalty` 返回插入新项目到特定分支的"代价"值。 项目将会被插入到树中`penalty`最小的路径。 `penalty`的返回值应该是非负数。 如果返回了负数将会被当作0处理。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; -- in some cases penalty functions need not be strict ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_penalty(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_penalty); Datum my_penalty(PG_FUNCTION_ARGS) { GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); float *penalty = (float *) PG_GETARG_POINTER(2); data_type *orig = DatumGetDataType(origentry->key); data_type *new = DatumGetDataType(newentry->key); *penalty = my_penalty_implementation(orig, new); PG_RETURN_POINTER(penalty); } ``` `penalty`函数对索引的性能非常重要。 在插入阶段，它可以用来决定把新增加项目插入到哪个分支。 在查询阶段，越平衡的索引，检索速度越快。 `picksplit` 如果需要分裂一个索引页面的时候，这个函数决定页面中哪些项目保存在旧页面里，哪些移动到新页面里。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_picksplit(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_picksplit); Datum my_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); OffsetNumber maxoff = entryvec->n - 1; GISTENTRY *ent = entryvec->vector; GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); int i, nbytes; OffsetNumber *left, *right; data_type *tmp_union; data_type *unionL; data_type *unionR; GISTENTRY **raw_entryvec; maxoff = entryvec->n - 1; nbytes = (maxoff + 1) * sizeof(OffsetNumber); v->spl_left = (OffsetNumber *) palloc(nbytes); left = v->spl_left; v->spl_nleft = 0; v->spl_right = (OffsetNumber *) palloc(nbytes); right = v->spl_right; v->spl_nright = 0; unionL = NULL; unionR = NULL; /* 初始化项目数组 */ raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *)); for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) raw_entryvec[i] = &(entryvec->vector[i]); for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { int real_index = raw_entryvec[i] - entryvec->vector; tmp_union = DatumGetDataType(entryvec->vector[real_index].key); Assert(tmp_union != NULL); /* * 选择放置索引项目的位置，并相应地更新unionL和unionR。 * 追加项目到v_spl_left或者v_spl_right，并注意处理计数器。 */ if (my_choice_is_left(unionL, curl, unionR, curr)) { if (unionL == NULL) unionL = tmp_union; else unionL = my_union_implementation(unionL, tmp_union); *left = real_index; ++left; ++(v->spl_nleft); } else { /* * 右边做相同处理 */ } } v->spl_ldatum = DataTypeGetDatum(unionL); v->spl_rdatum = DataTypeGetDatum(unionR); PG_RETURN_POINTER(v); } ``` 像`penalty`一样，`picksplit`函数对索引的性能也非常重要， 设计合适的`penalty`和`picksplit`函数直接关系到实现良好性能的GiST索引。 `same` 2个索引项目等价时为真，否则为假。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_same(internal, internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_same(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_same); Datum my_same(PG_FUNCTION_ARGS) { prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0); prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1); bool *result = (bool *) PG_GETARG_POINTER(2); *result = my_eq(v1, v2); PG_RETURN_POINTER(result); } ``` 由于历史的原因，`same`函数并不是单纯地返回布尔值， 而是将标志位存储到由第3个参数指向的位置。 `distance` 给定一个索引项目`p`和查询值`q`，这个函数决定这2者之间的"距离"。 如果操作符类包含任何排序的操作符，必须要提供这个函数。 通过先返回最小"距离"值的索引项目，可以实现使用了排序操作符的查询，因此结果必须和操作符的语义一致。 对一个叶子索引项目，结果只是到索引项目的距离；对内部项目，结果必须是任何子节点项目的最小距离。 这个函数的SQL声明必须按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid) RETURNS float8 AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模块中的对应代码可以参考下面的骨架代码。 ``` Datum my_distance(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_distance); Datum my_distance(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); data_type *query = PG_GETARG_DATA_TYPE_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); /* Oid subtype = PG_GETARG_OID(3); */ data_type *key = DatumGetDataType(entry->key); double retval; /* * determine return value as a function of strategy, key and query. */ PG_RETURN_FLOAT8(retval); } ``` `distance`函数的参数，除了recheck标志位，其他和`consistent`函数相同。 一个叶子节点的距离值必须是精确的，因为一旦返回了元组就没有办法再进行排序了。 对内部节点允许一定程度的近似，只要不大于任何一个子节点的实际距离。 比如，在地理应用中到矩形边界的距离就足够了。 结果值可以是任何有限的`float8`类型值。 （无穷和负无穷用于在内部作为空等情况使用，因此，不建议`distance`返回这些值。） 所有的GiST支持方法通常在短周期内存上下文中被调用，也就是说，在每个元组被处理后`CurrentMemoryContext`都会被重置。 因此不太需要担心pfree被palloc出来的所有东西。 然而，有些情况下，需要支持方法在多次调用间缓存数据。 为了实现这个目的，需要在`fcinfo->flinfo->fn_mcxt`中分配长生命周期的数据， 并且在`fcinfo->flinfo->fn_extra`中保存其指针。 这样的数据在索引操作(比如:单个的GiST索引扫描，索引创建或索引元组插入)完成后仍然有效。 在覆盖`fn_extra`的值前要小心的pfree掉先前的值，否则在操作期间内存泄漏会越积越多。