An Overview of Query Optimization in Relational Systems

An Overview of Query Optimization in Relational Systems CMUデータベース輪読会資料 作者: @kumagi

Abstract ● ● ● 1998年に書かれた比較的古い論文 とはいえそこより古いOptimizerの研究に関して重要なところをかいつまんでいる 「技術的な正確性より説明しやすさに重きを置いたよ」と序論で堂々と書いてて好 感が持てる

位置づけ ● VLDB1979 Query Processing in a Relational Database Management System ○ ○ ○ ● Ingresや古いOracle(1990年代まで)で使われた古い Optimizer 適用可能なルールをひたすら適用しまくる戦略 (Predicate Push-DownとJOINの左右の決定が典 型的) Andyの講義によると Oracleで働いていた人曰くコードは洗練されていたがシステム内最大のコン ポーネントであり Cで書かれた巨大な if-then-elseの塊は悪夢でメンテ不能であった SIGMOD1979 Access path selection in a relational database management system ○ ○ RDBMS黎明期のIBMの中で発明されたオプティマイザ。 System Rや初期のDB2やMySQL, PostgreSQL, SQLiteは基本的にこれを使っている Left-Deepなプランだけを探す事に専念すれば圧倒的にプラン探索領域が減らせるよねという気づ きがある

Optimizerは何故重要なのか 単一のクエリに対しても複数の関係代数表現がある 一つの関係代数表現に対しても複数の実行戦略がある（JOINの種類とか） 戦略によって計算にかかるコストが圧倒的に変わる 一番高速な実行プランを高速かつ高精度に見つけたい

System-R の Optimizer 概要 ● 探索空間を狭めるためLeft-DeepなJoin順序しか考えない事にした ○ ● ● ● Bush Joinは捨てた DPを用いて探索に掛かるコストをO(N!)をO(N*2^{N-1})まで減らした 順序情報を探索空間に組み入れて、Sort-Merge Joinが効くケースをちゃんと見つ けられるようにした(Interesting Order) コストの見積もりは割とカジュアルにやっているように見える

Left-Deep Join A⨝B⨝C⨝Dを考える ⨝ ⨝ D ⨝ C ⨝ ⨝ D ⨝ B Left Deep Tree A Bushy Tree A B C C A ⨝ D A ⨝ C B ...… でN!通り D ⨝ ⨝ ⨝ ⨝ A B ⨝ ⨝ B ⨝ C ⨝ D A ⨝ D C ⨝ B ...… でN!通り

Left-Deep Join A⨝B⨝C⨝Dを考える ⨝ ⨝ D ⨝ C ⨝ ⨝ D ⨝ B Left Deep Tree A Bushy Tree B A C A ...… でN!通り D ⨝ ⨝ ⨝ ⨝ ⨝ B ⨝ C Bushy TreeはMaterializationが必須になるが速くなる事もある。 ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ...… でN!通りの方は無視 …が切り捨てる。 A B C D A C B D A D C B

DPを用いた網羅的探索 仮説：最適プランの部分プランもまた最適 つまりテーブル数N-1での最適解はNテーブルでの部分最適解として利用できる 最適解を探索 ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ⨝ ・・・ 再利用 再利用 再利用

DPを用いた網羅的探索 N行あるテーブルAとM行あるテーブルBをJOINする場合（In-Memory) ● Nested Loop Join: O(N*M) ○ ● Sort Merge Join: O(NlogN+MlogM) ○ ● Aの全行について Bから探索する AとBをそれぞれSortしてから編み上げる Hash Join: O(N+M) ○ BをIDをKeyに辞書に放り込んでから Aの各行について辞書を引く

DPを用いた網羅的探索 まずN個のJoin対象テーブルの中の2テーブルの結合を考える。NC2 通り 全部の2テーブル結合に対して3テーブル目を結合させる。N-2通り 結合させていないテーブルが無くなるまで上の操作を繰り返す。 j+1テーブルの最適なJOIN戦略はjテーブルの最適解それぞれに1テーブルを加えた中 での最適解。

