PostgreSQL 9.0.4文書 | ||||
---|---|---|---|---|
前のページ | 巻戻し | 第 52章GiSTインデックス | 早送り | 次のページ |
GiST用の演算子クラスが提供しなければならない7つのメソッドを以下に示します。
インデックスの正確性は、確実にsame
、consistent
、union
メソッドを適切に実装することです。
一方、インデックスの効率(容量と速度)はpenalty
とpicksplit
メソッドに依存します。
残りの2メソッドはcompress
とdecompress
ですが、これによりインデックスはインデックス付けするデータと異なるデータ型のツリーデータを内部で持つことができるようになります。
リーフはインデックス付けするデータ型となりますが、他のツリーノードは何らかのC構造体を取ることができます。
(しかしここでもPostgreSQLのデータ型規約に従わなければなりません。
容量が可変のデータに関してはvarlenaを参照してください。)
ツリーの内部データ型がSQLレベルで存在する場合、CREATE OPERATOR CLASSコマンドのSTORAGEオプションを使用することができます。
consistent
インデックス項目pと問い合わせ値qが与えられると、この関数はインデックス項目が問い合わせと"一貫性"があるかどうか、つまり、述語"indexed_columnindexable_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コマンドの演算子番号の1つに一致します。 このクラスに含めた演算子が何かに応じて、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値の圧縮に関して注意をしなければなりません。 例えばgist_circle_compressなどでは(Datum) 0を格納します。
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
が最小の経路に挿入されます。
この関数の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 { /* * Same on the right */ } } 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番目の引数で指定された場所にフラグを格納しなければなりません。