MySQLのNested-Loop Joinアルゴリズムのまとめ
2846 ワード
知らず知らずのうちに2年以上MySQLをやっていて、多くの人がMySQLがOracleと比べて、オプティマイザが悪いと言っているのを発見しました.実はある程度はそうですが、結局MySQLは5.7バージョンになって、Oracleは12 cに発展しました.今日はMySQLの接続アルゴリズムを見てみました.ええと、今はHash Joinをサポートしていません.Nested-Loop Joinだけです.では、今日は私の勉強の心得をまとめましょう.
Nested-Loop Join基本アルゴリズム実装、疑似コードはこうです.
このコードはとても簡単で、私もあまりコードを書くことができませんが、私はやはり理解することができます.ここでは、3枚のテーブル、t 1、t 2、t 3があると仮定します.このコードは、それぞれexplain計画のrange、ref、ALLを示し、SQL実行計画層に表現され、t 3は全表スキャンを行います.私は今日、この場所でSQLの最適化方法を見ました.Straight-join:http://hidba.ga/2014/09/26/join-query-in-mysql/で、その中でドライバテーブルの概念に言及して、それに対応して、ドライバテーブルは偽コードの中のt 3テーブルで、博文の中でMySQLは自動的に結果セットの最小のテーブルをドライバテーブルとして選択して、アルゴリズムの分析として、このようにドライバテーブルを選択するのは確かに最小の方法です.ここでまた,ドライバテーブル結果セットを縮小して接続最適化を行うことで,このアルゴリズムによれば,結果セットの小さいドライバテーブルは確かにサイクル数を減少させることができる.
もちろん、MySQL自身はこのアルゴリズムの基礎の上で、Block Nested-Loop joinアルゴリズムを演じて、実は基本的に上のアルゴリズムと区別がなくて、偽のコードは以下の通りです:
このアルゴリズムは,外層サイクルのデータをjoin bufferに緩やかに存在させ,内層サイクルの表ラウンドbufferのデータを比較してサイクル回数を減らすことで効率を向上させることができる.公式サイトにexampleがありますが、10行がbufferにキャッシュされている場合、この10行が内層サイクルに渡され、内層サイクルのすべての行がbufferの10行と比較されます.原文はこうです.
For example,if 10 rows are read into a buffer and the buffer is passed to the next inner loop,each row read in the inner loop can be compared against all 10 rows in the buffer Sがt 1,t 2がキャッシュに組み込まれたサイズを指す場合、Cはこれらの組合せがbufferに含まれる数であり、t 3テーブルがスキャンされる回数は:
(S * C)/join_buffer_size + 1
この計算式によればjoin_buffer_sizeが大きいほどスキャン回数が小さくなりjoin_buffer_sizeはすべての前の行の組み合わせをキャッシュできるようになったので、この時が性能が一番いい時で、それから大きくなっても効果はありません.
インデックスがある場合、MySQLはIndex Nested-Loop Joinアルゴリズムを使用しようとします.場合によっては、Joinの列にインデックスがない可能性があります.この場合、MySQLの選択は絶対に最初に紹介したSimple Nested-Loop Joinアルゴリズムではありません.そのアルゴリズムは乱暴で、直視に耐えられないからです.データ量の多い複雑なSQLは、数年で結果が出ない可能性があると推定されています.信じない場合は、too young too simpleです.あるいはInside君はSQLを走って見せることができます.
Simple Nested-Loop Joinアルゴリズムの欠点は、内部テーブルに対するスキャン回数が多すぎて、スキャンの記録が膨大すぎることである.Block Nested-Loop JoinアルゴリズムのSimple Nested-Loop Joinに比べて改善されたのは、内部テーブルのスキャン回数を減らすことができ、Hash Joinアルゴリズムと同様に、内部テーブルを1回スキャンするだけでよいことである.
Nested-Loop Join基本アルゴリズム実装、疑似コードはこうです.
for each row in t1 matching range {
for each row in t2 matching reference key {
for each row in t3 {
if row satisfies join conditions,
send to client
}
}
}
このコードはとても簡単で、私もあまりコードを書くことができませんが、私はやはり理解することができます.ここでは、3枚のテーブル、t 1、t 2、t 3があると仮定します.このコードは、それぞれexplain計画のrange、ref、ALLを示し、SQL実行計画層に表現され、t 3は全表スキャンを行います.私は今日、この場所でSQLの最適化方法を見ました.Straight-join:http://hidba.ga/2014/09/26/join-query-in-mysql/で、その中でドライバテーブルの概念に言及して、それに対応して、ドライバテーブルは偽コードの中のt 3テーブルで、博文の中でMySQLは自動的に結果セットの最小のテーブルをドライバテーブルとして選択して、アルゴリズムの分析として、このようにドライバテーブルを選択するのは確かに最小の方法です.ここでまた,ドライバテーブル結果セットを縮小して接続最適化を行うことで,このアルゴリズムによれば,結果セットの小さいドライバテーブルは確かにサイクル数を減少させることができる.
もちろん、MySQL自身はこのアルゴリズムの基礎の上で、Block Nested-Loop joinアルゴリズムを演じて、実は基本的に上のアルゴリズムと区別がなくて、偽のコードは以下の通りです:
for each row in t1 matching range {
for each row in t2 matching reference key {
store used columns from t1, t2 in join buffer
if buffer is full {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
empty buffer
}
}
}
if buffer is not empty {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
}
このアルゴリズムは,外層サイクルのデータをjoin bufferに緩やかに存在させ,内層サイクルの表ラウンドbufferのデータを比較してサイクル回数を減らすことで効率を向上させることができる.公式サイトにexampleがありますが、10行がbufferにキャッシュされている場合、この10行が内層サイクルに渡され、内層サイクルのすべての行がbufferの10行と比較されます.原文はこうです.
For example,if 10 rows are read into a buffer and the buffer is passed to the next inner loop,each row read in the inner loop can be compared against all 10 rows in the buffer Sがt 1,t 2がキャッシュに組み込まれたサイズを指す場合、Cはこれらの組合せがbufferに含まれる数であり、t 3テーブルがスキャンされる回数は:
(S * C)/join_buffer_size + 1
この計算式によればjoin_buffer_sizeが大きいほどスキャン回数が小さくなりjoin_buffer_sizeはすべての前の行の組み合わせをキャッシュできるようになったので、この時が性能が一番いい時で、それから大きくなっても効果はありません.
インデックスがある場合、MySQLはIndex Nested-Loop Joinアルゴリズムを使用しようとします.場合によっては、Joinの列にインデックスがない可能性があります.この場合、MySQLの選択は絶対に最初に紹介したSimple Nested-Loop Joinアルゴリズムではありません.そのアルゴリズムは乱暴で、直視に耐えられないからです.データ量の多い複雑なSQLは、数年で結果が出ない可能性があると推定されています.信じない場合は、too young too simpleです.あるいはInside君はSQLを走って見せることができます.
Simple Nested-Loop Joinアルゴリズムの欠点は、内部テーブルに対するスキャン回数が多すぎて、スキャンの記録が膨大すぎることである.Block Nested-Loop JoinアルゴリズムのSimple Nested-Loop Joinに比べて改善されたのは、内部テーブルのスキャン回数を減らすことができ、Hash Joinアルゴリズムと同様に、内部テーブルを1回スキャンするだけでよいことである.