備忘録

「詳解MySQL 5.7 止まらぬ進化に乗り遅れないためのテクニカルガイド」を読みながら学習していたときの自分用のメモ。

カーディナリティ

テーブルのカラムに格納されているデータの種類がどの程度あるかを示す値をカーディナリティという。あるカラムに性別を格納した場合は、データの種類は男と女で２種類となるためカーディナリティは２となる。

またインデックスを作るときの目安は、そのカラムで検索したときに全体の5%に絞り込めるカーディナリティであること。上記の性別の例だと、1/2で50%でしかないため、この場合はインデックス作成はしない方が良いという判断。

複合インデックスを貼るときはカーディナリティが高い方から順に貼っていく。

参考

https://qiita.com/soyanchu/items/034be19a2e3cb87b2efb

MysqlのJOINアルゴリズム

NJL（ネステッドループJOIN）しか存在しない。その他のJOINアルゴリズムとして、ソートマージJOINやハッシュJOINなどがあるが、MysqlはNJLのみ。基本となるアルゴリズムはループ。

JOINのキーが指定されたり、WHERE句で絞り込みをこなった場合のアルゴリズム

for each row in t1 matching where condition
{
    for each row in t2 matching join and where condition
    {
        send joined row to client
    }
}

ループになっているため、テーブル数が増えればループのネストがどんどん深くなる。
できるだけ早い段階で多くの絞り込みを行うほうが効率的なクエリになる（つまり、順序がクエリを効率化するために重要な要因になる）

内部表と駆動表

JOINするときのベースになる表が駆動表で、外部表にくっつく表が内部表と呼ばれる。JOINのアルゴリズム例で載せたプログラムの例では、t1が駆動表であり、t2が内部表となる。

BNLJ

駆動表から１行フェッチするたびに、その行とマッチする内部表をスキャンするときにインデックスが使えない場合は、スキャンが繰り返されるため非常に効率が悪い。内部表が巨大であれば致命的な効率の悪さになる。

可能であればインデックスを貼るべきだが、インデックスがあれば更新コストが高くなったり、必要なストレージのサイズも増える。

BNLJはそのような場合にJOINバッファというメモリ領域を使って内部表がスキャンされる回数を減らすアルゴリズム。

駆動表から条件にマッチする行をフェッチするとJOINバッファに貯める
JOINバッファが一杯になったら内部表をスキャンしてマッチする行を探す

ポイント

JOINバッファにためてまとめて内部表をスキャンすることでI/O負荷を軽減
バッファに貯められたデータと内部表の行が逐一比較されるためCPUには負荷
バッファサイズが大きすぎるとメモリ割り当てのオーバーヘッドが増加、メモリ枯渇の可能性
JOINバッファはセッションごとに変更可能

参考

https://zenn.dev/captain_blue/articles/three-types-of-join-algorithms