传统上,实现新的索引访问方法意味着大量困难的工作。有必要了解数据库的内部工作原理,例如锁管理器和预写式日志。GiST 接口具有很高的抽象级别,要求访问方法实现者仅实现正在访问的数据类型的语义。GiST 层本身负责并发、日志记录和搜索树结构。
此可扩展性不应与其他标准搜索树在可处理数据方面的可扩展性相混淆。例如,PostgreSQL 支持可扩展 B 树和哈希索引。这意味着您可以使用 PostgreSQL 对任何所需数据类型构建 B 树或哈希。但是,B 树仅支持范围谓词 (<
、=
、>
),而哈希索引仅支持相等性查询。
因此,如果您使用 PostgreSQL B 树对图像集合进行索引,则只能发出诸如 “imagex 等于 imagey”、“imagex 小于 imagey” 和 “imagex 大于 imagey” 之类的查询。根据您在此上下文中定义 “等于”、“小于” 和 “大于” 的方式,这可能很有用。但是,通过使用基于 GiST 的索引,您可以创建提出特定于领域的问题的方法,例如 “查找所有马匹图像” 或 “查找所有曝光过度图像”。
启动并运行 GiST 访问方法所需的一切就是实现几个用户定义的方法,这些方法定义树中键的行为。当然,这些方法必须非常花哨才能支持花哨的查询,但对于所有标准查询(B 树、R 树等),它们相对简单。简而言之,GiST 将可扩展性与通用性、代码重用和简洁的界面结合在一起。
对于 GiST,索引操作员类必须提供五种方法,并且有六种方法是可选的。通过正确实现 same
、consistent
和 union
方法来确保索引的正确性,而索引的效率(大小和速度)将取决于 penalty
和 picksplit
方法。两种可选方法是 compress
和 decompress
,它们允许索引具有与它索引的数据不同类型的内部树数据。叶子应该是索引数据类型,而其他树节点可以是任何 C 结构(但您仍然必须在此处遵循 PostgreSQL 数据类型规则,请参阅有关 varlena
的可变大小数据)。如果树的内部数据类型存在于 SQL 级别,则可以使用 CREATE OPERATOR CLASS
命令的 STORAGE
选项。可选的第八个方法是 distance
,如果操作员类希望支持有序扫描(最近邻搜索),则需要此方法。如果操作员类希望支持仅索引扫描,则需要可选的第九个方法 fetch
,但省略 compress
方法时除外。如果操作员类具有用户指定的参数,则需要可选的第十个方法 options
。可选的第十一个方法 sortsupport
用于加速构建 GiST 索引。
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 模块中的匹配代码可以遵循此框架
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; /* * determine return value as a function of strategy, key and query. * * Use GIST_LEAF(entry) to know where you're called in the index tree, * which comes handy when supporting the = operator for example (you could * check for non empty union() in non-leaf nodes and equality in leaf * nodes). */ *recheck = true; /* or false if check is exact */ PG_RETURN_BOOL(retval); }
此处,key
是索引中的元素,query
是在索引中查找的值。StrategyNumber
参数指示正在应用操作符类的哪个操作符——它与 CREATE OPERATOR CLASS
命令中的一个操作符编号匹配。
根据在类中包含哪些操作符,query
的数据类型可能随操作符而异,因为它将是操作符右侧的任何类型,该类型可能与左侧出现的已索引数据类型不同。(上述代码框架假定只有一种类型是可能的;如果不是,则获取 query
参数值必须取决于操作符。)建议 consistent
函数的 SQL 声明将 opclass 的已索引数据类型用于 query
参数,即使实际类型可能根据操作符而有所不同。
并集
此方法合并树中的信息。给定一组条目,此函数生成一个新的索引条目,表示所有给定的条目。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_union(internal, internal) RETURNS storage_type AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
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()
ed 内存的指针。即使没有类型更改,您也不能按原样返回输入值。
如上所示,union
函数的第一个 internal
参数实际上是一个 GistEntryVector
指针。第二个参数是指向整型变量的指针,可以忽略。(过去要求 union
函数将结果值的大小存储到该变量中,但现在不再需要这样做。)
压缩
将数据项转换为适合在索引页中物理存储的格式。如果省略 compress
方法,则数据项将存储在索引中,而不会进行修改。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_compress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* replace entry->key with a compressed version */ compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); /* fill *compressed_data from entry->key ... */ retval = palloc(sizeof(GISTENTRY)); gistentryinit(*retval, PointerGetDatum(compressed_data), entry->rel, entry->page, entry->offset, FALSE); } else { /* typically we needn't do anything with non-leaf entries */ retval = entry; } PG_RETURN_POINTER(retval); }
当然,您必须将 compressed_data_type
调整为要转换到的特定类型,以压缩叶节点。
解压缩
将数据项的存储表示转换为可由操作符类中的其他 GiST 方法操作的格式。如果省略 decompress
方法,则假定其他 GiST 方法可以直接处理存储的数据格式。(decompress
不一定是 compress
方法的逆运算;特别是,如果 compress
有损,则 decompress
不可能完全重建原始数据。 decompress
也不一定等同于 fetch
,因为其他 GiST 方法可能不需要完全重建数据。)
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_decompress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
PG_FUNCTION_INFO_V1(my_decompress); Datum my_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); }
上述框架适用于不需要解压缩的情况。(当然,完全省略该方法更简单,并且在这些情况下建议这样做。)
penalty
返回一个值,表示将新条目插入树的特定分支的 “成本”。项目将沿着树中 penalty
最小的路径插入。 penalty
返回的值应为非负值。如果返回负值,则将其视为零。
函数的 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 模块中的匹配代码可以遵循此框架
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
函数不只返回一个 float
结果;相反,它必须将值存储在第三个参数指示的位置。返回值本身会被忽略,尽管按惯例将该参数的地址传回。
penalty
函数对于索引的良好性能至关重要。在插入时,它将用于确定在选择在树中添加新条目的位置时要遵循哪个分支。在查询时,索引越平衡,查找速度就越快。
picksplit
当需要索引页面拆分时,此函数决定页面上的哪些条目保留在旧页面上,哪些条目移至新页面。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
PG_FUNCTION_INFO_V1(my_picksplit); Datum my_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); OffsetNumber maxoff = entryvec->n - 1; GISTENTRY *ent = entryvec->vector; 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; /* Initialize the raw entry vector. */ 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); /* * Choose where to put the index entries and update unionL and unionR * accordingly. Append the entries to either v->spl_left or * v->spl_right, and care about the counters. */ 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 { /* * Same on the right */ } } v->spl_ldatum = DataTypeGetDatum(unionL); v->spl_rdatum = DataTypeGetDatum(unionR); PG_RETURN_POINTER(v); }
请注意,picksplit
函数的结果是通过修改传入的 v
结构来传递的。返回值本身会被忽略,尽管按惯例将 v
的地址传回。
与 penalty
一样,picksplit
函数对于索引的良好性能至关重要。设计合适的 penalty
和 picksplit
实现是实现性能良好的 GiST 索引的挑战所在。
same
如果两个索引项相同,则返回 true,否则返回 false。(““索引项””是索引存储类型的某个值,不一定就是原始索引列的类型。)
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
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
函数不仅仅返回一个布尔结果;相反,它必须将标志存储在由第三个参数指示的位置。返回的值本身会被忽略,尽管按惯例会将该参数的地址传回。
distance
给定索引项 p
和查询值 q
,此函数确定索引项与查询值的““距离””。如果运算符类包含任何排序运算符,则必须提供此函数。使用排序运算符的查询将通过首先返回具有最小““距离””值的索引项来实现,因此结果必须与运算符的语义一致。对于叶索引项,结果仅表示到索引项的距离;对于内部树节点,结果必须是任何子项可能具有的最小距离。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal) RETURNS float8 AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然后,C 模块中的匹配代码可以遵循此框架
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); */ /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */ data_type *key = DatumGetDataType(entry->key); double retval; /* * determine return value as a function of strategy, key and query. */ PG_RETURN_FLOAT8(retval); }
distance
函数的参数与 consistent
函数的参数相同。
在确定距离时允许进行一些近似,只要结果永远不大于项的实际距离即可。因此,例如,在几何应用中,到边界框的距离通常就足够了。对于内部树节点,返回的距离不得大于到任何子节点的距离。如果返回的距离不准确,则函数必须将 *recheck
设置为 true。(对于内部树节点,这是没有必要的;对于它们,计算始终被假定为不准确的。)在这种情况下,执行器将在从堆中获取元组后计算准确的距离,并在必要时重新排序元组。
如果距离函数对任何叶节点返回 *recheck = true
,则原始排序运算符的返回类型必须是 float8
或 float4
,并且距离函数的结果值必须可与原始排序运算符的结果值进行比较,因为执行器将使用距离函数结果和重新计算的排序运算符结果进行排序。否则,距离函数的结果值可以是任何有限的 float8
值,只要结果值的相对顺序与排序运算符返回的顺序匹配即可。(无穷大和负无穷大在内部用于处理空值等情况,因此不建议 distance
函数返回这些值。)
fetch
对于仅索引扫描,将数据项的压缩索引表示转换为原始数据类型。返回的数据必须是原始索引值的精确无损副本。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_fetch(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
参数是一个指向 GISTENTRY
结构的指针。在进入时,其 key
字段包含一个非空叶数据以压缩形式。返回值是另一个 GISTENTRY
结构,其 key
字段包含相同的原始未压缩形式的数据。如果 opclass 的压缩函数对叶条目无效,则 fetch
方法可以按原样返回参数。或者,如果 opclass 没有压缩函数,也可以省略 fetch
方法,因为它必然是一个空操作。
C 模块中的匹配代码可以遵循此框架
PG_FUNCTION_INFO_V1(my_fetch); Datum my_fetch(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); input_data_type *in = DatumGetPointer(entry->key); fetched_data_type *fetched_data; GISTENTRY *retval; retval = palloc(sizeof(GISTENTRY)); fetched_data = palloc(sizeof(fetched_data_type)); /* * Convert 'fetched_data' into the a Datum of the original datatype. */ /* fill *retval from fetched_data. */ gistentryinit(*retval, PointerGetDatum(converted_datum), entry->rel, entry->page, entry->offset, FALSE); PG_RETURN_POINTER(retval); }
如果压缩方法对叶条目有损,则运算符类不支持仅索引扫描,并且不得定义 fetch
函数。
选项
允许定义控制运算符类行为的用户可见参数。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_options(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
该函数传递给 local_relopts
结构的指针,该结构需要用一组运算符类特定选项填充。可以使用 PG_HAS_OPCLASS_OPTIONS()
和 PG_GET_OPCLASS_OPTIONS()
宏从其他支持函数访问这些选项。
下面给出了 my_options() 的示例实现以及其他支持函数的参数使用
typedef enum MyEnumType { MY_ENUM_ON, MY_ENUM_OFF, MY_ENUM_AUTO } MyEnumType; typedef struct { int32 vl_len_; /* varlena header (do not touch directly!) */ int int_param; /* integer parameter */ double real_param; /* real parameter */ MyEnumType enum_param; /* enum parameter */ int str_param; /* string parameter */ } MyOptionsStruct; /* String representation of enum values */ static relopt_enum_elt_def myEnumValues[] = { {"on", MY_ENUM_ON}, {"off", MY_ENUM_OFF}, {"auto", MY_ENUM_AUTO}, {(const char *) NULL} /* list terminator */ }; static char *str_param_default = "default"; /* * Sample validator: checks that string is not longer than 8 bytes. */ static void validate_my_string_relopt(const char *value) { if (strlen(value) > 8) ereport(ERROR, (errcode(ERRCODE_INVALID_PARAMETER_VALUE), errmsg("str_param must be at most 8 bytes"))); } /* * Sample filler: switches characters to lower case. */ static Size fill_my_string_relopt(const char *value, void *ptr) { char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID); int len = strlen(tmp); if (ptr) strcpy((char *) ptr, tmp); pfree(tmp); return len + 1; } PG_FUNCTION_INFO_V1(my_options); Datum my_options(PG_FUNCTION_ARGS) { local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0); init_local_reloptions(relopts, sizeof(MyOptionsStruct)); add_local_int_reloption(relopts, "int_param", "integer parameter", 100, 0, 1000000, offsetof(MyOptionsStruct, int_param)); add_local_real_reloption(relopts, "real_param", "real parameter", 1.0, 0.0, 1000000.0, offsetof(MyOptionsStruct, real_param)); add_local_enum_reloption(relopts, "enum_param", "enum parameter", myEnumValues, MY_ENUM_ON, "Valid values are: \"on\", \"off\" and \"auto\".", offsetof(MyOptionsStruct, enum_param)); add_local_string_reloption(relopts, "str_param", "string parameter", str_param_default, &validate_my_string_relopt, &fill_my_string_relopt, offsetof(MyOptionsStruct, str_param)); PG_RETURN_VOID(); } PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { int int_param = 100; double real_param = 1.0; MyEnumType enum_param = MY_ENUM_ON; char *str_param = str_param_default; /* * Normally, when opclass contains 'options' method, then options are always * passed to support functions. However, if you add 'options' method to * existing opclass, previously defined indexes have no options, so the * check is required. */ if (PG_HAS_OPCLASS_OPTIONS()) { MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS(); int_param = options->int_param; real_param = options->real_param; enum_param = options->enum_param; str_param = GET_STRING_RELOPTION(options, str_param); } /* the rest implementation of support function */ }
由于 GiST 中键的表示是灵活的,因此它可能取决于用户指定的参数。例如,可以指定键签名的长度。例如,请参阅 gtsvector_options()
。
sortsupport
返回一个比较器函数,以保留局部性的方式对数据进行排序。它由 CREATE INDEX
和 REINDEX
命令使用。创建的索引的质量取决于比较器函数确定的排序顺序在多大程度上保留了输入的局部性。
sortsupport
方法是可选的。如果未提供,则 CREATE INDEX
通过使用 penalty
和 picksplit
函数将每个元组插入到树中来构建索引,这要慢得多。
函数的 SQL 声明必须如下所示
CREATE OR REPLACE FUNCTION my_sortsupport(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
参数是一个指向 SortSupport
结构的指针。该函数至少必须填充其比较器字段。比较器采用三个参数:两个要比较的数据,以及指向 SortSupport
结构的指针。数据是索引中存储的格式中的两个索引值;也就是说,以 compress
方法返回的格式。完整的 API 在 src/include/utils/sortsupport.h
中定义。
C 模块中的匹配代码可以遵循此框架
PG_FUNCTION_INFO_V1(my_sortsupport); static int my_fastcmp(Datum x, Datum y, SortSupport ssup) { /* establish order between x and y by computing some sorting value z */ int z1 = ComputeSpatialCode(x); int z2 = ComputeSpatialCode(y); return z1 == z2 ? 0 : z1 > z2 ? 1 : -1; } Datum my_sortsupport(PG_FUNCTION_ARGS) { SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); ssup->comparator = my_fastcmp; PG_RETURN_VOID(); }
所有 GiST 支持方法通常在短期内存上下文中调用;也就是说,在处理每个元组后,CurrentMemoryContext
将重置。因此,不必担心释放所有 palloc。但是,在某些情况下,支持方法跨重复调用缓存数据很有用。要执行此操作,请在 fcinfo->flinfo->fn_mcxt
中分配较长时间的数据,并在 fcinfo->flinfo->fn_extra
中保留指向它的指针。此类数据将在索引操作的整个生命周期内保留(例如,单个 GiST 索引扫描、索引构建或索引元组插入)。替换 fn_extra
值时,请小心释放前一个值,否则泄漏将在操作期间累积。