B-Treeインデックス。btbeginscan()

DB PostgreSQL

インデックスアクセスメソッドのインタフェース定義というものがあり、インデックスの実装を抽象化している。「select * from pg_am」とすれば、インデックスの種類ごとのインタフェースを実装した関数の名前がわかる。
B-Treeインデックスの場合、次のもの。

  • btinsert
  • btbeginscan
  • btgettuple
  • btgetmulti
  • btrescan
  • btendscan
  • btmarkpos
  • btrestrpos
  • btbuild
  • btbulkdelete
  • btvacuumcleanup
  • btcostestimate

これらを中心に見れば、B-Treeインデックスがやっていることがわかるはず。この前は、btgettuple()あたりを見た。今回は、名前からしてインデックススキャンが始まるときに呼ばれるbtbeginscan()を見てみる。

GDBを使ってしらべた呼び出しシーケンス（抜粋）。

(gdb) bt
#0  btrescan (fcinfo=0xbfb657e0) at nbtree.c:363
#1  0x0831df38 in FunctionCall2 (flinfo=0x84e1d30, arg1=139420248, arg2=139420120) at fmgr.c:1279
#2  0x080a840e in index_rescan (scan=0x84f6258, key=0x84f61d8) at indexam.c:321
#3  0x080a7e5e in RelationGetIndexScan (indexRelation=0xb5600938, nkeys=1, key=0x84f61d8) at genam.c:106
#4  0x080aeef8 in btbeginscan (fcinfo=0xbfb65a90) at nbtree.c:352
#5  0x0831dff8 in FunctionCall3 (flinfo=0x84e1ce8, arg1=3042969912, arg2=1, arg3=139420120) at fmgr.c:1304
#6  0x080a830e in index_beginscan_internal (indexRelation=0xb5600938, nkeys=1, key=0x84f61d8) at indexam.c:281
#7  0x080a8208 in index_beginscan (heapRelation=0xb55fee28, indexRelation=0xb5600938, snapshot=0x84e2d18, nkeys=1, key=0x84f61d8) at indexam.c:222
#8  0x081a1adb in ExecInitIndexScan (node=0x84f3fd8, estate=0x84f5748, eflags=0) at nodeIndexscan.c:592
#9  0x0818f077 in ExecInitNode (node=0x84f3fd8, estate=0x84f5748, eflags=0) at execProcnode.c:169
#10 0x0818c11a in InitPlan (queryDesc=0x84e2d40, eflags=0) at execMain.c:666
#11 0x0818b890 in ExecutorStart (queryDesc=0x84e2d40, eflags=0) at execMain.c:200
#12 0x0824e4b7 in PortalStart (portal=0x84d9cb0, params=0x0, snapshot=0x0) at pquery.c:528
#13 0x082492e2 in exec_simple_query (query_string=0x84ac870 select * from accounts where aid = 100) at postgres.c:949

btbeginscan()は、最終的にbtrescan()を呼び出しているので、btrescan()までのシーケンスを確認。btrescan()は単独でも呼ばれる。単独で呼ばれるのはドキュメントを見る限りだとネステッドループ結合のときのよう。


主な関数は以下のとおり。indexam.cの関数はインデックス実装の関数に対するファサードのようなものなので以下には含めていない。

  • btrescan()
    • IndexScanDescから参照されるBTScanOpaqueを初期化する。BTScanOpaqueはインデックスアクセスメソッドのプライベートな情報を格納する（どこまでヒットしたとか）。killedItemsとかmarkPosとかのメンバの役割がよくわからない。
  • RelationGetIndexScan()
    • IndexScanDescを作成する。IndexScanDescは、ヒープのリレーションやインデックスのリレーション情報、スナップショット、インデックスに対応するヒープのタプルに関する情報などをもつ。
  • btbeginscan()
    • IndexScanDescを返す。
  • ExecInitIndexScan()
    • IndexScanStateを作成する。IndexScanStateはPlanStateのサブタイプ相当。実行計画のノードIndexScanに対応する実行時のノード。インデックススキャン実行時の状態を管理する構造体。クエリの実行全体の状態は、EStateという構造体で管理し、実行を表す木構造の各ノードでは、それに対応する構造体（ここではIndexScanState）で管理するというしくみになっているように見える。
    • ヒープのリレーションやインデックスのリレーションをオープン。
    • ExecIndexBuildScanKeys()を呼び出しScanKeyを作成する。
      • 実行計画の情報を見て、定数との比較なのか、定数以外との比較なのか、列との比較なのか、配列との比較なのか、NULLとの比較なのかが考慮される。