GINとは汎用転置インデックス(Generalized Inverted Index)を表します。 GINは、以下のような状況を取り扱うために設計されました。(1)インデックス対象の項目が複合型である。(2)そのインデックスにより処理される問い合わせは、複合型の項目内に存在する要素の値を検索する必要がある。 例えば、項目は文書であり、問い合わせは特定の単語を含む文書の検索です。
ここでは、インデックス対象の複合型の値を項目と呼びます。また、要素値をキーと呼びます。 GINは項目の値自体ではなく、常にキーを格納し検索します。
GINインデックスは(キー、ポスティングリスト(posting list))の組み合わせの集合を格納します。 ここでポスティングリストはキーが発生した行IDの集合です。 項目は１つ以上のキーを含むことができますので、同じ行IDが複数のポスティングリストに現れることがあり得ます。 キー値はそれぞれ一度のみ格納されます。 このためGINインデックスの容量は、同じキーが何度も現れる場合に非常に小さくなります。
GINインデックスは、GINアクセスメソッドが高速化対象の操作を把握する必要がないという意味で汎用化されています。 その代わり、特定のデータ型に対して定義された独自の戦略を使用します。 戦略は、インデックス付けされた項目と問い合わせ条件からキーを抽出する方法および問い合わせ内のいくつかのキー値を含む行が実際に問い合わせを満たすかどうかを決定する方法を定義します。
GINの利点の1つは、データベース専門家ではなくデータ型の分野における専門家により、適切なアクセスメソッドを持つ独自のデータ型を開発できるという点です。 これはGiSTの使用とほぼ同じ利点です。
PostgreSQLにおけるGINの実装は、主にTeodor SigaevとOleg Bartunovにより保守されています。 GINに関する情報は彼らのwebサイトにより多く記載されています。
PostgreSQLのコア配布物は表 64.3に示すGIN演算子クラスを含みます。 (付録Fに記載された追加モジュールの中には追加のGIN演算子クラスを提供するものもあります。)
表64.3 組み込みGIN演算子クラス
| 名前 | インデックス可能な演算子 |
|---|---|
array_ops | && (anyarray,anyarray) |
@> (anyarray,anyarray) | |
<@ (anyarray,anyarray) | |
= (anyarray,anyarray) | |
jsonb_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
? (jsonb,text) | |
?| (jsonb,text[]) | |
?& (jsonb,text[]) | |
jsonb_path_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
tsvector_ops | @@ (tsvector,tsquery) |
jsonb型の2つの演算子クラスのうち、jsonb_opsがデフォルトです。
jsonb_path_opsはより少数の演算子しかサポートしませんが、その演算子に対してはより良いパフォーマンスを提供します。
詳細は8.14.4を参照してください。
GINインタフェースは高度に抽象化されています。 アクセスメソッド実装者に要求されることは、アクセスするデータ型の意味を実装することだけです。 GIN層自体が同時実行性、ログ処理、ツリー構造の検索処理に関する面倒を見ます。
GINアクセスメソッドを動作させるために必要なことは、少数のユーザ定義関数を実装することだけです。 これは、ツリー内のキーの動作とキーとインデックス付けされる項目、インデックス可能な問い合わせ間の関係を定義します。 すなわち、GINは、一般化、コード再利用、整理されたインタフェースによる拡張性を組み合わせます。
GIN用の演算子クラスが提供しなければならないメソッドは2つあります。
Datum *extractValue(Datum itemValue, int32 *nkeys,
bool **nullFlags)
インデックス対象値に与えられる、pallocで割り当てられたキーの配列を返します。
返されるキーの数は*nkeysに格納しなければなりません。
キーのいずれかがNULLになるかもしれない場合、*nkeys個のboolの配列をpallocで割り当てそのアドレスを*nullFlagsに格納し、必要に応じてNULLフラグを設定してください。
すべてのキーが非NULLであれば、*nullFlagsをNULL（初期値）のままにすることができます。
項目がキーを含まない場合、戻り値はNULLになるかもしれません。
Datum *extractQuery(Datum query, int32 *nkeys,
StrategyNumber n, bool **pmatch, Pointer **extra_data,
bool **nullFlags, int32 *searchMode)
問い合わせ対象の値に与えられる、pallocで割り当てられたキーの配列を返します。
つまり、queryはインデックス可能な演算子の右辺の値です。
この左辺はインデックス対象の列です。
nは演算子クラス内の演算子の戦略番号です（36.16.2を参照）。
extractQueryはしばしば、queryのデータ型とキー値を抽出するために使用しなければならないメソッドを決定するために、nを調べなければなりません。
返されるキーの数を*nkeysに格納しなければなりません。
キーのいずれかがNULLとなる可能性がある場合はまた、*nkeys個のboolの配列をpallocで割り当て、*nullFlagsにそのアドレスを格納し、必要に応じてNULLフラグを設定してください。
すべてのキーが非NULLならば*nullFlagsはNULL（初期値）のままにしておくことができます。
queryがキーを含まない場合、戻り値をNULLにすることができます。
searchModeは出力引数です。
これによりextractQueryは検索がどのように行われるかの詳細を指定することができます。
*searchModeがGIN_SEARCH_MODE_DEFAULT（呼び出し前にこの値に初期化されます。）に設定された場合、返されるキーの少なくとも１つに一致する項目が合致候補とみなされます。
*searchModeがGIN_SEARCH_MODE_INCLUDE_EMPTYに設定された場合、少なくとも１つの一致するキーを含む項目に加え、キーをまったく含まない項目が合致候補とみなされます。
（このモードは例えば何のサブセットかを求める演算子を実装する際に有用です。）
*searchModeがGIN_SEARCH_MODE_ALLに設定された場合、返されるキーのいずれかに一致するかどうかは関係なく、インデックス内の非NULLの項目すべてが合致候補とみなされます。
（このモードは、基本的にインデックス全体のスキャン処理が必要ですので、他の２つの選択肢と比べてかなり低速になります。
しかし境界条件を正確に実装するためにこれが必要になるかもしれません。
おそらく、このモードを必要とする演算子はほとんどの場合、GIN演算子クラス向けに優れた候補ではありません。）
このモードを設定するために使用する記号はaccess/gin.hで定義されています。
pmatchは部分一致が提供されている場合に使用する出力引数です。
使用するには、extractQueryが*nkeys個のboolの配列を割り当て、そのアドレスを*pmatchに格納しなければなりません。
関連するキーが部分一致を必要とするとき、それぞれの配列要素は真に、そうでなければ偽に設定されなければなりません。
*pmatchがNULLに設定されている場合、GINは部分一致が必要ないと想定します。
呼び出し前に変数はNULLに初期化されますので、この引数は部分一致が提供されていない演算子クラスでは、単に無視できます。
extra_dataは、extractQueryがconsistentとcomparePartialメソッドに追加データを渡すことができるようにする出力引数です。
使用するには、extractQueryが*nkeysポインタの配列を割り当て、そのアドレスを*extra_dataに格納し、そして望まれるものは何でも個別のポインタに格納しなければなりません。
変数は呼び出し前にNULLに初期化されますので、追加データを必要としない演算子クラスでこの引数は単に無視できます。
もし*extra_dataが設定されれば、配列全部がconsistentメソッドに、適切な要素がcomparePartialメソッドに渡されます。
演算子クラスは、インデックス付けされた項目が問い合わせに一致するか確認する関数も提供しなければなりません。
それは2つの方法で行なわれます。
2値のconsistent関数と3値のtriConsistent関数です。
triConsistentが両方の機能を含みますので、triConsistentだけを提供しても十分です。
しかし、2値の亜種を計算するのが著しく安価であれば、両方を提供することは役に立つかもしれません。
2値の亜種のみが提供されていれば、すべてのキーを取得する前にインデックス項目が一致しないことを確認することに基づく最適化の中には無効となるものもあります。
bool consistent(bool check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[], bool *recheck,
Datum queryKeys[], bool nullFlags[])
インデックス付けられた項目が戦略番号nを持つ問い合わせ演算子を満たす（または、recheck印が返されたときはたぶん満たすかもしれない）場合に真を返します。
GINは項目を明示的に格納しませんので、この関数はインデックス付けされた項目の値に直接アクセスすることができません。
どちらかというと、この問い合わせから取り出される指定された問い合わせで現れるキー値に関する知識が利用できるものです。
check配列は長さnkeysであり、このqueryデータに対して事前に行われたextractQueryが返したキーの数と同じです。
インデックス対象の項目が対応する問い合わせキーを持つ場合、check配列の各要素は真です。
つまり、(check[i] == true)の場合、extractQueryの結果配列のi番目のキーがインデックス対象項目内に存在します。
元のqueryデータは、consistentメソッドがそれを調査する必要がある場合に、渡されます。
このためqueryKeys[]およびnullFlags[]は事前にextractQueryによって返されます。
extra_dataはextractQueryにより返された追加データ配列で、ない場合はNULLです。
extractQueryがqueryKeys[]内でNULLキーを返す時、インデックス対象項目がNULLキーを含む場合は対応するcheck[]要素は真です、
つまり、check[]の意味はIS NOT DISTINCT FROMのようなものです。
consistent関数は、通常の値の合致とNULL合致との違いを通知する必要がある場合、対応するnullFlags[]要素を検査することができます。
成功の場合、*recheckは、問い合わせ演算子に対してヒープタプルを再検査する必要があればtrue、インデックス検査が的確であればfalseに設定する必要があります。
つまり、falseの戻り値はヒープタプルが問い合わせに一致しないことを保証します。
trueの戻り値で、*recheckがfalseに設定された場合はヒープタプルが問い合わせに一致することを保証します。
trueの戻り値で、*recheckがtrueに設定された場合はヒープタプルが問い合わせに一致する可能性があることを意味します。
したがって、それを取り出し、元のインデックス付けされた項目を直接問い合わせ演算子で評価することで再検査する必要があることを意味します。
GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[],
Datum queryKeys[], bool nullFlags[])
triConsistentはconsistentと似ていますが、checkベクトルの論理値の代わりに、各キーに対して3つの可能な値があります。GIN_TRUE、GIN_FALSE、GIN_MAYBEです。
GIN_FALSEとGIN_TRUEは通常の論理値と同じ意味であり、GIN_MAYBEはそのキーの存在が分からないこと意味します。
GIN_MAYBE値があれば、インデックス項目が対応する問い合わせキーを含むかどうかに関わらず、項目が確実に一致する場合にのみ関数はGIN_TRUEを返すべきです。
同様に、GIN_MAYBEを含むかどうかに関わらず項目が確実に一致しない場合にのみ関数はGIN_FALSEを返さなければなりません。
結果がGIN_MAYBE項目に依存する、すなわち、分かっている問い合わせキーに基づいて、一致することもしないことも確認できない場合には、関数はGIN_MAYBEを返さなければなりません。
checkベクトルにGIN_MAYBE値がなければ、GIN_MAYBE戻り値は論理値のconsistent関数でrecheckフラグを設定することと同じです。
さらに、GINにはインデックス内に格納されているキー値をソートする方法がなければなりません。 演算子クラスは比較メソッドを指定することでソート順を定義できます。
int compare(Datum a, Datum b)キー（インデックス付けされる項目ではありません）を比較し、0より小さい、0、または0より大きい整数を返します。 それぞれ、最初のキーが2番目のキーより、小さい、等しい、または大きいことを示します。 NULLキーがこの関数に渡されることはありません。
あるいは、演算子クラスがcompareメソッドを提供しない場合には、GINはそのインデックスキーデータ型に対するデフォルトのbtree演算子クラスを探し、その比較関数を使います。
btree演算子クラスを探すのは処理に多少掛かりますので、GIN演算子クラスの中で比較関数を指定することを勧めます。それはただ一つのデータ型に対するものであることを意味します。
しかし、(array_opsのような)多様GIN演算子クラスでは、通常は単一の比較関数を指定できません。
省略可能ですが、GINに対する演算子クラスは以下のメソッドを提供します。
int comparePartial(Datum partial_key, Datum key, StrategyNumber n,
Pointer extra_data)
問い合わせキーとインデックスキーの部分一致を比較します。
符号が結果を示す整数が返ります。
ゼロ未満はインデックスキーは問い合わせに一致しないが、インデックススキャンを続けるべきであることを示します。
ゼロはインデックスキーが問い合わせに一致することを示します。
ゼロより大きな値はこれ以上の一致はありえないためインデックススキャンを停止すべきであることを示します。
スキャンをいつ停止するかを決めるためにセマンティクスが必要とされる場合、部分一致問い合わせを生成した演算子の戦略番号nが提供されます。
またextra_dataはextractQueryで作成される追加データ配列の対応する要素、もしなければNULLです。
NULLキーがこの関数に渡されることはありません。
void options(local_relopts *relopts)演算子クラスの振舞いを制御するユーザに可視のパラメータの集合を定義します。
options関数にはlocal_relopts構造体へのポインタが渡されますが、構造体を演算子クラスに固有のオプションの集合で満たすことが必要です。
オプションはマクロPG_HAS_OPCLASS_OPTIONS()とPG_GET_OPCLASS_OPTIONS()を使って他のサポート関数からアクセスできます。
インデックス付けされた値からのキーの抽出にもGINでのキーの表現にも柔軟性がありますので、ユーザに固有のパラメータに依存するかもしれません。
「部分一致」問い合わせをサポートするためには、演算子クラスはcomparePartialメソッドを提供しなければなりません。
またそのextractQueryは、部分一致問い合わせであった時にpmatchパラメータを設定しなければなりません。
詳細については64.4.4.2を参照してください。
上記の各種Datum値の実データ型は、演算子クラスに依存して変動します。
extractValueに渡される項目値は常に演算子クラスの入力型であり、キー値はすべてそのクラスのSTORAGE型でなければなりません。
extractQuery、consistentおよびtriConsistentに渡されるquery引数の型は、戦略番号によって識別されるクラスのメンバ演算子の右辺入力型です。
正しい型のキー値がそこから抽出できる限り、これはインデックス付けされた型と同じである必要はありません。
しかしながら、この3つのサポート関数のSQL宣言では、実際の型は演算子に依存して何か他のものであるとしても、query引数には演算子クラスのインデックス付けされたデータ型を使うことを勧めます。
GINインデックスはキー全体に対するB-treeインデックスを持ちます。 そのキーはそれぞれインデックス対象項目の要素（例えば配列のメンバ）であり、リーフページ内のタプルはそれぞれ、ヒープポインタのB-treeへのポインタ（「ポスティングツリー(posting tree)」）か、もしリストがキー値と共に単一インデックスタプルに合う程度十分に小さければヒープポインタの単純なリスト（「ポスティングリスト(posting list)」）です。 図 64.1にGINインデックスのこれらのコンポーネントを示します。
PostgreSQL 9.1からNULLキー値をインデックスに含められるようになりました。
またプレースホルダとしてのNULLが、NULLまたはextractValueによるとキーを含まないインデックス対象項目についてインデックスに含められます。
これにより空の項目を見つけ出すための検索を行うことができます。
複数列に対するGINインデックスは複合型の値（列番号、キー値）全体について単一のB-treeを構築することで実装されます。 異なる列に対するキー値は別の型となるかもしれません。
図64.1 GINの内部
1つのヒープ行の挿入または更新によりインデックスへの挿入が多く発生するという、転置インデックスの本質的な性質のためGINインデックスの更新は低速になりがちです。
（各キー用のヒープ行はインデックス付けされた項目から取り出されます。）
GINは、新しいタプルを一時的なソートされていない、待機中の項目リストに挿入することにより、この作業の大部分を遅延させることができるようになりました。
テーブルがバキュームまたは自動解析された時、gin_clean_pending_list関数が呼ばれたとき、または、待機中のリスト(pending list)がgin_pending_list_limitよりも大きくなった時、初期のインデックス作成の際に使用されるものと同様の一括挿入技法を使用して、項目は主GINデータ構造に移動されます。
これは、バキュームのオーバーヘッドが追加されることを考慮したとしても、GINインデックスの更新速度を著しく向上します。
さらに、フォアグラウンドの問い合わせ処理ではなくバックグラウンド処理でこのオーバーヘッド作業を実行することができます。
この手法の大きな欠点は、検索時に通常のインデックス検索に加え待機中の項目リストのスキャンを行わなければならない点です。 このため、待機中の項目リストが大きくなると検索が顕著に遅くなります。 他の欠点は、ほとんどの更新は高速ですが、待機中の項目リストが「大きくなりすぎる」きっかけとなった更新は即時の整理処理を招くことになり、他の更新に比べ大きく低速になります。 自動バキュームを適切に使用することで、これらの両方の問題を最小化することができます。
一貫した応答時間が更新速度より重要な場合、GINインデックスに対するfastupdate格納パラメータを無効にすることにより、待機中の項目の使用を無効にすることができます。
詳細はCREATE INDEXを参照してください。
GINは「部分一致」問い合わせをサポートすることができます。
この問い合わせは１つ以上のキーに正確に一致することは決定しませんが、キー値の合理的に狭い（compareサポートメソッドで決まるキーのソート順に従った）範囲内に一致する可能性があります。
extractQueryは、正確に一致したキー値を返す代わりに、検索される範囲の下限となるキー値を返し、pmatchフラグを真に設定します。
そしてキー範囲をcomparePartialメソッドを使用して検索します。
comparePartialは一致するインデックスキーではゼロを、一致しないが検索すべき範囲内にあればゼロ未満の値を、インデックスキーが一致可能な範囲を超えた場合はゼロより大きな値を返さなければなりません。
各項目に対して多くのキーが挿入される可能性がありますので、GINインデックスへの挿入は低速になることがあります。 ですので、テーブルに対する大量の挿入では、GINインデックスを削除し、大量の挿入が終わった段階で再作成することを勧めます。
GINではfastupdateが有効である場合、このペナルティはそうでない場合よりも少なくなります。
（64.4.4.1を参照してください。）
しかし非常に大規模な更新では、インデックスの削除と再作成がまだ最善かもしれません。
GINインデックスの構築時間はmaintenance_work_memの設定に非常に敏感です。
インデックス作成時に作業メモリをより少なく使用しようとはしません。
fastupdateが有効な既存のGINインデックスに対して挿入を繰り返す間、待機中の項目リストがgin_pending_list_limitより大きくなると、システムはこのリストを整理します。
観測される応答時間の変動を防ぐためには、待機中リストの整理をバックグラウンド（すなわち自動バキューム）で起きるようにすることが望まれます。
フォアグラウンドでの整理処理は、gin_pending_list_limitを大きくすること、もしくは自動バキュームをより積極的に行うことで防ぐことができます。
しかし、整理処理の閾値を大きくすることは、フォアグラウンドで整理処理が発生した時により長い時間がかかることを意味します。
gin_pending_list_limitは格納パラメータを変更することで個々のGINインデックスに対して上書きでき、それにより各GINインデックスが自身の整理閾値を持てます。
例えば、頻繁に更新される可能性のあるGINインデックスの閾値のみを増やして、それ以外は減らすことができます。
GINインデックス開発の主な目的は、スケーラビリティが高い全文検索のサポートをPostgreSQLで作成することでした。 全文検索の結果は非常に大規模な結果セットを返します。 さらに、問い合わせが非常に高頻度な単語を持つ場合、こうした状況はよく発生しますが、大規模な結果セットは有用ですらありません。 ディスクから大量のタプルを読み、ソートすることは長い時間がかかりますので、実運用レベルでは受け入れられません。 （インデックス検索自体は非常に高速であることに注意してください。）
こうした問い合わせの実行を簡単に制御できるように、GINは返される行数に対して設定可能なソフト上限、gin_fuzzy_search_limit設定パラメータを持ちます。
これはデフォルトでは0です（無制限を意味します）。
非0の制限が設定された場合、返されるセットは結果セット全体からランダムに選んだサブセットになります。
「ソフト」は、問い合わせとシステムの乱数ジェネレータの品質に依存して、返される結果の実際の数が指定した上限より多少異なることを意味します。
経験上、数千（例えば5000から20000）の値がうまく動作します。
GINは、インデックス付け可能な演算子は厳密であると仮定します。
これはextractValueはNULL項目値についてはまったく呼び出されない（代わりにインデックス項目のプレースホルダが自動的に生成される）こと、および、extractQueryは問い合わせの値がNULLの場合に呼び出されない（代わりに問い合わせは不一致であるとみなされる）ことを意味します。
しかし非NULLの複合型項目内または問い合わせ値内のNULLキー値はサポートされます。