indexes.re

= インデクス

インデクス(Index, 索引)は、ひとことで言うと、
ある Table において Key を指定して Record を絞り込む操作を高速に実行するための補助的なデータ構造です。
インデクスがなくても、Table の全 Records をチェックすれば、絞り込み操作は実現できます。
これを Table の Full scan と呼びます。
例えば、1M 個 (M は Million、100万の意味) の Records が存在する Table の中で、たった 1 行を見付け出すために
1M 個の Records を全部読んで調べるというのはいかにも効率が悪いですね。

典型的なインデクスは Tree map または Hash table を使って構成されています。
これらは N 個の Records から成る Table を検索するために必要なデータアクセスが、
log N 回程度で済んだり、定数回程度で済んだりするようなデータ構造です。
しっかりと考える場合は最悪のケースも検討しなければなりませんが、
今はそれをあまり考えずに、これらのアクセス回数の目安を O(log N)、O(1) と書いて表現します。
詳しく知りたい人は、「計算量」や「O記法」などのキーワードで調べてみてください。
アルゴリズムとデータ構造の教科書には必ず載っているはずです。


== Tree map を用いたインデクス

Tree map を実現するには Directed rooted tree (根付き有向木) 構造を使います。
Directed rooted tree は Directed graph (有向グラフ) に制約を加えたものです。
Directed graph を表現するためには Vertex (頂点) の集合 @<m>{V} と Edge (辺) の集合 @<m>{E \subset V \times V} を用います。
@<m>{e=(v_1, v_2) \in E} について、
@<m>{v_1}から見て@<m>{e}を Outcoming edge、
@<m>{v_2}から見て@<m>{e}を Incoming edge と呼びます。
また、@<m>{e} から見て @<m>{v_1} を Source、@<m>{v_2} を Destination と呼びます。
Directed rooted tree とは、
(1) 連結 (Connected) しており、
(2) Incoming edge が存在しない Root (根) と呼ばれる Vertex がひとつだけ存在し、
(3) Root 以外の Vertex は全て Incoming edge が唯ひとつのみ存在する、
これらの条件を全て満たす Directed graph です。
Outcoming edge の存在しない Vertex を Leaves (葉) と呼びます。
各 Vertex にとって、自身の Outcoming edge で直接繋がっている Vertex を Children(子) と呼び、
Incoming edge で直接繋がっている Vertex を Parent(親) と呼びます。
Directed rooted tree を考えるときは Vertex のことを Node と呼ぶことが多いので
ここでもそれに倣います。

実際にメモリ上で Tree map を作るとき、典型的には Node を構造体として作ります。
Children や Parent を参照するのにはポインタを使います。
(Parent へのポインタはなくても良いですが、効率的なアクセスのため用意することが多いです。
その代わり、冗長な情報を持つことになるので操作時に気を使う必要が出ます。)

Tree map は Key を表す型が全順序を持つことを要求します。
Tree map を Directed rooted tree で実現するとき、
各 Node は自分の担当する Key の連続部分空間を Children の数だけ連続部分空間に分割して保持します。
ここでの連続部分空間とは、ひとつの範囲で表現できる部分空間、という意味で使っています。
つまり、ある Key 値を持つ Record が存在するならば、Root node から
Key 値が含まれる連続部分空間を持つ Child を選ぶという操作を繰り返すことで
到達した Leaf node が保持していることが保証されます。
つまり、木の深さ分だけ Child を辿れば良いわけです。
木の深さは木がバランスしている(一番深い Leaf node と浅い Leaf node の深さの差が高々定数倍と見做せる)とき、
Node 数 N に対して深さが O(log N) と見做せ、
平均的には O(log N) のステップ数で Record に辿りつけます。


二分木(Fanout すなわち Children の数が高々 2 の木構造)による
Key の型が整数である Tree map の例を示します:


//list[tree_map_example][]{
Root:
  border_key: 5
  children: N11, N12

N11:
  border_key: 3
  children: N21, N22

N12:
  border_key: 8
  children: N23, N24

N21:
  border_key: 1
  records: (1, 'aaa')

N22:
  records: (3, 'ccc'), (4, 'ddd')

N23:
  records: (6, 'fff')

N24:
  records: (8, 'hhh'), (10, 'jjj')
//}


Root node には @<tt>{border_key} として 5 が格納されています。これは、Left child を辿っていった先には
@<tt>{key} @<m>{<} 5 の record しか存在しないことを意味します。
同様に、Right child を辿っていった先は 5 @<m>{\le} @<tt>{key} の Record しか存在しないことを意味します。
N12 は 5 @<m>{\le} @<tt>{key} の連続領域を担当しています。
そして、担当領域をさらに 5 @<m>{\le} @<tt>{key} @<m>{<} 8 と 8 @<m>{\le} @<tt>{key} の 2 つの領域に分割し、
それぞれ Children である @<tt>{N23, N24} に割り当てます。
@<tt>{N21, N22, N23, N24} は Leaf node なので、その中に Children へのポインタではなく、
対応する Key 値を持つ Record (もしくは Record へのポインタ等)が格納されています。
この例では @<m>{N = 7}、@<m>{\log_{2\} N \approx 2.8} で、深さは 3 となります。

