Docs4dev
Docs
postgre-sql / 10.7 / reference / spgist-extensibility.html

63.3. Extensibility

SP-GiST 提供了具有高度抽象的接口，要求访问方法开发人员仅实现特定于给定数据类型的方法。 SP-GiST 核心负责高效的磁盘 Map 和搜索树结构。它还考虑了并发性和日志记录注意事项。

SP-GiST 树的叶 Tuples 包含与索引列相同的数据类型的值。根级别的叶 Tuples 将始终包含原始索引数据值，但较低级别的叶 Tuples 可能仅包含压缩的表示形式，例如后缀。在那种情况下，操作员类别支持功能必须能够使用从内部 Tuples 累积的信息重建原始值，这些内部 Tuples 通过这些信息到达叶级别。

内部 Tuples 更为复杂，因为它们是搜索树中的分支点。每个内部 Tuples 包含一组一个或多个* node ，它们代表相似叶值的组。一个节点包含一个下行链路，该下行链路通向另一个较低级别的内部 Tuples，或通向全部位于同一索引页上的叶 Tuples 的简短列表。每个节点通常都有一个描述它的“标签”；例如，在基数树中，节点标签可以是字符串值的下一个字符。 (或者，如果操作符类对所有内部 Tuples 使用一组固定的节点，则可以省略节点标签；请参见Section 63.4.2。)可选地，内部 Tuples 可以具有 prefix *值来描述其所有成员。在基数树中，这可能是所表示字符串的通用前缀。前缀值不一定是 true 的前缀，而可以是运算符类所需的任何数据；例如，在四叉树中，它可以存储相对于四个象限进行测量的中心点。然后，四叉树内部 Tuples 还将包含与该中心点周围的象限相对应的四个节点。

一些树算法需要了解当前 Tuples 的级别(或深度)，因此 SP-GiST 核心为操作员类提供了在树下降时 Management 级别计数的可能性。还支持在需要时以增量方式重建表示的值，并支持在树下降期间传递附加数据(称为“遍历值”)。

Note

SP-GiST 核心代码负责空条目。尽管 SP-GiST 索引确实将空条目存储在索引列中，但这在索引运算符类代码中是隐藏的：绝不会将空索引条目或搜索条件传递给运算符类方法。 (假定 SP-GiST 运算符是严格的，因此对于空值无法成功执行.)因此，此处不再讨论空值。

SP-GiST 的索引运算符类必须提供五种用户定义的方法。所有这五个都遵循接受两个internal参数的约定，第一个参数是指向包含支持方法 Importing 值的 C 结构的指针，而第二个参数是指向必须放置输出值的 C 结构的指针。其中四个方法只返回void，因为它们的所有结果都出现在输出结构中；但leaf_consistent另外会返回boolean结果。这些方法不得修改其 Importing 结构的任何字段。在所有情况下，在调用用户定义的方法之前，将输出结构初始化为零。

用户定义的五个方法是：

  • config

    • 返回有关索引实现的静态信息，包括前缀的数据类型 OID 和节点标签数据类型。

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

CREATE FUNCTION my_config(internal, internal) RETURNS void ...

第一个参数是指向spgConfigIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgConfigOut C 结构的指针，该函数必须用结果数据填充。

typedef struct spgConfigIn
{
    Oid         attType;        /* Data type to be indexed */
} spgConfigIn;

typedef struct spgConfigOut
{
    Oid         prefixType;     /* Data type of inner-tuple prefixes */
    Oid         labelType;      /* Data type of inner-tuple node labels */
    bool        canReturnData;  /* Opclass can reconstruct original data */
    bool        longValuesOK;   /* Opclass can cope with values > 1 page */
} spgConfigOut;

传递attType是为了支持多态索引运算符类；对于普通的固定数据类型运算符类，它将始终具有相同的值，因此可以忽略。

对于不使用前缀的运算符类，可以将prefixType设置为VOIDOID。同样，对于不使用节点标签的运算符类，可以将labelType设置为VOIDOID。如果操作符类能够重建原始提供的索引值，则应将canReturnData设置为 true。仅当attType的长度可变并且操作员类能够通过重复后缀来分割长值时，才应将longValuesOK设置为 true(请参见Section 63.4.1)。

  • choose

    • 选择一种将新值插入内部 Tuples 的方法。

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

CREATE FUNCTION my_choose(internal, internal) RETURNS void ...

第一个参数是指向spgChooseIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgChooseOut C 结构的指针，该函数必须用结果数据填充。

typedef struct spgChooseIn
{
    Datum       datum;          /* original datum to be indexed */
    Datum       leafDatum;      /* current datum to be stored at leaf */
    int         level;          /* current level (counting from zero) */

    /* Data from current inner tuple */
    bool        allTheSame;     /* tuple is marked all-the-same? */
    bool        hasPrefix;      /* tuple has a prefix? */
    Datum       prefixDatum;    /* if so, the prefix value */
    int         nNodes;         /* number of nodes in the inner tuple */
    Datum      *nodeLabels;     /* node label values (NULL if none) */
} spgChooseIn;

typedef enum spgChooseResultType
{
    spgMatchNode = 1,           /* descend into existing node */
    spgAddNode,                 /* add a node to the inner tuple */
    spgSplitTuple               /* split inner tuple (change its prefix) */
} spgChooseResultType;

typedef struct spgChooseOut
{
    spgChooseResultType resultType;     /* action code, see above */
    union
    {
        struct                  /* results for spgMatchNode */
        {
            int         nodeN;      /* descend to this node (index from 0) */
            int         levelAdd;   /* increment level by this much */
            Datum       restDatum;  /* new leaf datum */
        }           matchNode;
        struct                  /* results for spgAddNode */
        {
            Datum       nodeLabel;  /* new node's label */
            int         nodeN;      /* where to insert it (index from 0) */
        }           addNode;
        struct                  /* results for spgSplitTuple */
        {
            /* Info to form new upper-level inner tuple with one child tuple */
            bool        prefixHasPrefix;    /* tuple should have a prefix? */
            Datum       prefixPrefixDatum;  /* if so, its value */
            int         prefixNNodes;       /* number of nodes */
            Datum      *prefixNodeLabels;   /* their labels (or NULL for
                                             * no labels) */
            int         childNodeN;         /* which node gets child tuple */

            /* Info to form new lower-level inner tuple with all old nodes */
            bool        postfixHasPrefix;   /* tuple should have a prefix? */
            Datum       postfixPrefixDatum; /* if so, its value */
        }           splitTuple;
    }           result;
} spgChooseOut;

datum是要插入索引中的原始基准。 leafDatum最初与datum相同，但是如果choose或picksplit方法对其进行更改，则可以在树的较低级别进行更改。当插入搜索到达叶子页面时，leafDatum的当前值将存储在新创建的叶子 Tuples 中。 level是当前内部 Tuples 的级别，从根级别的零开始。如果当前内部 Tuples 被标记为包含多个等效节点，则allTheSame为 true(请参见Section 63.4.3)。如果当前内部 Tuples 包含前缀，则hasPrefix为 true；如果是，则prefixDatum是其值。 nNodes是内部 Tuples 中包含的子节点的数量，nodeLabels是其标签值的数组，如果没有标签，则为 NULL。

choose函数可以确定新值与现有子节点之一匹配，或者必须添加新的子节点，或者新值与 Tuples 前缀不一致，因此必须拆分内部 Tuples 以创建一个限制性较小的前缀。

如果新值与现有子节点之一匹配，则将resultType设置为spgMatchNode。将nodeN设置为节点数组中该节点的索引(从零开始)。将levelAdd设置为通过该节点下降引起的level增量，如果操作员类不使用级别，则将其设置为零。如果操作员类未将基准从一个级别修改到下一个级别，请将restDatum设置为等于datum，否则将其设置为修改的值以用作下一个级别的leafDatum。

如果必须添加新的子节点，请将resultType设置为spgAddNode。将nodeLabel设置为用于新节点的标签，并将nodeN设置为将节点插入节点数组的索引(从零开始)。添加节点后，将使用修改后的内部 Tuples 再次调用choose函数。该调用应导致spgMatchNode结果。

如果新值与 Tuples 前缀不一致，则将resultType设置为spgSplitTuple。该动作将所有现有节点移动到新的较低级内部 Tuples 中，并用具有指向新低级内部 Tuples 的单个下行链路的 Tuples 来替换现有的内部 Tuples。设置prefixHasPrefix以指示新的上级 Tuples 是否应具有前缀，如果是，则将prefixPrefixDatum设置为前缀值。此新前缀值的限制必须比原始限制少得多，以接受要索引的新值。将prefixNNodes设置为新 Tuples 中所需的节点数，并将prefixNodeLabels设置为包含其标签的 palloc 数组，或者将prefixNodeLabels设置为 NULL(如果不需要节点标签)。请注意，新的上层 Tuples 的总大小必须不超过要替换的 Tuples 的总大小；这限制了新前缀和新标签的长度。将childNodeN设置为将下行到新的较低级内部 Tuples 的节点的索引(从零开始)。设置postfixHasPrefix以指示新的较低级内部 Tuples 是否应具有前缀，如果是，则将postfixPrefixDatum设置为前缀值。这两个前缀和下行链路节点标签(如果有)的组合必须具有与原始前缀相同的含义，因为没有机会更改移至新的下级 Tuples 的节点标签，也没有任何更改的机会。子索引条目。拆分节点后，将使用替换内部 Tuples 再次调用choose函数。如果spgSplitTuple操作未创建合适的节点，则该调用可能返回spgAddNode结果。最终choose必须返回spgMatchNode才能使插入下降到下一个级别。

  • picksplit

    • 决定如何在一组叶 Tuples 上创建新的内部 Tuples。

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

CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...

第一个参数是指向spgPickSplitIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgPickSplitOut C 结构的指针，该函数必须用结果数据填充。

typedef struct spgPickSplitIn
{
    int         nTuples;        /* number of leaf tuples */
    Datum      *datums;         /* their datums (array of length nTuples) */
    int         level;          /* current level (counting from zero) */
} spgPickSplitIn;

typedef struct spgPickSplitOut
{
    bool        hasPrefix;      /* new inner tuple should have a prefix? */
    Datum       prefixDatum;    /* if so, its value */

    int         nNodes;         /* number of nodes for new inner tuple */
    Datum      *nodeLabels;     /* their labels (or NULL for no labels) */

    int        *mapTuplesToNodes;   /* node index for each leaf tuple */
    Datum      *leafTupleDatums;    /* datum to store in each new leaf tuple */
} spgPickSplitOut;

nTuples是提供的叶子 Tuples 的数量。 datums是其基准值的数组。 level是所有叶 Tuples 共享的当前级别，它将成为新内部 Tuples 的级别。

设置hasPrefix以指示新的内部 Tuples 是否应具有前缀，如果是，则将prefixDatum设置为前缀值。设置nNodes以指示新内部 Tuples 将包含的节点数，并将nodeLabels设置为其标签值的数组，或者将nodeLabels设置为 NULL(如果不需要节点标签)。将mapTuplesToNodes设置为一个数组，该数组给出每个叶 Tuples 应分配给的节点的索引(从零开始)。将leafTupleDatums设置为要存储在新叶 Tuples 中的值的数组(如果操作员类未将基准从一个级别修改到另一个级别，则这些值将与 Importingdatums相同)。请注意，picksplit函数负责对nodeLabels，mapTuplesToNodes和leafTupleDatums数组进行分配。

如果提供了多个叶 Tuples，则预期picksplit函数会将它们分类为多个节点；否则，否则，不可能将叶 Tuples 拆分为多个页面，这是此操作的最终目的。因此，如果picksplit函数最终将所有叶 Tuples 放置在同一节点中，则核心 SP-GiST 代码将覆盖该决策，并生成一个内部 Tuples，其中，叶 Tuples 被随机分配给几个相同标签的节点。这样的 Tuples 标记为allTheSame，表示已发生这种情况。 choose和inner_consistent函数必须适当注意此类内部 Tuples。有关更多信息，请参见Section 63.4.3。

只有在config函数将longValuesOK设置为 true 且已提供大于页面 Importing 值的情况下，才能将picksplit应用于单个叶 Tuples。在这种情况下，操作的重点是剥离前缀并产生新的较短的叶子基准值。该调用将重复进行，直到生成了足够短以适合页面的叶数据为止。有关更多信息，请参见Section 63.4.1。

  • inner_consistent

    • 返回树搜索期间要遵循的节点(分支)集。

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

CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...

第一个参数是指向spgInnerConsistentIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgInnerConsistentOut C 结构的指针，该函数必须用结果数据填充。

typedef struct spgInnerConsistentIn
{
    ScanKey     scankeys;       /* array of operators and comparison values */
    int         nkeys;          /* length of array */

    Datum       reconstructedValue;     /* value reconstructed at parent */
    void       *traversalValue; /* opclass-specific traverse value */
    MemoryContext traversalMemoryContext;   /* put new traverse values here */
    int         level;          /* current level (counting from zero) */
    bool        returnData;     /* original data must be returned? */

    /* Data from current inner tuple */
    bool        allTheSame;     /* tuple is marked all-the-same? */
    bool        hasPrefix;      /* tuple has a prefix? */
    Datum       prefixDatum;    /* if so, the prefix value */
    int         nNodes;         /* number of nodes in the inner tuple */
    Datum      *nodeLabels;     /* node label values (NULL if none) */
} spgInnerConsistentIn;

typedef struct spgInnerConsistentOut
{
    int         nNodes;         /* number of child nodes to be visited */
    int        *nodeNumbers;    /* their indexes in the node array */
    int        *levelAdds;      /* increment level by this much for each */
    Datum      *reconstructedValues;    /* associated reconstructed values */
    void      **traversalValues;        /* opclass-specific traverse values */
} spgInnerConsistentOut;

长度为nkeys的数组scankeys描述了索引搜索条件。这些条件与 AND 结合使用-只有满足所有条件的索引条目才有意义。 (请注意nkeys = 0 表示所有索引条目都满足查询.)通常，一致性函数只关心每个数组条目的sk_strategy和sk_argument字段，它们分别提供可索引的运算符和比较值。特别是，不必检查sk_flags来查看比较值是否为 NULL，因为 SP-GiST 核心代码将过滤掉这种情况。 reconstructedValue是为父 Tuples 重构的值；在根级别为(Datum) 0，或者inner_consistent函数未在父级别提供值。 traversalValue是指向从父索引 Tuples 上的inner_consistent的先前调用向下传递的任何遍历数据的指针，或在根级别为 NULL。 traversalMemoryContext是用于存储输出导线值的存储器上下文(请参见下文)。 level是当前内部 Tuples 的级别，从根级别的零开始。如果此查询需要重建数据，则returnData为true；仅当config函数 assertcanReturnData时才如此。如果当前内部 Tuples 标记为“全部相同”，则allTheSame为 true；在这种情况下，所有节点都具有相同的标签(如果有的话)，因此全部或都不匹配查询(请参见Section 63.4.3)。如果当前内部 Tuples 包含前缀，则hasPrefix为 true；否则为hasPrefix。如果是这样，则prefixDatum是其值。 nNodes是内部 Tuples 中包含的子节点的数量，并且nodeLabels是其标签值的数组；如果节点没有标签，则为 NULL。

必须将nNodes设置为搜索需要访问的子节点的数量，并且将nodeNumbers设置为其索引的数组。如果操作员类别跟踪级别，则将levelAdds设置为下降到要访问的每个节点时所需的级别增量的数组。 (通常这些增量对于所有节点都是相同的，但是不一定如此，因此使用数组.)如果需要值重构，请将reconstructedValues设置为为每个要访问的子节点重构的值的数组；否则，将reconstructedValues保留为 NULL。如果希望将附加的带外信息(“遍历值”)传递给树搜索的较低级别，请将traversalValues设置为适当的遍历值的数组，每个要访问的子节点一个；否则，将traversalValues保留为 NULL。请注意，inner_consistent函数负责在当前内存上下文中分配nodeNumbers，levelAdds，reconstructedValues和traversalValues数组。但是，traversalValues数组所指向的任何输出遍历值都应在traversalMemoryContext中分配。每个遍历值必须是单个分配的块。

  • leaf_consistent

    • 如果叶子 Tuples 满足查询，则返回 true。

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

CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...

第一个参数是指向spgLeafConsistentIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgLeafConsistentOut C 结构的指针，该函数必须用结果数据填充。

typedef struct spgLeafConsistentIn
{
    ScanKey     scankeys;       /* array of operators and comparison values */
    int         nkeys;          /* length of array */

    Datum       reconstructedValue;     /* value reconstructed at parent */
    void       *traversalValue; /* opclass-specific traverse value */
    int         level;          /* current level (counting from zero) */
    bool        returnData;     /* original data must be returned? */

    Datum       leafDatum;      /* datum in leaf tuple */
} spgLeafConsistentIn;

typedef struct spgLeafConsistentOut
{
    Datum       leafValue;      /* reconstructed original data, if any */
    bool        recheck;        /* set true if operator must be rechecked */
} spgLeafConsistentOut;

长度为nkeys的数组scankeys描述了索引搜索条件。这些条件与 AND 结合使用-只有满足所有条件的索引条目才能满足查询。 (请注意nkeys = 0 表示所有索引条目都满足查询.)通常，一致性函数只关心每个数组条目的sk_strategy和sk_argument字段，它们分别提供可索引的运算符和比较值。特别是，不必检查sk_flags来查看比较值是否为 NULL，因为 SP-GiST 核心代码将过滤掉这种情况。 reconstructedValue是为父 Tuples 重构的值；在根级别为(Datum) 0，或者inner_consistent函数未在父级别提供值。 traversalValue是指向从父索引 Tuples 上的inner_consistent的先前调用向下传递的任何遍历数据的指针，或在根级别为 NULL。 level是当前叶 Tuples 的级别，从根级别的零开始。如果此查询需要重建的数据，则returnData为true；仅当config函数 assertcanReturnData时才如此。 leafDatum是存储在当前叶 Tuples 中的键值。

如果叶子 Tuples 与查询匹配，则该函数必须返回true，否则返回false。在true的情况下，如果returnData是true，则必须将leafValue设置为最初提供的值，以便为此叶子 Tuples 构建索引。此外，如果匹配不确定，则recheck可以设置为true，因此必须将运算符重新应用于实际堆 Tuples 以验证匹配。

通常在短期内存上下文中调用所有 SP-GiST 支持方法。也就是说，CurrentMemoryContext将在处理每个 Tuples 后重置。因此，担心 pfreeing 分配 palloc 的所有内容并不是很重要。 (config方法是一个 exception：它应尽量避免泄漏内存.但是通常config方法无需执行任何操作，只不过将常量分配给传递的参数 struct.)

如果索引列是可排序数据类型，则将使用标准PG_GET_COLLATION()机制将索引排序规则传递给所有支持方法。