B-Treeインデックス。btbuild()。インデックスのタプルを一時領域に格納するまで

DB PostgreSQL

インデックスの構築のときに呼ばれるbtbuild()を見てみる。btbuild()はCREATE INDEXとかインデックスの再構築で呼ばれる。概要はインタフェースであるambuildのところをみるとわかる。インデックスアクセスメソッド関数。

今回は、CREATE INDEXしたときを確かめる。すでにデータがある場合の動きを見てみたいのでINSERTしてからCRATE INDEXする。

create table hoge (id integer, name varchar(10));
insert into hoge values (1, 'aaa');
create index hoge_ix on hoge (name);

GDBでの呼び出しシーケンス（抜粋）。

(gdb) bt
#0  btbuildCallback (index=0xb55a9ba8, htup=0x84e32d4, values=0xbf87bc60, isnull=0xbf87bc40 "", tupleIsAlive=1 '\001', state=0xbf87bd48) at nbtree.c:199
#1  0x080eb2db in IndexBuildHeapScan (heapRelation=0xb55a6dc8, indexRelation=0xb55a9ba8, indexInfo=0x84e1708, callback=0x80aeb1f <btbuildCallback>, callback_state=0xbf87bd48) at i\
ndex.c:1784
#2  0x080aea9e in btbuild (fcinfo=0xbf87bd98) at nbtree.c:120
#3  0x0831e7cc in OidFunctionCall3 (functionId=338, arg1=3042602440, arg2=3042614184, arg3=139335432) at fmgr.c:1585
#4  0x080eab64 in index_build (heapRelation=0xb55a6dc8, indexRelation=0xb55a9ba8, indexInfo=0x84e1708, isprimary=0 '\0') at index.c:1366
#5  0x080ea1e4 in index_create (heapRelationId=24686, indexRelationName=0x84e1630 "hoge_ix", indexRelationId=24689, indexInfo=0x84e1708, accessMethodObjectId=403, tableSpaceId=0, \
classObjectId=0x84e3288, coloptions=0x84e36b8, reloptions=0, isprimary=0 '\0', isconstraint=0 '\0', allow_system_table_mods=0 '\0', skip_build=0 '\0', concurrent=0 '\0') at index.\
c:843
#6  0x0814fd53 in DefineIndex (heapRelation=0x84e1578, indexRelationName=0x84e1630 "hoge_ix", indexRelationId=0, accessMethodName=0x84e1650 "btree", tableSpaceName=0x0, attributeL\
ist=0x84e1408, predicate=0x0, options=0x0, unique=0 '\0', primary=0 '\0', isconstraint=0 '\0', is_alter_table=0 '\0', check_rights=1 '\001', skip_build=0 '\0', quiet=0 '\0', concu\
rrent=0 '\0') at indexcmds.c:443
#7  0x08251053 in ProcessUtility (parsetree=0x84ad858, queryString=0x84ace98 "--create table hoge (id integer, name varchar(10));\n--insert into hoge values (1, 'aaa');\ncreate in\
dex hoge_ix on hoge (name);\n\n", params=0x0, isTopLevel=1 '\001', dest=0x84ad8c8, completionTag=0xbf87c50a "") at utility.c:919
#8  0x0824f150 in PortalRunUtility (portal=0x84d9fb8, utilityStmt=0x84ad858, isTopLevel=1 '\001', dest=0x84ad8c8, completionTag=0xbf87c50a "") at pquery.c:1173
#9  0x0824f2c2 in PortalRunMulti (portal=0x84d9fb8, isTopLevel=1 '\001', dest=0x84ad8c8, altdest=0x84ad8c8, completionTag=0xbf87c50a "") at pquery.c:1266
#10 0x0824ea27 in PortalRun (portal=0x84d9fb8, count=2147483647, isTopLevel=1 '\001', dest=0x84ad8c8, altdest=0x84ad8c8, completionTag=0xbf87c50a "") at pquery.c:813
#11 0x0824939c in exec_simple_query (query_string=0x84ace98 "--create table hoge (id integer, name varchar(10));\n--insert into hoge values (1, 'aaa');\ncreate index hoge_ix on ho\
ge (name);\n\n") at postgres.c:986
  • btbuildCallback()
    • ヒープのタプルからインデックスのタプルを作成し、BTSpoolという構造体に一旦格納する。BTSpoolに入れられたインデックスのタプルは、後でソートされてインデックスのページに入れられる。
  • IndexBuildHeapScan()
    • ヒープをスキャンして、1タプルずつbtbuildCallback()に送る。btbuildCallback()に送る前には、有効なタプルかどうか（可視性がOKか）のチェックもしている。HOTの場合はルートのタプルだけを対象にしている？
  • btbuild()
    • 主な処理は2つ。1つは、IndexBuildHeapScan()を呼び出してインデックスのタプルを一時領域（閾値を超えるまではメモリ、超えたらディスク）に置く。2つ目は、_bt_leafbuild()を呼んで、一時領域のデータをソートしながらB-Treeを実際に作成する。
  • index_build()
    • 壊れているかもしれないHOTなタプルを考慮したり、カタログ情報を更新したり。
  • index_create()
    • ヒープのリレーションのオープン、インデックスのリレーションの作成、各種エラーチェック、カタログの更新など。
  • DefineIndex()
    • CRATE INDEXにほぼそのまま対応する処理のよう。細かくは見ていない。


実際にB-Treeを作成する_bt_leafbuild()より下位の処理については次回以降。

所感

  • tuplesort.cがタプルをソートする処理だが、データが少なければメモリで多ければディスクへ退避してということをやっているみたい。インデックスのとき専用というわけではなく汎用的なものとして用意されている。ORDER BYとかJOINとかでも使われるんだろうな。