MySQL ソートの原則とケース分析

序文

ソートはデータベースの基本的な機能であり、MySQL も例外ではありません。ユーザーは、Order by ステートメントを使用して、指定した結果セットを並べ替えるという目的を達成できます。実際、Order by ステートメントだけでなく、Group by ステートメントや Distinct ステートメントでも暗黙的に並べ替えが使用されます。この記事では、まず SQL がインデックスを使用してソートのコストを回避する方法を簡単に紹介し、次に MySQL ソートの内部原理とソートに関連するパラメータを紹介します。最後に、ソートの一貫性の問題について議論し、この現象の本質的な理由を説明するために、いくつかの「奇妙な」ソートの例を示します。

1. ソートの最適化とインデックスの使用

SQL ステートメントのソートパフォーマンスを最適化するには、ソートを回避するのが最適です。インデックスを適切に使用するのがよい方法です。インデックス自体も順序付けされるため、ソートが必要なフィールドに適切なインデックスを作成すると、ソート処理をスキップでき、SQL クエリの速度が向上します。以下では、いくつかの一般的な SQL ステートメントを使用して、どの SQL ステートメントがインデックスを使用してソートを減らすことができるか、またどの SQL ステートメントができないかを説明します。テーブルt1にインデックスkey1(key_part1,key_part2),key2(key2)があると仮定します。

a. インデックスを使用してソートを回避できるSQL

SELECT * FROM t1 ORDER BY key_part1,key_part2;
SELECT * FROM t1 WHERE key_part1 = constant ORDER BY key_part2;
SELECT * FROM t1 WHERE key_part1 > constant ORDER BY key_part1 ASC;
SELECT * FROM t1 WHERE key_part1 = constant1 AND key_part2 > constant2 ORDER BY key_part2;

b. ソートを回避するためにインデックスを使用できないSQL

// ソート フィールドが複数のインデックスにあるため、インデックス ソートは使用できません SELECT * FROM t1 ORDER BY key_part1, key_part2, key2;
 
// ソート キーの順序がインデックス内の列の順序と一致していないため、インデックスをソートに使用できません。SELECT * FROM t1 ORDER BY key_part2, key_part1;
 
// 昇順と降順が一致せず、インデックスソートは使用できません SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
 
//key_part1 は範囲クエリであり、key_part2 はインデックスを使用して並べ替えることはできません SELECT * FROM t1 WHERE key_part1> constant ORDER BY key_part2;

2. ソートアルゴリズム

インデックスを使用してソートを回避できない SQL の場合、データベースはユーザーのニーズを満たすためにソート機能自体を実装する必要があります。このとき、SQL 実行プランに「filesort の使用」が表示されます。ここで注意すべき点は、filesort はファイルソートを意味するわけではないということです。実際には、メモリソートである可能性もあります。メモリソートは主に sort_buffer_size パラメータと結果セットのサイズによって決まります。 MySQL でソートを実装する方法は主に 3 つあります。従来のソート、最適化されたソート、および優先キューソートです。これらのソートには主に、クイックソート、マージソート、ヒープソートの 3 つのソートアルゴリズムが含まれます。テーブル構造と SQL ステートメントが次のとおりであると仮定します。

テーブル t1(id int、col1 varchar(64)、col2 varchar(64)、col3 varchar(64)、主キー(id)、キー(col1、col2)) を作成します。
SELECT col1,col2,col3 FROM t1 WHERE col1>100 ORDER BY col2;

a. 従来の分類

（１）テーブルt1からWHERE条件を満たすレコードを取得する

（２）各レコードについて、そのレコードの主キー＋ソートキー（id, col2）を取り出し、ソートバッファに入れる。

（３）ソートバッファに条件を満たす（id、col2）のペアがすべて格納できる場合はソートし、そうでない場合はソートバッファがいっぱいのときにソートして一時ファイルに固定する。（使用されるソートアルゴリズムはクイックソートアルゴリズムです）

