この記事の趣旨
2015年に発表されたクエリオプティマイザにおけるカーディナリティ推定とコストモデル、列挙アルゴリズムの貢献度を 評価した論文を読んでいきます。
How Good Are Query Optimizers, Really?
著者について
Viktor Leis、Andrey Gubichev、Atanas Mirchev、Peter Boncz、Alfons Kemper、Thomas Neumannらの グループによる論文。
ほとんどのメンバーはDBMSにおける最適化について研究しているが、Atanas Mirchevはより 統計や探索といった最適化よりの研究をしている。
問題意識
良い結合順序を見つけることはクエリの性能に対して大きな影響を与えるため、熱心に研究されてきた。 古典的なクエリ最適化のアプローチでは以下のステップで動的計画方に基づいた最適化を行なう。 1. 有効な結合順序の列挙 1. カーディナリティ推定値を入力としたコストモデルの選択
理論的にはカーディナリティとコストモデルの推定値が正確であれば、最適なクエリプランを選択することができる。 しかし現実にはカーディナリティ推定は一様性や独立性といった単純化された仮定に基づいており、しばしばそのような 仮定は間違っているため悲惨な計画を作成する。
手法
この論文ではカーディナリティ推定器の評価と正確なコストモデルの重要性の評価、そして列挙された結合順序の空間が どの程度影響するのかを以下の方法で検証し、貢献を行なっている。 1. IMDBデータを用いたJoin Order BenchmarkというJOINにフォーカスしたベンチマークによる評価を行なう 1. 実世界のデータセットにおける現実的なクエリを用いたE2Eの検証を行なう。 1. クエリ性能に対するカーディナリティ・コストモデル・列挙アルゴリズムの貢献度を定量化し、最適なクエリプラン生成のため のガイドラインを策定している。
作業時間
- read
- 29:38
- 29:38
- author
- 33:08
- 3:30
- summary
- 48:44
- 14:36
感想
時間が無くまとめ途中で切り上げてしまった。やらないよりマシではあるものの、ちゃんと纏めるときに くらべて理解度に影響が出そうなので時間に余裕を持っておきたい。 内容自体はGW中にPostgreSQLの実装を読んでいたこともあり、わりと理解しやすかった。
