62.3. Extensibility

传统上，实现新的索引访问方法意味着很多困难的工作。有必要了解数据库的内部工作原理，例如锁 Management 器和预写日志。 GiST 接口具有很高的抽象度，要求访问方法实现者仅实现被访问数据类型的语义。 GiST 层本身负责并发，日志记录和搜索树结构。

就其可处理的数据而言，此可扩展性不应与其他标准搜索树的可扩展性相混淆。例如，PostgreSQL 支持可扩展的 B 树和哈希索引。这意味着您可以使用 PostgreSQL 在所需的任何数据类型上构建 B 树或哈希。但是 B 树仅支持范围谓词(<，=，>)，并且哈希索引仅支持相等性查询。

因此，如果您用 PostgreSQL B 树索引一个图像集合，则只能发出诸如“ is imagex 等于 imagey”，“ is imagex 小于 imagey”和“ is imagex 大于 imagey”之类的查询。在此上下文中，取决于定义“等于”，“小于”和“大于”的方式，这可能会很有用。但是，通过使用基于 GiST 的索引，您可以创建方法来询问特定领域的问题，例如“查找所有马匹图像”或“查找所有曝光过度的图像”。

启动和运行 GiST 访问方法所需的全部工作就是实现几个用户定义的方法，这些方法定义了树中键的行为。当然，这些方法必须相当不错才能支持复杂查询，但是对于所有标准查询(B 树，R 树等)，它们都是相对简单的。简而言之，GiST 将可扩展性与通用性，代码重用和干净的界面结合在一起。

GiST 的索引运算符类必须提供 7 种方法，其中 2 种是可选的。正确执行same，consistent和union方法可确保索引的正确性，而索引的效率(大小和速度)将取决于penalty和picksplit方法。剩下的两个基本方法是compress和decompress，它们允许索引具有与其索引的数据不同类型的内部树数据。叶子将是索引数据类型，而其他树节点可以是任何 C 结构(但是您仍然必须遵循 PostgreSQL 数据类型规则，有关可变大小的数据，请参见varlena)。如果树的内部数据类型在 SQL 级别存在，则可以使用CREATE OPERATOR CLASS命令的STORAGE选项。可选的第八种方法是distance，如果操作员类别希望支持有序扫描(最近邻居搜索)，则需要使用该方法。如果操作员类希望支持仅索引扫描，则需要可选的第九种方法fetch。

consistent
- 给定一个索引条目p和一个查询值q，此函数确定索引条目是否与查询“一致”；也就是说，谓词“ * indexed_column * * indexable_operator * q”对于由索引条目表示的任何行是否为真？对于叶索引条目，这等效于测试可索引条件，而对于内部树节点，这确定是否需要扫描由树节点表示的索引的子树。当结果为true时，还必须返回recheck标志。这表明谓词是肯定的，还是仅可能是真的。如果recheck = false，则索引已完全测试谓词条件，而如果recheck = true，则该行仅是候选匹配项。在那种情况下，系统将根据实际的行值自动评估* indexable_operator *，以查看它是否 true 匹配。该约定允许 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的数据类型可能会随运算符而变化，因为它会是运算符右侧的任何类型，可能与左侧显示的索引数据类型不同侧。 (以上代码框架假定只能使用一种类型；否则，取_参数值将必须取决于运算符.)建议consistent函数的 SQL 声明对query使用 opclass 的索引数据类型。参数，即使实际类型取决于操作符也可能是其他类型。

union
- 此方法将信息合并到树中。给定一组条目，此函数将生成一个代表所有给定条目的新索引条目。

该函数的 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()版本的内存的指针。即使没有类型更改，也不能按原样返回 Importing 值。

如上所示，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 *以适应要转换的特定类型，以便压缩叶节点。

decompress
- compress方法的相反过程。将数据项的索引表示形式转换为可由操作符类中的其他 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结果，还返回了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);
}

请注意，通过修改传入的v结构来传递picksplit函数的结果。返回值本身被忽略，尽管按惯例传回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。 (对于内部树节点，这不是必需的；对于它们，始终假定计算不精确.)在这种情况下，执行程序将在从堆中获取 Tuples 之后计算准确的距离，并在必要时对 Tuples 进行重新排序。

如果距离函数对于任何叶节点返回*recheck = true，则原始排序运算符的返回类型必须为float8或float4，并且距离函数的结果值必须与原始排序运算符的结果值相当，因为执行程序将同时使用两个距离函数结果进行排序和重新计算的 OrderOperators 结果。否则，距离函数的结果值可以是任何有限的float8值，只要结果值的相对 Sequences 与排序运算符返回的 Sequences 匹配即可。 (内部使用无穷大和负无穷大来处理诸如 null 之类的情况，因此不建议distance函数返回这些值.)

fetch
- 将数据项的压缩索引表示形式转换为原始数据类型，以进行仅索引扫描。返回的数据必须是原始索引值的准确无损副本。

该函数的 SQL 声明必须如下所示：

CREATE OR REPLACE FUNCTION my_fetch(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

该参数是指向GISTENTRY结构的指针。在 Importing 时，其key字段包含压缩形式的非 NULL 叶子数据。返回值是另一个GISTENTRY结构，其key字段以原始的未压缩形式包含相同的数据。如果 opclass 的 compress 函数对叶条目不执行任何操作，则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);
}

如果 compress 方法对于叶条目而言是有损的，则操作符类不能支持仅索引扫描，并且不能定义fetch函数。

通常在短期内存上下文中调用所有 GiST 支持方法。也就是说，处理完每个 Tuples 后，CurrentMemoryContext将被重置。因此，担心 pfreeing 分配 palloc 的所有内容并不是很重要。但是，在某些情况下，对于支持方法在重复调用之间缓存数据很有用。为此，请在fcinfo->flinfo->fn_mcxt中分配寿命更长的数据，并在fcinfo->flinfo->fn_extra中保留指向它的指针。这样的数据将在索引操作的生命周期内保持生存(例如，单个 GiST 索引扫描，索引构建或索引 Tuples 插入)。替换fn_extra值时，请小心释放先前的值，否则在操作期间将累积泄漏。

Docs

Docs4dev

Title here

62.3. Extensibility