アルゴリズムの芸術: MySQL order by のさまざまなソートアルゴリズムの巧みな使用

[[337135]]

この記事では、MySQL におけるキーワードの原則を比較的マクロな観点から見ていきます。この記事では、主に order by ステートメントの基本原則について説明します。この記事を読むと、次のことがわかります。

order by ステートメントのソート モードと、各ソート モードの長所と短所は何ですか。

order by ステートメントではどのソート アルゴリズムが使用されるか、また、どのようなシナリオでどのソート アルゴリズムが選択されるか。

最適化方法 (実行プラン + OPTIMIZER_TRACE ログ) による SQL の順序を表示および分析する方法。

order by ステートメントの実行効率を最適化するにはどうすればよいでしょうか? (考え: 行サイズを減らし、インデックスを使用するようにし、カバーリング インデックスを使用するのが最善で、ソート バッファーのメモリ サイズを適切に増やします)

ここでは、データとインデックスをデータ構造の観点から見ていきます。つまり、それらはすべて B+ ツリーであると考えられます。データが必要な場合は、ストレージ エンジンの B+ ツリーからデータを読み取ります。

以下は、この記事でデモンストレーションの例として使用する表です。次の表があるとします。

インデックスは次のとおりです。

対応する idx_d インデックス構造は次のとおりです (ここでは、インデックス ツリーでの検索プロセスを示すために、データ ページを小さくするために多少誇張しています)。

1. 実行の最適化を追跡する方法

SQL 実行プロセスの分析を容易にするために、現在のセッションで optimizer_trace を有効にすることができます。

 optimizer_trace を'enabled=on'に設定します。

次に、SQL を実行します。実行後、次のスタック情報を通じて実行の詳細を表示できます。

 information_schema.OPTIMIZER_TRACE\Gから*を選択します。

以下は

1t20力からa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限100,2;

