SP-GiST提供了一个高抽象层次的接口,要求访问方法开发者实现与一个给定数据类型相关的几种方法。SP-GiST核心负责高效的磁盘映射和搜索树结构。它也会处理并发和日志。
SP-GiST树的叶子元组包含与被索引列数据类型相同的值。在根层的叶子元组总是包含原始的被索引数据值,但是在较下层的叶子元组可能只含有一个压缩后的表示,例如一个后缀。在这种情况下,操作符类支持函数必须能够使用从内部元组计算出来的信息重构出原始的值,这些内部元组指的是在到达叶子层的过程中穿过的元组。
内部元组更加复杂,因为它们是搜索树的分支点。每一个内部元组包含一个或者更多个结点,结点表示一个具有相似叶子值的组。一个结点包含一个向下的链接,这个链接可以导向另一个较下层的内部元组,或者是由位于同一索引页面的叶子元组组成的一个短列表。每一个结点通常还有一个标签来描述它,例如,在一个 radix 树中结点标签可以是串值的下一个字符(或者,如果一种操作符类对于所有内部元组使用一个固定的节点集合,则它可以省略节点标签,见第 63.4.2 节)。可选地,一个内部元组可以有一个前缀值来描述它所有的成员。在一个 radix 树中前缀可以是所表示的串的公共前缀。前缀值并不一定非要是一个真正的前缀,它可以是操作符类需要的任何数据。例如,在一个四叉树中它可以存储用于划分四个象限的中心点。一个四叉树的内部元组则可以包含对应于围绕该中心点的象限的四个结点。
某些树算法要求当前元组所在层(或深度)的知识,因此SP-GiST核心为操作符类提供了机会以便在沿着树下降时管理层计数。当需要重组被表示的值时,这也可以为增量地重构过程提供支持,这还可以为沿着树下降时向下层传递附加数据(称为贯穿值)提供支持。
SP-GiST核心代码会关注空项。尽管SP-GiST索引确实可以存储被索引列中的空值,但这对索引操作符类代码是隐藏的:不会有空索引项或搜索条件会被传递给操作符类方法(我们假定SP-GiST操作符是严格的并且因此无法成功处理空值)。因此这里不会进一步讨论空值。
一个SP-GiST的索引操作符类必须提供五个用户定义的方法。所有五个方法都接受两个内部
参数,其中第一个是一个指针,它指向一个包含用于支持方法的值的 C 结构。而第二个参数也是一个指针,它指向将放置输出值的 C 结构。其中四个函数只返回void
,因为它们的所有结果都出现在输出结构中。但是leaf_consistent
会额外返回一个boolean
结果。这些方法不能修改它们的输入结构的任何域。在所有情况下,调用用户定义的方法之前输出结构都被初始化为零。
五个用户定义的方法是:
config
返回关于索引实现的静态信息,包括前缀的数据类型的OID以及结点标签数据类型。
这个函数的SQL声明必须看起来像这样:
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
第一个参数是一个指向spgConfigIn
C 结构的指针,包含该函数的输入数据。第二个参数是一个指向spgConfigOut
C 结构的指针,函数必须将结果数据填充在其中。
typedef struct spgConfigIn { Oid attType; /* 要被索引的数据类型 */ } spgConfigIn; typedef struct spgConfigOut { Oid prefixType; /* 内部元组前缀的数据类型 */ Oid labelType; /* 内部元组结点标签的数据类型 */ bool canReturnData; /* 操作符类能重构原始数据 */ bool longValuesOK; /* 操作符类能处理值 > 1 页 */ } spgConfigOut;
为了支持多态的索引操作符类,attType
要被传入;对于普通固定数据类型的操作符类,它将总是取相同的值,因此可以被忽略。
对于不使用前缀的操作符类,prefixType
可以被设置为VOIDOID
。同样,对于不使用结点标签的操作符类,labelType
可以被设置为VOIDOID
。如果操作符类能够重构出原来提供的被索引值,则canReturnData
应该被设置为真。只有当attType
是变长的并且操作符类能够将长值通过反复的添加后缀分段时,longValuesOK
才应当被设置为真(参见第 63.4.1 节)。
choose
为将一个新值插入到一个内部元组选择一种方法。
该函数的SQL声明必须看起来像这样:
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
第一个参数是一个指向spgChooseIn
C 结构的指针,包含该函数的输入数据。第二个参数是一个指向spgChooseOut
C 结构的指针,函数必须将结果数据填充在其中。
typedef struct spgChooseIn { Datum datum; /* 要被索引的原始数据 */ Datum leafDatum; /* 要被存储在叶子中的当前数据 */ int level; /* 当前层(从零计数) */ /* 来自当前内部元组的数据 */ bool allTheSame; /* tuple is marked all-the-same? */ bool hasPrefix; /* 元组有一个前缀? */ Datum prefixDatum; /* 如果有,前缀值 */ int nNodes; /* 内部元组中的结点数目 */ Datum *nodeLabels; /* 结点标签值(如果没有为 NULL) */ } spgChooseIn; typedef enum spgChooseResultType { spgMatchNode = 1, /* 下降到现有结点 */ spgAddNode, /* 向内部元组增加一个结点 */ spgSplitTuple /* 划分内部元组(修改它的前缀) */ } spgChooseResultType; typedef struct spgChooseOut { spgChooseResultType resultType; /* 动作代码,见上文 */ union { struct /* 用于spgMatchNode的结果 */ { int nodeN; /* 下降到这个结点(索引从 0 开始) */ int levelAdd; /* 这次匹配增加的层 */ Datum restDatum; /* 新叶数据 */ } matchNode; struct /* 用于spgAddNode的结果 */ { Datum nodeLabel; /* 新结点的标签 */ int nodeN; /* 在哪里插入它(索引从 0 开始) */ } addNode; struct /* 用于spgSplitTuple的结果 */ { /* 以一个子元组形成新的上层内部元组的信息*/ bool prefixHasPrefix; /* 元组能有前缀吗? */ Datum prefixPrefixDatum; /* 如果有,前缀值 */ int prefixNNodes; /* 节点数 */ Datum *prefixNodeLabels; /* 它们的标签 (没有标签为NULL) */ int childNodeN; /* 哪个节点获取子元组 */ /* 来自放有所有旧结点的新下层内部元组的信息 */ bool postfixHasPrefix; /* 元组能有前缀吗? */ Datum postfixPrefixDatum; /* 如果有,前缀值 */ } splitTuple; } result; } spgChooseOut;
datum
是将被插入到索引中的原始数据。leafDatum
最初和datum
一样,但是如果choose
或picksplit
改变了它,那么位于较低层的leafDatum
值就会有所改变。当插入搜索到达一个叶子页,leafDatum
的当前值就会被存储在新创建的叶子元组中。level
是当前内部元组的层次,根层是 0 。如果当前内部元组被标记为包含多个等价节点(见第 63.4.3 节),allTheSame
为真。如果当前内部元组有一个前缀,hasPrefix
为真,如果这样,prefixDatum
为前缀值。nNodes
是包含在内部元组中子结点的数量,并且nodeLabels
是这些子结点的标签值的数组,如果没有标签则为 NULL。
choose
函数能决定新值是匹配一个现有子结点,或是必须增加一个新的子节点,亦或是新值和元组的前缀不一致并且因此该内部元组必须被分裂来创建限制性更低的前缀。
如果新值匹配一个现有的子结点,将resultType
设置为spgMatchNode
。将nodeN
设置为该结点在结点数组中的索引(从零开始)。将levelAdd
设置为传到该结点导致的level
增加,或者在操作符类不使用层数时将它置为零。如果操作符类没有把数据从一层修改到下一层,将restDatum
设置为等于datum
,否则将它设置为在下一层用作leafDatum
的被修改后的值。
如果必须增加一个新的子结点,将resultType
设置为spgAddNode
。将nodeLabel
设置为在新结点中使用的标签,并将nodeN
设置为插入该结点的位置在结点数组中的索引(从零开始)。在结点被增加之后,choose
函数将被再次调用并使用修改后的内部元组,那时将会导致一个spgMatchNode
结果。
如果新值和元组的前缀不一致,将resultType
设置为spgSplitTuple
。
这个动作将所有现有的结点移动到一个新的下层内部元组,并且将现有的内部元组用一个新元组替换,
该元组有个下行链路指向那个新的下层内部元组。将prefixHasPrefix
设置为指示新的上层元组是否具有一个前缀,并且在如果有前缀时设置
prefixPrefixDatum
为前缀值。
这个新的前缀值必须比原来的值要足够宽松以便能够接受将被索引的新值。
将prefixNNodes
设置为新元组中所需的节点数,
并将prefixNodeLabels
设置为保存其标签的palloc'd数组,
或者如果不需要节点标签,则将其设置为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; /* 叶子元组的数量 */ Datum *datums; /* 它们的数据(长度为 nTuples 的数组) */ int level; /* 当前层次(从零开始计) */ } spgPickSplitIn; typedef struct spgPickSplitOut { bool hasPrefix; /* 新内部元组应该有一个前缀吗? */ Datum prefixDatum; /* 如果有,前缀值 */ int nNodes; /* 新内部元组的结点数 */ Datum *nodeLabels; /* 它们的标签(没有标签则为NULL) */ int *mapTuplesToNodes; /* 每一个叶子元组的结点索引 */ Datum *leafTupleDatums; /* 存储在每一个新叶子元组中的数据 */ } spgPickSplitOut;
nTuples
是所提供的叶子元组的数量。
datums
是它们的数据值的数组。
level
是所有叶子元组共有的当前层次,它将成为新内部元组的层次。
将hasPrefix
设置为指示新内部元组是否应该有前缀,并且如果有前缀则将prefixDatum
设置成前缀值。将nNodes
设置为新内部元组将包含的结点数目,并且将nodeLabels
设置为它们的标签值的数组或者 NULL(如果结点不要求标签)。将mapTuplesToNodes
设置为一个数组,该数组告诉每一个叶子元组应该被赋予的结点的索引(从零开始)。将leafTupleDatums
设置为由将要被存储在新叶子元组中的值构成的一个数组(如果操作符类不将数据从一层修改到下一层,这些值将和输入的datums
相同)。注意picksplit
函数负责为nodeLabels
、mapTuplesToNodes
和leafTupleDatums
数组进行 palloc。
如果提供了多于一个叶子元组,picksplit
被寄望于将它们分类到多余一个结点中;否则不可能将叶子元组划分到多个页面,这也是这个操作的终极目的。因此,如果picksplit
函数结束时把所有叶子元组放在同一个结点中,核心SP-GiST代码将覆盖该决定,并且生成一个内部元组,将叶子元组随机分配到多个不同标签的结点。这样一个元组被标记为allTheSame
来表示发生了这种情况。choose
和inner_consistent
函数必须对这样的内部元组采取合适的处理。详见第 63.4.3 节。
picksplit
只能在一种情况下被应用在单独一个叶子元组上,这种情况是config
函数将longValuesOK
设置为真并且提供了一个长于一页的输入。在这种情况中,该操作的要点是剥离一个前缀并且产生一个新的、较短的叶子数据值。这种调用将被重复直到产生一个足够短能够放入到一页的叶子数据。详见第 63.4.1 节。
inner_consistent
在树搜索过程中返回一组要追求的结点(分支)。
该函数的SQL声明必须看起来像这样:
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
第一个参数是一个指向spgInnerConsistentIn
C 结构的指针,包含该函数的输入数据。第二个参数是一个指向spgInnerConsistentOut
C 结构的指针,函数必须将结果数据填充在其中。
typedef struct spgInnerConsistentIn { ScanKey scankeys; /* 操作符和比较值的数组 */ int nkeys; /* 数组的长度 */ Datum reconstructedValue; /* 在父结点中的重构值 */ void *traversalValue; /* 操作符类相关的贯穿值 */ MemoryContext traversalMemoryContext; /* 把新的贯穿值放在这里 */ int level; /* 当前层次(从零开始计) */ bool returnData; /* 是否必须返回原始数据? */ /* 来自当前内元组的数据 */ bool allTheSame; /* 元组被标记为完全相同? */ bool hasPrefix; /* 元组有前缀? */ Datum prefixDatum; /* 如果有,前缀值 */ int nNodes; /* 内元组中的结点数 */ Datum *nodeLabels; /* 结点标签值(没有就是 NULL) */ } spgInnerConsistentIn; typedef struct spgInnerConsistentOut { int nNodes; /* 要被访问的子结点数 */ int *nodeNumbers; /* 它们在结点数组中的索引 */ int *levelAdds; /* 为每个子结点要增加的层数 */ Datum *reconstructedValues; /* 相关的重构值 */ void **traversalValues; /* 操作符类相关的贯穿值 */ } spgInnerConsistentOut;
长度为nkeys
的数组scankeys
描述了索引搜索条件。这些条件用 AND 组合 — 只对满足所有条件的索引项感兴趣(注意,nkeys
= 0 表示所有索引项满足该查询)。通常一致函数只关心每个数组项的sk_strategy
和sk_argument
,它们分别给出了可索引操作符和比较值。特别要说明的是,没有必要去检查sk_flags
来看比较值是否为 NULL,因为 SP-GiST 的核心代码会过滤这样的条件。reconstructedValue
是用于父元组的重构值,在根层时或者如果inner_consistent
函数没有在父层提供一个值时,它为(Datum) 0
。traversalValue
是任意贯穿数据的指针,该数据由父索引元组上的上一次inner_consistent
调用传递下来,在根层上这个指针为 NULL。traversalMemoryContext
是用于存放输出的贯穿值(见下文)的内存上下文。level
是当前内元组层次,根层是 0。如果这个查询要求重构的数据,returnData
是true
。如果config
断言canReturnData
,returnData
只会是true
。如果当前的内元组被标记为“完全一样”,那么allTheSame
为真。在这种情况下,所有的结点都具有相同的标签(如果有),而且它们要么全部匹配该查询,要么一个都不匹配查询(见第 63.4.3 节)。如果当前内元组包含一个前缀,则hasPrefix
为真。如果这样,prefixDatum
就是该前缀的值。nNodes
是包含在内元组中的子结点的数量,nodeLabels
是它们的标签值的数组。当然如果结点没有标签,这个数组就为 NULL。
nNodes
必须被设置为搜索需要访问的子结点数,并且nodeNumbers
必须被设置为子结点索引的数组。如果操作符类跟踪层次,把levelAdds
设置成一个数组,其中说明了在下降到要被访问的每一个结点时需要增加的层数(通常这些增量对于所有结点都是相同的,但是并不一定如此,所以需要使用一个数组)。如果需要值重构,将reconstructedValues
设置成要被访问的每一个子结点的重构值数组。否则让reconstructedValues
为 NULL。如果想要把额外的带外信息(“贯穿值”)向下传递给树搜索的较低层,可以把traversalValues
设置成合适的贯穿值的数组,其中每一个元素用于一个要被访问的子节点。如果不需要传递额外的带外信息,则把traversalValues
设置为 NULL。注意,inner_consistent
函数负责在当前内存上下文中分配nodeNumbers
、levelAdds
、reconstructedValues
和traversalValues
数组。不过,任何由traversalValues
数组指向的输出贯穿值应该在traversalMemoryContext
中分配。每一个贯穿值必须是一个单独分配的块(chunk)。
leaf_consistent
如果一个叶子元组满足一个查询则返回真。
该函数的SQL声明必须看起来像这样:
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
第一个参数是一个指向spgLeafConsistentIn
C 结构的指针,包含该函数的输入数据。第二个参数是一个指向spgLeafConsistentOut
C 结构的指针,函数必须将结果数据填充在其中。
typedef struct spgLeafConsistentIn { ScanKey scankeys; /* 操作符和比较值的数组 */ int nkeys; /* 数组的长度 */ Datum reconstructedValue; /* 在父结点中的重构值 */ void *traversalValue; /* 操作符类相关的贯穿值 */ int level; /* 当前层次(从零开始计) */ bool returnData; /* 是否必须返回原始数据? */ Datum leafDatum; /* 叶子元组中的数据 */ } spgLeafConsistentIn; typedef struct spgLeafConsistentOut { Datum leafValue; /* 重构的原始数据,如果有 */ bool recheck; /* 如果操作符必须被重新检查则设为真 */ } spgLeafConsistentOut;
长度为nkeys
的数组scankeys
描述了索引搜索条件。这些条件用 AND 组合在一起 — 只有满足所有条件的索引项才满足该查询(注意nkeys
= 0 表示所有的索引项都满足查询)。通常 consistent 函数值关注每一个数组项的sk_strategy
和sk_argument
域,它们分别给出了可索引操作符和比较值。特别是它无需检查sk_flags
来检查比较值是否为 NULL,因为 SP-GiST 核心代码将过滤掉这类条件。reconstructedValue
是为父元组重构的值,在根层或者当inner_consistent
没有提供父层上的值时,它是(Datum) 0
。traversalValue
是任意贯穿数据的指针,该数据由父索引元组上的上一次inner_consistent
调用传递下来,在根层上这个指针为 NULL。level
是当前的叶子元组所在的层次,根层为零。如果这个查询要求重构的数据,则returnData
为true
。只有在config
函数主张了canReturnData
时才会如此。leafDatum
是存储在当前叶子元组中的键值。
如果叶子元组匹配查询,则该函数必须返回true
,否则返回false
。在返回true
的情况中,如果returnData
为true
,则leafValue
必须被设置为最初为构建这个叶子元组提供的值。还有,如果匹配是不确定的并且操作符必须被重新应用在实际堆元组上验证匹配,则recheck
会被设置为true
。
所有的 SP-GiST 支持方法通常都在一个短期存在的内存上下文中被调用,即在处理完每一个元组后CurrentMemoryContext
将被重置。因此并不需要操心 pfree 你 palloc 的任何东西(config
方法是一个特例:它应该避免泄漏内存。但是通常config
方法只需要为传出的参数结构赋常数值)。
如果被索引的列是一种可排序的数据类型,索引的排序规则将被使用标准的PG_GET_COLLATION()
机制传递给所有的支持方法。