実行計画

概要

実行計画（query execution plan）は、SQL 文を受け取ったデータベースが「このクエリを実際にどんな手順で処理するか」を決めた作戦書です。SQL は「どんなデータが欲しいか」だけを宣言する言語で、「どうやって取ってくるか」は書きません。テーブルを端から全部読むのか、インデックスで絞り込むのか、2つのテーブルをどの順番・どの方式で結合するのか — その具体的な手順を決めるのがデータベース内部のオプティマイザ（最適化器）であり、その決定結果が実行計画です。

開発者がこの語彙に出会うのは、ほぼ間違いなく「クエリが遅い」ときです。EXPLAIN コマンドを SQL の頭に付けて実行すると、データベースは実行計画をそのまま見せてくれます。同じ SQL でも、インデックスの有無やデータ量によって選ばれる計画はまったく変わり、性能は数千倍違うこともあります。遅いクエリの調査は「SQL を眺める」のではなく「実行計画を読む」ことから始まる — これがデータベース性能改善の第一歩です。

なぜ生まれたか

SQL 以前のデータベースでは、プログラマがレコードへのアクセス経路（どのインデックスをどの順でたどるか）を自分でコードに書いていました。データの物理的な持ち方が変わればプログラムも書き直しです。1970年代のリレーショナルモデルは「欲しい結果だけを宣言し、取り方はシステムに任せる」という分離を打ち出しましたが、これが成立するには「システムが取り方を賢く決められる」ことが必須でした。同じ結果を返す手順は無数にあり、選択を誤れば宣言型の利便性は「遅くて使いものにならない」で終わってしまうからです。

この課題に答えたのが、IBM の System R（1970年代後半）で開発されたコストベースオプティマイザです。Patricia Selinger らの1979年の論文は、取りうる手順それぞれの処理コストを、テーブルの行数や値の分布といった統計情報から見積もり、最も安い計画を選ぶ方法を示しました。結合の順番を動的計画法で絞り込むこの設計は、いまの PostgreSQL や MySQL のオプティマイザにも受け継がれています。この発明によって「人間は what を書き、機械が how を決める」という SQL の理想が実用になりました。実行計画とは、この自動化された意思決定を人間が覗き込むための窓なのです。

詳細

計画は木である

実行計画の実体は、演算子（オペレータ）を積み上げた木構造です。葉にあたるノードがテーブルからデータを読み出し（スキャン）、その上のノードが結合・絞り込み・集約・並べ替えを行い、根が最終結果を返します。データは葉から根へ向かって流れます。EXPLAIN の出力はこの木をインデントや矢印で表現したものなので、「一番深い（内側の）行から読む」のが読み方の基本です。

フルスキャンとインデックススキャン — 該当行の数で勝ち負けが入れ替わる

葉のノードで最も重要な分岐が、テーブルの読み方です。フルスキャン（PostgreSQL では Seq Scan）はテーブルの全ページを先頭から順に読む方式で、条件に何行が当たろうと、読む量は表の大きさ n に比例します。インデックススキャンはインデックスの木を根から葉までたどって該当行の場所を見つけ、その行だけを本体から拾いに行く方式です。計算量で書くと、木をたどる部分が O(log n)、該当する k 行を拾う部分が O(k) で、合わせて O(log n + k) です。

この「+ k」が肝心です。インデックスの順に並んだ行は、本体のページの上ではたいていばらばらの場所にあるので、1行拾うたびに別のページへ飛ぶランダムな読み取りになります。ディスクでは、まとめて順に読むより飛び飛びに読むほうが1ページあたりずっと高くつきます（PostgreSQL の既定の見積もりでは4倍）。そのため k が小さいうちはインデックスが圧勝しますが、該当行が表の数%を超えるあたりで、全部を順に読むフルスキャンのほうが安くなります。「なぜインデックスを使ってくれないのか」の答えは、多くの場合「使わないほうが安いと見積もったから」です。

逆転する割合は、1ページに入る行の数、表の大きさ、行の物理的な並び（インデックスの順と本体の並びがそろっていれば飛び飛びにならない）、ストレージの種類で変わります。中間には、該当するページの一覧を先に作ってからページ順に読む Bitmap Heap Scan という折衷もあります。結合方式（少数の行どうしなら Nested Loop、大量の行どうしなら Hash Join など）の選び方も同じ理屈で、どれも「何行ありそうか」の見積もりが判断の土台になっています。

WHERE の範囲を広げたり狭めたりして、オプティマイザがどこで計画を切り替えるかを確かめてください。統計を「古い」にすると、見積もりが外れたまま誤った計画を選ぶ様子も再現できます。

統計情報 — 見積もりの原料

その見積もりの原料が統計情報です。データベースはテーブルごとに行数、各列の値の分布（ヒストグラムと、特に多い値の一覧）、値の種類数などを、サンプリングで集めて保持しています。オプティマイザは「この条件なら全体の約2%が該当するはず」という推定（選択率）をここから導きます。

ということは、統計が実態とずれていれば計画も狂います。大量のデータを一括で投入・更新した直後や、値の分布が偏っている列で、オプティマイザが行数を何百倍も少なく見積もり、インデックスで1行ずつ拾う最悪の計画を選ぶ、というのは実務で本当によく起きる事故です。PostgreSQL の ANALYZE（自動実行の autovacuum も含む）や MySQL の ANALYZE TABLE で統計を更新することは、インデックス設計と並ぶ性能運用の基本です。また「昨日まで速かったクエリが今日突然遅くなった」という現象の多くは、データ量や分布の変化で見積もりが逆転点を越え、計画が切り替わったことが原因です。

EXPLAIN の読み方と実務の勘所

調査の実際は、EXPLAIN で計画を見るところから始まり、可能なら EXPLAIN ANALYZE（実際に実行して、実測の行数と時間も表示する形式）まで取ります。ANALYZE 付きは本当にクエリを実行するので、UPDATE や DELETE ではトランザクションの中で試してロールバックします。着目点は3つです。第一に、大きなテーブルへの意図しないフルスキャンがないか。第二に、推定行数（rows）と実際の行数（actual rows）が大きく食い違うノードがないか。食い違いがあれば統計の問題で、そのノードより上の判断はすべて疑わしくなります。第三に、ソートや集約がメモリに収まらずディスクにあふれていないか。改善の手段は、インデックスの追加や複合インデックスの列順の見直し、クエリの書き換え、統計の更新が三本柱です。

なお、ORM が生成する SQL は開発者の目に触れにくいため、実行計画の問題（そもそもクエリが件数ぶん飛ぶ N+1問題も含めて）に気づくのが遅れがちです。RDBMS のスロークエリログを監視し、遅いクエリが見つかったら EXPLAIN を取る、という定常的なループを回すことが、データベースを長く健康に保つ運用の型になります。PostgreSQL の auto_explain のように、遅かったクエリの計画を自動でログに残す仕組みも用意されています。

試問

10万行の注文の表に SELECT * FROM orders WHERE price BETWEEN a AND b を投げます。上の棒は値段ごとの実際の行数、破線はデータベースの統計（見積もりの原料）が思っている分布です。統計はセール価格への一括 UPDATE の前に取ったままです。取っ手や帯を動かして範囲を変えると、オプティマイザ（計画を選ぶ部品）が推定行数から Index Scan（索引で拾う）か Seq Scan（全部読む）を選んで実行し、「ANALYZE を実行」で統計を取り直せます。