SQL クエリオプティマイザー・実行計画

2021.10.12
データベース設計
データベースの基礎知識
おうちで学べるデータベースのきほん
おうちで学べるデータベースのきほん
翔泳社
Amazonの商品レビュー・口コミを見る
SQL 第2版: ゼロからはじめるデータベース操作
SQL 第2版: ゼロからはじめるデータベース操作
翔泳社
Amazonの商品レビュー・口コミを見る
スポンサーリンク

初めに・実行計画とは

実行計画とは、SQL クエリを実行するために使用される手順の組合せです。

データベースでは扱うデータ量が多く、ストレージのスケールアウトが困難なため、すぐにボトルネックが発生します。

そのため、データベースには SQL クエリから複数の実行計画を生成し、最も実行コストの低い実行計画を選択するオプティマイザーという機能があります。

以下にデータベースが SQL クエリを実行する手順を紹介します。

当然ですが、投入する SQL クエリによって、オプティマイザーで最適化された実行計画は異なります。

そのため、投入する SQL クエリ自体を人間が最適化することもあります。これを SQL チューニングと呼びます。

スポンサーリンク

パーサー（Parser）とは

パーサーは主に以下の４つの役割を持ちます。

  • 構文チェック
  • テーブルやカラムの存在チェック
  • アクセス権限のチェック
  • SQL クエリからクエリツリーを生成

構文チェック

構文が間違っている場合はエラーを返します。

SELECT * FRO tbl;
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'FRO tbl' at line 1

正しくは「SELECT * FROM tbl;」です。

テーブルやカラムの存在チェック

テーブルやカラムが存在しない場合はエラーを返します。

SELECT * FRO tbl;
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'FRO tbl' at line 1

test データベースの none テーブルは無いと返されています。

アクセス権限のチェック

アクセス権限をチェックし、権限がない場合はエラーを返します。

SELECT * FROM test.account;
ERROR 1142 (42000): SELECT command denied to user 'hogetech'@'localhost' for table 'account'

ユーザー hogetech はテーブル account に対する SELECT コマンドの権限が無いと表示されています。

クエリツリーの生成

SQL クエリを、データベースが処理しやすい論理的な表現であるクエリツリーに変換します。

https://eng.uber.com/queryparser/

このクエリツリーを後続のオプティマイザーに渡し、最適なクエリ実行計画を作成します。

スポンサーリンク

クエリ実行計画とは

クエリ実行計画では、クエリツリーを実際に実行するために、主に以下の３つのオペレーションを決定することです。

アクセスパス (Access Path)

アクセスパス (Access Path) には、主に以下の２種類方法があります。

  • フルスキャン
  • インデックススキャン

フルスキャン

フルスキャンはテーブルの全ての行をスキャンしてから処理する方法です。

id = 3 以外の行は使用しないので、無駄にストレージから読み込んだことになり、その分 SQL クエリの実行が遅くなります。

インデックススキャン

インデックススキャンは、インデックスから必要な行を探索した後、スキャンする方法です。

上記の例では、フルスキャンと比較して、スキャンする行を７行から３行に削減できます。

■インデックスの種類

主なインデックスの種類は、以下の記事が参考になります。

データベース性能を向上させる「インデックス」を理解する
あの“津崎さん”も保有する難関資格「データベーススペシャリスト」。本企画では、データベーススペシャリスト試験 午前／午後試験対策のための「基礎知識」を抜粋してお届けします。今回は「インデックス」の基礎を解説します。
atmarkit.itmedia.co.jp

■インデックスの作成方法

インデックスは主キーで必ず自動作成される他、「CREATE INDEX」文を利用してあらかじめ自作することも可能です。

■インデックスの利点

  • スキャンする行を削減
  • ソート処理をスキップ可能（インデックスはソートされているため）
    • 以下の SQL は内部的にソート処理を行う可能性があります
      • GROUP BY 句
      • 集約関数（COUNT, SUM, AVG 等）
      • 集合演算（UNION,INTERSECT,EXCEPT）

■インデックスの欠点

UPDATE 文や DELETE 文が遅くなる可能性があります。これはテーブルが変更するとインデックスを変更する必要があるためです。

■インデックスを作成する基準

インデックスの利点、欠点を踏まえた上で、インデックスを作成する基準は以下のとおりとなります。

インデックスを作成する基準説明
サイズの大きなテーブルだけ大きなテーブルはフルスキャンだと時間がかかる
小さなテーブルはフルスキャンで十分早い
カーディナリティの高い（異なる値が多い）カラムを選択カーディナリが高いと、行を絞り込みやすい
カーディナリが低いと、値が重複し多くの行が残ってしまう
値の更新回数が少ないUPDATE 文や DELETE 文が遅くなるため

