傳統上,實作新的索引存取方法意味著許多困難的工作。有必要了解資料庫的內部運作,例如鎖定管理員和預寫式記錄。 GiST 介面具有高度的抽象化,只要求存取方法實作者實作正在存取的資料類型的語意。 GiST 層本身負責並行性、記錄和搜尋樹狀結構。
此可擴充性不應與其他標準搜尋樹在可處理資料方面的可擴充性混淆。例如,PostgreSQL 支援可擴充 B 樹和雜湊索引。這表示您可以使用 PostgreSQL 建立 B 樹或雜湊,以涵蓋任何您想要的資料類型。但是,B 樹僅支援範圍謂詞 (<
、=
、>
),而雜湊索引僅支援等式查詢。
因此,如果您使用 PostgreSQL B 樹為影像集合建立索引,您只能發出類似於 “影像 x 是否等於影像 y”、“影像 x 是否小於影像 y” 和 “影像 x 是否大於影像 y” 的查詢。根據您在此脈絡中定義“等於”、“小於”和“大於”的方式,這可能會很有用。然而,透過使用基於 GiST 的索引,您可以建立提出特定領域問題的方法,例如 “找出所有馬匹影像” 或 “找出所有曝光過度的影像”。
要讓 GiST 存取方法啟動並執行,您只需要實作數個使用者定義的方法,這些方法定義樹中金鑰的行為。當然,這些方法必須相當精巧才能支援精巧的查詢,但對於所有標準查詢(B 樹、R 樹等),它們相對簡單。簡而言之,GiST 結合了可擴充性、通用性、程式碼重複使用和簡潔的介面。
索引操作員類別對於 GiST 必須提供五種方法,以及六種選用方法。正確的索引是由 same
、consistent
和 union
方法的正確實作確保,而索引的效率(大小和速度)則會取決於 penalty
和 picksplit
方法。兩種選用方法為 compress
和 decompress
,它們允許索引擁有與其所索引資料不同的內部樹狀資料。葉節點必須是索引資料類型,而其他樹狀節點可以是任何 C 結構(但您仍必須遵循 PostgreSQL 資料類型規則,請參閱有關變動大小資料的 varlena
)。如果樹狀結構的內部資料類型存在於 SQL 層級,則可以使用 CREATE OPERATOR CLASS
指令的 STORAGE
選項。第八個選用方法為 distance
,如果操作員類別希望支援已排序的掃描(最近鄰搜尋),則需要此方法。第九個選用方法 fetch
是在操作員類別希望支援僅索引掃描時需要,但 compress
方法被省略時除外。第十個選用方法 options
是在操作員類別有使用者指定的參數時需要。第十一個選用方法 sortsupport
用於加速建立 GiST 索引。
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 模組中的配對程式碼可以遵循此架構
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; /* * determine return value as a function of strategy, key and query. * * Use GIST_LEAF(entry) to know where you're called in the index tree, * which comes handy when supporting the = operator for example (you could * check for non empty union() in non-leaf nodes and equality in leaf * nodes). */ *recheck = true; /* or false if check is exact */ PG_RETURN_BOOL(retval); }
在此,key
是索引中的元素,query
是在索引中查詢的值。StrategyNumber
參數表示套用運算子類別的哪個運算子,它與 CREATE OPERATOR CLASS
命令中的其中一個運算子編號相符。
根據您在類別中包含哪些運算子,query
的資料類型可能會隨著運算子而有所不同,因為它會是運算子右側的任何類型,這可能與左側出現的索引資料類型不同。(上述程式碼範例假設只有一個類型是可能的;如果不是,擷取 query
參數值將必須取決於運算子。)建議 consistent
函式的 SQL 宣告使用 opclass 的索引資料類型作為 query
參數,即使實際類型可能會根據運算子而有所不同。
聯集
此方法會合併樹中的資訊。給定一組項目,此函式會產生一個新的索引項目,代表所有給定的項目。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_union(internal, internal) RETURNS storage_type AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
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()
ed 記憶體的指標。即使沒有類型變更,您也不能只傳回輸入值。
如上所示,union
函式的第一個 internal
參數實際上是一個 GistEntryVector
指標。第二個參數是指向整數變數的指標,可以忽略。(過去要求 union
函式將其結果值的大小儲存在該變數中,但現在不再需要了。)
壓縮
將資料項目轉換成適合在索引頁面中實體儲存的格式。如果省略 compress
方法,資料項目會在索引中儲存而不修改。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_compress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* replace entry->key with a compressed version */ compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); /* fill *compressed_data from entry->key ... */ retval = palloc(sizeof(GISTENTRY)); gistentryinit(*retval, PointerGetDatum(compressed_data), entry->rel, entry->page, entry->offset, FALSE); } else { /* typically we needn't do anything with non-leaf entries */ retval = entry; } PG_RETURN_POINTER(retval); }
當然,您必須將 compressed_data_type
調整為您要轉換到的特定類型,才能壓縮您的葉節點。
解壓縮
將資料項目的儲存表示轉換成其他 GiST 方法在運算子類別中可以處理的格式。如果省略 decompress
方法,則假設其他 GiST 方法可以直接處理儲存的資料格式。(decompress
方法不一定是 compress
方法的反向,特別是如果 compress
方法有損失,則 decompress
方法不可能完全重建原始資料。此外,decompress
方法也不一定等於 fetch
方法,因為其他 GiST 方法可能不需要完全重建資料。)
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_decompress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
PG_FUNCTION_INFO_V1(my_decompress); Datum my_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); }
上述範例適用於不需要解壓縮的情況。(但是,當然,完全省略該方法更為容易,而且建議在這種情況下使用。)
penalty
傳回一個值,用以表示將新條目插入樹狀結構的特定分支的「成本」。項目將會插入樹狀結構中 penalty
最小的路徑。由 penalty
傳回的值應為非負數。如果傳回負值,則會視為零。
函數的 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 模組中的配對程式碼可以遵循此架構
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
函數不只傳回 float
結果,而是必須將值儲存在第三個引數所指示的位置。傳回值本身會被忽略,儘管慣例是傳回該引數的位址。
對於索引的良好效能而言,penalty
函數至關重要。它會在插入時使用,以決定在選擇將新條目新增到樹狀結構中的位置時要遵循哪個分支。在查詢時,索引越平衡,查詢就越快。
picksplit
當索引頁面需要分割時,此函數會決定頁面上的哪些條目要留在舊頁面上,哪些要移到新頁面上。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
PG_FUNCTION_INFO_V1(my_picksplit); Datum my_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); OffsetNumber maxoff = entryvec->n - 1; GISTENTRY *ent = entryvec->vector; 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; /* Initialize the raw entry vector. */ 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); /* * Choose where to put the index entries and update unionL and unionR * accordingly. Append the entries to either v->spl_left or * v->spl_right, and care about the counters. */ 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 { /* * Same on the right */ } } v->spl_ldatum = DataTypeGetDatum(unionL); v->spl_rdatum = DataTypeGetDatum(unionR); PG_RETURN_POINTER(v); }
請注意,picksplit
函數的結果是透過修改傳入的 v
結構來傳遞的。傳回值本身會被忽略,儘管慣例是傳回 v
的位址。
與 penalty
類似,picksplit
函數對於索引的良好效能至關重要。設計適當的 penalty
和 picksplit
實作是實作效能良好的 GiST 索引的挑戰所在。
same
如果兩個索引條目相同,則傳回 true,否則傳回 false。(「索引條目」是索引儲存類型的值,不一定是原始索引欄位的類型。)
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
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
函數不只傳回布林結果,而是必須將旗標儲存在第三個引數所指示的位置。傳回值本身會被忽略,儘管慣例是傳回該引數的位址。
distance
給定一個索引項 p
和一個查詢值 q
,此函數會決定索引項與查詢值的“距離”。如果運算子類別包含任何排序運算子,則必須提供此函數。使用排序運算子的查詢會透過先傳回具有最小“距離”值的索引項來實作,因此結果必須與運算子的語意一致。對於葉索引項,結果僅表示與索引項的距離;對於內部樹節點,結果必須是任何子項可能具有的最小距離。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal) RETURNS float8 AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
然後,C 模組中的配對程式碼可以遵循此架構
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); */ /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */ data_type *key = DatumGetDataType(entry->key); double retval; /* * determine return value as a function of strategy, key and query. */ PG_RETURN_FLOAT8(retval); }
distance
函數的引數與 consistent
函數的引數相同。
在決定距離時允許一些近似值,只要結果永遠不會大於項的實際距離即可。因此,例如,在幾何應用中,與邊界框的距離通常就足夠了。對於內部樹節點,傳回的距離不得大於與任何子節點的距離。如果傳回的距離不精確,函數必須將 *recheck
設為 true。(對於內部樹節點不需要這樣做;對於它們,計算值總是假設為不精確。)在這種情況下,執行器會在從堆中擷取組後計算精確距離,並在必要時重新排序組。
如果距離函數傳回 *recheck = true
給任何葉節點,原始排序運算子的傳回類型必須是 float8
或 float4
,而距離函數的結果值必須與原始排序運算子的結果值相容,因為執行器會使用距離函數結果和重新計算的排序運算子結果來排序。否則,距離函數的結果值可以是任何有限的 float8
值,只要結果值的相對順序與排序運算子傳回的順序相符即可。(無窮大和負無窮大在內部用於處理 Null 值等情況,因此不建議 distance
函數傳回這些值。)
擷取
將資料項的壓縮索引表示轉換為原始資料類型,以進行僅索引掃描。傳回的資料必須是原始索引值的精確、無損失副本。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_fetch(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
參數是指向 GISTENTRY
結構的指標。在進入時,其 key
欄位包含以壓縮形式表示的非 NULL 葉資料。傳回值是另一個 GISTENTRY
結構,其 key
欄位包含以其原始未壓縮形式表示的相同資料。如果 opclass 的壓縮函數對葉資料無作用,則 fetch
方法可以原樣傳回參數。或者,如果 opclass 沒有壓縮函數,也可以省略 fetch
方法,因為它必定是空操作。
C 模組中的對應程式碼可以遵循下列架構
PG_FUNCTION_INFO_V1(my_fetch); Datum my_fetch(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); input_data_type *in = DatumGetPointer(entry->key); fetched_data_type *fetched_data; GISTENTRY *retval; retval = palloc(sizeof(GISTENTRY)); fetched_data = palloc(sizeof(fetched_data_type)); /* * Convert 'fetched_data' into the a Datum of the original datatype. */ /* fill *retval from fetched_data. */ gistentryinit(*retval, PointerGetDatum(converted_datum), entry->rel, entry->page, entry->offset, FALSE); PG_RETURN_POINTER(retval); }
如果壓縮方法對葉資料有損失,則運算子類別無法支援僅索引掃描,且不得定義 fetch
函數。
選項
允許定義控制運算子類別行為的使用者可見參數。
函數的 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()
巨集,從其他支援函數存取選項。
以下是 my_options() 的範例實作,以及從其他支援函數使用的參數
typedef enum MyEnumType { MY_ENUM_ON, MY_ENUM_OFF, MY_ENUM_AUTO } MyEnumType; typedef struct { int32 vl_len_; /* varlena header (do not touch directly!) */ int int_param; /* integer parameter */ double real_param; /* real parameter */ MyEnumType enum_param; /* enum parameter */ int str_param; /* string parameter */ } MyOptionsStruct; /* String representation of enum values */ static relopt_enum_elt_def myEnumValues[] = { {"on", MY_ENUM_ON}, {"off", MY_ENUM_OFF}, {"auto", MY_ENUM_AUTO}, {(const char *) NULL} /* list terminator */ }; static char *str_param_default = "default"; /* * Sample validator: checks that string is not longer than 8 bytes. */ static void validate_my_string_relopt(const char *value) { if (strlen(value) > 8) ereport(ERROR, (errcode(ERRCODE_INVALID_PARAMETER_VALUE), errmsg("str_param must be at most 8 bytes"))); } /* * Sample filler: switches characters to lower case. */ static Size fill_my_string_relopt(const char *value, void *ptr) { char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID); int len = strlen(tmp); if (ptr) strcpy((char *) ptr, tmp); pfree(tmp); return len + 1; } PG_FUNCTION_INFO_V1(my_options); Datum my_options(PG_FUNCTION_ARGS) { local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0); init_local_reloptions(relopts, sizeof(MyOptionsStruct)); add_local_int_reloption(relopts, "int_param", "integer parameter", 100, 0, 1000000, offsetof(MyOptionsStruct, int_param)); add_local_real_reloption(relopts, "real_param", "real parameter", 1.0, 0.0, 1000000.0, offsetof(MyOptionsStruct, real_param)); add_local_enum_reloption(relopts, "enum_param", "enum parameter", myEnumValues, MY_ENUM_ON, "Valid values are: \"on\", \"off\" and \"auto\".", offsetof(MyOptionsStruct, enum_param)); add_local_string_reloption(relopts, "str_param", "string parameter", str_param_default, &validate_my_string_relopt, &fill_my_string_relopt, offsetof(MyOptionsStruct, str_param)); PG_RETURN_VOID(); } PG_FUNCTION_INFO_V1(my_compress); Datum my_compress(PG_FUNCTION_ARGS) { int int_param = 100; double real_param = 1.0; MyEnumType enum_param = MY_ENUM_ON; char *str_param = str_param_default; /* * Normally, when opclass contains 'options' method, then options are always * passed to support functions. However, if you add 'options' method to * existing opclass, previously defined indexes have no options, so the * check is required. */ if (PG_HAS_OPCLASS_OPTIONS()) { MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS(); int_param = options->int_param; real_param = options->real_param; enum_param = options->enum_param; str_param = GET_STRING_RELOPTION(options, str_param); } /* the rest implementation of support function */ }
由於 GiST 中金鑰的表示方式具有彈性,因此它可能取決於使用者指定的參數。例如,可以指定金鑰簽章的長度。請參閱 gtsvector_options()
作為範例。
sortsupport
傳回比較器函數,以保留區域性的方式對資料進行排序。它由 CREATE INDEX
和 REINDEX
指令使用。建立的索引品質取決於比較器函數所決定的排序順序如何保留輸入的區域性。
sortsupport
方法是選用的。如果未提供,CREATE INDEX
會使用 penalty
和 picksplit
函數將每個元組插入樹狀結構中來建立索引,這會慢很多。
函數的 SQL 宣告必須如下所示
CREATE OR REPLACE FUNCTION my_sortsupport(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
參數是指向 SortSupport
結構的指標。此函數至少必須填入其比較器欄位。比較器有三個參數:兩個要比較的資料,以及指向 SortSupport
結構的指標。資料是索引中儲存格式的兩個索引值;也就是說,是 compress
方法傳回的格式。完整的 API 定義在 src/include/utils/sortsupport.h
中。
C 模組中的對應程式碼可以遵循下列架構
PG_FUNCTION_INFO_V1(my_sortsupport); static int my_fastcmp(Datum x, Datum y, SortSupport ssup) { /* establish order between x and y by computing some sorting value z */ int z1 = ComputeSpatialCode(x); int z2 = ComputeSpatialCode(y); return z1 == z2 ? 0 : z1 > z2 ? 1 : -1; } Datum my_sortsupport(PG_FUNCTION_ARGS) { SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); ssup->comparator = my_fastcmp; PG_RETURN_VOID(); }
所有 GiST 支援方法通常會在短暫的記憶體內容中呼叫;也就是說,在處理每個元組後,CurrentMemoryContext
會重設。因此,不必太擔心 pfree 所有您 palloc 的內容。不過,在某些情況下,支援方法用於跨重複呼叫快取資料會很有用。為此,請在 fcinfo->flinfo->fn_mcxt
中配置較長期的資料,並在 fcinfo->flinfo->fn_extra
中保留指向它的指標。此類資料會在索引操作的期間內持續存在(例如,單一 GiST 索引掃描、索引建立或索引元組插入)。更換 fn_extra
值時,請小心 pfree 前一個值,否則外洩會在操作期間累積。
如果您在文件當中看到任何不正確、與您使用特定功能的經驗不符,或需要進一步澄清的內容,請使用 此表單 回報文件問題。