クエリチューニングのための実行計画/統計情報/オプティマイザー

クエリチューニングのために、「クエリを実行してから結果を取得するまで」の流れを紹介します。

クエリチューニングの際には、実行計画を確認したり、統計情報を更新します。

EXPLAIN <SQL クエリ>

ANALYZE TABLE <テーブル名>

関連記事：データベースの基礎知識編
データベースとは	SQL コマンド	ACID 特性	Backup/PITR	レプリケーション	実行計画

学習ロードマップ
Linux	ネットワーク	データベース	データ分析	機械学習	セキュリティ

おうちで学べるデータベースのきほん第2版

翔泳社

Amazonの商品レビュー・口コミを見る

SQL 第2版: ゼロからはじめるデータベース操作

翔泳社

Amazonの商品レビュー・口コミを見る

パーサー（Parser）とは

パーサー (Parser)パーサーとは、SQL 文の構文をチェックするプログラムです。

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

構文/テーブルやカラムの存在/アクセス権限のチェック
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 tbl2;

ERROR 1146 (42S02): Table 'db.tbl2' doesn't exist

SELECT * FROM tbl3;

ERROR 1142 (42000): SELECT command denied to user 'hogetech'@'localhost' for table 'tbl3'

クエリツリーの生成

SQL 文を、データベースが処理しやすい AST (抽象構文木) に変換します。

一般的な AST：https://eng.uber.com/queryparser/

MySQL の AST：https://www.slideshare.net/slideshow/mysql-server-query-path/249835483#5

絵で見てわかるOS/ストレージ/ネットワーク新装版

翔泳社

Amazonの商品レビュー・口コミを見る

達人に学ぶSQL徹底指南書第2版初級者で終わりたくないあなたへ

翔泳社

Amazonの商品レビュー・口コミを見る

実行計画とは

オプティマイザーの説明に入る前に、出力の実行計画を事前知識として説明します。

実行計画実行計画とは、SQL 文(から生成した AST) を実行するための手順です。

実行計画では、主に以下の 2 つの手順を決定します。

アクセスパス (Access Path)
結合方法 (JOIN Method)

アクセスパス (Access Path)

アクセスパス (Access Path) には、フルテーブルスキャンとインデックススキャンがあります。

フルテーブルスキャン (全表スキャン/sequential scan)

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

インデックススキャン

インデックススキャンとは、インデックスを探索し、必要な行だけスキャンする方法です。

インデックスの詳細については、以下の記事をご覧ください。

フルテーブルスキャンとインデックスの比較

	フルテーブルスキャン	インデックススキャン
読み込み速度	低速上記の例では 7 行をスキャン	高速 ※1 上記の例では 3 回探索 + 1 行をスキャン
書き込み速度	普通	低速データと別に、インデックスも更新するため
ソート	スキップ不可	スキップ可能 ※2

※1 インデックスを探索するオーバーヘッドがあるため、小さなテーブルの場合はフルテーブルスキャンの方が早い
※2 インデックスはソートされているため。インデックス以外はソートする必要あり

結合方法 (JOIN Method)

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

ネステッドループ結合 (Nested Loops Join)
ソート/マージ結合 (Sort Merge Join)
ハッシュ結合 (Hash Join)

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

ネステッドループ結合とは、外部テーブルと内部テーブルを 1 行ずつ結合する方法です。

プログラマーだと、for 文のネストループ
最悪計算量は O(M * N)、内部テーブルにインデックスを使った場合は O(M log(N))。(外部テーブル M 行、内部テーブル N 行)

外部テーブル (駆動表)外部テーブルとは、最初にアクセスするテーブルです。

内部テーブル内部テーブルとは、2 番目以降にアクセスして、外部テーブルに結合するテーブルです。

パフォーマンスについて

ネステッドループ結合は、内部/外部テーブルの選択がパフォーマンスに影響します。

今のオプティマイザーは、どのテーブルを外部/内部テーブルにするか判断します。
(昔は FROM 句のテーブルが外部テーブルだったり、そうじゃなかったり)

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

ソート/マージ結合とは、ソートした値を利用して、結合キーの確認をスキップする方法です

クイックソートなので各テーブルの計算量は O(N log(N))
これを外部テーブルと内部テーブルで行うので、Sort/Merge の計算量は O(N log(N) + M log(M))

ソート済みの場合、この 1 行ずつ見る処理だけなので計算量は O(M + N)
ソートしてない場合、ソート計算量が大半を占めるので O(N log(N) + M log(M)) となる。O(M + N) は無視できるサイズ

ソートにより、ネステッドループような全行チェックをスキップできます。

ソートマージの利用用途

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

利用シーン	説明
大きい (行数の多い) テーブルを結合	スキップできる行数が増えやすい逆に行数が少ないと、ソートのオーバーヘッドが処理の大部分を占める
ソート済みのデータに効率的	ソートフェーズをスキップできるため
結合条件が非等価結合（<, <=, >, >=）	ソートしているため、非常に高速

