非公式MySQL 8.0オプティマイザガイド
ソート
原文URL: http://www.unofficialmysqlguide.com/sorting.html翻訳者: taka-h (@takaidohigasi)
MySQLには結果をソートされた順序で返す4つの方法があり、これらはORDER BYまたはGROUP BY(ORDER BY NULLを除く)の機能の一部として必要とされます。EXPLAINはソート操作が必要かどうかを表示しますが、どのソートアルゴリズムが利用されるかは表示しません。この情報はOPTIMIZER_TRACEによって取得できます。結果をソートするのに利用される4つの手法はそれぞれ次のとおりです。
- インデックスを利用 : B+ツリーインデックスはソート順に保たれるため、
ORDER BYクエリーの中には全くソートする必要がないケースがあります。 -
優先度つきキューを利用: limitで小さな値が指定された
ORDER BYは全ての結果セットを一時バッファーに格納できます。例えば、次のクエリーを考えてみてください。SELECT * FROM Country IGNORE INDEX (p, p_c) ORDER BY population LIMIT 10;このクエリーはテーブルスキャンとなり、人口の多い10行をバッファーに持つことになります。新しくより人口の多い行が見つかれば、以前の行が優先度つきキューから押しだされます。
- 代替ソートアルゴリズムを利用: このアルゴリズムは
TEXTまたはBLOB型の列がない場合に利用されます。MySQLのマニュアル1 に次のように定義されています。WHERE句の条件に一致する行を読みこみます。- 各行に対してソートキーの値およびクエリーにより参照される追加のフィールドから構成されるタプルの値を記録します。
- ソートバッファーが一杯になったら、メモリー内のソートキーの値でタプルを並び替え、一時ファイルに書き込みます。
- 一時ファイルをマージソートした後、行をソートキーの値の順に並び替え、ソートされたタプルから必要な行を直接読み取ります。
- 元のソートアルゴリズムを利用:
TEXTまたはBLOB型の列が存在する場合にこのアルゴリズムが利用されます。MySQLのマニュアル2 には次のように定義されています。- 全ての行をキーに従って、あるいはテーブルスキャンで読み込みます。WHERE条件に一致しない行はスキップします。
- 各行について、ある値のペア(ソートキーの値と行ID)からなる値で構成されるタプルをソートバッファーに保存します。
- 全てのペアがソートバッファーに収まれば、一時ファイルは作成されません。ソートバッファーが一杯になったら、メモリ上でqsort(クイックソート)を実行し一時ファイルに書き込みます。ソートされたブロックへのポインターを保存します。
- 全ての行が読み込まれるまで上記のステップを実施します。
- MERGEBUFF(7)までの領域を他の一時ファイル内のブロックへマルチマージします。最初のファイルの全てのブロックが2番目のファイルに移動されるまで繰り返します。
- 残りがMERGEBUFF2(15)ブロックになるまで次のことを繰り返します。
- マルチマージの一番最後に、結果ファイルに行ID(値のペアの一番最後)のみが書き込まれます。
- 結果ファイルの行IDを使って行をソート順に読み込みます。これを最適化するためには、行IDを大きなブロックで読込んでソートし、それによって行を所定のソート順に行バッファーに読みこみます。行バッファーのサイズは
read_rnd_buffer_sizeシステム変数の値で規定されます。この手続きの内容は、ソースコードとしてsql/records.ccに記載されています。
例30: インデックスによってソートされる例
EXPLAIN FORMAT=JSON
SELECT * FROM Country WHERE continent='Asia' ORDER BY population;
{
"query_block": {
"select_id": 1,
"cost_info": {
"query_cost": "34.10"
},
"ordering_operation": {
"using_filesort": false, # c_pインデックスによってソートが実現されている
"table": {
"table_name": "Country",
"access_type": "ref",
"possible_keys": [
"c",
"c_p"
],
"key": "c_p",
"used_key_parts": [
"Continent"
],
"key_length": "1",
"ref": [
"const"
],
"rows_examined_per_scan": 51,
"rows_produced_per_join": 51,
"filtered": "100.00",
"index_condition": "(`world`.`Country`.`Continent` <=> 'Asia')",
"cost_info": {
"read_cost": "23.90",
"eval_cost": "10.20",
"prefix_cost": "34.10",
"data_read_per_join": "13K"
},
"used_columns": [
"Code",
"Name",
"Continent",
"Region",
"SurfaceArea",
"IndepYear",
"Population",
"LifeExpectancy",
"GNP",
"GNPOld",
"LocalName",
"GovernmentForm",
"HeadOfState",
"Capital",
"Code2"
]
}
}
}
}
例31: OPTIMIZER_TRACEにより優先度つきキューが利用されていることがわかる
SET OPTIMIZER_TRACE="ENABLED=on";
SELECT * FROM Country IGNORE INDEX (p, p_c) ORDER BY population LIMIT 10;
SELECT * FROM information_schema.optimizer_trace\G
{
"steps": [
{
"join_preparation": {
"select#": 1,
"steps": [
{
"expanded_query": "/* select#1 */ select `Country`.`Code` AS `Code`,`Country`.`Name` AS `Name`,`Country`.`Continent` AS `Continent`,`Country`.`Region` AS `Region`,`Country`.`SurfaceArea` AS `SurfaceArea`,`Country`.`IndepYear` AS `IndepYear`,`Country`.`Population` AS `Population`,`Country`.`LifeExpectancy` AS `LifeExpectancy`,`Country`.`GNP` AS `GNP`,`Country`.`GNPOld` AS `GNPOld`,`Country`.`LocalName` AS `LocalName`,`Country`.`GovernmentForm` AS `GovernmentForm`,`Country`.`HeadOfState` AS `HeadOfState`,`Country`.`Capital` AS `Capital`,`Country`.`Code2` AS `Code2` from `Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`) order by `Country`.`Population` limit 10"
}
]
}
},
{
"join_optimization": {
"select#": 1,
"steps": [
{
"substitute_generated_columns": {
}
},
{
"table_dependencies": [
{
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"row_may_be_null": false,
"map_bit": 0,
"depends_on_map_bits": [
]
}
]
},
{
"rows_estimation": [
{
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"table_scan": {
"rows": 239,
"cost": 9
}
}
]
},
{
"considered_execution_plans": [
{
"plan_prefix": [
],
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"best_access_path": {
"considered_access_paths": [
{
"rows_to_scan": 239,
"access_type": "scan",
"resulting_rows": 239,
"cost": 56.8,
"chosen": true
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 239,
"cost_for_plan": 56.8,
"chosen": true
}
]
},
{
"attaching_conditions_to_tables": {
"original_condition": null,
"attached_conditions_computation": [
],
"attached_conditions_summary": [
{
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"attached": null
}
]
}
},
{
"clause_processing": {
"clause": "ORDER BY",
"original_clause": "`Country`.`Population`",
"items": [
{
"item": "`Country`.`Population`"
}
],
"resulting_clause_is_simple": true,
"resulting_clause": "`Country`.`Population`"
}
},
{
"reconsidering_access_paths_for_index_ordering": {
"clause": "ORDER BY",
"index_order_summary": {
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"index_provides_order": false,
"order_direction": "undefined",
"index": "unknown",
"plan_changed": false
}
}
},
{
"refine_plan": [
{
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)"
}
]
}
]
}
},
{
"join_execution": {
"select#": 1,
"steps": [
{
"filesort_information": [
{
"direction": "asc",
"table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
"field": "Population"
}
],
"filesort_priority_queue_optimization": {
"limit": 10,
"rows_estimate": 939,
"row_size": 272,
"memory_available": 262144,
"chosen": true # 優先度つきキューの最適化が適用されている
},
"filesort_execution": [
],
"filesort_summary": {
"rows": 11,
"examined_rows": 239,
"number_of_tmp_files": 0,
"sort_buffer_size": 3080,
"sort_mode": "<sort_key, additional_fields>"
}
}
]
}
}
]
}