CMU Database Systems をひたすら追っていく ~10 Query Processing~
この記事は「けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」19日目の記事です
はじめに
どうも、最近という出だしでブログ記事を 19 個も連続で書くと流石にそろそろネタがなくなってくるけんつです。
今回は SQL の実行周りに関連する話で、久々に CMU の講義に戻ってきます。
Query Processing
Query Plan
Query がどのように実行されるかというと、まず SQL が DBMS に投げられるとそれを構文解析に通してツリー構造を作る。
そのツリー構造をもとにどのように実行するか決定する。このとき、実行計画では可能な限りインデックススキャンを利用する必要がある。
Processing Model
DBMSではどのようにクエリプランを実行するかということを定義する。ワークロードに対して色々なトレードオフをもつ様々なモデルが存在する。
ここではそれらについて解説する。
Access Methods
Access Methods とはそのままで、SQL を解析した結果のクエリプランに基づいてクエリを実行する際にどうやってテーブルにアクセスするかという話
大きく分けて2つある。
Sequential Scan
これは順番にアクセスしていくやつ。
- Prefetch: 各ページにアクセスする際に、DBMS がディスクからのロードなどを極力挟まないように事前に数ページまとめて保持しておく
- 並列化: 複数のスレッドやプロセスをつかって並行スキャンしていく。
- Zone Map: 各タプル属性の集計を事前に計算しておく。DBMS はゾーンマップを最初にチェックすることで、ページにアクセスする必要があるかどうかを判断できる。検索するページの総数を減らす目的がある
- Late Materialization: 各オペレータは次のオペレータが必要する最小限の情報を渡す。
- Heap Clustering: タプルをクラスタインデックスで指定された順序を使用して、ページに格納する。
Index Scan
一つ以上のインデックスを選択して、クエリに必要なタプルを見つける。
複数のインデックスを使用する場合、DBMS は一致するレコードIDの集合を生成する。Bitmap, Hash Table, Bloom Filter などを使用することが多い。
おわりに
書かれていることが少なかったので自分で調べていく必要がありそう。
OLTP を目指していきたいので Iterator Model を実装する必要があるのかな?