結合順序 (JOIN Order)

結合順序 (JOIN Order)では、アクセスするテーブル（表）の順番を入れ替えることで実行コストを抑えます。

結合処理では、最初にアクセスする表を「外部表（駆動表）」、２番目以降にアクセスし、外部表に結合する表を「内部表」と呼びます。

以下の SQL クエリでは、結合順序を変更する前は tbl1 を「外部表（駆動表）」、tbl2 を「内部表」と呼びます。

SELECT * FROM tbl1 JOIN tbl2 on tbl1.id = tbl2.id;

後述するネステッドループ結合 (Nested Loops Join) では、内部表でインデックススキャンを利用可能なため、行数が大きいテーブルを指定したほうが実行コストが下がります。

なお、最近のオプティマイザーは必要に応じて実行順序を変更します。

結合方法 (JOIN Method)

結合方法には主に以下の３つのアルゴリズムが存在します。

ネステッドループ結合 (Nested Loops Join)

ネステッドループ結合 (Nested Loops Join) は、外部表と内部表を総当りで結合条件を比較する方法です。

ネステッドループ結合の利用シーンは以下のとおりです。

利用シーン説明
外部表（テーブル）の行数が少ない総当りの数が少なくなる
内部表（テーブル）にインデックスがある総当りの数が少なくなる
内部表はインデックススキャンを利用するが、外部表はフルスキャンを利用するため、行数を少ないテーブルを外部表にすると良い

また、バッファを利用してテーブルの読み取り回数を削減する Block Nested-Loop (BNL) 結合という方法もあります。

Block Nested-Loop (BNL) 結合アルゴリズムは、外側のループで読み取られた行のバッファリングを使用して、内側のループでテーブルを読み取る必要がある回数が削減されます。

https://dev.mysql.com/doc/refman/8.0/ja/nested-loop-joins.html

ハッシュ結合 (Hash Join)

ハッシュ結合 (Hash Join) は以下の手順で結合する方法です。

  1. データ・セットの小さい方を使用して、メモリーに結合キーについてのハッシュテーブルを作成
  2. データ・セットの大きい方をスキャンし、ハッシュ表を調べて結合された行を見つける

ハッシュ結合の利用シーンは以下のとおりです。

利用シーン説明
テーブルの行数が多い行数が小さいとハッシュテーブルを作成する時間が大きなオーバーヘッドとなる
結合条件が等価結合（＝）非等価結合はハッシュテーブルで判断不可

ソート/マージ結合 (Sort Merge Join)

ソート/マージ結合(Sort Merge Join) は以下の手順で結合する方法です。

  1. 結合キーでソート
  2. ソート順に比較して結合

ソート/マージ結合の利用シーンは以下のとおりです。

利用シーン説明
テーブルの行数が多い行数が小さいとソートする時間が大きなオーバーヘッドとなる
結合条件が非等価結合（<, <=, >, >=）ソートしているため、非常に高速

クエリ実行計画の確認（EXPLAIN）

EXPLAIN ステートメントでは、SQL クエリのクエリ実行計画を確認することが可能です。

EXPLAIN SELECT id FROM tbl;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
|  1 | SIMPLE      | tbl   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    3 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
オペレーション対応する EXPLAIN の表示
アクセスパス (Access Path)type
結合順序 (JOIN Order)EXPLAINの出力の順序でテーブルを処理
結合方法 (JOIN Method)Extra に記載

MySQL EXPLAIN のもっと詳細な見方は以下の記事をご覧ください。

漢(オトコ)のコンピュータ道: MySQLのEXPLAINを徹底解説!!
ちょっと硬派なコンピュータフリークのBlogです。
nippondanji.blogspot.com

オプティマイザー（Optimizer）とは

オプティマイザーは、パーサーから受け取ったクエリツリーを元に、複数のクエリ実行計画を生成し、最適な（コストの低い）実行計画を選択します。

参考：https://docs.oracle.com/cd/E57425_01/121/TGSQL/tgsql_optcncpt.htm

オプティマイザーでクエリツリーから最適なクエリ実行計画を選択する手順は以下のとおりです。

  1. クエリトランスフォーマーは、必要に応じて処理効率の良いクエリツリーに書き換え
  2. エスティメーターは、「1. で作成したクエリツリー」と「元のクエリツリー」を比較し、実行コストの低いものを選択
  3. プランジェネレーターは、2. で選択したクエリツリーを元にクエリ実行計画を複数生成
  4. エスティメーターは 3. で生成したクエリ実行計画からコストの低いものを選択

