他のバージョンの文書 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

66.4. 実装

GINインデックスはキー全体に対するB-treeインデックスを持ちます。 そのキーはそれぞれインデックス対象項目の要素(例えば配列のメンバ)であり、リーフページ内のタプルはそれぞれ、ヒープポインタのB-treeへのポインタ(ポスティングツリー(posting tree))か、もしリストがキー値と共に単一インデックスタプルに合う程度十分に小さければヒープポインタの単純なリスト(ポスティングリスト(posting list))です。 図 66.1にGINインデックスのこれらのコンポーネントを示します。

PostgreSQL 9.1からNULLキー値をインデックスに含められるようになりました。 またプレースホルダとしてのNULLが、NULLまたはextractValueによるとキーを含まないインデックス対象項目についてインデックスに含められます。 これにより空の項目を見つけ出すための検索を行うことができます。

複数列に対するGINインデックスは複合型の値(列番号、キー値)全体について単一のB-treeを構築することで実装されます。 異なる列に対するキー値は別の型となるかもしれません。

図66.1 GINの内部


66.4.1. GIN高速更新手法

1つのヒープ行の挿入または更新によりインデックスへの挿入が多く発生するという、転置インデックスの本質的な性質のためGINインデックスの更新は低速になりがちです。 (各キー用のヒープ行はインデックス付けされた項目から取り出されます。) PostgreSQL 8.4からGINは、新しいタプルを一時的なソートされていない、待機中の項目リストに挿入することにより、この作業の大部分を遅延させることができるようになりました。 テーブルがバキュームまたは自動解析された時、gin_clean_pending_list関数が呼ばれたとき、または、待機中のリスト(pending list)がgin_pending_list_limitよりも大きくなった時、初期のインデックス作成の際に使用されるものと同様の一括挿入技法を使用して、項目は主GINデータ構造に移動されます。 これは、バキュームのオーバーヘッドが追加されることを考慮したとしても、GINインデックスの更新速度を著しく向上します。 さらに、フォアグラウンドの問い合わせ処理ではなくバックグラウンド処理でこのオーバーヘッド作業を実行することができます。

この手法の大きな欠点は、検索時に通常のインデックス検索に加え待機中の項目リストのスキャンを行わなければならない点です。 このため、待機中の項目リストが大きくなると検索が顕著に遅くなります。 他の欠点は、ほとんどの更新は高速ですが、待機中の項目リストが大きくなりすぎるきっかけとなった更新は即時の整理処理を招くことになり、他の更新に比べ大きく低速になります。 自動バキュームを適切に使用することで、これらの両方の問題を最小化することができます。

一貫した応答時間が更新速度より重要な場合、GINインデックスに対するfastupdate格納パラメータを無効にすることにより、待機中の項目の使用を無効にすることができます。 詳細はCREATE INDEXを参照してください。

66.4.2. 部分一致アルゴリズム

GINは部分一致問い合わせをサポートすることができます。 この問い合わせは1つ以上のキーに正確に一致することは決定しませんが、キー値の合理的に狭い(compareサポートメソッドで決まるキーのソート順に従った)範囲内に一致する可能性があります。 extractQueryは、正確に一致したキー値を返す代わりに、検索される範囲の下限となるキー値を返し、pmatchフラグを真に設定します。 そしてキー範囲をcomparePartialメソッドを使用して検索します。 comparePartialは一致するインデックスキーではゼロを、一致しないが検索すべき範囲内にあればゼロ未満の値を、インデックスキーが一致可能な範囲を超えた場合はゼロより大きな値を返さなければなりません。