btree index (22)

PostgreSQL

_bt_endpoint

btree indexの先頭または末尾のアイテムから、検索条件を満たすアイテムを探す。先頭から探す場合、以下の処理を行う。
(1)_bt_getendpointで左端のリーフページを取得する
(2)ページの先頭のアイテムを取得する
(3)_bt_checkkeysで検索条件を満たしていたら、それを返す
(4)最初のアイテムが検索条件と一致しなかったら、_bt_nextで検索条件に一致するまで順番にアイテムを調べる

_bt_leafbuild

ソートしてからbtree indexを構築するとき、スプールに全アイテムを登録した後に実行される。
(1)tuplesort_performsortでスプールのアイテムをソートする
(2)BTWriteStateを初期化する(WALを使用するかなど)
(3)_bt_loadでindexを構築する

_bt_preprocess_keys

btree indexの検索を開始する前に、検索条件(Scan Key)を整理する。
この関数は、以下のような処理を行う。

  • 検索条件に一致しなくてもindexの検索を続ける必要がある検索条件の数を調べる

例えばindexの属性としてx, y, zがあって、x = 1 and y < 4 and z < 5という検索条件が指定された場合を考える。indexの検索中に(x, y, z)が(1, 2, 7)のような検索条件に一致しないデータを見付けても、このデータの後ろ(インデックスの右側)に(1, 3, z)のようなデータが見付かるかもしれないので検索を続ける必要がある。反対に(1, 4, z)のようなデータを見付けた場合は、このデータの後ろには検索条件に一致するデータはないので検索をやめてもいい。この例では、検索を続けなければならない条件はx = 1とy < 4の2つとなる。この数はso->numberOfRequiredKeysに設定される。

  • 余分な検索条件を減らす

y < 4 and y < 10のように冗長な検索条件が指定された場合、y < 4のみを使う。同様にy = 4 and y < 10のときはy = 4が、y < 4 and y <= 4のときは y < 4が使われる。このようにして検索条件を減らしていき、残った検索条件(検索に使用される検索条件)の数をso->numberOfKeysに設定する。

  • 矛盾する検索条件を検出する

x = 1 and x > 2などのように検索条件の矛盾を検出する。矛盾を検出したら検索を実行しなくても検索結果が無いことがわかるので、so->qual_okをfalseに設定して上位の関数に伝える。また、 現在のbtree indexではx is NULLやx is not NULLなどのような、NULL値の検索条件は使えない。この場合もso->qual_okをfalseにする。(NULLの検索でもbtree indexの使用を可能にするパッチが提案されているので、将来はこの制約は無くなるかもしれない)

  • unique indexの完全一致検索か調べる

インデックスがunique indexで、全部のキーを'='で検索する場合、検索結果は最大1件になる。この場合は、scan->keys_are_uniqueをtrueにする。