DBアタマアカデミー

第4回 クエリ評価エンジンと実行計画―“シェフおまかせ”はいつも美味しいのか(3)

この記事を読むのに必要な時間:およそ 4 分

結合の実行計画

最後に実行計画の見方を学ぶ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です。名前のとおり,結合キーの値をハッシュ値にマッピングします。これもハッシュテーブルを確保するための領域を必要とします。

注9)
Sort Mergeと名前が似ているアルゴリズムにMerge Sortがありますが,両者は異なるものです。前者が結合のアルゴリズムで「ソートしてからマージする」という意味なのに対し,後者はソートのアルゴリズムで,内部でマージを行っているためこの名前があります。

各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と同じアルゴリズムということになります。

著者プロフィール

ミック

SI企業に勤務するDBエンジニア。主にデータウェアハウス業務に従事している。自身のサイト「リレーショナル・データベースの世界」でデータベースとSQLについての技術情報を公開している。『Web+DB Press』で「SQLアタマアカデミー」を連載中。

著書:『SQL ゼロからはじめるデータベース操作』(翔泳社,2010)『達人に学ぶ SQL徹底指南書』(翔泳社,2008)訳書:J.セルコ『SQLパズル 第2版』(翔泳社,2007)

DBアタマアカデミー:サポートページ

コメント

コメントの記入