（４）ソート中に一時ファイルが生成される場合、一時ファイル内のレコードが正しい順序になっていることを確認するためにマージソートアルゴリズムを使用する必要があります。

（５）条件を満たすすべてのレコードがソートされるまで、上記のプロセスをループします。

（6）ソートされた（id、col2）ペアをスキャンし、idを使用してSELECTが返す必要のある列（col1、col2、col3）を取得します。

（７）得られた結果セットをユーザーに返す。

上記のプロセスから、ファイルソートを使用するかどうかは、主にソートバッファーがソートする必要のある (id、col2) ペアを収容できるかどうかによって決まります。このバッファーのサイズは、sort_buffer_size パラメーターによって制御されます。さらに、1 つのソートには 2 つの IO が必要です。1 つは (id、col2) を取得するもので、もう 1 つは (col1、col2、col3) を取得するものです。返される結果セットは col2 でソートされるため、ID は無秩序です。無秩序な ID で (col1、col2、col3) を取得すると、大量のランダム IO が生成されます。 2 回目は、MySQL 自体に最適化が施されており、取得前に ID がまずソートされてバッファに格納されます。このバッファのサイズは、パラメータ read_rnd_buffer_size によって制御され、その後、レコードが順番に取得され、ランダム IO がシーケンシャル IO に変換されます。

b. ソートを最適化する

従来のソート方法では、ソート自体に加えて、さらに 2 つの IO 操作が必要になります。従来のソートと比較して、最適化されたソート方法では 2 番目の IO が削減されます。主な違いは、ソートバッファーに入れられるのは (id、col2) ではなく (col1、col2、col3) であることです。ソートバッファにはクエリに必要なすべてのフィールドが含まれているため、ソートが完了した後、データを再度取得することなく直接返すことができます。このアプローチのデメリットは、同じサイズのソートバッファーに格納できる (col1、col2、col3) の数が (id、col2) の数より少なくなることです。ソートバッファーが十分に大きくない場合は、一時ファイルを書き込む必要があり、追加の IO が発生する可能性があります。もちろん、MySQL はパラメータ max_length_for_sort_data を提供します。ソートタプルが max_length_for_sort_data より小さい場合にのみ、最適化されたソート方法を使用できます。それ以外の場合は、従来のソート方法のみを使用できます。

c. 優先キューソート

最終的なソート結果を得るには、条件を満たすすべてのレコードをソートしてから返す必要があります。では、ソート方法を最適化することと比較して、最適化の余地はまだあるのでしょうか?バージョン 5.6 では、Order by limit M, N ステートメントがスペースレベルで最適化され、ヒープソートを使用して実装される新しいソート方法である優先キューが追加されました。ヒープソートアルゴリズムの特性により、M、N の制限のソート問題を解決できます。ソートにはすべての要素が参加する必要がありますが、必要なのは M+N タプルのソートバッファスペースだけです。M と N が非常に小さいシナリオでは、ソートバッファが不足しているためにマージソートに一時ファイルが必要になるという問題は基本的に発生しません。昇順の場合、最大ヒープが使用され、最終ヒープ内の要素が最小の N 要素を構成します。降順の場合、最小ヒープが使用され、最終ヒープ内の要素が最大の N 要素を構成します。

3. 一貫性のないソート問題

ケース1

Mysql を 5.5 から 5.6 に移行した後、ページングで重複した値が見つかりました。

テストテーブルとデータ:

テーブル t1(id int 主キー、c1 int、c2 varchar(128)) を作成します。
t1に値(1,1,'a')を挿入します。
t1に値(2,2,'b')を挿入します。
t1に値(3,2,'c')を挿入します。
t1に値(4,2,'d')を挿入します。
t1に値(5,3,'e')を挿入します。
t1に値(6,4,'f')を挿入します。
t1に値(7,5,'g')を挿入します。

1 ページあたり 3 つのレコードがあると仮定すると、最初のページ制限は 0.3、2 番目のページ制限は 3.3 です。クエリの結果は次のようになります。

