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

# 55.2\. 擴展性傳統上，實現一種新的索引訪問方法意味著大量的艱苦工作。必須理解數據庫的內部工作機制，比如鎖的機制和預寫日志。 GiST接口有一個高層的抽像，只要求訪問方法的實現者實現被訪問的數據類型的語意。 GiST層本身會處理并發，日志和搜索樹結構等任務。不要把這個擴展性和其它標準搜索樹的擴展性混淆在一起，比如它們所能處理的數據等方面。比如，PostgreSQL支持可擴展的 B-trees和哈希索引。這就意味著可以用PostgreSQL在任意你需要的數據類型上建立 B-tree或哈希。但是 B-trees 只支持范圍謂詞(`<`、`=`、`>`),而哈希僅支持相等查詢。所以，如果你用PostgreSQL B-tree 索引了一個圖像集，那么你就只能發出類似 "圖像 x 和圖像 y 相等嗎"、"圖像 x 是不是比圖像 y 小"、"圖像 x 是否大于圖像 y"這樣的查詢。依賴于你在這個環境下定義的"等于"、"小于"、"大于"的含義，上面這些查詢可能有意義。但是，使用一個基于GiST的索引，你可以創建一些方法來提出和領域相關的問題，比如"找出所有馬的圖像"或者"找出所有曝光過頭的圖像"。要讓一種GiST訪問方法跑起來只要實現幾個用戶定義方法，這些方法定義了樹里面的鍵字的行為。當然，為了支持那些怪異的查詢，這些方法也會相當怪異，但是對于所有標準的查詢(B-tree，R-tree 等)，他們是相當直接的。簡單說，GiST組合了擴展性和通用性，以及代碼復用和一個干凈的界面。 GiST用的索引操作符類必須提供7個方法，第8個方法是可選的。索引的正確性通過正確的實現`same`, `consistent`和`union`方法來確保,而索引的效率(大小和速度)依賴于`penalty`和`picksplit`。剩下的2個方法是`compress`和`decompress`，它們允許索引持有的內部數據和它索引的對象數據的類型不同。葉子節點的類型必須和被索引數據相同，而其他節點可以是任意C結構(但是，這里仍然必須遵守PostgreSQL中數據類型的規則，對可變大小數據請參考`varlena`)。如果樹的內部數據類型在SQL級別存在，可以在`CREATE OPERATOR CLASS`命令中使用`STORAGE`選項。可選的第8個方法是`distance`,如果希望操作符類支持排序的掃描（最鄰近搜索），就需要提供這個方法。 `consistent` 給定一個索引項`p`和查詢值`q`，這個函數決定是否索引項和查詢"一致"；也即是，對任何該索引項代表的行，謂詞 "`_indexed_column_``_indexable_operator_` `q`"是否可能為真？對葉子索引項這等價于測試索引條件，對內部樹節點它指示是否有必要掃描該節點代表的索引子樹。當結果為`true`，必須還要返回`recheck`標志位。這指示了謂詞是精確為真還是只是可能為真。如果`recheck` = `false`，索引已經精確地測試了謂詞條件，如果`recheck`= `true`，相應的行僅僅是一個候選匹配。這種情況下，系統還將自動對實際的行值進行評價`_indexable_operator_`以檢查是否真的匹配。這一規則允許GiST同時支持無損索引和有損索引。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal) RETURNS bool AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_consistent(PG_FUNCTION_ARGS); 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; /* * 根據strategy,key和query決定返回值。 * * 使用GIST_LEAF(entry)可以感知函數在索引樹的什么位置被調用，比如這在支持=操作符時很方便 * （可以在非葉子節點檢查非空的union()和在葉子節點檢測等價性)。 */ *recheck = true; /* 如果是精確檢查則為假 */ PG_RETURN_BOOL(retval); } ``` 這里`key`是索引中的一個元素，而`query`是要在索引中查找的值。 `StrategyNumber`參數指示要應用操作符類中的哪個操作符，它必須是`CREATE OPERATOR CLASS`命令指定的操作符編號之一。依賴于在操作符類中包含的操作符，`query`的數據類型可能和操作符不同，但是上面的骨架代碼假設不是這種情況。 `union` 這個方法用于合并樹中的信息。輸入一個項目的集合，這個函數生成一個代表所有給定項目的新的索引項目。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_union(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_union(PG_FUNCTION_ARGS); 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()`分配的內存的指針。不能簡單地直接返回輸入的東西。 `compress` 把數據項轉換為適合在索引頁中存儲的格式。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_compress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_compress(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* 把entry->key替換為壓縮的版本 */ compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); /* 從entry->key填充*compressed_data */ retval = palloc(sizeof(GISTENTRY)); gistentryinit(*retval, PointerGetDatum(compressed_data), entry->rel, entry->page, entry->offset, FALSE); } else { /* 通常不需要對非葉子節點做任何處理 */ retval = entry; } PG_RETURN_POINTER(retval); } ``` 當然，為了壓縮葉子節點，你需要把`_compressed_data_type_`適配到特定的數據類型。根據你的需求，可能還需要關心如何壓縮`NULL`值，例如存儲為`(Datum) 0`，就像`gist_circle_compress`那樣。 `decompress` 與`compress`函數正好相反。把數據項的索引表現轉換為可以被數據庫處理的格式。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_decompress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_decompress(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_decompress); Datum my_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); } ``` 上面的骨架代碼適合不需要解壓縮的場合。 `penalty` 返回插入新項目到特定分支的"代價"值。項目將會被插入到樹中`penalty`最小的路徑。 `penalty`的返回值應該是非負數。如果返回了負數將會被當作0處理。這個函數的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模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_penalty(PG_FUNCTION_ARGS); 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`函數對索引的性能非常重要。在插入階段，它可以用來決定把新增加項目插入到哪個分支。在查詢階段，越平衡的索引，檢索速度越快。 `picksplit` 如果需要分裂一個索引頁面的時候，這個函數決定頁面中哪些項目保存在舊頁面里，哪些移動到新頁面里。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_picksplit(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(my_picksplit); Datum my_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); OffsetNumber maxoff = entryvec->n - 1; GISTENTRY *ent = entryvec->vector; GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); 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; /* 初始化項目數組 */ 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); /* * 選擇放置索引項目的位置，并相應地更新unionL和unionR。 * 追加項目到v_spl_left或者v_spl_right，并注意處理計數器。 */ 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 { /* * 右邊做相同處理 */ } } v->spl_ldatum = DataTypeGetDatum(unionL); v->spl_rdatum = DataTypeGetDatum(unionR); PG_RETURN_POINTER(v); } ``` 像`penalty`一樣，`picksplit`函數對索引的性能也非常重要，設計合適的`penalty`和`picksplit`函數直接關系到實現良好性能的GiST索引。 `same` 2個索引項目等價時為真，否則為假。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_same(internal, internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_same(PG_FUNCTION_ARGS); 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`函數并不是單純地返回布爾值，而是將標志位存儲到由第3個參數指向的位置。 `distance` 給定一個索引項目`p`和查詢值`q`，這個函數決定這2者之間的"距離"。如果操作符類包含任何排序的操作符，必須要提供這個函數。通過先返回最小"距離"值的索引項目，可以實現使用了排序操作符的查詢，因此結果必須和操作符的語義一致。對一個葉子索引項目，結果只是到索引項目的距離；對內部項目，結果必須是任何子節點項目的最小距離。這個函數的SQL聲明必須按照如下方式。 ``` CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid) RETURNS float8 AS 'MODULE_PATHNAME' LANGUAGE C STRICT; ``` C模塊中的對應代碼可以參考下面的骨架代碼。 ``` Datum my_distance(PG_FUNCTION_ARGS); 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); */ data_type *key = DatumGetDataType(entry->key); double retval; /* * determine return value as a function of strategy, key and query. */ PG_RETURN_FLOAT8(retval); } ``` `distance`函數的參數，除了recheck標志位，其他和`consistent`函數相同。一個葉子節點的距離值必須是精確的，因為一旦返回了元組就沒有辦法再進行排序了。對內部節點允許一定程度的近似，只要不大于任何一個子節點的實際距離。比如，在地理應用中到矩形邊界的距離就足夠了。結果值可以是任何有限的`float8`類型值。（無窮和負無窮用于在內部作為空等情況使用，因此，不建議`distance`返回這些值。）所有的GiST支持方法通常在短周期內存上下文中被調用，也就是說，在每個元組被處理后`CurrentMemoryContext`都會被重置。因此不太需要擔心pfree被palloc出來的所有東西。然而，有些情況下，需要支持方法在多次調用間緩存數據。為了實現這個目的，需要在`fcinfo->flinfo->fn_mcxt`中分配長生命周期的數據，并且在`fcinfo->flinfo->fn_extra`中保存其指針。這樣的數據在索引操作(比如:單個的GiST索引掃描，索引創建或索引元組插入)完成后仍然有效。在覆蓋`fn_extra`的值前要小心的pfree掉先前的值，否則在操作期間內存泄漏會越積越多。