# CMU DB 12. Query Execution I
tags: CMU DB
インターンの面接でScalaがやりたいということを言ったら，｢うちではもうScala扱ってないんだよね｣的なことを言われてしまいながらも内容的には全然やりたかいので｢別にScalaじゃなくてもいい｣と若干矛盾する発言をしてしまいましたピカチュウです．今回で授業は半分終わりました．これからペースを上げたいと思います．
授業
Processing models
どのようにクエリを実行するかを定義する．
- iterator model
- materialization model
- vectorized / batch model
という方法がある．
iterator model
各query plan演算子がNext関数を実装する．
各呼び出しで，演算子は単一tupleもしくはNULL markerを返す(もしtupleがなければ)．その演算子はそのchildrenでchildrenのtuplesを得，処理するためにループを実装する．
valcanoもしくはpipeline modelと呼ばれている．
もぼ全てのDBMSで使われている．
出力制御はこの方法だと簡単に上手く行く．
materialization model
それぞれの演算子はその入力を一度に処理し，一度のその出力を出す．
演算子は出力を単一の結果として｢実現｣する．DBMSはtuplesを検査しすぎないようにヒントを押さえ込む．実現された行か単一の列のいずれかを送ることが可能．
出力は全体のtuples(NSM)もしくは列の部分集合(DSM)になる．
OLTP workloadにはより良い．というのもクエリは小さな数のtuplesにアクセスするだけだから．より低い実行と協力がオーバーヘッドする．より少ない関数呼び出し．
大きな中間結果のあるOLAPクエリには向いていない．
vectorized. / batch model
iterator modelyのようにそれぞれの演算子がNext関数をこのモデルでは実装している．それぞれの演算子が単一のtupleの代わりにtuplesのbatchを出す．
演算子の内部のループ処理は一度に複数のtuplesを出す．batchの大きさはハードウェアとクエリの特性によって異なる．
OLAPクエリには理想的．というのも演算子ごとの呼び出しの数を大きく減らせるから．
tuplesのbatchesを処理するために演算子が行列化した命令(SIMG)を使うことを許している．
pan proessing direction
- top-to-bottom
- tuplesはいつも関数呼び出しで渡される
- bottom-to-top
- パイプラインのキャッシュ/レジスタのより厳しい制御を想定する
Access Methods
DBMSがテーブルに保管されたデータにアクセスすることが出来る方法．逐次代数では定義されていない．
- sequential scan
- index scan
- multi-index / bitmap scan
sequential scan
テーブルのそれぞれのページに対して，buffer poolからそれを取り出す．それぞれのtuple上で繰り返し，それを含むか調べる．
DBMSは最後のページを追跡し，調査する内部のカーソルを保持する
for page in table.pages:
for t in page.tuples:
if evalPred(t):
// Do something
これはほとんどいつもDBMSがクエリを実行する上で最悪
- prefetching
- parallelization
- buffer pool bypasss
- late materialization
- heap clustering
などが最適化の手法としてある．
index scan
複数のindexを検索する時に少ないindexのクエリから投げ，計算量を落とす．
multi-index
DBMSが複数のindexをクエリに使える時，
- それぞれの合致しているindexを使い，records idの集合を計算する
- クエリの述語に基づいてこれらの集合を組み合わせる(union, intersection)
- recordsを得，残った述語のどれかに適用させる
PostgresはこれをBitmap Scanと呼んでいる．
Expression Evaluation
DBMSはWHERE句を式の木として表現している．
結論
同じquery planは複数の方法で実行される．
大半のDBMSはindex scanを出来るだけ使おうとする．
式の木は柔軟だが遅い
感想
あまり新しいことはなくなってきた(？)というかだんだんDBMSが分かってきた気がします．