Tree map が有効に機能するためには木がバランスしていることが必要となります。
これを実現する操作方法を持つ木構造をバランス木と呼びます。
二分木だと、赤黒木(Red-black tree) や AVL-tree が例として挙げられます。
また、大前提として Fanout は 2 以上であることが必要となります。
Fanout が 1 だと、Root を先頭とする連結リスト構造を意味しますので、我々が欲しい性質を持たないからです。

扱うデータの量が使えるメインメモリよりも大きいことが想定される DBMS は、
メインメモリとディスク@<fn>{footnote_disk}上の細かいデータのやりとりを頻繁に行う必要があるため、
ページと呼ばれる(4KiB や 16KiB などの)固定サイズ連続領域を Node として扱う
B+tree もしくはその亜種が良く使われています。
一般に、Non-leaf node は Fanout - 1 個の Key を格納する必要があるので、
B+tree の Fanout は Key のサイズに依存します。

//footnote[footnote_disk][HDD や SSD などの不揮発性を持つ二次記憶装置のことを総称してディスクと呼んでしまったりします。Hard Disk Drive の Disk です。一方で、不揮発メモリ(NVRAM) をディスクと呼ぶことに私は抵抗があります。たぶん、ブロックデバイスとして扱うか、バイト単位(実際はキャッシュライン単位)で扱うかで大きな隔りがあるのでしょう。]

昨今研究開発が盛んなインメモリデータベースは、データが全てメインメモリに納まる前提を置きますが、
必ずしもディスク上の構造とメモリ上の構造が一致する必要はないため、
メモリ上の Tree map の表現は、必ずしもページではなく、
ポインタなどの間接参照データが使われていても問題ありません。

C++ を使っていてとりあえず Tree map が欲しいときは、
@<tt>{std::map<Key, Value>} 型のオブジェクトを作ればそれでおしまいです。
もちろん Thread-safe ではないことには注意が必要です。
Rust だと標準で @<tt>{std::collections::BTreeMap} なるものが使えるらしいです。
しかし、内部の Node に直接アクセスできるわけではないので、
使い勝手は C++ の @<tt>{std::map} とあまり変わらないかも知れません。


== Hash table を用いたインデクス


@<m>{N} を自然数とし、Key 空間から @<m>{\\{0, 1, ..., N-1\\\}} への写像 @<m>{h} を考えます。
例えば、Key 値を入力として適当な非負整数を出力する副作用のない関数を用意し、
出力された非負整数を @<m>{N} で割って余りをとれば @<m>{h} は実現できます。

また、予め @<m>{N} 個のバケットと呼ばれる要素からなる配列を用意しておき、
Key 値から @<m>{h} で得た値を配列のインデクスとしてひとつのバケットにアクセスします。
バケットには、複数の Record が格納できるようになっており、
バケット内の Key が一致する Record を探すことで絞り込みます。
一例としてバケット内の Records は連結リストを用いて管理します。
同一の Key 値を持つ Record は他のバケットには存在しないことが保証されており、
このバケット内を探すだけで済みます。

以上が素朴な Hash table の設計です。たくさんの亜種があります。
写像 @<m>{h} は Hash 関数と呼ばれており、
このデータ構造が Hash table と呼ばれている理由となっていると思います。
Hash 関数は入力サイズに依存する計算量を必要とするものを使いますが、
Key サイズは Record 数を @<m>{M} としたとき、@<m>{M} に対して定数と見做せることがほとんどです。
つまり Key 値からバケットを特定する計算量は @<m>{O(1)} となります。


