★PostgreSQLカンファレンス2021 11月12日開催/チケット販売中★
他のバージョンの文書 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

63.4. 実装

本節では、上級ユーザに役立つかもしれない、B-Treeインデックスの実装の詳細について説明します。 更なる詳細、B-Tree実装の内部に焦点をあてた記述については、ソース配布物のsrc/backend/access/nbtree/READMEを参照してください。

63.4.1. B-Treeの構造

PostgreSQLのB-Treeインデックスは複数階層のツリー構造で、ツリーの各階層はページの双方向連結リストとして使用できます。 一つのメタページがインデックスの最初のセグメントファイルの固定位置に格納されます。 それ以外の全てのページはリーフページか内部ページのいずれかです。 リーフページはツリーの最下階層にあるページです。 各リーフページはテーブルの行を指すタプルを含みます。 各内部ページはツリーの次の下位層を指すタプルを含みます。 典型的には、全ページの99%以上がリーフページです。 内部ページとリーフページは共に、68.6に記載されている標準のページ書式を使用します。

既存リーフページがやってくるタプルをはめ込むことができないとき、新たなリーフページがB-Treeインデックスに追加されます。 ページ分割操作は一部のアイテムを新ページに動かすことで、当初は溢れているページに属していたアイテムのために空間を作ります。 ページ分割は、また、新ページへの新たなダウンリンクを親ページに挿入しなければなりません。これは親ページの分割を同様に引き起こすかもしれません。 ページは分割は再帰的に上向きに連鎖します。 最終的にルートページが新たなダウンリンクをはめ込みできないときには、ルートページ分割が実施されます。 これは元のルートページの一つ上の階層に新たなルートページを作ることで、ツリー構造に新しい階層を加えます。

63.4.2. 重複排除

重複とは、同じインデックスで全てのインデックスキー列が少なくとも一つの他のリーフページタプルの該当する列の値と一致する値をもっている、リーフページタプル(テーブルの行を指すタプル)です。 重複タプルは実際によくあります。 オプションの技法「重複排除」が有効にされているとき、B-Treeインデックスは、特別な重複に対する空間効率の良い表現方法を使用できます。

重複排除は重複タプルのグループを定期的に合併して、各グループに対する単一のポスティングリストタプルを形成することで機能します。 この表現方法では列のキー値は一度だけ現れます。 テーブルの行を指すTIDのソートされた配列がこれに続きます。 概して各値(あるいは列値の異なる組み合わせ)が複数回出現する場合に、これは顕著にインデックスの格納サイズを減らします。 問い合わせの遅延も顕著に削減できます。 全体的な問い合わせのスループットも顕著に増加するかもしれません。 インデックスのバキューム処理のオーバーヘッドも顕著に削減されるかもしれません。

注記

B-Tree重複排除は、B-Tree演算子クラスの=項に従ってNULL値が決して互いに等しくならないとしても、NULL値を含む重複に効果的です。 ディスク上のB-Tree構造を解するいかなる実装部分に関しても、NULLはまさにインデックス値の定義域以外の一つの値です。

既存のリーフページにはめ込みできない新たな要素が挿入されたとき、重複排除の処理は怠惰に実行されます。 これはリーフページの分割を防止(あるいは少なくとも遅延)します。 GINのポスティングリストのタプルと違って、B-Treeのポスティングリストのタプルは新たな重複が挿入される度に拡張する必要がありません。それらはリーフページの元の論理内容に対する単なる代替の物理表現にすぎません。 この設計は読み書き混合のワークロードでの性能の一貫性を重視しています。 ほとんどのクライアントアプリケーションは重複排除を使うことで少なくとも控えめな性能の恩恵を確認することができるでしょう。

CREATE INDEXREINDEXは、使用する手順が若干異なりますが、ポスティングリストタプルを作って重複排除を適用します。 テーブルから取得されてソートされた入力で遭遇した重複した通常タプルの各グループは、現在のペンディングリーフページに追加される前に、ポスティングリストタプルにマージされます。 個別のポスティングリストタプルには、可能な限り多数のTIDが詰め込まれます。 リーフページは、重複排除用の別パスではなく、通常の方法で書き出されます。 この戦略はCREATE INDEXREINDEXに良く適合します。これらは1回で終わるバッチ操作であるからです。

インデックスの値に重複が無いか殆ど無いために重複排除から利益を得られない、書き込みの多いワークロードには、(重複排除が明示的に無効化されて居ない限り)固定のペナルティによる小さい負荷増があります。 deduplicate_items格納パラメータは個別のインデックス内で重複排除を無効化するのに使うことができます。 ポスティングリストタプルの読み込みは少なくとも通常タプル表現の読み込み程度に効率的であるため、読み込みのみのワークロードで性能ペナルティは一切ありません 通常は重複排除を無効化することは有益ではありません。

B-Treeインデックスは、MVCC下で同じ論理テーブル行が複数バージョン存在していることを、直接には認識していません。 インデックスにとっては、各タプルは自身のインデックスエントリを必要とする独立したオブジェクトです。 バージョン重複は時に積み重なって問い合わせのレイテンシとスループットに不利に作用するかもしれません。 これは典型的には、(しばしば一つ以上のインデックス列が変更されて、新たなインデックスタプルバージョンの一式 — それぞれのインデックスに対するもの、の設置が必要となるために)大部分の各更新がHOTを適用できないUPDATEが重たいワークロードで発生します。 実際のところ、B-Treeの重複排除はバージョンの大量発生によるインデックス膨張を改善します。 一意インデックスのタプルであっても、バージョン重複のため、ディスクに格納されるときに物理的に一意とは限らないことに注意してください。 重複排除の最適化は一意性インデックス内に選択的に適用されます。 バージョン重複を持つと見られるページが対象となります。 高位の目標は、起こりうるバージョン大量発生によって生じる不要なページ分割の前により多くVACUUM実行を施すことです。

ヒント

一意性インデックスで重複排除パスを実行すべきかどうかの判断には、特別なヒューリスティックが適用されます。 これは、しばしばリーフページ分割まで連続してスキップして、無益な重複排除パスでの無駄なサイクルによる性能ペナルティを回避できます。 重複排除のオーバーヘッドを懸念するなら、選択的に設定deduplicate_items = offを検討してください。 一意性インデックスでは重複排除を無効にすることに不都合はありません。

実装レベルの制限により、重複排除は全ての場合に使えるわけではありません。 重複排除の安全性はCREATE INDEXあるいはREINDEXが実行されたときに決定されます。

等しいデータの間で意味的に明らかな違いを伴う以下の場合には、重複排除は安全でないと見做されて使用できないことに注意してください。

  • 非決定的な照合順序が使われているときtextvarchar、および、charは重複排除を使えません。 等しいデータの間で大文字小文字やアクセントの違いが維持されなければなりません。

  • numericは重複排除を使えません。 等しいデータの間で数の表示スケールが維持されなければなりません。

  • jsonbのB-Tree演算子クラスは内部的にnumericを使っているため、jsonbは重複排除を使えません。

  • float4およびfloat8は重複排除を使えません。 これらの型は-00に異なる表現を持ち、にもかかわらずこれらは等しいと見做されます。 この違いは維持されなければなりません。

さらに以下の実装レベルの制限があります。これはPostgreSQLの将来バージョンで解消されるかもしれません。

  • コンテナ型(複合型、配列型、あるいは、範囲型など)は、重複排除を使えません。

さらに以下の実装レベルの制限があります。これは使われている演算子クラスや照合順序にかかわりなく該当します。

  • INCLUDEインデックスには重複排除は使えません。