Internally, a <acronym>GIN</acronym> index contains a B-tree index constructed over keys, where each key is an element of one or more indexed items (a member of an array, for example) and where each tuple in a leaf page contains either a pointer to a B-tree of heap pointers (a <quote>posting tree</quote>), or a simple list of heap pointers (a <quote>posting list</quote>) when the list is small enough to fit into a single index tuple along with the key value. <xref linkend="gin-internals-figure"/> illustrates these components of a GIN index. GINインデックスはキー全体に対するB-treeインデックスを持ちます。 そのキーはそれぞれインデックス対象項目の要素(例えば配列のメンバ)であり、リーフページ内のタプルはそれぞれ、ヒープポインタのB-treeへのポインタ(「ポスティングツリー(posting tree)」)か、もしリストがキー値と共に単一インデックスタプルに合う程度十分に小さければヒープポインタの単純なリスト(「ポスティングリスト(posting list)」)です。 図 70.1にGINインデックスのこれらのコンポーネントを示します。
As of <productname>PostgreSQL</productname> 9.1, null key values can be
included in the index. Also, placeholder nulls are included in the index
for indexed items that are null or contain no keys according to
<function>extractValue</function>. This allows searches that should find empty
items to do so.
PostgreSQL 9.1からNULLキー値をインデックスに含められるようになりました。
またプレースホルダとしてのNULLが、NULLまたはextractValue
によるとキーを含まないインデックス対象項目についてインデックスに含められます。
これにより空の項目を見つけ出すための検索を行うことができます。
Multicolumn <acronym>GIN</acronym> indexes are implemented by building a single B-tree over composite values (column number, key value). The key values for different columns can be of different types. 複数列に対するGINインデックスは複合型の値(列番号、キー値)全体について単一のB-treeを構築することで実装されます。 異なる列に対するキー値は別の型となるかもしれません。
図70.1 GINの内部
Updating a <acronym>GIN</acronym> index tends to be slow because of the
intrinsic nature of inverted indexes: inserting or updating one heap row
can cause many inserts into the index (one for each key extracted
from the indexed item).
<acronym>GIN</acronym> is capable of postponing much of this work by inserting
new tuples into a temporary, unsorted list of pending entries.
When the table is vacuumed or autoanalyzed, or when
<function>gin_clean_pending_list</function> function is called, or if the
pending list becomes larger than
<xref linkend="guc-gin-pending-list-limit"/>, the entries are moved to the
main <acronym>GIN</acronym> data structure using the same bulk insert
techniques used during initial index creation. This greatly improves
<acronym>GIN</acronym> index update speed, even counting the additional
vacuum overhead. Moreover the overhead work can be done by a background
process instead of in foreground query processing.
1つのヒープ行の挿入または更新によりインデックスへの挿入が多く発生するという、転置インデックスの本質的な性質のためGINインデックスの更新は低速になりがちです。
(各キー用のヒープ行はインデックス付けされた項目から取り出されます。)
GINは、新しいタプルを一時的なソートされていない、待機中の項目リストに挿入することにより、この作業の大部分を遅延させることができるようになりました。
テーブルがバキュームまたは自動解析された時、gin_clean_pending_list
関数が呼ばれたとき、または、待機中のリスト(pending list)がgin_pending_list_limitよりも大きくなった時、初期のインデックス作成の際に使用されるものと同様の一括挿入技法を使用して、項目は主GINデータ構造に移動されます。
これは、バキュームのオーバーヘッドが追加されることを考慮したとしても、GINインデックスの更新速度を著しく向上します。
さらに、フォアグラウンドの問い合わせ処理ではなくバックグラウンド処理でこのオーバーヘッド作業を実行することができます。
The main disadvantage of this approach is that searches must scan the list of pending entries in addition to searching the regular index, and so a large list of pending entries will slow searches significantly. Another disadvantage is that, while most updates are fast, an update that causes the pending list to become <quote>too large</quote> will incur an immediate cleanup cycle and thus be much slower than other updates. Proper use of autovacuum can minimize both of these problems. この手法の大きな欠点は、検索時に通常のインデックス検索に加え待機中の項目リストのスキャンを行わなければならない点です。 このため、待機中の項目リストが大きくなると検索が顕著に遅くなります。 他の欠点は、ほとんどの更新は高速ですが、待機中の項目リストが「大きくなりすぎる」きっかけとなった更新は即時の整理処理を招くことになり、他の更新に比べ大きく低速になります。 自動バキュームを適切に使用することで、これらの両方の問題を最小化することができます。
If consistent response time is more important than update speed,
use of pending entries can be disabled by turning off the
<literal>fastupdate</literal> storage parameter for a
<acronym>GIN</acronym> index. See <xref linkend="sql-createindex"/>
for details.
一貫した応答時間が更新速度より重要な場合、GINインデックスに対するfastupdate
格納パラメータを無効にすることにより、待機中の項目の使用を無効にすることができます。
詳細はCREATE INDEXを参照してください。
GIN can support <quote>partial match</quote> queries, in which the query
does not determine an exact match for one or more keys, but the possible
matches fall within a reasonably narrow range of key values (within the
key sorting order determined by the <function>compare</function> support method).
The <function>extractQuery</function> method, instead of returning a key value
to be matched exactly, returns a key value that is the lower bound of
the range to be searched, and sets the <literal>pmatch</literal> flag true.
The key range is then scanned using the <function>comparePartial</function>
method. <function>comparePartial</function> must return zero for a matching
index key, less than zero for a non-match that is still within the range
to be searched, or greater than zero if the index key is past the range
that could match.
GINは「部分一致」問い合わせをサポートすることができます。
この問い合わせは1つ以上のキーに正確に一致することは決定しませんが、キー値の合理的に狭い(compare
サポートメソッドで決まるキーのソート順に従った)範囲内に一致する可能性があります。
extractQuery
は、正確に一致したキー値を返す代わりに、検索される範囲の下限となるキー値を返し、pmatch
フラグを真に設定します。
そしてキー範囲をcomparePartial
メソッドを使用して検索します。
comparePartial
は一致するインデックスキーではゼロを、一致しないが検索すべき範囲内にあればゼロ未満の値を、インデックスキーが一致可能な範囲を超えた場合はゼロより大きな値を返さなければなりません。