B-Treeインデックス。btgettuple()。検索時に使われる関数のざっくりとした概要

DB PostgreSQL

backend/access/nbtree/READMEを読んでもよくわからなかったので先にコードを追うことにした。bt_first()の前半部分はとりあえずとばして後半部分を眺めていたら最初よりはずいぶん見通しが良くなってきた。

  • index_getnext()
    • IndexScanDesc.xs_ctup.t_self には検索対象のタプルID（実テーブルの行へのポインタ）が入っている。これを使ってタプルを取得している。HOTに関するチェーンをタグって対象とすべきタプルを判定しているのもここ。
  • btgettuple()
    • タプル1件を取得する処理。1度のインデックススキャンに複数回呼ばれるはず（1件しかヒットしない場合は2回目でNULLを返す）。1度目と2度目以降で呼び出す関数が異なる。1度目は_bt_first()、2度目以降は_bt_next()。
  • _bt_first()
    • BTScanPosData構造体に詰まった1件目のタプルIDをIndexScanDesc.xs_ctup.t_selfにセット。
  • _bt_next()
    • BTScanPosData構造体に詰まった2件目のタプルIDをIndexScanDesc.xs_ctup.t_selfにセット。
  • _bt_search()
    • ルートのページからリーフのページへと下降しながらインデックスのキーが含まれるバッファを探している。
  • _bt_relandgetbuf()
    • インデックスのキーが含まれるバッファを取得。さらに奥のほうではバッファにのっていなかったらディスクから読むとかしている。
  • _bt_binsrch()
    • インデックスのキーを含むページ内をバイナリサーチしてキーに一致する最初のItemのオフセットを求める。
  • _bt_readpage()
    • キーに一致したItemのオフセットを開始位置としてページ内のキーに一致するItemすべてを読む。一致したものはBTScanPosData構造体とBTScanPosItem構造体に詰める。
  • _bt_checkkeys()
    • Itemがインデックスのキーと一致するかどうかチェックする。
  • BTScanPosData構造体
    • インデックススキャンでヒットしたインデックスのページに関する情報をもつ。BTScanPosItem構造体の配列を持つ。1ページで複数ヒットする場合が考慮されている。
  • BTScanPosItem構造体
    • インデックスから参照されるヒープ（テーブル）のタプルIDとインデックスのページ内におけるインデックスのItemのオフセットを持つ。

ポイント

  • 実テーブルのタプルにアクセスするのはindex_getnext()。ここより下の関数ではインデックスが管理するタプルIDを特定の場所にセットすることを担当し、index_getnext()はセットされたタプルIDを使うことを担当。
  • _bt_readpage()で、ページ内のItemを一度に全部読み取ってしまっている。これはシーケンシャルスキャンのとき（heapgetpage()）と同じかんじ。