本節では、上級ユーザに役立つかもしれない、B-Treeインデックスの実装の詳細について説明します。
更なる詳細、B-Tree実装の内部に焦点をあてた記述については、ソース配布物のsrc/backend/access/nbtree/README
を参照してください。
PostgreSQLのB-Treeインデックスは複数階層のツリー構造で、ツリーの各階層はページの双方向連結リストとして使用できます。 一つのメタページがインデックスの最初のセグメントファイルの固定位置に格納されます。 それ以外の全てのページはリーフページか内部ページのいずれかです。 リーフページはツリーの最下階層にあるページです。 各リーフページはテーブルの行を指すタプルを含みます。 各内部ページはツリーの次の下位層を指すタプルを含みます。 典型的には、全ページの99%以上がリーフページです。 内部ページとリーフページは共に、73.6に記載されている標準のページ書式を使用します。
既存リーフページがやってくるタプルをはめ込むことができないとき、新たなリーフページがB-Treeインデックスに追加されます。 ページ分割操作は一部のアイテムを新ページに動かすことで、当初は溢れているページに属していたアイテムのために空間を作ります。 ページ分割は、また、新ページへの新たなダウンリンクを親ページに挿入しなければなりません。これは親ページの分割を同様に引き起こすかもしれません。 ページは分割は再帰的に「上向きに連鎖」します。 最終的にルートページが新たなダウンリンクをはめ込みできないときには、ルートページ分割が実施されます。 これは元のルートページの一つ上の階層に新たなルートページを作ることで、ツリー構造に新しい階層を加えます。
B-Treeインデックスは、MVCCの下で同じ論理テーブル行の複数の現存するバージョンが存在する可能性があることを直接認識していません。
インデックスに対して、各タプルは独自のインデックスエントリを必要とする独立したオブジェクトです。
「バージョンチャーン」タプルは蓄積し、クエリ待ち時間とスループットに悪影響を与える可能性があります。
これは通常、個々の更新のほとんどがHOT最適化を適用できないようなUPDATE
の重いワークロードで発生します。
UPDATE
中にあるインデックスによって、カバーされる一つだけの行の値を変更するには、新しいインデックスタプルのセットをいつも必要とします。
テーブル上にある ありとあらゆるインデックスにつき一つです。
具体的には、UPDATE
によって「論理的に変更」されなかったインデックスが含まれることに注意してください。
すべてのインデックスは、テーブル上で最新バージョンを指す後継の物理的なインデックスタプルを必要とします。
各インデックス中のそれぞれの新しいタプルは通常元の「更新された」タプルと短期間共存する必要があります(通常、UPDATE
トランザクションのコミットした直後までです)。
B-Treeインデックスは、ボトムアップインデックスの削除パスの実行によって、バージョンチャーンのインデックスタプルを徐々に削除します。
各削除パスは、予期された「バージョンチャーンのページ分割」に対してトリガーされます。
これは、UPDATE
文によって論理的に変更されてないインデックスだけで発生します。
さもないと、特定のページで使われなくなったバージョンが集中的に蓄積されます。
ある種の実装レベルの発見的手法は、均一のごみインデックスタプルの特定及び削除に失敗する可能がありますが、ページの分割は通常避けることができます(ページ分割もしくは重複排除パスの場合に、リーフページ上の収まらない新しいタプルが入ることの問題が解決します)。
インデックススキャンが(単一の論理行に対して)通過しなければならない最悪の場合のバージョン数は、システム全体の応答性やスループットに重要な影響があります。
ボトムアップインデックス削除パスは、論理行とバージョンを含む定性的な特徴に基づいた単一のリーフページ内の疑わしいごみタプルを対象としています。
これは、一定の定量的なテーブルレベルの閾値が超えられたとき(25.1.6参照)に起動されるautovacuumワーカーによって実行された「トップダウン」インデックスのクリーンアップと対照的です。
B-Treeインデックス内で実行されたすべての削除操作がボトムアップ削除操作とは限りません。
インデックスタプルの削除の異なる分類があります。
それは、単純なインデックスのタプル削除です。
これは、削除が安全であると分かるインデックスタプル(アイテム識別子のLP_DEAD
ビットが既に設定されているタプル)を削除する遅延メンテナンス操作です。
ボトムアップインデックス削除と同様に、単純インデックス削除は分割を回避する方法としてページ分割が予測された時点で実行されます。
単純削除は、最近のインデックススキャンでは影響があるアイテムにLP_DEAD
ビットをセットする際に、ついでに実行できる機会の場合のみに実行されるという意味で、機会主義と言えます。
PostgreSQL 14より前では、B-Treeの削除の種類は単純な削除のみでした。
単純な削除とボトムアップ削除の主な違いは、前者だけがインデックススキャンの動きによって機会を狙って駆動されることに対して、後者だけがインデックスカラムが論理的に変更されないUPDATE
からのバージョンチャーンを具体的に対象とすることです。
ボトムアップインデックス削除は、明確なワークロードによる特定インデックスのすべてのゴミインデックスタプルの掃除の大多数を実行します。
これは、インデックスがカバーするカラムを論理的に変更することが滅多にまたは決してないUPDATE
からの有意なバージョンチャーンに依存するB-Treeインデックスで予想されます。
論理行ごとのバージョン数の平均と最も悪いケースは、対象とされた増分削除パスによって純粋に低く維持することができます。
特定インデックスのディスク上のサイズは、UPDATE
からの一定のバージョンチャーンがあるにも関わらず、ページやブロックが一つも増加することがない可能性が十分にあります。
そのような場合でも、VACUUM
操作(通常、自動バキュームワーカープロセスで実行します)による、徹底的な「一掃」が、テーブルとその各インデックスの共通のクリーンアップの一部として最終的に要求されます。
VACUUM
とは異なり、ボトムアップインデックス削除は最も古いゴミのインデックスタプルがどのくらい経過しているかについて強い保証を提供しません。
テーブルと全てのインデックスの合計によって共通する保守的な切り捨て点より前に、不要になる「浮いているゴミ」インデックスタプルの維持を許可することはできません。
この基本的なテーブルレベルの不変条件は、テーブルのTIDを安全にリサイクルします。
これにより、時間の経過と共に異なる論理行が同じテーブルTIDを再利用することが可能です(ただし、これは存続期間が同じVACUUM
サイクルにまたがる、二つの論理行に同時には発生しません)。
重複とは、同じインデックスで全てのインデックスキー列が少なくとも一つの他のリーフページタプルの該当する列の値と一致する値をもっている、リーフページタプル(テーブルの行を指すタプル)です。 重複タプルは実際によくあります。 オプションの技法「重複排除」が有効にされているとき、B-Treeインデックスは、特別な重複に対する空間効率の良い表現方法を使用できます。
重複排除は重複タプルのグループを定期的に合併して、各グループに対する単一のポスティングリストタプルを形成することで機能します。 この表現方法では列のキー値は一度だけ現れます。 テーブルの行を指すTIDのソートされた配列がこれに続きます。 概して各値(あるいは列値の異なる組み合わせ)が複数回出現する場合に、これは顕著にインデックスの格納サイズを減らします。 問い合わせの遅延も顕著に削減できます。 全体的な問い合わせのスループットも顕著に増加するかもしれません。 インデックスのバキューム処理のオーバーヘッドも顕著に削減されるかもしれません。
B-Tree重複排除は、B-Tree演算子クラスの=
項に従ってNULL値が決して互いに等しくならないとしても、NULL値を含む「重複」に効果的です。
ディスク上のB-Tree構造を解するいかなる実装部分に関しても、NULLはまさにインデックス値の定義域以外の一つの値です。
既存のリーフページに収まらない新たな要素が挿入されたとき、重複排除の処理は怠惰に実行されますが、インデックスタプルの削除は新しいアイテムのための十分なスペースを解放できなかった場合に限ります(通常、削除は簡易に検討した上で無視されます)。 GINのポスティングリストのタプルと違って、B-Treeのポスティングリストのタプルは新たな重複が挿入される度に拡張する必要がありません。それらはリーフページの元の論理内容に対する単なる代替の物理表現にすぎません。 この設計は読み書き混合のワークロードでの性能の一貫性を重視しています。 ほとんどのクライアントアプリケーションは重複排除を使うことで少なくとも控えめな性能の恩恵を確認することができるでしょう。
CREATE INDEX
とREINDEX
は、使用する手順が若干異なりますが、ポスティングリストタプルを作って重複排除を適用します。
テーブルから取得されてソートされた入力で遭遇した重複した通常タプルの各グループは、現在のペンディングリーフページに追加される前に、ポスティングリストタプルにマージされます。
個別のポスティングリストタプルには、可能な限り多数のTIDが詰め込まれます。
リーフページは、重複排除用の別パスではなく、通常の方法で書き出されます。
この戦略はCREATE INDEX
とREINDEX
に良く適合します。これらは1回で終わるバッチ操作であるからです。
インデックスの値に重複が無いか殆ど無いために重複排除から利益を得られない、書き込みの多いワークロードには、(重複排除が明示的に無効化されて居ない限り)固定のペナルティによる小さい負荷増があります。
deduplicate_items
格納パラメータは個別のインデックス内で重複排除を無効化するのに使うことができます。
ポスティングリストタプルの読み込みは少なくとも通常タプル表現の読み込み程度に効率的であるため、読み込みのみのワークロードで性能ペナルティは一切ありません
通常は重複排除を無効化することは有益ではありません。
一意性インデックス(や一意制約)が重複排除に使用できる場合があります。 これにより、リーフページは余分なバージョンチャーンの重複を一時的に「吸収」することができます。 一意性インデックス内の重複排除は、特に時間のかかるトランザクションがガベージコレクションを妨げるスナップショットを保持している場合にボトムアップインデックス削除を増強します。 目的は、ボトムアップインデックス削除の戦略が再び有効になるための時間を稼ぐことです。 一つの時間のかかるトランザクションが自然に消えるまでページ分割を遅らせることで、以前の削除パスが失敗した場所でボトムアップ削除パスを成功することができます。
一意性インデックスで重複排除パスを実行すべきかどうかの判断には、特別なヒューリスティックが適用されます。
これは、しばしばリーフページ分割まで連続してスキップして、無益な重複排除パスでの無駄なサイクルによる性能ペナルティを回避できます。
重複排除のオーバーヘッドを懸念するなら、選択的に設定deduplicate_items = off
を検討してください。
一意性インデックスでは重複排除を無効にすることに不都合はありません。
実装レベルの制限により、重複排除は全ての場合に使えるわけではありません。
重複排除の安全性はCREATE INDEX
あるいはREINDEX
が実行されたときに決定されます。
等しいデータの間で意味的に明らかな違いを伴う以下の場合には、重複排除は安全でないと見做されて使用できないことに注意してください。
非決定的な照合順序が使われているときtext
、varchar
、および、char
は重複排除を使えません。
等しいデータの間で大文字小文字やアクセントの違いが維持されなければなりません。
numeric
は重複排除を使えません。
等しいデータの間で数の表示スケールが維持されなければなりません。
jsonb
のB-Tree演算子クラスは内部的にnumeric
を使っているため、jsonb
は重複排除を使えません。
float4
およびfloat8
は重複排除を使えません。
これらの型は-0
と0
に異なる表現を持ち、にもかかわらずこれらは等しいと見做されます。
この違いは維持されなければなりません。
さらに以下の実装レベルの制限があります。これはPostgreSQLの将来バージョンで解消されるかもしれません。
コンテナ型(複合型、配列型、あるいは、範囲型など)は、重複排除を使えません。
さらに以下の実装レベルの制限があります。これは使われている演算子クラスや照合順序にかかわりなく該当します。
INCLUDE
インデックスには重複排除は使えません。