ハッシュ結合 (Hash Join)

ハッシュ結合とは、ハッシュテーブルを作成して、結合キーを確認する方法です。

オプティマイザーは、小さいテーブルの方でハッシュテーブルを作ります。
(ハッシュテーブルを小さくするため)

ハッシュ結合の利用例

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

利用シーン	説明
インデックスが無い	結合キーにインデックスが無くても、ハッシュテーブルで高速に結合
小さいテーブルと大きいテーブルを結合	小さいテーブルを選んで小さいハッシュテーブルを作成できるため両方のテーブルが大きい場合、ハッシュテーブルが大きくなる
メモリが潤沢	ハッシュテーブルが大きい場合、スワップが発生して遅くなるため
結合条件が等価結合 (＝)	ハッシュ関数の都合上、同じ値しか比較できない

実行計画の確認 (EXPLAIN)

EXPLAIN 文で、SQL クエリの実行計画を確認可能です。

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

+-------+------+---------------+------+------+------+----------+--------------------------------------------+
| table | type | possible_keys | key  |  ref | rows | filtered | Extra                                      |
+-------+------+---------------+------+------+------+----------+--------------------------------------------+
| tbl2  | ALL  | NULL          | NULL | NULL |    3 |   100.00 | NULL                                       |
| tbl1  | ALL  | NULL          | NULL | NULL |    5 |    20.00 | Using where; Using join buffer (hash join) |
+-------+------+---------------+------+------+------+----------+--------------------------------------------+

実行計画の手順	対応する EXPLAIN の表示
アクセスパス (Access Path)	type: ・ALL はフルテーブルスキャン、・range や index はインデックススキャン　インデックスで利用した列は key で確認
結合方法 (JOIN Method)	Extra: ・Using join buffer (hash join) はハッシュ結合

MySQL の EXPLAIN の詳細な見方は、以下のドキュメントをご覧ください。

https://dev.mysql.com/doc/refman/8.0/ja/explain-output.html#explain_type

達人に学ぶDB設計徹底指南書

翔泳社

Amazonの商品レビュー・口コミを見る

SQLアンチパターン

オライリージャパン

Amazonの商品レビュー・口コミを見る

オプティマイザー (Optimizer) とは

オプティマイザー(Optimizer)オプティマイザーとは、実行計画を決めるプログラムです。

オプティマイザーは、実行計画の候補を複数生成し、実行コストの低い実行計画を選択します。

オプティマイザーは以下の３つの要素で構成されます。

クエリトランスフォーマー (リライターとも。オプティマイザーと独立している場合もある)
プランジェネレーター
エスティメーター

クエリトランスフォーマー

クエリトランスフォーマーとは、元の SQL 文を同じ結果でコストの低い文に書き換えます。

例えば、結合処理を減らすために、絞り込みを先に行うように書き換えます。

実際には AST の形です
JOIN 句 --> WHERE の順で実行されるので、JOIN 句で絞り込むように書き換える
https://ryuichi1208.hateblo.jp/entry/2022/11/13/103003

プランジェネレーター

プランジェネレーターとは、実行計画の候補を複数生成するプログラムです。

エスティメーター

プランジェネレーターとは、書き換え後の AST や実行計画の実行コストを算出します。

ようするに、以下のように一番速い実行方法を算出するものです。

プランジェネレーターで生成した実行計画の候補の中で、どれが一番速いか？
クエリトランスフォーマーで「書き換えた後と「書き換える前」でどっちが速いか？

エスティメーターは、リソース (CPU, メモリ, I/O) や統計情報などで実行コストを推定します。

統計情報

統計情報とは、テーブルやインデックスに関するデータ (つまりメタデータ) です。

統計情報は mysql.innodb_table_stats(MySQL) や pg_stat_user_tables(PostgreSQL) などで確認できます。

永続統計は、mysql.innodb_table_stats テーブルおよび mysql.innodb_index_stats テーブルに格納されます。[1]
非永続オプティマイザ統計は、次の場合に更新されます:
SHOW TABLE STATUS、SHOW INDEX を実行するか、...(省略)[2]
[1] https://dev.mysql.com/doc/refman/8.0/ja/innodb-persistent-stats.html
[2] https://dev.mysql.com/doc/refman/8.0/ja/innodb-statistics-estimation.html

SELECT * FROM mysql.innodb_table_stats;

+---------------+------------+---------------------+--------+----------------------+--------------------------+
| database_name | table_name | last_update         | n_rows | clustered_index_size | sum_of_other_index_sizes |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| db            | tbl1       | 2024-09-29 09:59:27 |      5 |                    1 |                        0 |
+---------------+------------+---------------------+--------+----------------------+--------------------------+

統計情報には、主に以下のような情報が含まれまれていることが確認できます。