PostgreSQLのB-Treeインデックスドキュメントを読む
hmarui66ドキュメント
hmarui6667.4.1. B-Treeの構造
PostgreSQLのB-Treeインデックスは複数階層のツリー構造で、ツリーの各階層はページの双方向連結リストとして使用できます。
b-link tree だから right link のみかと思っていたけど、双方向。
一つのメタページがインデックスの最初のセグメントファイルの固定位置に格納されます。
メタ情報が1ページ目に配置される。
それ以外の全てのページはリーフページか内部ページのいずれかです。 リーフページはツリーの最下階層にあるページです。 各リーフページはテーブルの行を指すタプルを含みます。
「行を指すタプル」の「行」はヒープタプルで、「指す」のは(ヒープ)タプルIDだとすると、「行を指すタプル」というのはヒープタプルIDを保持するインデックス上でのvalueのこと？
各内部ページはツリーの次の下位層を指すタプルを含みます。 典型的には、全ページの99％以上がリーフページです。 内部ページとリーフページは共に、73.6に記載されている標準のページ書式を使用します。
下位層を指す情報を持つのも「タプル」と呼ばれる。
「標準のページ書式」は 図 73.1で図示されている。
図の「Item」に上記の「タプル」が配置されるということのはず。
既存リーフページがやってくるタプルをはめ込むことができないとき、新たなリーフページがB-Treeインデックスに追加されます。 ページ分割操作は一部のアイテムを新ページに動かすことで、当初は溢れているページに属していたアイテムのために空間を作ります。 ページ分割は、また、新ページへの新たなダウンリンクを親ページに挿入しなければなりません。これは親ページの分割を同様に引き起こすかもしれません。 ページは分割は再帰的に「上向きに連鎖」します。 最終的にルートページが新たなダウンリンクをはめ込みできないときには、ルートページ分割が実施されます。 これは元のルートページの一つ上の階層に新たなルートページを作ることで、ツリー構造に新しい階層を加えます。
この辺は一般的な B-Tree 実装の話。
hmarui6667.4.2. ボトムアップインデックスの削除
B-Treeインデックスは、MVCCの下で同じ論理テーブル行の複数の現存するバージョンが存在する可能性があることを直接認識していません。
インデックス自体も MVCC で扱うことは一般的ではない、という話は聞いたことある。理由はいまいちわかってない。
インデックスに対して、各タプルは独自のインデックスエントリを必要とする独立したオブジェクトです。
ここでいう「タプル」はヒープタプルのことを指していそう。更新によってヒープタプルが追加されると、そのヒープタプルを指すインデックスエントリが必要になる。
ここでいう「インデックスエントリ」が何を指すかはこの時点では分からないが、おそらく「ヒープタプルIDを保持するタプル」のことだと思われる。
ただ、そうすると同一キーに対して複数のインデックスエントリが存在することになり、キーの重複を許可するインデックスになる？
「バージョンチャーン」タプルは蓄積し、クエリ待ち時間とスループットに悪影響を与える可能性があります。
「バージョンチャーン」は "version churn" と書く。追記型の PostgreSQL においては Update 時の論理削除 & 挿入によって発生する、複数バージョンのことを意味するはず。
これは通常、個々の更新のほとんどがHOT最適化を適用できないようなUPDATEの重いワークロードで発生します。
HOT(Heap Only Tuple)最適化は更新対象がインデックスが参照するカラム以外で、かつ更新後も行が元のページに収まる場合に実施される最適化。
新しいインデックスエントリは必要無く、更新された行の古いバージョンは、VACUUMではなく SELECT など通常の操作中に削除可能。
hmarui66UPDATE中にあるインデックスによって、カバーされる一つだけの行の値を変更するには、
原文は "Changing the value of only one column covered by one index during an UPDATE" となっている。ある一つのインデックスによってカバー(参照?)される一つのカラムのみの値を更新する場合、という意味の模様。
新しいインデックスタプルのセットをいつも必要とします。 テーブル上にある ありとあらゆるインデックスにつき一つです。
ヒープタプルの新しいバージョンを指すように該当テーブルのインデックス全てに反映する必要がある。
具体的には、UPDATEによって「論理的に変更」されなかったインデックスが含まれることに注意してください。 すべてのインデックスは、テーブル上で最新バージョンを指す後継の物理的なインデックスタプルを必要とします。
「論理的に変更されなかった」というのはインデックスが参照する列は更新対象ではなかったケース。それでも新しいヒープタプルを指すように反映が必要。
各インデックス中のそれぞれの新しいタプルは通常元の「更新された」タプルと短期間共存する必要があります（通常、UPDATEトランザクションのコミットした直後までです）。
古いヒープタプルを参照し得るトランザクションが残っている限り、インデックス中の該当のヒープタプルIDを保持するエントリも残される、ということ？
B-Treeインデックスは、ボトムアップインデックスの削除パスの実行によって、バージョンチャーンのインデックスタプルを徐々に削除します。
この節の本題である「ボトムアップインデックスの削除」。
各削除パスは、予期された「バージョンチャーンのページ分割」に対してトリガーされます。 これは、UPDATE文によって論理的に変更されてないインデックスだけで発生します。
どう予期するのかは不明。UPDATE対象のカラムを参照していないインデックスで、新たなヒープタプルを指すためだけにインデックスエントリが追加されるもの、ということのはず。
さもないと、特定のページで使われなくなったバージョンが集中的に蓄積されます。
さもないと、が掛かっている事が分かりづらいが、ここて説明されている削除パスを通らないと、ということだと解釈。
ある種の実装レベルの発見的手法は、均一のごみインデックスタプルの特定及び削除に失敗する可能がありますが、ページの分割は通常避けることができます（ページ分割もしくは重複排除パスの場合に、リーフページ上の収まらない新しいタプルが入ることの問題が解決します）。
これは非常に分かりづらいが、原文は "A page split will usually be avoided, though it's possible that certain implementation-level heuristics will fail to identify and delete even one garbage index tuple"
となっていて、通常はsplitは避けられるが、ヒューリスティクスな方法では削除対象のインデックスエントリを1つも見つけられない可能性がある、という意味になりそう。
インデックススキャンが（単一の論理行に対して）通過しなければならない最悪の場合のバージョン数は、システム全体の応答性やスループットに重要な影響があります。
全てのバージョンのヒープタプルを見に行くことになるので、影響がある。
ボトムアップインデックス削除パスは、論理行とバージョンを含む定性的な特徴に基づいた単一のリーフページ内の疑わしいごみタプルを対象としています。
〜特徴に基づいた、が良く分からないが対象は単一のリーフページということ。
原文は "... a single leaf page based on qualitative distinctions involving logical rows and versions." なので、論理行とそのバージョンによる質的な区別に基づいて…、という感じか。
これは、一定の定量的なテーブルレベルの閾値が超えられたとき（25.1.6参照）に起動されるautovacuumワーカーによって実行された「トップダウン」インデックスのクリーンアップと対照的です。
単一のリーフページを対象にsplitが起こり得る時にバージョンチャーンによってゴミが溜まっている可能性がある時にトリガーされるので、ボトムアップとなる。
hmarui66注記
B-Treeインデックス内で実行されたすべての削除操作がボトムアップ削除操作とは限りません。 インデックスタプルの削除の異なる分類があります。 それは、単純なインデックスのタプル削除です。 これは、削除が安全であると分かるインデックスタプル(アイテム識別子のLP_DEADビットが既に設定されているタプル)を削除する遅延メンテナンス操作です。 ボトムアップインデックス削除と同様に、単純インデックス削除は分割を回避する方法としてページ分割が予測された時点で実行されます。
インデックスエントリの削除方式は他にもあり、インデックスをスキャン時に参照されることがないと判明したらビットを立てておいて回収する方式もある。
いつ回収されるかは不明。
単純削除は、最近のインデックススキャンでは影響があるアイテムにLP_DEADビットをセットする際に、ついでに実行できる機会の場合のみに実行されるという意味で、機会主義と言えます。 PostgreSQL 14より前では、B-Treeの削除の種類は単純な削除のみでした。 単純な削除とボトムアップ削除の主な違いは、前者だけがインデックススキャンの動きによって機会を狙って駆動されることに対して、後者だけがインデックスカラムが論理的に変更されないUPDATEからのバージョンチャーンを具体的に対象とすることです。