56.2. 擴展性 · PostgreSQL 中文文檔 9.3

# 56.2\. 擴展性 SP-GiST提供了一個高度抽象的接口,只需要訪問方法開發人員實現特定于給定數據類型的方法。SP-GiST核心負責高效的磁盤映射和搜索樹結構。它還負責考慮并發性和日志記錄。 SP-GiST樹的葉元組包含和被索引列相同數據類型的值。在根層級的葉元組總是包含原來的索引數據值,但是低層級的葉元組可能只包含一個壓縮表示,如一個后綴。在這種情況下,操作符類支持函數必須能夠，通過利用從到達葉元組所經過的內部元組中收集到的信息，重建原始值。內部元組更為復雜,因為它們是搜索樹中的分支點。每個內部元組包含由一個或多個_節點_組成的集合,表示一組類似的葉元組值。一個節點包含一個鏈接指向另一個低級內部元組,或指向一個短的葉元組的列表，這些葉元組存儲在相同的索引頁面中。每個節點都有一個用來描述它的_標簽_。例如,在一個基數樹中節點標簽可以是字符串值的下一個字符。可選地,一個內部元組可以有一個_前綴_值,描述了它的所有成員。在基數樹中這可能是其所代表的字符串的共同前綴。前綴值不一定真的是一個前綴,可以是操作符類所要求的任何數據。例如,在四叉樹中它可以存儲可度量四個象限的中心點，四叉樹的內部元組也就會相應的存儲四個節點，每個代表了這個中心點周圍的一個象限。一些樹算法需要知道當前元組的層級(或深度),所以SP-GiST核心為操作符類提供了在向下訪問樹時管理層級計數的能力。并且也支持在需要時遞增地重建所代表的值。 > **Note:** SP-GiST核心代碼考慮了null條目。盡管SP-GiST索引為被索引列中的null值存儲了的條目,但這對索引操作符類代碼是隱藏的:null索引條目或搜索條件不會被傳遞給操作符類的方法。 (假定SP-GiST操作符是嚴格的,因此不能在null值上匹配成功。)因此后面也就不會再討論null值的問題了。一個用于SP-GiST的索引操作符類必須提供五個用戶定義的方法。所有五個方法按照約定接受兩個`internal`參數，第一個參數是一個指向包含了支持方法的輸入值的C結構體的指針，而第二個參數是一個指向放置輸出值的C結構體的指針。其中四個方法只是返回void,因為它們所有的結果都出現在輸出結構體里;但`leaf_consistent`返回一個布爾結果。這些方法不能修改輸入結構體中的任何域。在所有情況下，在調用用戶定義的方法之前，輸出結構體的內容被用初始化為0。五個用戶定義的方法如下： `config` 返回關于索引實現的靜態信息,包括前綴的數據類型OID和節點標簽的數據類型。函數的SQL聲明必須看起來像這樣: ``` CREATE FUNCTION my_config(internal, internal) RETURNS void ... ``` 第一個參數是一個指向C結構體`spgConfigIn`的指針,包含函數的輸入數據。第二個參數是一個指向C結構體`spgConfigOut`的指針,該函數必須填充結果數據到里面。 ``` 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 56.3.1](#calibre_link-552))。 `choose` 選擇一種方法將一個新值插入到一個內部元組。函數的SQL聲明必須看起來像這樣: ``` CREATE FUNCTION my_choose(internal, internal) RETURNS void ... ``` 第一個參數是一個指向C結構體`spgChooseIn`的指針,包含函數的輸入數據。第二個參數是一個指向C結構體`spgChooseOut`的指針,該函數必須填充結果數據到里面。 ``` 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 inner tuple with one node */ bool prefixHasPrefix; /* tuple should have a prefix? */ Datum prefixPrefixDatum; /* if so, its value */ Datum nodeLabel; /* node's label */ /* 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`值就是存儲到新生成的葉元組中的值。 `level`是當前內部元組的層級，從0，也就是根的層級，開始計數。如果當前內部元組包含多個等價節點，`allTheSame`為true(參見[Section 56.3.3](#calibre_link-553))。如果當前內部元組包含前綴，`hasPrefix`為true。此時，`prefixDatum`是前綴值。 `nNodes`是內部元組中包含子節點的數量，`nodeLabels`是它們的標簽值的數組,或者是NULL如果沒有標簽的話。 `choose`函數可以確定新值匹配一個現有的子節點,或者必須添加一個新的子節點,或者新值與元組前綴不一致,所以內部元組必須分裂開以創建一個限制較少的前綴。如果新值匹配的一個現有的子節點,把`resultType`設置為`spgMatchNode`。把`nodeN`設置為那個索引節點在節點數組中的索引(從0開始)。把`levelAdd`設置為，由下降到那個節點導致的`level`增量；或者為0如果操作符類不使用層級。把`restDatum`設置為和`datum`相等的值，如果操作符類從一個層級到下一個層級不會修改數據值；否則將其設置為修改后的值，它在下一個層級被用作`leafDatum`。如果必須添加一個新的子節點,把`resultType`設置為`spgAddNode`。設置`nodeLabel`為新節點的標簽,并設置`nodeN`為插入位置在節點數組中的索引(從0開始)。添加了節點后,`choose`函數將再次與被修改的內部元組一起被調用，那次調用應該導致一個`spgMatchNode`結果。如果新值與元組前綴是不一致的,把`resultType`設置為`spgSplitTuple`。這一動作把所有現有的節點移動到一個新的低層級的內部元組,并把現有內部元組替換為一個只有一個鏈接到新的低層級內部元組的單個節點的元組。設定`prefixHasPrefix`表明是否新的較高的元組應該有一個前綴,如果是的話，設置`prefixPrefixDatum`為前綴值。這個新的前綴值必須比原來的限制足夠小以接受新的被索引值,而且應當不超過原前綴的長度。設置`nodeLabel`為指向新的低層級內部元組的節點的標簽值。設定`postfixHasPrefix`表明是否新的較低的元組應該有一個前綴,如果是的話，設置`postfixPrefixDatum`為前綴值。這兩個前綴和額外的標簽的組合必須與原始前綴具有相同的含義,因為沒有機會改變被移動到新的低層級元組中的節點標簽，也不能改變任何子索引條目。節點被分裂后,`choose`會被再次調用，針對替換的內部元組。那個調用通常會導致`spgAddNode`結果,因為分裂步驟添加的節點標簽可能不會匹配新值；所以在那之后,還會有第三次調用,最后的調用返回`spgMatchNode`,允許插入操作下去到葉層級。 `picksplit` 決定如何在一組葉元組之上創建一個新的內部元組。函數的SQL聲明必須看起來像這樣: ``` CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ... ``` 第一個參數是一個指向C結構體`spgPickSplitIn`的指針,包含函數的輸入數據。第二個參數是一個指向C結構體`spgPickSplitOut`的指針,該函數必須填充結果數據到里面。 ``` 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`是數據值的數組。 `level`是所有的葉元組共享的當前層級,這將成為新的內部元組的層級。 `hasPrefix`表明是否新的內部元組應該有一個前綴,如果是的話設置prefixDatum前綴值。 `nNodes`表明新內部元組將包含的節點數量,并設置`nodeLabels`為它們的標簽值的數組。 (如果節點不需要標簽,設置`nodeLabels`為NULL;有關詳細信息,請參見[Section 56.3.2](#calibre_link-554)。) 設置`mapTuplesToNodes`為各個葉元組應該被分配的節點的索引(從0開始)的數組。設置`leafTupleDatums`為存儲在新的葉元組的值的數組(如果操作符類從一個層級到下一個層級不修改數據,它們將和輸入數據相同)。注意,`picksplit`函數負責分配(palloc) `nodeLabels`, `mapTuplesToNodes`和`leafTupleDatums`數組。如果提供了不止一個葉元組,預計`picksplit`函數會把它們分類到多個節點,否則不可能把葉元組分裂到多個頁面,這是這個操作的最終目的。因此,如果`picksplit`函數最終把所有葉元組放在同一節點,核心SP-GiST代碼將覆蓋這一決定并生成一個內部元組，這些葉元組會被隨機分配到這個內部元組的幾個有等價標簽(identically-labeled)的節點上。這樣的元組被設置了`allTheSame`標志，以表示發生這樣的事情了。 `choose`和`inner_consistent`函數必須小心對待這樣的內部元組。有關更多信息,請參見[Section 56.3.3](#calibre_link-553)。只有當`config`函數設置`longValuesOK`為true,并且提供了大于一頁面的輸入值時， `picksplit`才可以被應用到單個葉元組。在這種情況下操作的要點是剝離前綴并產生一個新的、更短的葉數據值。這個調用將被反復執行，直到葉數據已經短到可以放到一個被生成的頁面上。有關更多信息,請參見[Section 56.3.1](#calibre_link-552)。 `inner_consistent` 返回樹搜索需要繼續訪問的節點集合(分支)。函數的SQL聲明必須看起來像這樣: ``` CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ... ``` 第一個參數是一個指向C結構體`spgInnerConsistentIn`的指針,包含函數的輸入數據。第二個參數是一個指向C結構體`spgInnerConsistentOut`的指針,該函數必須填充結果數據到里面。 ``` typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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 */ } spgInnerConsistentOut; ``` 長度為`nkeys`的`scankeys`數組描述了索引搜索條件。這些條件以"AND"聯接在一起，即，只有滿足所有條件的索引條目才能匹配這個查詢。 (注意,如果`nkeys`為0意味著所有索引條目都滿足查詢。) 通常這個函數只關心每個數組項目的`sk_strategy`和`sk_argument`字段,它們分別給出了可索引的操作符和比較值。特別是沒有必要看`sk_flags`以檢查比較值是否為NULL,因為SP-GiST核心代碼會過濾掉這樣的條件。 `reconstructedValue`是為父元組重建的值；如果在根層級或`inner_consistent`函數在父層級沒有提供一個值，它會是0。 `level`是當前內部元組的層級，從0，也就是根的層級，開始計數。 `returnData`為`true`，如果這個查詢需要重建數據的話；只有`config`函數聲明了`canReturnData`時，才有可能是這樣。 `allTheSame`是true，如果當前內部元組標記"all-the-same";在這種情況下的所有節點具有相同的標簽(如果有的話),所以要么全部要么沒有一個匹配這個查詢(參見[Section 56.3.3](#calibre_link-553))。如果當前內部元組包含前綴，`hasPrefix`為true。此時，`prefixDatum`是前綴值。 `nNodes`是內部元組中包含子節點的數量，`nodeLabels`是它們的標簽值的數組,或者是NULL如果節點沒有標簽。 `nNodes`必須被設置為搜索需要訪問的子節點的數量, 并且`nodeNumbers`必須被設置的它們的索引的數組。如果操作符類跟蹤層級,設置`levelAdds`為向下訪問到每個節點時層級增量的數組。 (通常這些增量對所有節點是相同的,但這并不一定是這樣,所以使用一個數組)。如果需要重建數據值,設置`reconstructedValues`為每個要訪問的子節點的重建值的數組;否則,保持`reconstructedValues`為NULL。注意,`inner_consistent`函數負責分配(palloc) `nodeNumbers`, `levelAdds`和`reconstructedValues`數組。 `leaf_consistent` 如果葉元組滿足查詢返回true。函數的SQL聲明必須看起來像這樣: ``` CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ... ``` 第一個參數是一個指向C結構體`spgLeafConsistentIn`的指針,包含函數的輸入數據。第二個參數是一個指向C結構體`spgLeafConsistentOut`的指針,該函數必須填充結果數據到里面。 ``` typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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`是父元組重建的值；如果在根層級或`inner_consistent`函數在父層級沒有提供一個值，它會是0。 `level`是當前葉元組的層級，從0，也就是根的層級，開始計數。 `returnData`為`true`，如果這個查詢需要重建數據的話；只有`config`函數聲明了`canReturnData`時，才有可能是這樣。 `leafDatum`是存儲在當前葉元組中的鍵值。如果這個葉元組匹配查詢，這個函數必須返回`true`,否則返回`false`。在`true`的情況下,如果`returnData`是`true`，那么`leafValue`必須被設置為最初提供的這個葉元組索引的值。如果匹配是不確定的,`recheck`也被設置為`true`，因此操作符必須被重新應用到實際的堆元組上以驗證匹配。所有SP-GiST支持方法通常在一個短期的內存上下文中被調用;也就是說, 在處理每一個元組后`CurrentMemoryContext`將被重置。因此不太需要擔心地去pfree你palloc出來的所有東西。（`config`方法是一個例外:它應該盡量避免內存泄露。但通常`config`方法除了把常數賦值到傳遞過來的結構體中外，其它什么也不需要做。）如果被索引列是一個collatable數據類型,該索引排序規則將被傳遞給所有的支持方法,使用標準的`PG_GET_COLLATION()` 機制。