DPを用いた網羅的探索 下からj段目のステップではj個のテーブルがJOINされておりNCj個の候補がある。 j+1段目の各部分最適解はj番目の最適解に1つテーブルを足す操作を網羅的に試す 試した中で一番コストが低い物がそこのJOIN結果の最適解 4段目 3段目 2段目 1段目

DPを用いた網羅的探索 下からj段目のステップではj個のテーブルがJOINされておりNCj個の候補がある。 j+1段目の各部分最適解はj番目の最適解に1つテーブルを足す操作を網羅的に試す 試した中で一番コストが低い物がそこのJOIN結果の最適解 = MIN(JOIN( , ), JOIN( , ), JOIN( , ))

DPを用いた網羅的探索（補足） ● ● ● JOINすべきキーが存在しないテーブルの組み合わせも一応全部見積もる（直積は 機械的にあらゆる2テーブルで算出できる）が出力行が大きいので基本的に切り捨 てる事になる 単一テーブルの読み出しであってもPush-DownしてきたSelectionによって Full-Scan/Index-Scan/Index-Only-Scanなど最適解が変わるのでDPは1テーブル から始まる テーブル結合コストは統計情報により見積もられ、結合済みテーブルの統計情報も 統計情報によって推定する ○ ○ 値の分布が独立していないので推定値はその分だけズレる 例: 都道府県ごとに男女比に極端な差はないが年齢分布は東京が明らかに若い、など

統計情報 ● データ全部をK個のバケットに等分するequi-depth histogramをよく使う ○ ● ● Kが大きいほど高精度かつ容量や計算コストを食う そのバケット内でのヒット件数に対して（バケット内では一様分布しているという仮説 の上で）当たりを付けられる 亜種・改善などの議論については別の論文参照 equi-width histogram equi-depth histogram

統計情報 x=70を満たす件数は 50〜74 の25の幅に120件のデータが ある所から推定して 120 / 25で 4.8件！ equi-width histogram x=70を満たす件数は 63〜70 の8の幅に68件のデータがあ る所から推定して 8.6件！ equi-depth histogram

統計情報 2次元ヒストグラムを用意できれば行選択後のテーブルに対してもそれなりの精度で見 積もりができる N列あるテーブルに対して網羅的にやるとNC2個の2次元ヒストグラムを用意することに なって容量・計算量的にだいぶ辛い 複合キーによるインデックスに対してはヒストグラムを用意すると便利なことが経験上多 いのでそれぐらいに限定してN次元ヒストグラムを持つ実装などがあり得る

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id 1万行 100万行 owner 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id indexで探す。cardinalityか ら見て出力は推定 1行 1行 owner owner_idとbrand_idのペア を全通り吐き出す 推定100万行 100万行 brand_idとnameのペアを全 通り吐き出す 推定100行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id 1行 owner 100万行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id carの中でowner.idにヒットする 行を探して100万行読む。 計算コスト100万行分 推定出力1行 コスト100万 出力1行 直接JOINできないので直 積を求めるしかない 計算コスト100行分 推定出力100行 コスト100 出力100行 1行 owner HJ使って1000100行分の計算 コスト 出力されるのは推定 100万行 コスト1000100 出力100万行 100万行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id car⨝brandの100万行を走査して owner.idと一致するcar.owner_id を見つける。 計算コスト100万 推定出力1行 合計コスト2000100 コスト100万 出力1行 コスト100 出力100行 1行 owner コスト1000100 出力100万行 100万行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id 100行のowner⨝brandから owner.idとbrand.idの組が carテーブルの中にあるもの をHJで探す。 計算コスト1000100 推定出力1行 合計コスト1000200 コスト100万 出力1行 コスト100 出力100行 1行 owner コスト1000100 出力100万行 100万行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id brandテーブルの中で car.idを1 行NLJで探すだけ 計算コスト100行分 推定出力1行 合計コスト1000100 コスト100万 出力1行 コスト100 出力100行 1行 owner コスト1000100 出力100万行 100万行 100行 car brand

DPを用いた網羅的探索 クエリ：Taroさんが所有する車のブランド名を列挙 SELECT brand.name FROM owner, car, brand WHERE owner.name = "Taro" AND car.owner_id = owner.id AND car.brand_id = brand.id つまりこのプランが一番安い 合計コスト1000100 コスト100万 出力1行 1行 owner 100万行 100行 car brand

