結合の実行計画
最後に実行計画の見方を学ぶSQL文は、結合を行うものです。SQLが遅いケースの十中八九は結合が絡んでいますし、結合が利用される場合、実行計画が必ずしも最適にはならないケースがあるため、これを学ぶことには重要な意味があります。
結合を行うにはテーブルが2つ以上必要ですので、図4の予約管理テーブルを追加しましょう。データ件数は10件を登録するとします。
図4 予約管理テーブル
Reservations（予約）
reserve_id
（予約ID） | shop_id
（店舗ID） | reserve_name
（予約者） |
| 1 | 00001 | Aさん |
| 2 | 00002 | Bさん |
| 3 | 00003 | Cさん |
| 4 | 00004 | Dさん |
：
：
|
| 10 | 00010 | Jさん |
実行計画を取得する対象のクエリは、次のような予約の存在する店舗を選択するSELECT文です。
SELECT shop_name
FROM Shops S INNER JOIN Reservations R
ON S.shop_id = R.shop_id;
結合のアルゴリズム
一般的に、DBMSが結合を行うアルゴリズムは3種類あります。最も基本的でシンプルなのがNested Loopです。片方のテーブルを読み込み、その1つのレコードに対して、結合条件に合致するレコードをもう一方のテーブルから読み込みます。手続き型言語で書くと二重ループで実装するので、この名前があります。
2つ目は、Sort Merge[9]です。結合キー（今のケースでは店舗ID）でレコードをソートしてから、順次アクセスを行って2つのテーブルを結合します。結合の前処理として必ずソートを行うので、そのための領域を必要とします。
3つ目は、Hashです。名前のとおり、結合キーの値をハッシュ値にマッピングします。これもハッシュテーブルを確保するための領域を必要とします。
各DBMSが採用するアルゴリズム
Oracle、PostgreSQL、MySQLが、それぞれどのような結合方式を採用するか見てみましょう（リスト7～9）。
リスト7 結合の実行計画（Oracle）
実行計画
----------------------------------------------------------
Plan hash value: 1724488161
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 48 | 3 (0)| 00:00:01 |
| 1 | NESTED LOOPS | | 1 | 48 | 3 (0)| 00:00:01 |
| 2 | TABLE ACCESS FULL | RESERVATIONS | 1 | 7 | 2 (0)| 00:00:01 |
| 3 | TABLE ACCESS BY INDEX ROWID| SHOPS | 1 | 41 | 1 (0)| 00:00:01 |
|* 4 | INDEX UNIQUE SCAN | SYS_C004157 | 1 | | 0 (0)| 00:00:01 |
-----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("S"."SHOP_ID"="R"."SHOP_ID")
リスト8 結合の実行計画（PostgreSQL）
QUERY PLAN
----------------------------------------------------------------------------------
Merge Join (cost=1.27..2.75 rows=10 width=2)
Merge Cond: (s.shop_id = r.shop_id)
-< Index Scan using shops_pkey on shops s (cost=0.00..13.15 rows=60 width=8)
-< Sort (cost=1.27..1.29 rows=10 width=6)
Sort Key: r.shop_id
-< Seq Scan on reservations r (cost=0.00..1.10 rows=10 width=6)
リスト9 結合の実行計画（MySQL）
+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+----------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+----------+-------+
| 1 | SIMPLE | R | ALL | NULL | NULL | NULL | NULL | 10 | 100.00 | |
| 1 | SIMPLE | S | eq_ref | PRIMARY | PRIMARY | 5 | mysql.R.shop_id | 1 | 100.00 | |
+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+----------+-------+
Oracleの場合、Operation列にはっきりとNESTED LOOPSと出ているため、迷うことはありません（リスト7②）。また、PostgreSQLがSort Mergeを行っていることもわかります（リスト8②）。
ここでちょっと実行計画の読み方のワンポイントを書いておくと、実行計画は一般的にツリー構造で出力されるため、入れ子の深い操作が先に実施されます。PostgreSQLの結果を例にとると、MergeよりもSortのほうが階層が深いため、Sortが先に実施されることがわかります。
これら2つに比べると、MySQLの結果は見づらいものです。ツリー構造にもなっていないし、結合アルゴリズムも明示されていません。実は後者の問題については簡単に解決します。というのも、MySQLが選択する結合アルゴリズムは、Nested Loopただ一つだからです（正確にはその変形版もありますが）。しかし、ツリー構造になっていないという問題については、残念ながら読む人間が再構成してやる必要があります。今、実行計画の「type」列（リスト9②）から、ReservationsテーブルはALLつまりフルスキャンが行われていることを示します。一方、Shopsテーブルにはeq_refという奇妙な用語が現れていますが、これはもう一方のテーブルのレコードの値をもとにインデックススキャンを行っていることを示します。したがって、結局のところOracleと同じアルゴリズムということになります。
アルゴリズムはオプティマイザが決定する
どのようなアルゴリズムが選択されるかは、基本的にオプティマイザ任せで、ユーザが口出しすることはできません。また、DBMSによっても癖があります。まったく同じDDL（Data Definition Language）とデータなのに、OracleとMySQLがNested Loopを選択したのに対し、PostgreSQLがSort Mergeを選択したことからもそれがわかります。
ただ、経験則から見ると、テーブルの件数が少ないとき―少なくとも片方のテーブルの件数が少ないとき―には、Nested Loopが選択されることが多く、両者のテーブル件数が大きくなればなるほど、Sort MergeやHashが選択されることが多くなります。これにはもちろん理論的な理由もあって、Nested Loopに比べると、Hashはデータ量の増大に対する処理コストの増大が緩やかな傾向があるからです。
これに加えて、Hashは「=」による等値結合でしか使えない、結合キーにインデックスが存在する場合はNested Loopが選択されやすいなど、多くの条件が関係してアルゴリズムが決定されます。
オプティマイザの失敗？
しかし、データ件数が多くて、かつSort MergeやHashが選択されている場合、注意を払う必要があります。というのも、実はオプティマイザが良かれと思って選んだアルゴリズムが最適でない可能性があるからです。
3つのアルゴリズムのうち、Sort MergeとHashは、先述のように作業領域を必要とします。DBMSは可能な限りこれをメモリ上に確保しようとしますが、常にすべての処理をメモリ上で完結させられる保証はありません。オプティマイザが十分に賢ければ、必要なメモリ量を見切ったうえで実行計画を立てるでしょうが、実際にはそれほどうまくいかないこともよくあります。
メモリ上で処理が完結しなかった場合、DBMSはしかたなくデータの一部をディスクへ書き出します。しかし、メモリに比べてディスクのI/O性能は非常に悪いため、オプティマイザが予想した以上に膨大な時間がかかることがあるのです。HashやSort Mergeが使用されたSQL文のパフォーマンスが悪い場合、最も多い原因がこの「データ落ち」です。
データベースの鉄則 1
結合で一番怖いのは、データがメモリから落ちること
実行計画を変える
最近のオプティマイザは優秀ですが、完全ではありません。前節でも解説したように、良かれと思って選んだ実行計画が惨憺（さんたん）たるパフォーマンスを生むこともあります。また、そうした複雑な問題以前に、絶対に使ったほうが速いはずのインデックスを使ってくれない、テーブルの結合順序が明らかにおかしい、といったポカもやります。
そうした場合、最後のチューニング手段が実行計画を手動で変えてしまうことです。たとえば、Oracle、MySQLなどが持っているヒント句を使うと、SQL文の中に埋め込むことで、オプティマイザに強制的に命令を出すことができます。ヒント句は結果には中立で、あくまでデータへのアクセスパスだけを変更するものです。
しかしお気づきのように、これはリレーショナルデータベースの基本精神を真っ向から否定する所業です。そのためか、どのベンダーも実行計画を変える手段を増やすことには消極的です。要するに、実行計画を手動で変えなければならないとしたら、それは現在のデータベースがまだまだ非力な存在だからなのです。いずれ、より精度の高いプランニングを行うオプティマイザが現れることによって、この問題は解消されていくでしょう。その意味で、ヒントが急場しのぎの手段だということは、みなさんも覚えておいてください。
まとめ
本稿では、データアクセスの方法を決定する実行計画と、それを作成するオプティマイザの動作について見てきました。パフォーマンスチューニングを行うときはこの2つの基礎知識を持っていることが必須になります。それでは、重要なポイントをまとめましょう。
- ユーザがデータアクセスの手続きを考えないのがリレーショナルデータベースの理想
- ユーザの代わりに実行計画を考えてくれるのがオプティマイザ
- オプティマイザを正しく動かすには統計情報が正しいことが必須
- しかしオプティマイザが常に正しく動くとは限らない
- そういうときは実行計画を調べる必要があるので、読めるようにしておこう
今回の演習問題は次のものです。
演習問題
あなたの使うDBMSで、マニュアルで実行計画を変える手段を調べなさい。
演習問題の解答は筆者のWebサイトおよび技術評論社のWebサイトで公開します。それでは、次回でまたお会いしましょう。
参考資料
- 『データベースシステム概論 第6版』
（C.J.Date著／藤原譲訳／丸善／1997年）
- 「18章 最適化」がRDBMSにおける最適化戦略についての概略を知るのに便利です。
- 『Database Management Systems 3rd ed.』
（Raghu Ramakrishnan、Johannes Gehrke 著、McGraw Hill Higher Education、2002年）
- オプティマイザの動作については「12 Overview of Query Evaluation」を参照してください。また「14 Evaluating Relational Operators」は、Nested Loop、Sort Merge、Hashのそれぞれのアルゴリズムを理解するのに役立ちます。
