論文メモ Integrating the UB-Tree into a Database System Kernel

April 29, 2021

商用DBMS TransBaseのインデックスをB木からUB木に変え、複数の範囲クエリからなる多次元アクセスを高速化した。 高速な多次元アクセスの拡張を商用DBMSのインデックスに導入することは複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスであり、B木のキーの生成とページ分割方法を工夫し、範囲クエリを高速化する。 範囲クエリに向きB木に似たインデックスを使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスのインターフェースを呼び出す変更ではなく、もとのインデックス自体を変更する当手法には、クエリのオプティマイザを継続して利用できる利点もある。

UB木は、Z階数曲線で多次元空間を1次元に写像する。 以下の図は、2次元空間を1次元に写像した様子をあらわす。 (b)のマスには(a)の曲線にそったアドレスがあり、写像後も局所的な位置関係が一定保存されている。 z-addresses

UB木は、データであるタプルの値からキー(Z-value)を生成する。 以下のアルゴリズムからなるUBKEYがZ階数曲線の写像関数にあたる。 z-addresses はじめに、タプルの\(d\)個の要素を\(\texttt{TransformAttribute}\)でビット列に変換する。 変換後も要素の順序関係は保存される。 タプルの要素を\(a\), \(\textit{bitstr}: A \rightarrow\{b\mid b\in[0,1]^{*}\} \)とすると $$ a_i\le a_j \Leftrightarrow \textit{bitstr}(a_i) \le_{\text{bitstr}}\textit{bitstr}(a_j) $$ が成立する。 ビット列の先頭は\(0\)で埋められ、連続する末尾の\(0\)はデータサイズを抑えるために省かれる。 下方の2重のfor文は下図のように各ビット列の先頭から順にビットを選び、キーの末尾にビットをたす。 z-value

ページ分割とUBKEYによるキーの生成を除けば、挿入、更新、削除のアルゴリズムは、B木と変わらない。 UB木は、範囲クエリと重なる図のZで示されるクラスタの数を減らすために、できるだけクラスタが収まるようにページを分割する。 これを満たすには、分割するページの中で最も短いキー、すなはち末尾の0が最も長いキーを境界として分割するとよい。

タプル\(\textit{ql},\textit{qh}\)で範囲を指定したクエリがあたえられると、\(\textit{ql}\)から\(\textit{ql}\)を含むページの末尾までにある目的のタプルを探す。 これは、以下のアルゴリズムのwhile文の最初の処理にあたる。 q \(\texttt{getNextZvalue}\)は、ページの走行を追えたカーソルが次に進むべきキー\(\)を返す。 ページの末尾が下図の点線で囲まれた範囲クエリ内であれば、隣接するページに移動し、先頭から末尾までを調べる。 q 他方、下図のようにページ末尾が範囲クエリの枠外に出たのならば、下図のように、連続するベージを飛び越え、範囲クエリの境界を含むページにカーソルを移動し、検索を続ける。 q2

論文をこちらからダウンロードできます。 画像は論文から引用されています。