CMU Database Systems をひたすら追っていく ~10 Query Processing~

どうも、最近という出だしでブログ記事を 19 個も連続で書くと流石にそろそろネタがなくなってくるけんつです。
今回は SQL の実行周りに関連する話で、久々に CMU の講義に戻ってきます。

Query がどのように実行されるかというと、まず SQL が DBMS に投げられるとそれを構文解析に通してツリー構造を作る。
そのツリー構造をもとにどのように実行するか決定する。このとき、実行計画では可能な限りインデックススキャンを利用する必要がある。

DBMSではどのようにクエリプランを実行するかということを定義する。ワークロードに対して色々なトレードオフをもつ様々なモデルが存在する。
ここではそれらについて解説する。

殆どの DBMS で採用されているモデルで以下のような特徴がある。

- next がコールされる度にオペレータは単一のタプルを返すかタプルが無い場合は Null を返す
- オペレータは子の next を呼び出してタプルを取得して処理するループを実装する

Access Methods とはそのままで、SQL を解析した結果のクエリプランに基づいてクエリを実行する際にどうやってテーブルにアクセスするかという話
大きく分けて２つある。

これは順番にアクセスしていくやつ。

Prefetch: 各ページにアクセスする際に、DBMS がディスクからのロードなどを極力挟まないように事前に数ページまとめて保持しておく
並列化：複数のスレッドやプロセスをつかって並行スキャンしていく。
Zone Map: 各タプル属性の集計を事前に計算しておく。DBMS はゾーンマップを最初にチェックすることで、ページにアクセスする必要があるかどうかを判断できる。検索するページの総数を減らす目的がある
Late Materialization: 各オペレータは次のオペレータが必要する最小限の情報を渡す。
Heap Clustering: タプルをクラスタインデックスで指定された順序を使用して、ページに格納する。

一つ以上のインデックスを選択して、クエリに必要なタプルを見つける。
複数のインデックスを使用する場合、DBMS は一致するレコードIDの集合を生成する。Bitmap, Hash Table, Bloom Filter などを使用することが多い。

書かれていることが少なかったので自分で調べていく必要がありそう。
OLTP を目指していきたいので Iterator Model を実装する必要があるのかな？

それが僕には楽しかったんです。