実行結果には、a=3 に一致するレコードが 8457 件あることが示されています。order by では、次の属性に注目します。

 "filesort_priority_queue_optimization" : { // 優先キューを有効にするかどうか
"limit" : 102, // ソート後に取得する行数。ここでは limit 100,2、つまり 100+2=102 です。
 "rows_estimate" : 24576, // ソートに関係する行数を推定します
"row_size" : 123, // 行サイズ
"memory_available" : 32768, // 使用可能なメモリ サイズ、つまり設定されたソート バッファ サイズ
"chosen" : true // 優先キューを有効にするかどうか
},
 ...
 「ファイルソートサマリー」 : {
 "rows" : 103, // ソート処理中に保持される行数
"examined_rows" : 8457, // ソートに関係する行数、InnoDB レイヤーによって返される行数
"number_of_tmp_files" : 0, // 外部ソート中に使用される一時ファイルの数
"sort_buffer_size" : 13496, // メモリソートで使用されるメモリサイズ
"sort_mode" : "sort_key, additional_fields" // ソートモード

1.1. ソートモード

sort_mode には次の形式があります。

• sort_key、rowid: ソート バッファ タプルに、ソート キー値と元のテーブル行の行 ID が含まれていることを示します。ソート後、行 ID を使用してテーブルに戻る必要があります。このアルゴリズムは、元のファイルソート アルゴリズムとも呼ばれます。
• sort_key、additional_fields: ソート バッファ タプルに、ソート キー値とクエリに必要な列が含まれていることを示します。ソート後、データはテーブルに戻されずにバッファ タプルから直接取得されます。このアルゴリズムは、修正されたファイルソート アルゴリズム (テーブルに戻らないソート) とも呼ばれます。
• sort_key、packed_additional_fields: 前の形式と似ていますが、固定長エンコードを使用する代わりに、追加の列 (varchar 型など) が密にパックされます。

並べ替えモードの選択方法

ソート モードの選択は max_length_for_sort_data 属性に関連しており、デフォルト値は 1024 バイトです。

• クエリ列とソート列のサイズがこの値を超える場合は、代わりに sort_key、rowid モードが使用されます。
• そうでない場合は、sort_key、additional_fields または sort_key、packed_additional_fields モードを使用して、すべての列がソート バッファーに格納されます。
• クエリするレコードが多すぎる場合は、sort_key と packed_additional_fields を使用して変数列を圧縮します。

1.2 ソートアルゴリズム

ソートに関係するデータの量に基づいて、さまざまなソート アルゴリズムを選択できます。

• ソート結果が小さく、メモリよりも小さい場合は、優先キューがヒープソートに使用されます。
• たとえば、次の例では、最初の 10 件のレコードのみを取得し、優先度キューで並べ替えます。

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限10まで

• ソート制限 n、m、n が大きすぎる場合、つまりソートの最後にデータを取得する必要がある場合は、ソート バッファーを使用してクイック ソートが行われます。
• 下図のように、テーブルには a=1 のレコードが 3 つあります。ただし、最後までレコード数を制限する必要があるため、MySQL は優先キュー ソートとクイック ソートのオーバーヘッドを比較し、より適切なソート アルゴリズムを選択します。ここでは、最終的に優先キューを放棄し、クイック ソートにソート バッファを使用します。

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =1 の順序  d制限300,2;

• ソート バッファーがソートするデータでいっぱいの場合、ソート バッファーに対してメモリ クイック ソートをバッチで実行し、結果を一時ソート ファイルに格納し、最後にソートされたすべての一時ファイルをマージしてソートし、最終結果を取得します。
• 以下に示すように、a=3 のレコードはソート バッファを超えています。検索したいデータは、ソート後の 1000 行目にあります。ソート バッファは 1000 行のデータを保持できません。最終的に、MySQL はバッチ クイック ソートにソート バッファを使用することを選択し、最終結果をマージしてソートします。

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限1000,10;

2. Order byはソートを避けるためにインデックスを使用する

次のSQLを実行します。

 t20 forceからa、b、c、dを選択 インデックス（idx_d ） dは  't%'  注文  d 制限 2による;

実行計画を見てみましょう。

Extra 列には「Using index condition」と表示されており、ここではインデックスのみが使用されていることがわかります。

実行フローは次の図に示されています。

idx_d インデックスを介して range_scan 検索を実行し、4 つのレコードをスキャンします。次に、order by は、すでに順序付けされているインデックスを引き続き使用し、最初の 2 つのレコードを直接取得します。次に、クラスター化インデックスを使用して完全なレコードをクエリし、クエリ結果として最終的な必須フィールドを返します。このプロセスではインデックスの助けだけが必要です。

ソート バッファ サイズを表示および変更するにはどうすればよいですか?

現在のソート バッファ サイズを見てみましょう。

ソート バッファ サイズはデフォルトで 512k に設定されていることがわかります。

このプロパティのサイズを設定できます:

セット グローバルソートバッファサイズ = 32*1024;
または
ソートバッファサイズを32*1024に設定します。

次に、ソートバッファを32kに均一に設定します。

ソートバッファサイズを32*1024に設定します。

3. ソートアルゴリズムの例

3.1. ヒープソートに優先キューを使用する

ソートの結果が小さく、ソート バッファーよりも小さい場合は、優先キューがヒープ ソートに使用されます。

たとえば、次の例では最初の 10 件のレコードのみが取得されます。

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限10まで

a=3 のレコードの合計数: 8520。実行プランを表示します。

where 条件ではインデックスが使用され、order by 制限ではソートが使用されることがわかります。実行の optimizer_trace ログを詳しく見てみましょう。

 「ファイルソート優先度キュー最適化」 : {
 「制限」 : 10,
 "行数推定" : 27033,
 "行サイズ" : 123,
 「利用可能なメモリ」 : 32768、
 "chosen" : true // ソートに優先キューを使用する
},
 「ファイルソート実行」 : [
 ]、
 「ファイルソートサマリー」 : {
 「行」 : 11,
 "検査された行" : 8520,
 "tmp ファイル数" : 0,
 "ソートバッファサイズ" : 1448,
 "sort_mode" : "sort_key、additional_fields"  
 }

ここでは、ソートに優先キューが使用されていることがわかります。ソート モードは sort_key、additional_fields です。つまり、最初にテーブルに戻って完全なレコードを照会し、ソートに必要なすべてのフィールドをソート バッファーに入れてソートします。

実行フローは次のようになります。

1. where 条件 a=3 を通じて 8520 件のレコードがスキャンされます。
2. テーブルに戻ってレコードを見つけます。
3. 8520 レコードから必要なフィールドをソート バッファーに格納します。
4. ソート バッファー内でヒープ ソートを実行します。
5. ソートされた結果から、制限 10 内の最初の 10 項目を取得し、ネット バッファーに書き込み、クライアントに送信する準備をします。
   

3.2 内部クイックソート

ソート制限 n、m、n が大きすぎる場合、つまりソートの最後にデータを取得する必要がある場合は、クイックソートにソートバッファーが使用されます。 MySQL は、優先キュー ソートとマージ ソートのオーバーヘッドを比較し、より適切なソート アルゴリズムを選択します。

優先キューを使用するか、メモリ内クイックソートを使用するかをどのように決定しますか?

一般的に言えば、クイック ソート アルゴリズムはヒープ ソートよりも効率的ですが、ヒープ ソートによって実装された優先キューは、すべての要素をソートしなくても order by limit の結果を取得できます。

MySQL のソースコードによると、クイックソートはヒープソートより 3 倍高速です。実際のソート時には、ソートする項目の数に応じてアルゴリズムが切り替えられます。データの量が多すぎる場合は、代わりにクイックソートが使用されます。

次のSQLがあります:

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =1 の順序  d制限300,2;

ソートバッファを 32k に設定します。

ソートバッファサイズを32*1024に設定します。

a=1 のレコードが 3 つあります。実行プランを表示します。

where 条件ではインデックスが使用され、order by 制限ではソートが使用されることがわかります。実行の optimizer_trace ログを詳しく見てみましょう。

 「ファイルソート優先度キュー最適化」 : {
 「制限」 : 302,
 "行数推定" : 27033,
 "行サイズ" : 123,
 「利用可能なメモリ」 : 32768、
 「追加フィールドの削除」 : {
 "行サイズ" : 57,
 "ソートマージコスト" : 33783,
 "優先度キューコスト" : 61158,
 "chosen" : false // 比較すると、クイックソートのコストは優先キューのコストよりも低いことがわかったので、優先キューはここでは適用できません
  }
 },
 「ファイルソート実行」 : [
 ]、
 「ファイルソートサマリー」 : {
 「行」 : 3,
 「検査された行」 : 3,
 "tmp ファイル数" : 0,
 "ソートバッファサイズ" : 32720,
 "sort_mode" : "<ソートキー、パックされた追加フィールド>"  
 }

ここで、優先キューは最終的に放棄され、代わりにソート バッファーがクイック ソートに使用されていることがわかります。

実行フローは次のようになります。

1. where 条件 a=1 で 3 つのレコードをスキャンします。
2. テーブルに戻ってレコードを見つけます。
3. 3 つのレコードの必須フィールドをソート バッファーに格納します。
4. ソート バッファー内でクイック ソートを実行します。
5. ソートされた結果から、制限 300、2 の 300 番目と 301 番目のレコードを取得し、ネット バッファーに書き込み、クライアントに送信する準備をします。
   

3.3 外部マージソート

ソートするデータが多すぎて、ソート バッファーに一度に格納できない場合は、メモリ内のソート バッファーをバッチでソートし、その結果を一時ソート ファイルに格納し、最後にソートされたすべての一時ファイルをマージしてソートし、最終結果を取得します。

次のSQLがあります:

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限1000,10;

a=3 のレコードは 8520 件あります。実行計画は次のとおりです。

画像-20200614171147989

where はインデックスを使用し、order by limit はソートを使用していることがわかります。さらに、実行の optimizer_trace ログを表示します。

 「ファイルソート優先度キュー最適化」 : {
 「制限」 : 1010,
 "行数推定" : 27033,
 "行サイズ" : 123,
 「利用可能なメモリ」 : 32768、
 「追加フィールドの削除」 : {
 "行サイズ" : 57,
 「選択された」 : false 、
 "cause" : "not_enough_space" // ソートバッファが、ソートに優先キューを使用するのに十分な大きさではありません
  }
 },
 「ファイルソート実行」 : [
 ]、
 「ファイルソートサマリー」 : {
 「行」 : 8520,
 "検査された行" : 8520,
 "number_of_tmp_files" : 24, // ソートには24個の外部ファイルが使用されます
"ソートバッファサイズ" : 32720,
 "sort_mode" : "<ソートキー、パックされた追加フィールド>"  
 }

1000 という制限があるため、ソート後に 1000 行後のレコードを返すには、ソート バッファーがこのような大きな優先キューをサポートできなくなるため、代わりにソート バッファー メモリ ソートが使用されることがわかります。ここでは、ソート バッファー内でクイック ソートをバッチで実行して、複数のソートされた外部一時ファイルを取得し、最後にマージ ソートを実行する必要があります。 (外部一時ファイルの場所はtmpdirパラメータで指定されます)

プロセスを次の図に示します。

4. ソートモードの例

4.1、sort_key、additional_fields モード

sort_key、additional_fields、ソート バッファ タプルには、ソート キー値とクエリに必要な列が含まれます (最初にテーブルに戻って必要なデータを取得し、ソート バッファに格納します)。ソート後、データはテーブルに戻らずにバッファ タプルから直接取得されます。

上記のセクション 2.3.1 と 2.3.2 の例はすべてこのソート モードを使用しているため、これ以上の例は示しません。

4.2 モード

sort_key、packed_additional_fields: 前の形式と似ていますが、固定長エンコードを使用する代わりに、追加の列 (varchar 型など) が密にパックされます。

上記のセクション 2.3.3 の例は、このソート モードです。ソートに関係するレコードの合計サイズが大きすぎるため、メモリを節約するために追加の列を密に詰める必要があります。

4.3 モード

前述のように、ソートモードの選択は、ソートされた行の最大サイズを指定するmax_length_for_sort_data[2]属性に関連しています。この属性のデフォルト値は1024バイトです。

つまり、クエリ列とソート列が占めるサイズがこの値より小さい場合は、sort_key、additional_fields または sort_key、packed_additional_fields アルゴリズムが使用されます。それ以外の場合は、代わりに sort_key、rowid モードが使用されます。

ここで、sort_key、rowid モードをシミュレートするために、この値を意図的に小さい値に設定します。

ソートデータの最大長を 100 に設定します。

この時点でSQLを実行します:

 t20 forceからa、b、c、dを選択 インデックス(idx_abc)、 a =3 の順序  d制限10まで

この時点で、SQL 実行の optimizer_trace ログを確認します。

 「ファイルソート優先度キュー最適化」 : {
 「制限」 : 10,
 "行数推定" : 27033,
 "行サイズ" : 49,
 「利用可能なメモリ」 : 32768、
 「選択された」 : true  
 },
 「ファイルソート実行」 : [
 ]、
 「ファイルソートサマリー」 : {
 「行」 : 11,
 "検査された行" : 8520,
 "tmp ファイル数" : 0,
 "ソートバッファサイズ" : 632,
 "sort_mode" : "<sort_key, rowid>"  

モードが sort_key、rowid モードに切り替わっていることがわかります。このモードでは、実行プロセスは次のようになります。

1. 条件 a=3 の場合、8520 件のレコードがスキャンされます。
2. テーブルに戻ってレコードを見つけます。
3. これらの 8520 レコードの id フィールドと d フィールドを見つけて、ヒープ ソート用のソート バッファーに格納します。
4. 分類が完了したら、最初の 10 個のアイテムを取得します。
5. これら 10 件のレコードの ID を取得し、テーブルに戻って必要な a、b、c、d フィールド値を照会します。
6. 結果は順番にクライアントに返されます。

行レコードが大きすぎるため、ソート バッファーにはソートが必要なフィールドと主キー ID のみが格納されていることがわかります。時間とスペースが交換されます。最後に、ソートが完了し、必要なすべてのフィールドがクラスター化インデックスから再度検索され、クライアントに返されます。明らかに、テーブルを返す操作のために追加のディスク読み取りがあり、全体的な効率はわずかに低下します。

5. 順序最適化のまとめ

上記の紹介に基づいて、order by ステートメントの最適化方法を次のようにまとめることができます。

• ソート フィールドは圧縮をサポートしていないため、順序付けフィールドでは可能な限り固定長フィールド タイプを使用する必要があります。
• order by フィールドを可変長にする必要がある場合、長さを可能な限り制御する必要がありますが、同じ理由が適用されます。
• クエリが多すぎると、order by 中にソート バッファー メモリが不足して外部ソートが実行される可能性があります。また、行サイズが max_length_for_sort_data を超えて sort_key、rowid ソート モードが使用され、ディスク読み取りが増えてパフォーマンスに影響する可能性があります。そのため、クエリで select * を使用しないようにしてください。
• 並べ替えフィールドと関連条件に結合インデックスを追加してみてください。カバーリング インデックスを使用するのが最適です。

参考文献

[1]: Didi Cloud。MySQLのフルテーブルCOUNT(*)の簡単な説明。zhihu.com。https://zhuanlan.zhihu.com/p/54378839から取得

[2]: MySQL. 8.2.1.14 ORDER BY最適化。https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.htmlから取得

[3]: MySQL: ソートの詳細な分析 (filesort)。https://www.jianshu.com/p/069428a6594e から取得

[4]: ORDER BY LIMITと優先キュー（ヒープソート）のMYSQL実装。http://blog.itpub.net/7728585/viewspace-2130920/から取得

この記事はWeChatの公開アカウント「Java Architecture Talk」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合は、Java Architecture Talk のパブリック アカウントにお問い合わせください。

ブログアドレス: https://www.itzhai.com