64.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 的索引运算符类必须提供五种方法,其中四种是可选的。正确执行sameconsistentunion方法可确保索引的正确性,而索引的效率(大小和速度)将取决于penaltypicksplit方法。 compressdecompress这是两个可选方法,它们允许索引具有与其索引的数据不同类型的内部树数据。叶子将是索引数据类型,而其他树节点可以是任何 C 结构(但您仍然必须在这里遵循 PostgreSQL 数据类型规则,有关可变大小的数据,请参见varlena)。如果树的内部数据类型在 SQL 级别存在,则可以使用CREATE OPERATOR CLASS命令的STORAGE选项。可选的第八种方法是distance,如果操作员类别希望支持有序扫描(最近邻居搜索),则需要使用该方法。如果操作员类希望支持仅索引扫描,则需要可选的第九种方法fetch,除非省略了compress方法。

  • 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

    • 将数据项转换为适合物理存储在索引页中的格式。如果省略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

    • 将存储的数据项表示形式转换为可由操作员类中其他 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结果,还返回了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函数对于索引的良好性能至关重要。设计合适的penaltypicksplit实现是实现性能良好的 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,则原始排序运算符的返回类型必须为float8float4,并且距离函数的结果值必须与原始排序运算符的结果值相当,因为执行程序将同时使用两个距离函数结果进行排序和重新计算的 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方法可以按原样返回参数。或者,如果 opclass 不具有 compress 函数,则fetch方法也可以省略,因为它必然是 no-op。

然后,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值时,请小心释放先前的值,否则在操作期间将累积泄漏。