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

ミドルウェアとかやってます

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

この記事は「けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」19日目の記事です

はじめに

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

Query Processing

Query Plan

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

Processing Model

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

Iterator Model

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

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

  • DBMS が次のタプルを取得する前にできるだけ多くの演算子を介してタプルを処理する
  • ただし、一部の JOIN, Subquery, ORDER BY などはタプルを全て取得するまでブロックする。

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 を実装する必要があるのかな?