Oracle Database のクエリオプティマイザに関するエッセイ

JPOUG Advent Calendar 2019 の23日目のエントリーです。22日目は新久保浩二さんのCOMMITについて少し考えてみた(1) でした。JPOUG Advent Calendar に参加するのも7回目になりました(皆勤賞)。Oracle Database などの商用DBや PostgreSQL、MySQL など RDBMS だけでなく、Amazon Redshift などの DWH、Hive、Presto や Spark などでもクエリオプティマイザは実装されており、本質を理解していれば、Oracle Database エンジニアのスキルは応用が効きます。
先日、Spark Meetup Tokyo #2 に参加して、SPARK-23128 Adaptive Execution in Spark SQL や SPARK-11150 Implement Dynamic Partition Pruning を見て Spark もここまで来ているのかと驚きました。今回は Oracle Database のクエリオプティマイザの進化の歴史についてエッセイを書きます。

Quick Overview of Upcoming Spark 3.0 + α from Takeshi Yamamuro

データ構造とSQLからアルゴリズム(実行計画)を導出するのがルールベースオプティマイザ、それに加えて統計情報もインプットとするのがコストベースオプティマイザです。Oracle Database では大量データ処理を睨み、Oracle 7(1992) からコストベースオプティマイザが登場しました。誰かに最初はコストベースオプティマイザの実装が難しかったので、ルールベースでリリースして後からコストベースに変えたという噂を聞いたことがありますが、特に日本では計算量が固定されるルールベースに人気が出たのは面白いですね。脱線しますが、マルチプロセスアーキテクチャも Segmentation fault でサーバプロセスならセッションレベルの障害で済むから好むお客さんもいたとのことで、設計者の意図と異なる点が好まれたり、歴史を振り返ると面白いです。RDBMSの歴史に興味がある方は東大でデータベースの研究をされている早水先生が書かれた The Database Times vol.1 の「データベースシステムの夜明け」を超おすすめします。

Oracle Database のクエリ最適化には「問合せの変換（Query Transformation）」と「アクセス・パス解析（Access Path Analysis）」がありますが、今回はアクセスパス解析について書きます。Query Transformation はユーザーの発行したSQLをオプティマイザが内部的により効率的なSQLに書き換えることです。例えばビューに対するSQLでビューを展開する View Merging やフィルタ条件や結合条件をビューの中に入れる Predicate Push Down などがあります。Optimizer(10053) Trace で final query のセクションを見ると最終的にどのようなSQLに書き換えられたかを見ることができます。クエリ最適化について詳しくは Oracle でクエリオプティマイザのソースコードを書かれていた真下さんの記事 Oracleのオプティマイザが問い合わせ処理を最適化する方法～ソースコードを書いているエンジニアが語る | Oracle オラクルエンジニア通信 - 技術資料、マニュアル、セミナー Blog をご覧ください。
性能を出す（実行時間を短くする）方法は仕事量を減らす、並列化、高速化の3つしかありませんが、最も大切なのは仕事量を減らすことです。コストベースオプティマイザも仕事量（コスト）を最小化するアルゴリズムを予測します。今回は触れませんが仕事量を減らす上で1番大切なのはデータ構造です。

RDBMSのコスト計算式は以下のように単価×回数で算出します。シーケンシャルリード1回の時間×ページ(ブロック)数+ランダムリード1回の時間×ページ(ブロック)数+1タプル(行)の処理に必要なCPUサイクル×タプル(行)数などです。この総コストが一番小さくなる実行計画が選択されます。

より深く知るオプティマイザとそのチューニング from Yuto Hayamizu

Oracle Database のコスト計算式は以下のように、シングルブロックリード×回数+マルチブロックリード×回数+CPUサイクル数×回数のようになっています。

この予測が EXPLAIN PLAN などに出てくるコストですが、

SQLチューニングの際は予測ではなく実態を見るようにしましょう。往々にしてSQLが遅いときには予測が外れていることがあります。「推測するな、計測せよ」と言いますが、パフォーマンス分析は「時間ベース」で行うことが大切です。Oracle Database の SQL Monitor(SQL監視)は便利ですね。このような機能のない RDBMS でもコールスタックをサンプリングして発生回数の多いものを調べれば似たようなことができると思います。アクセスパスが分かるような関数名で実装されている前提ですが。

特に仕事量が大きく見積が難しいのが結合です。結合対象テーブル数が多く、フィルタ条件が多いと統計学的に見積ミスが発生しやすくなります。結合方法と仕事量の関係は以下の通りです。Nested loop、Hash Join、Sort Merge Join などの結合方法が一般的ですが、Db2 にはジグザグ結合というものがあるらしいです。

問合せ最適化インサイド from Takahiro Itagaki

フィルタ条件が多いと行数（カーディナリティ）見積がはずれやすくなります。

例えば、12.1の適応計画やSQL計画ディレクティブはこれを補正する機能です。

このように Oracle Database はクエリオプティマイザの改善を重ねてきました。

東大でデータベースの研究をされている早水さんのスライドを拝見しているとアカデミックではそれより前に似たような話が出ているなと思います。

より深く知るオプティマイザとそのチューニング from Yuto Hayamizu

Oracle Database には Optimizer(10053) Trace というクエリオプティマイザがどのようにコスト計算をしたかを詳細に追える機能がありますので、興味がある方は戯れてみてください。yoheia/get_53_46_xplan.sql at master · yoheia/yoheia · GitHub は難解なトラブルシューティングでクエリオプティマイザの計算ロジックを紐解いたときに使った SQL スクリプトです。
さらに詳しくクエリオプティマイザについて知りたい方は参考情報をご覧ください。特におすすめは Jonathan Lewis の Cost-Based Oracle Fundamentals です。14章まるまる使って Optimizer(10053) Trace の読み方が解説されています。