探索のtips ● Outer Joinは交換法則が成り立たないのでそれを壊さない範囲で列挙する ○ ● 結合法則は成り立つので探索空間が無くなるわけではない Aggregation操作は基本的に一気に行数を減らせられるのでできる限り push-downしたほうが良い ○ ただのGroup By操作が2回のaggregationになる場合もある

多段Aggregation push-down クエリ：部署ごとに売上の合計値を求めたい SELECT division.name, SUM(product.sales) FROM product, division WHERE product.div_id = division.id GROUP BY division.name 先に製品毎の合計値を求めておいてから、JOIN後にdivison(複数のproductを持つ)毎の合計値を division.id SUM(sales) product⨝division product.id SUM(sales) product division

Interesting Order Sort-Merge Joinを同一キーで複数回行える場合などはHashJoinの方が計算コストが 低くてもトータルではコストが低い場合がある つまり2テーブルのJoinコストの中で最適でない解が3テーブルのJoinコストの中での部 分最適解である可能性が捨てきれない 列が順序付けされている場合は同じテーブル同士のJoin結果であっても別の結果とし て取り扱う事にする ＝あらゆる列でsortされた場合のコストもDPの対象として別々にトラックする しかし複合キーによるsortを考慮に入れると列の数の階乗だけ選択肢があるので多分 System-Rは複合キーまでは検討しないと思う

Interesting Order Andy の授業の動画では「System-Rは段階ごとに最適解を探すので局所最適に落ちて しまい個別のSM JOINを用いた場合の最適解を見つけることができない」と言っている ように見える。 動画のコメントでもAndyは「the original System R dynamic programming algorithm only considers join orderings. The physical sort order of the data is not part of that search.」と言っている。 しかしこの論文では明らかにInteresting OrderはSystem-Rの一部として書かれてい る。

Interesting Order with DP 「特定の列で整列されたテーブル」を別のターゲットとして扱う 下から順にテーブルを埋めていくが SortMerge Joinなどで順序が違う物は別の物として DP表を埋める NoOrder .b_id .a_id 1000100 ∞ 1000100 NA 100 .name ∞ sort NA ∞ .score 2441231 sort 1000000 100 .t_id ∞ NA ∞ 21233242 ∞ ∞ NA ∞ ∞ 223 NA 284 NA ∞ in e jo ∞ g r me 1000000 NA NA ∞ NA NA 1 1 NA NA NA 1

Optimizer Generator System-Rが実装しているわけではないが探索空間を拡張可能にする発展形 ● Starburst ○ ○ ○ ● IBMからSystem-Rの後継として出したシステムで、 Bottom-Up探索をルールベースで行う 論理的な代数表現を QueryGraphModel(QGM)の形で表し、QGMを入力してQGMを出力するrule を{書き換え条件 : 書き換え先}の形でメンテナンスすればいい ■ コンパイラに似てる 充分最適化した QGMを物理プランに書き換える Volcano/Cascade ○ ○ ○ ○ ○ Top-Downで部分解を求めていく 同じテーブルの組み合わせに対して再度同じものを算出しなくていいようにメモ化を行う ■ fib(x)をメモ化再帰でやるイメージ 明らかに筋悪な方向には早期に探索を打ち切れる（枝刈り） 論理→論理プラン 論理→物理プラン のルールの羅列だけを管理すればいい Physical Propertyを用いてSM Joinの活用もヨシ！

Cascade Optimizer ● gporca ○ ● Cockroach DB ○ ○ ● GreenPlumのOptimizerだけ切り出したプロジェクト、 C++のマクロでルールを記述する Goで書かれた分散 RDBMS opt形式で書かれた DSLで書き換えルールを列挙してて、これで見つけていく ■ optファイルを増やすだけでオプティマイザが賢くなる！ Peloton ○ ○ ○ Andy Pavlo先生のところで作ってる RDBMS C++でCascadeを実装しているとのこと コードレベルでは追っていないが説明には Columbiaに基づいて実装したと書いている