Hash table が有効に機能するためには、
各バケットに格納されている Record 数が高々定数と見做せることが求められます。
このとき、Key 値から Record に到達するための計算量が @<m>{O(1)} と見做せるからです。
そのため、@<m>{h} は典型的に使われる Key 空間の部分集合に対して一部のバケットに偏らないような
値を出力することが求められます。
また、ここで説明した Hash table はバケット数 @<m>{N} が固定であるため、
@<m>{N} に対して Record 数 @<m>{M} が小さすぎれば空のバケットが多くなって空間が無駄になるし、
逆に大きすぎれば、バケット内の Record 数が増えすぎて定数と見做せなくなってしまいます。
このような状況に対応するため、@<m>{N} 個の要素を持つ配列から
(通常は @<m>{N < N'} であるような) @<m>{N'} 個の要素を持つバケット配列にデータを移動することを Rehash と呼びます。
このとき、値域が異なるので、当然 Hash 関数も異なります。@<m>{N} で割る代わりに @<m>{N'} で割るなどする必要があるからです。
Rehashは 一般に @<m>{O(M)} かかりますので、
Rehash が頻繁に発生する状況は Hash table が有効に機能しているとは言い難いです。


如何にごく単純な Hash table の例を示します。Key 型は @<tt>{uint}とし、@<m>{h} は簡単のためただの剰余としました:

//list[hash_table_example][]{
h(key: uint) -> {0,1,2,3,4}:
  return key % 5

Array as a hash table with size 5:
  [B0,B1,B2,B3,B4]


B0: (10, 'jjj')
B1: (1, 'aaa'), (6, 'fff')
B2: (7, 'ggg'), (12, 'lll')
B3:
B4: (9, 'iii')
//}

@<m>{N = 5} の Hash table です。@<m>{h} はただの剰余なので、
5 で割った余りがそのままバケットインデクスを示しています。


C++ を使っていてとりあえず Hash table が欲しいときは、
@<tt>{std::unordered_map<Key, Value>} 型のオブジェクトを作ればそれでおしまいです。
Rust だと @<tt>{std::collections::HashMap} が対応します。
これらについても Thread-safe ではありません。
少し探せば、Thread-safe な Concurrent hash map の実装はいくつかあるようです。



== インデクスのトレードオフ

ひとつの Table について、一般に Key (型)は複数存在します。
典型的にはひとつの Key についてインデクスを高々ひとつ作って使います。
性質の異なるインデクスを同じ Key に対して作ることは考えられなくはないですが、
それはかなり特殊な状況だと思います。

インデクスはその Key を用いた絞り込み操作を高速化しますが、その代償として、
Record をひとつ Write する度に、変更に関係するインデクスを全て更新する必要が生まれ、
Record の Write コストが増えるというデメリットが発生します。
どの Key についてのどのようなデータ構造を用いたインデクスが必要か、
または不要かについての判断は、データベースの Key 分布と
ワークロード(どのようなアクセスがどの程度発生するか)に依存します。
つまり、最適なインデクス構成を決めるのは簡単ではないということです。

また、インデクスの使用についても難しい問題があります。
複数の条件で Record を絞り込む場合、必ずしも全ての条件に一致するインデクスが必要というわけではありません。
例えば、@<tt>{age = 30 and weight = 60} という条件であれば、
@<tt>{(age, weight)} という Key に対応するインデクスを使う方法もありますが、
@<tt>{(age)} という Key に対応するインデクスで絞り込んだ Records を
さらに @<tt>{(weight)} という Key に対応するインデクスで絞り込む方法もありますし、
@<tt>{(age)} のインデクスで絞り込んだ Records を全部チェックするという方法もあります。
性能の指標として重要なのは、最初もしくは最初の方でどれだけ絞り込めるかという点です。
そもそも Table に格納されている Records 数が少ない場合は Table full scan の方が高速なこともあります。

SQL をサポートする DBMS にはクエリ最適化(Query optimization)、もしくは
実行計画(Execution plan)作成と呼ぶ処理を行う機能があります。
その処理の中で最も重要な仕事が最適な絞り込み方法を推定することです。
Query optimization は SQL のような宣言的言語で書かれた命令を実行するときに必要になりますが、
組み込み DBMS では Execution plan を直接的にアプリケーションコードが書き下すことが多いです。
つまり、そのような DBMS ではどのインデクスをどの順番で使って Records を絞り込むかについても明示的に指定します。

どのインデクスを作るかについての判断は、どのインデクスをどの順番で使うかの判断よりも頻度が低いです。
前者はデータベース物理設計、後者はクエリ最適化における判断なので。
最近の商用プロダクトの一部では、
ワークロードを監視して自動的にインデクスを作成したり削除したりする機構も
実用化されているようなので、インデクス構成についての判断の頻度は上がっていると言えるでしょう。
また、特定の Key 範囲のみインデクスを作成することも有り得ます。
これらの判断はすべてインデクス作成と使用のトレードオフがあるから必要となるのです。



== インデクス構造のアクセス排他

シングルスレッドのプログラムであれば、インデクス構造を触っているのは自分ひとりなので、
アクセス排他について何も考える必要がありません。
もし、マルチスレッド/マルチプロセスのプログラムで、複数の Worker が同一のインデクス構造を触るときは、
アクセス排他の仕組みが必要となります。
これらのデータ構造は Concurrent tree とか Concurrent hash map などと呼ばれます。
総称して Concurrent index と呼ぶようです。
これらを自作する場合、どの部分をどう排他すべきかについて考える必要が生じますが、
これはこれで深淵な世界であり、一筋縄ではいきません。本書ではこれ以上踏み込みません。


== Table 本体の構造について



Table そのものはどのような構造をしているのかについて、2 パターン考えられます。
1 つ目は、Table 本体もインデクスとして実装する場合です。
この場合は Primary key もしくは代理 Key が定義されていて、それを使って
Record 本体の格納場所まで効率的に辿りつけるようになっています。
この場合、Table full scan はこのインデクスを強制的に使うことになりますし、
その他のインデクスにおける Value は Primary key を保持することもあります。

2 つ目は、Table 本体は独立したデータ構造として実装する場合です。
この場合、メモリ上、ディスク上のレイアウトには自由度があります。
Table full scan のみ実行できれば良いからです。
各 Record の位置は、なんらかのアドレスもしくはその組み合わせで表現することが多いと思います。