btree index (23)
_bt_binsrch
pageに登録されているデータが1, 2, 3, 3, 3, 3, 3, 7, 8, 9だとすると:
(1)nextkey = falseのとき: item >= scankeyの先頭の位置が検索できる
検索キー 0 1 2 3 4 7 8 9 10 ---------------------------------------------------------------- non leaf 先頭 先頭 1 2 3(末) 3(末) 7 8 9 leaf page 1 1 2 3(先) 7 7 8 9 末尾
(2)nextkey = trueのとき: item > scankeyの先頭の位置が検索できる
検索キー 0 1 2 3 4 7 8 9 10 ---------------------------------------------------------------- non leaf 先頭 1 2 3(末) 3(末) 7 8 9 9 leaf page 1 2 3(先) 7 7 8 9 末尾 末尾
_bt_first (1)
先頭のアイテムを探すために使用できる検索Strategyを決める。使用する検索条件はstartKeysに登録される。
Indexの属性の順番に使用する検索Strategyを決めていく。同一のattnoで複数の検索条件がある場合は'='が優先される。また，検索方向(dir)と反対のStrategyは選択されない。現在注目している属性で使用する検索Strategyが見つからない場合や，検索Strategyに'<'や'>'が選択された場合，次の属性の検索条件は，先頭のアイテムの検索には使わない。
Indexの属性に，(a, b, c)がある場合。
(1)a = 5 and b > 2 and c > 4: a = 5とb > 2を使って先頭のアイテムを探す (2)a = 5 and b >= 2 and c > 4: a = 5とb >= 2とc > 4を使って先頭のアイテムを探す (3)a = 5 and b >= 2 and c < 4: a = 5とb >= 2を使って先頭のアイテムを探す (c < 4はb >= 2の検索方向と逆になるので，使えない) (4)a = 5 and c > 4: a = 5を使って先頭のアイテムを探す (bの検索条件がないので，aの条件のみ使う)
最初に使用できる条件が無い場合，_bt_endpointでleaf pageの先頭または末尾から検索を開始する。
_bt_first (2)
_bt_firstの前半部分で決定した検索Strategyに基づいて，検索方法を決定する。
(1)BTLessStrategyNumber(item < scankey)
nextkeyをfalseにして，最初のitem >= scankeyを探す。
gobackをtrueにして一つ戻ると，item < scankeyの末尾になる。
(2)BTLessEqualStrategyNumber(item <= scankey)
nextkeyをtrueにして，最初のitem > scankeyを探す。
gobackをtrueにして一つ戻ると，item <= scankeyの末尾になる。
(3)BTEqualStrategyNumber(item = scankey)
逆方向にスキャンする場合(leaf pageを左に向かって検索)：
BTLessEqualStrategyNumberと同じにする。
順方向にスキャンする場合(leaf pageを右に向かって検索)：
BTGreaterEqualStrategyNumberと同じにする。
(4)BTGreaterEqualStrategyNumber(item >= scankey)
nextkeyをfalseにして，最初のitem >= scankeyを探す。
(5)BTGreaterStrategyNumber(item > scankey)
nextkeyをtrueにして，最初のitem > scankeyを探す。
_bt_first (3)
- _bt_searchでアイテムがあるかもしれないリーフページを探す。
- _bt_binsrchで最初のアイテムを探す。nextkeyがfalseの場合，item >= scankeyを満たす先頭のアイテムが見つかる。nextkeyがtrueの場合，item > scankeyを満たす先頭のアイテムが見つかる
- gobackがtrueのときは，_bt_stepで1つ前のアイテムに移動する
- gobackがfalseで_bt_binsrchの結果がend-of-pageだった場合，_bt_stepで次のページの先頭のアイテムに移動する。
- _bt_checkkeysで検索条件を満たしているかチェックする。検索条件を満たす場合，そのアイテムをscan->xs_ctup.t_selfに設定しtrueを返す。検索条件を満たしていない場合で，continuescanがtrueのときは，_bt_nextで検索を続ける。continuescanがfalseだったら，検索結果は無いのでfalseを返す。
memo
load
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 19.99 3.07 3.07 1000006 0.00 0.00 XLogInsert 12.17 4.94 1.87 1000003 0.00 0.00 PageAddItem 7.52 6.09 1.16 1000000 0.00 0.00 CopyReadAttributesText 7.29 7.21 1.12 1000001 0.00 0.00 CopyReadLineText 5.01 7.99 0.77 1 0.77 15.17 CopyFrom 2.67 8.39 0.41 1062699 0.00 0.00 hash_any 2.64 8.80 0.41 1000000 0.00 0.00 heap_insert 2.41 9.17 0.37 1000002 0.00 0.00 heap_formtuple 2.28 9.52 0.35 1000189 0.00 0.00 MemoryContextAllocZero 2.18 9.86 0.34 1000002 0.00 0.00 DataFill
create index
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 44.69 12.20 12.20 28937404 0.00 0.00 comparetup_index 13.00 15.75 3.55 2000000 0.00 0.00 tuplesort_heap_siftup 6.56 17.54 1.79 47295452 0.00 0.00 inlineApplySortFunction 5.57 19.06 1.52 47295458 0.00 0.00 btint4cmp 4.45 20.27 1.22 47295452 0.00 0.00 myFunctionCall2 1.90 20.80 0.52 4009293 0.00 0.00 AllocSetAlloc 1.79 21.29 0.49 3000036 0.00 0.00 slot_deform_tuple 1.39 21.66 0.38 8019139 0.00 0.00 AllocSetFreeIndex 1.36 22.04 0.37 1000022 0.00 0.00 index_form_tuple 0.95 22.30 0.26 3000044 0.00 0.00 slot_getattr
