B-Treeインデックス。btinsert()。ページの分割が不要な場合

DB PostgreSQL

インデックスの追加のときに呼ばれるbtinsert()を見てみる。btinsert()はINSERTやUPDATEやCOPYの処理で呼ばれることがある。概要はインタフェースであるaminsertのところをみるとわかる。インデックスアクセスメソッド関数。

呼び出しシーケンス(抜粋)はこんな感じ。

(gdb) bt
#0  PageAddItem (page=0xb5904260 "", item=0x84de9e8 "", size=12, offsetNumber=6, overwrite=0 '\0', is_heap=0 '\0') at bufpage.c:126
#1  0x080abf67 in _bt_pgaddtup (rel=0xb563cd78, page=0xb5904260 "", itemsize=12, itup=0x84de9e8, itup_off=6, where=0x834d542 "page") at nbtinsert.c:1836
#2  0x080aa20f in _bt_insertonpg (rel=0xb563cd78, buf=201, stack=0x0, itup=0x84de9e8, newitemoff=6, split_only_page=0 '\0') at nbtinsert.c:650
#3  0x080a97a0 in _bt_doinsert (rel=0xb563cd78, itup=0x84de9e8, index_is_unique=0 '\0', heapRel=0xb563db38) at nbtinsert.c:155
#4  0x080aec56 in btinsert (fcinfo=0xbfe35460) at nbtree.c:225
#5  0x0831e286 in FunctionCall6 (flinfo=0x8528b68, arg1=3043216760, arg2=3219347220, arg3=3219347188, arg4=139323724, arg5=3043220280, arg6=0) at fmgr.c:1392
#6  0x080a81d9 in index_insert (indexRelation=0xb563cd78, values=0xbfe35714, isnull=0xbfe356f4 "", heap_t_ctid=0x84de94c, heapRelation=0xb563db38, check_uniqueness=0 '\0') at indexam.c:195
#7  0x08199cd8 in ExecInsertIndexTuples (slot=0x84de5e0, tupleid=0x84de94c, estate=0x84de3f8, is_vacuum=0 '\0') at execUtils.c:1080
#8  0x0818d7de in ExecInsert (slot=0x84de5e0, tupleid=0x0, planSlot=0x84de5e0, dest=0x84ad820, estate=0x84de3f8) at execMain.c:1645
#9  0x0818d500 in ExecutePlan (estate=0x84de3f8, planstate=0x84de6a0, operation=CMD_INSERT, numberTuples=0, direction=ForwardScanDirection, dest=0x84ad820) at execMain.c:1485
#10 0x0818b98c in ExecutorRun (queryDesc=0x852a3b8, direction=ForwardScanDirection, count=0) at execMain.c:270
#11 0x0824ddce in ProcessQuery (plan=0x84ad7b0, params=0x0, dest=0x84ad820, completionTag=0xbfe35aca "") at pquery.c:179
#12 0x0824f248 in PortalRunMulti (portal=0x85069d0, isTopLevel=1 '\001', dest=0x84ad820, altdest=0x84ad820, completionTag=0xbfe35aca "") at pquery.c:1242
#13 0x0824ea27 in PortalRun (portal=0x85069d0, count=2147483647, isTopLevel=1 '\001', dest=0x84ad820, altdest=0x84ad820, completionTag=0xbfe35aca "") at pquery.c:813
#14 0x0824939c in exec_simple_query (query_string=0x84ac870 "insert into foo values (5);") at postgres.c:986

以下、処理順で。

  • ExecInsertIndexTuples()
    • heap_insert()の後、タプルが追加されるリレーションにインデックスが存在する場合に呼び出される。HOTでないときはheap_update()の後でも呼び出される。
    • インデックスの数だけindex_insert()を呼び出す。read onlyなインデックスかどうかのチェック、部分インデックスの場合対象範囲に収まるかどうかのチェック、インデックスのキーデータの抽出などを行っている。read onlyなインデックスって？
  • btinsert()
    • IndexTupleを作って_bt_doinsert()を呼び出す。IndexTupleはインデックスのページに追加されるタプル。IndexTupleはデータ部にインデックスのキーをもちヒープのTIDを指す。
  • _bt_doinsert()
    • ScanKeyを作成する。
    • _bt_search()を呼び出し作成したScanKeyを使ってScanKeyを含むページをルートからリーフへたどって探す。このときたどったページをスタックにつんでおく。
    • 他プロセスによってページが分割されたかもということで_bt_moveright()を呼び出し対応。
    • ユニークインデックスの場合は一意性を確認する処理が入っている。ロックに関する操作を行っているよう。詳しくは見ていない。
    • _bt_findinsertloc()を呼び出して、ページのどの部分に追加すべきかを調べる。空きがある場合は、バイナリサーチで適切な場所を探す。空きがない場合はそのページだけVACUUMEしたり、隣のページを探したりがんばる。
    • これまでの情報を元に_bt_insertonpg()を呼び出してページに追加する。
  • _bt_insertonpg()
    • ページに入りきらないときは分割。_bt_findinsertloc()でどうしても空きが探せないときに分割？分割の処理は_bt_findsplitloc()、_bt_split()で行われ、親との関連付けは_bt_insert_parent()で行われる。
    • ページに入る場合は_bt_pgaddtup()を呼び出す。
    • WALの作成。
  • _bt_pgaddtup()
    • 不要な情報を取り除いてPageAddItem()。
  • PageAddItem()
    • 実際に追加。
    • タプルがすでに存在しているところに追加されるならそれ以降を後ろに1つずつずらす。

課題

  • ロックについていろいろ考慮されているよう。だけどそこまでは把握できていないなぁ。ロックについてはもうちょっと余裕ができてから。
  • read onlyなインデックスって何？
  • 次はページの分割が起こる場合をもう少し詳しく見てみたい。