両方のクエリに ID 4 のレコードが表示されていますが、これは明らかに期待どおりではなく、バージョン 5.5 ではこのような問題は発生しません。この現象が発生する理由は、5.6 では limit M, N ステートメントに優先キューが使用され、優先キューがヒープを使用して実装されているためです。たとえば、上記の例では、 order by c1 asc limit 0, 3 にはサイズ 3 の最大ヒープが必要です。limit 3, 3 にはサイズ 6 の最大ヒープが必要です。 c1 が 2 のレコードが 3 つあり、ヒープソートは不安定 (同じキー値の場合、ソート後の位置がソート前の位置と一致する保証がない) であるため、ページングの重複が発生します。この問題を回避するには、主キー ID などの一意の値をソートに追加します。このように、ID は一意であるため、ソートに関係するキー値が異なることを保証できます。 SQL を次のように記述します。

t1 から * を選択し、c1、id、asc、limit 0、3 で順序付けします。
t1 から * を選択し、c1、id、asc、limit 3、3 で並べ替えます。

ケース2

2 つの類似したクエリステートメントは、返される列を除いて同一ですが、並べ替えの結果は一貫していません。

テストテーブルとデータ:

テーブル t2(id int 主キー、ステータス int、c1 varchar(255)、c2 varchar(255)、c3 varchar(255)、キー(c1)) を作成します。
t2に値(7,1,'a',repeat('a',255),repeat('a',255))を挿入します。
t2に値(6,2,'b',repeat('a',255),repeat('a',255))を挿入します。
t2に値(5,2,'c',repeat('a',255),repeat('a',255))を挿入します。
t2に値(4,2,'a',repeat('a',255),repeat('a',255))を挿入します。
t2に値(3,3,'b',repeat('a',255),repeat('a',255))を挿入します。
t2に値(2,4,'c',repeat('a',255),repeat('a',255))を挿入します。
t2に値(1,5,'a',repeat('a',255),repeat('a',255))を挿入します。

SQL ステートメントを個別に実行します。

t2 から id、status、c1、c2 を選択し、c1>='b' の場合にインデックス (c1) を強制的に取得し、ステータスで並べ替えます。
t2からid、statusを選択し、c1>='b'の場合、force index(c1)でステータスで順序付けします。

実行結果は次のとおりです。

2つの実行計画が同じかどうかを確認します

この問題を説明するために、ステートメントに強制インデックスヒントを追加して、c1 列インデックスが使用できることを確認しました。このステートメントは、c1 列インデックスを通じて ID を取得し、返された列をテーブルから取得します。 c1 列値のサイズに応じて、c1 インデックス内のレコードの相対位置は次のようになります。

(c1,id)===(b,6),(b,3),(5,c),(c,2)、対応するステータス値はそれぞれ2・3・2・4です。テーブルからデータを取得してステータスで並べ替えると、相対位置は (6,2,b)、(5,2,c)、(3,3,c)、(2,4,c) になります。これは、2 番目のクエリステートメントによって返される結果です。では、最初のクエリステートメント (6,2,b)、(5,2,c) が逆の順序になっているのはなぜでしょうか。ここで、先ほど述べた a. 従来のソートと b. 最適化されたソートの赤い部分を見れば、その理由がわかると思います。最初のクエリによって返される列のバイト数が max_length_for_sort_data を超えるため、従来のソートが使用されます。この場合、MYSQL は rowid をソートし、ランダム IO をシーケンシャル IO に変換するため、最初に 5 が返され、最後に 6 が返されます。2 番目のクエリでは、2 番目のデータ取得プロセスなしで最適化されたソートが使用され、ソートされたレコードの相対的な位置が維持されます。最初のステートメントでは、最適化されたソートを使用する場合は、max_length_for_sort_data 設定を 2048 などに増やすことができます。

4. 参考資料

順序最適化
http://mysql.taobao.org/monthly/2015/06/04/
参照:

これで、MySQL のソートの原則とケース分析に関するこの記事は終了です。より関連性の高い MySQL のソートの原則とケースの内容については、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。

以下もご興味があるかもしれません: