Postgresql 中文操作指南

69.3. Extensibility #

SP-GiST 提供了一个具有高抽象级别的高级接口，它要求访问方法开发人员只实现特定于给定数据类型的特定方法。SP-GiST 内核负责高效磁盘映射和搜索树形结构。它还可以处理并发性和记录事项。

SP-GiST 树的叶元组通常包含与索引列相同数据类型的值，尽管它们还可能包含索引列的丢失表示形式。存储在根级别的叶元组直接表示原始索引数据值，但较低级别的叶元组可能只包含部分值，如后缀。在这种情况下，运算符类支持函数必须能够使用从传递到叶级别的内部元组中积累的信息来重建原始值。

当使用 INCLUDE 列创建 SP-GiST 索引时，这些列的值也存储在叶元组中。SP-GiST 运算符类不关心 INCLUDE 列，因此此处不再讨论它们。

内部元组更复杂，因为它们是搜索树中的分支点。每个内部元组都包含一个或多个 nodes，它代表相似叶值组。一个节点包含一个向下链接，它要么通向另一个较低级别的内部元组，要么通向所有位于同一索引页上的叶元组的简短列表。每个节点通常都有一个 label 来描述它；例如，在基数树中，节点标签可以是字符串值的下一个字符。（或者，一个运算符类可以省略节点标签，如果它对所有内部元组使用一组固定的节点；请参阅 Section 69.4.2。）内部元组可以根据需要拥有一个 prefix 值来描述其所有成员。在径向树中，这可能是表示字符串的公共前缀。前缀值不一定真正是前缀，但可以是运算符类需要的任何数据；例如，在四叉树中，它可以存储相对于其测量四个象限的中心点。然后，一个四叉树内部元组还将包含四个与这个中心点周围象限对应的节点。

一些树算法需要具备有关当前元组的级别（或深度）的知识，因此 SP-GiST 内核使得运算符类能够在下降树时管理级别计数。它还支持在需要时对所表示的值进行增量重建，以及在树下降过程中传递附加数据（称为 traverse values ）。

Note

SP-GiST 核心代码负责空条目。虽然 SP-GiST 索引的确会存储已编制索引的列中的 NULL 的条目，但索引操作符类代码中不会显示这一点：绝不会将空索引条目或搜索条件传递给操作符类方法。（假定 SP-GiST 操作符是严格的，因此对空值无法成功。）因此，这里不再进一步讨论空值。

SP-GiST 的索引运算符类必须提供五种用户定义的方法，还有两种是可选的。所有五种必需的方法都遵循接受两个 internal 参数的约定，其中第一个参数是指向包含支持方法的输入值的 C 结构体的指针，而第二个参数是指向必须放置输出值的 C 结构体的指针。其中四种必需的方法只返回 void ，因为它们的所有结果都出现在输出结构中；但是， leaf_consistent 返回一个 boolean 结果。这些方法不得修改其输入结构的任何字段。在所有情况下，在调用用户定义的方法之前，输出结构全部初始化为零。可选项第六种方法 compress 接受一个将被编入索引的 datum 作为其唯一参数，并返回一个适合在叶元组中进行物理存储的值。可选项第七种方法 options 接受一个指向 C 结构体的 internal 指针，其中应放置特定于运算符类的参数，并返回 void 。

这五种必需的用户定义方法是：

  • config

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

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

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

  • 第一个参数是指向包含函数的输入数据 spgConfigIn C 结构体的指针。第二个参数是指向 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 */
    Oid         leafType;       /* Data type of leaf-tuple values */
    bool        canReturnData;  /* Opclass can reconstruct original data */
    bool        longValuesOK;   /* Opclass can cope with values > 1 page */
} spgConfigOut;

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

  • 对于不使用前缀的运算符类，prefixType 可以设置为 VOIDOID。同样，对于不使用节点标签的运算符类，labelType 可以设置为 VOIDOID。如果运算符类能够重建最初提供的索引值，则应将 canReturnData 设置为真。只有当 attType 是可变长度并且运算符类能够通过重复后缀对长值进行分段（请参阅 Section 69.4.1）时，才应将 longValuesOK 设置为真。

  • leafType 应与操作类 opckeytype 目录项定义的索引存储类型匹配。（请注意， opckeytype 可以为零，这意味着存储类型与操作类的输入类型相同，这是最常见的情况。）为了向后兼容， config 方法可以将 leafType 设置为其他值，并将使用该值；但是，这是不推荐的做法，因为索引内容随后在目录中被错误标识。此外，允许将 leafType 留空（为零）；这意味着从 opckeytype 派生的索引存储类型。

  • 当 attType 和 leafType 不同时，必须提供可选方法 compress。方法 compress 负责将数据从 attType 转换为 leafType 以便进行索引。

    • choose

  • 选择用于将新值插入内部元组的方法。

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

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

  • 第一个参数是 spgChooseIn C 结构的指针，包含用于函数的输入数据。第二个参数是 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 是 spgConfigIn 的原始基准。 attType 类型即将插入到索引中。 leafDatum 是 spgConfigOut 的值。 leafType 类型，它最初是方法 compress 的结果，应用到 datum 上，当提供 compress 方法时，或者与 datum 相同的值，否则。如果 choose 或 picksplit 方法更改 leafDatum ，则 leafDatum 在树的较低级别可能会更改。当插入搜索到达叶页时， leafDatum 的当前值将存储在新建的叶元组中。 level 是当前内元组的级别，从根级别开始为零。如果标记当前内元组为包含多个同等节点（请参见 Section 69.4.3 ），则 allTheSame 将为真。如果当前内元组包含前缀，则 hasPrefix 为真；如果是的话， prefixDatum 是它的值。 nNodes 是内元组中包含的子节点数，而 nodeLabels 是其标签值的数组，如果没有标签，则为NULL。

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

  • 如果新值与现有子节点之一匹配，将 resultType 设为 spgMatchNode。将 nodeN 设为该节点在节点数组中的索引（从 0 开始）。如果操作员类不使用级别，将 levelAdd 设为由于下降到该节点而导致的 level 增量，或将其保留为 0。如果操作员类不修改不同级别的 data，则将 restDatum 设为等于 leafDatum，否则将其设为要在下一级别用作 leafDatum 的修改值。

  • 如果必须添加新子节点，将 resultType 设为 spgAddNode。将 nodeLabel 设为要用于新节点的标签，并将 nodeN 设为可在节点数组中插入节点的索引（从零开始）。添加节点之后，choose 函数将使用修改后的内部元组再次调用；该调用应导致 spgMatchNode 结果。

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

    • picksplit

  • 决定如何为一组叶子元组创建新的内部元组。

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

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

  • 第一个参数是 spgPickSplitIn C 结构的指针，包含用于函数的输入数据。第二个参数是 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 是提供的叶子元组数。datums 是其数据值 spgConfigOut__leafType 类型的数组。level 是所有叶子元组共享的当前级别，它将成为新内部元组的级别。

  • 将 hasPrefix 设置为指示新的内部元组是否应具有前缀，如果应具有前缀，则将 prefixDatum 设置为前缀值。将 nNodes 设置为表示新内部元组将包含的节点数，并将 nodeLabels 设置为其标签值的数组，或如果不需要节点标签，则将其设置为 NULL。将 mapTuplesToNodes 设置为提供应将每个叶元组分配给哪个节点的索引（从零开始）的数组。将 leafTupleDatums 设置为要在新叶元组中存储的值的数组（如果运算符类未将数据从一个级别修改到下一个级别，则这些值将与输入 datums 相同）。请注意， picksplit 函数负责分配 nodeLabels 、 mapTuplesToNodes 和 leafTupleDatums 数组的 palloc。

  • 如果提供了多个叶元组，则预期 picksplit 函数会将它们分类为多个节点；否则，无法将叶元组拆分到多个页面中，而这是此操作的最终目的。因此，如果 picksplit 函数最终将所有叶元组都放在同一节点中，则核心 SP-GiST 代码将覆盖该决策并生成一个内部元组，其中叶元组被随机分配到几个标签相同的节点中。这样的元组被标记 allTheSame 以表示已经发生这种情况。choose 和 inner_consistent 函数必须对这种内部元组进行适当的处理。有关详细信息，请参阅 Section 69.4.3。

  • 只有在 config 函数将 longValuesOK 设置为真并且已经提供了大于页面输入值的情况下，才能将 picksplit 应用于单个叶元组。在这种情况下，操作的目的是剥离一个前缀并生成一个新的、更短的叶数据值。该调用将重复，直到生成一个足够短以适合页面的叶数据。有关详细信息，请参阅 Section 69.4.1。

    • inner_consistent

  • 返回树搜索期间要关注的节点（分支）集合。

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

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

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

typedef struct spgInnerConsistentIn
{
    ScanKey     scankeys;       /* array of operators and comparison values */
    ScanKey     orderbys;       /* array of ordering operators and comparison
                                 * values */
    int         nkeys;          /* length of scankeys array */
    int         norderbys;      /* length of orderbys 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 */
    double    **distances;              /* associated distances */
} spgInnerConsistentOut;

  • 长度为 nkeys 的数组 scankeys 描述了索引搜索条件。这些条件与 AND 结合使用 — 只有满足所有条件的索引条目才有意义。（请注意， nkeys = 0 表示所有索引条目都满足查询。）一般来说，一致函数只关心每个数组条目的 sk_strategy 和 sk_argument 字段，它们分别提供可索引运算符和比较值。尤其没有必要检查 sk_flags 以查看比较值是否为 NULL，因为 SP-GiST 核心代码会过滤掉此类条件。长度为 norderbys 的数组 orderbys 以相同的方式描述排序运算符（如果存在）。 reconstructedValue 是为父元组重建的值；如果为根级别或如果 inner_consistent 函数在父级别未提供值，则它为 (Datum) 0 。 traversalValue 是指向从 inner_consistent 在父索引元组上的先前调用传递下来的任何遍历数据的指针，或在根级别为 NULL。 traversalMemoryContext 是存储输出遍历值（如下所示）的内存上下文。 level 是当前内部元组的级别，根级别的起始值为零。如果此查询需要重建数据， returnData 为 true ；仅当 config 函数断言 canReturnData 时才出现这种情况。如果当前内部元组标记为“all-the-same”，则 allTheSame 为 true；在这种情况下，所有节点具有相同的标签（如果存在），因此所有节点匹配查询或没有节点匹配查询（请参阅 Section 69.4.3 ）。如果当前内部元组包含前缀，则 hasPrefix 为 true；如果是，则 prefixDatum 为其值。 nNodes 是内部元组中包含的子节点的数量， nodeLabels 是其标签值的数组，或如果节点没有标签，则为 NULL。

  • nNodes 必须设置为搜索需要访问的子节点的数量， nodeNumbers 必须设置为其索引的数组。如果运算符类跟踪级别，则将 levelAdds 设置为在下降到要访问的每个节点时所需的级别增量的数组。（通常，这些增量对所有节点都是相同的，但这不一定如此，因此使用数组。）如果需要值重建，则将 reconstructedValues 设置为为要访问的每个子节点重建的值的数组；否则，将 reconstructedValues 保留为 NULL。假定重建的值为类型 spgConfigOut . leafType 。（但是，由于核心系统除了可能复制它们之外不会对它们执行任何操作，因此它们具有与 leafType 相同的 typlen 和 typbyval 属性就足够了。）如果执行有序搜索，则将 distances 设置为根据 orderbys 数组的距离值数组（距离最小的节点将先处理）。否则将其保留为 NULL。如果需要将附加带外信息（“遍历值”）传递给树搜索的较低级别，请将 traversalValues 设置为适当遍历值的数组，每个要访问的子节点一个值；否则，将 traversalValues 保留为 NULL。请注意， inner_consistent 函数负责在当前内存上下文中分配 nodeNumbers 、 levelAdds 、 distances 、 reconstructedValues 和 traversalValues 数组的 palloc。但是，由 traversalValues 数组指向的任何输出遍历值都应分配在 traversalMemoryContext 中。每个遍历值都必须是单个 palloc 块。

    • leaf_consistent

  • 如果叶元组满足查询，则返回 true。

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

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

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

typedef struct spgLeafConsistentIn
{
    ScanKey     scankeys;       /* array of operators and comparison values */
    ScanKey     orderbys;       /* array of ordering operators and comparison
                                 * values */
    int         nkeys;          /* length of scankeys array */
    int         norderbys;      /* length of orderbys 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 */
    bool        recheckDistances; /* set true if distances must be rechecked */
    double     *distances;        /* associated distances */
} spgLeafConsistentOut;

  • 长度为 nkeys 的数组 scankeys 描述了索引搜索条件。这些条件与 AND 结合使用 — 只有满足所有条件的索引条目才能满足查询。（请注意， nkeys = 0 表示所有索引条目都满足查询。）一般来说，一致函数只关心每个数组条目的 sk_strategy 和 sk_argument 字段，它们分别提供可索引运算符和比较值。尤其没有必要检查 sk_flags 以查看比较值是否为 NULL，因为 SP-GiST 核心代码会过滤掉此类条件。长度为 norderbys 的数组 orderbys 以相同的方式描述排序运算符。 reconstructedValue 是为父元组重建的值；如果为根级别或如果 inner_consistent 函数在父级别未提供值，则它为 (Datum) 0 。 traversalValue 是指向从 inner_consistent 在父索引元组上的先前调用传递下来的任何遍历数据的指针，或在根级别为 NULL。 level 是当前叶元组的级别，根级别的起始值为零。如果此查询需要重建数据， returnData 为 true ；仅当 config 函数断言 canReturnData 时才出现这种情况。 leafDatum 是存储在当前叶元组中的 spgConfigOut . leafType 的键值。

  • 如果叶元组与查询匹配，则函数必须返回 true；如果不匹配，则返回 false。在 true 情况下，如果 returnData 为 true，则 leafValue 必须设置为值（类型为 spgConfigIn.attType），该值最初被提供为对此叶元组进行索引。此外，如果匹配不确定，则可以将 recheck 设置为 true，因此必须将操作符重新应用于实际的堆元组以验证匹配。如果执行有序搜索，则将 distances 设置为根据 orderbys 数组的距离值数组。否则将其保留为 NULL。如果返回的距离中至少有一个不精确，请将 recheckDistances 设置为 true。在这种情况下，执行器将在从堆中获取元组后计算精确距离，并在需要时重新对元组进行排序。

可选的用户定义方法为：

  • Datum compress(Datum in)

    • 将数据项转换为适合于物理存储在索引的叶元组中的格式。它接受类型为 spgConfigIn.attType 的值，并返回类型为 spgConfigOut.leafType 的值。输出值不得包含超链接 TOAST 指针。

    • 注意：compress 方法仅应用于要存储的值。一致方法接收未更改的查询 scankeys，而不使用 compress 进行转换。

  • options

    • 定义一组用户可见的参数来控制运算符类的行为。

    • 函数的 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() 宏从其他支持函数访问这些选项。

  • 由于 SP-GiST 中键的表示是灵活的，因此它可能取决于用户指定的参数。

通常在短期内存上下文中调用所有 SP-GiST 支持方法；即，CurrentMemoryContext 将在处理每个元组后重置。因此，不必非常担心释放分配给所有内容的大小。（config 方法是一个例外：它应该避免内存泄漏。但通常，config 方法无需执行任何操作，只需将常量分配给传递的参数结构即可。）

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