以降では「クエリトランスフォーマー」・「エスティメーター」・「プランジェネレーター」の詳細について説明します。

クエリトランスフォーマー (QueryTransformer）

クエリトランスフォーマーは、元のSQL文を、意味的に同等でよりコストの低いSQL 文を生成します。

例えば、以下の SQL クエリを実行したとします。（※実際にはクエリツリーの形です）

SELECT * FROM tbl1, tbl2
WHERE tbl1.id = 3
AND tbl1.id = tbl2.id

この SQL クエリの場合、データベースは tbl2 をフルスキャンした後、tbl1.id = tbl2.id となる行に絞ります。

一方で、クエリトランスフォーマーは SQL クエリに「AND tbl2.id = 3」を追加することがあります。（https://xtech.nikkei.com/it/article/COLUMN/20060111/227097/ より）

SELECT * FROM tbl1, tbl2
WHERE tbl1.id = 3
AND tbl2.id = tbl1.id
AND tbl2.id = 3

これにより、元の SQL と意味的に同等ですが、tbl2.id がプライマリーキーの場合は、データベースは tbl2 をインデックススキャンするため、コストを下げることができます。

エスティメーター (Estimator)

エスティメーターは、以下の２つのコストを判断し、低い方を選択します。
・クエリトランスフォーマーで生成した SQL クエリと元の SQL クエリのコスト
・プランジェネレーターで生成した複数のクエリ実行計画のコスト

エスティメーターは、統計情報を元に主に以下の５つの指標からコストを推定します。

カーディナリティ (Cardinality)

カーディナリティ (Cardinality) は、異なる値の数です。
SELECT DISTINCT COUNT(<カラム>)の結果に相当します。

カーディナリティが高いカラムほど、読み込む行数が少なくなるため、インデックス作成に適した行と言えます。

（上記の例の場合、「WHERE id = 1」 だと１行、「WHERE sex = 'male'」だと２行）

統計情報

統計情報とは、テーブルやインデックスでどんな値がどんな頻度で出現するか統計を取得したものです。

これにより、「テーブルの行数が少ないからフルスキャンのコストは低いかな」といった判断が可能になります。

統計情報には主に以下の情報が含まれます。

  • 最後に更新した時間
  • テーブル内の行数
  • インデックスのサイズ
  • インデックス内のページの総数
  • インデックス内のリーフページの数
  • インデックスのカラム内のカーディナリティ

(https://dev.mysql.com/doc/refman/8.0/ja/innodb-persistent-stats.html より)

なお、統計情報はテーブル内の全てのページを確認しているわけではありません。

適当にいくつかのページを抽出して、「大体こんな感じかな」と推測しています。

これは統計情報を更新するために、毎回フルスキャンをしているとデータベースが重くなるためです。

プランジェネレーター (PlanGenerator)

プランジェネレーターはクエリツリーから複数のクエリ実行計画を生成します。

例えば、プランジェネレーターがクエリ実行計画として、以下の３つの結合方法を生成した場合を考えます。

オプティマイザーでは以下のような動作となります。

NestedLoops Join
  NestedLoops Join cost: 13.17
    Outer table: Card: 27.00 Cost: 2.01 Resp: 2.01 Degree: 1 Bytes: 16 Access path analysis for EMPLOYEES
. . .
SortMerge Join
  SortMerge Join cost: 6.08
     resc: 6.08 resc_io: 4.00 resc_cpu: 2501688
     resp: 6.08 resp_io: 4.00 resp_cpu: 2501688
. . .
SM Join (with index on outer)
  Access Path: index (FullScan)
. . .
Hash Join
  Hash Join cost: 4.57
     resc: 4.57 resc_io: 4.00 resc_cpu: 678154
     resp: 4.57 resp_io: 4.00 resp_cpu: 678154
Best:: JoinMethod: Hash Join

(参考 https://docs.oracle.com/cd/E57425_01/121/TGSQL/tgsql_optcncpt.htm)

つまり、以下のような動作となります。

  1. クエリ実行計画を１つ生成
  2. エスティメーターでクエリ実行計画のコストを推定
  3. 1, 2 を繰り返し、最もコストの低いクエリ実行計画を選択

最後に

データベース設計
データベースの基礎知識

参考資料・おすすめの書籍

一番初めに読む本

経験者向けの入門本

MySQL を触る方におすすめ

問合せオプティマイザの概念
A solid understanding of the optimizer is essential for SQL tuning.
docs.oracle.com
スポンサーリンク