B-Treeインデックス。pg_filedumpと検索時の呼び出しシーケンスの確認

DB PostgreSQL

これまでにタプルの追加と削除を軽く見たので、今度はタプルの更新を見てみようと思った。だけど、Heap Only Tuple（HOT）の関係でタプルの更新処理にはインデックスに関するものも出てくる。ということで、先にインデックスを見ることにした（単にインデックスが気になってしかたなかったりもする）。

まずは、テーブルを作る。

create table hoge (id integer primary key, name varchar(10));

主キー付のテーブルを作ると自動でインデックスが作成される。

次に、データを入れる。

insert into hoge values (1, 'aaa');
insert into hoge values (2, 'bbb');

インデックスを格納しているファイルをpg_filedumpしてみる。

Block    1 ********************************************************
<Header> -----
 Block Offset: 0x00002000         Offsets: Lower      32 (0x0020)
 Block: Size 8192  Version    4            Upper    8152 (0x1fd8)
 LSN:  logid      0 recoff 0x006c5844      Special  8176 (0x1ff0)
 Items:    2                      Free Space: 8120
 TLI: 0x0001  Prune XID: 0x00000000  Flags: 0x0000 ()
 Length (including item array): 32

<Data> ------
 Item   1 -- Length:   12  Offset: 8164 (0x1fe4)  Flags: NORMAL
  Block Id: 0  linp Index: 1  Size: 12
  Has Nulls: 0  Has Varwidths: 0

 Item   2 -- Length:   12  Offset: 8152 (0x1fd8)  Flags: NORMAL
  Block Id: 0  linp Index: 2  Size: 12
  Has Nulls: 0  Has Varwidths: 0


<Special Section> -----
 BTree Index Section:
  Flags: 0x0003 (LEAF|ROOT)
  Blocks: Previous (0)  Next (0)  Level (0)  CycleId (0)

格納のされ方はタプルがリレーションに格納するのと同じ形式っぽい（Item部分はもちろんちがうけど）。Special Sectionについてはリレーションのときと大きく違う。

インデックススキャンされる次のSQLを実行してGDBでデバッグしてみる。

select * from hoge where id = 1;

インデックスを検索しているっぽいところまでの呼び出しシーケンス（抜粋）は次のとおり。

(gdb) bt
#0  _bt_binsrch (rel=0xb55b30a0, buf=200, keysz=1, scankey=0xbfda1e6c, nextkey=0 '\0') at nbtsearch.c:280
#1  0x080b0cd8 in _bt_first (scan=0x84f4f90, dir=ForwardScanDirection) at nbtsearch.c:862
#2  0x080aed47 in btgettuple (fcinfo=0xbfda2480) at nbtree.c:276
#3  0x0831df38 in FunctionCall2 (flinfo=0x8539e58, arg1=139415440, arg2=1) at fmgr.c:1279
#4  0x080a8750 in index_getnext (scan=0x84f4f90, direction=ForwardScanDirection) at indexam.c:466
#5  0x081a12c2 in IndexNext (node=0x84f47a0) at nodeIndexscan.c:109
#6  0x08197af7 in ExecScan (node=0x84f47a0, accessMtd=0x81a1164 <IndexNext>) at execScan.c:68
#7  0x081a134c in ExecIndexScan (node=0x84f47a0) at nodeIndexscan.c:147
#8  0x0818f44a in ExecProcNode (node=0x84f47a0) at execProcnode.c:338
#9  0x0818d14a in ExecutePlan (estate=0x84f4610, planstate=0x84f47a0, operation=CMD_SELECT, numberTuples=0, direction=ForwardScanDirection, dest=0x8500080) at execMain.c:1335
#10 0x0818b98c in ExecutorRun (queryDesc=0x84cbdb0, direction=ForwardScanDirection, count=0) at execMain.c:270

FunctionCall2という関数が間にはさまっている。PostgreSQLの関数(fuction)を呼び出しをしているということか？何のためにそういうしくみになっているのだろう？任意のインデックスの実装に簡単に切り替えられるようにするため？

コードはまだちょっとしか読めていない。コード読むより先にB-Treeインデックスのアルゴリズムを把握したほうが理解しやすいかもという印象を受けた。