MySQL Shell dumpInstance の分割ロジックその2

この記事は MySQL Advent Calendar 2023 の23日目の記事です。

MySQL Shell の dumpInstance の chunk ロジックの説明エントリーその２です。前回の記事では、主キーが数値型以外のケースを説明しました。主キーが数値型以外では、LIMIT句を利用して線形にレンジを求めるロジックが使われます。

今回の記事では、主キーが数値型のケースのロジック (chunk_integer_column) を説明します。

キーが数値型の場合 (chunk_integer_column)

主キーが数値型のテーブルに対する dumpInstance では、BETWEEN句を使ってテーブルを chunk に分割して(小分けにして)、バックアップが取得が行われます。

SELECT SQL_NO_CACHE `pk_int`,`col1` FROM `t`.`pkint_tbl`
WHERE (`pk_int` BETWEEN 873811 AND 1048572)

このBETWEEN の始まりと終わりを決めるロジックは constant_step() と adaptive_step() の2種類があります。

constant_step
- AUTO_INCREMENTのような歯抜けのない連続したPKを想定したロジック
- 単純に PKの範囲を chunk 数で割って区切りを求めるシンプルなロジック
adaptive_step
- 値が連続していないケースを想定したロジック
- 2分探索を用いてレンジを動的に決めるアルゴリズム

constant_step or adaptive_step どちらが使われるか

PKの空間(PKの最大値 - 最小値)に対して、行が入ってない空間が 10% 以下である場合に、 constant_step() が採用され、そうでなければ、adaptive_step() が採用されます。

    const bool use_constant_step =
        estimated_chunks < 2 ||
        (index_range > info.row_count
             ? index_range - info.row_count
             : info.row_count - index_range) <= row_count_accuracy;

dumper.cc#L1271-L1280

以下の図の左のように、行数とPKの空間が近ければ、constant_step() が採用されます。逆に右のように、行が存在していない空間が大きければ、adaptive_step() です。

constant_step の詳細

PKの範囲を chunk 数で割って区切りを求めるシンプルなロジックです。テーブルを触ることなく、計算だけで、BETWEENの値が決まります。

例) PKが 10000 〜 49999 (歯抜けなし、4万件) で、chunk 数が 4 の場合

chunk 数
  = (max(PK) - min(PK) + 1) / rows_per_chunk
  = (49999 - 10000 + 1) / rows_per_chunk
  = 40000 / (bytes_per_chunk(オプション指定) / average_row_length)

SELECT 〜 FROM `t`.`pkint_tbl` WHERE (`pk_int` BETWEEN 10000 AND 19999)
SELECT 〜 FROM `t`.`pkint_tbl` WHERE (`pk_int` BETWEEN 20000 AND 29999)
SELECT 〜 FROM `t`.`pkint_tbl` WHERE (`pk_int` BETWEEN 30000 AND 39999)
SELECT 〜 FROM `t`.`pkint_tbl` WHERE (`pk_int` BETWEEN 40000 AND 49999)

adaptive_step の詳細

一言でいうと二分探索。BETWEEN のレンジを動的に {広げ,狭め} ていき、EXPLAIN を利用して、結果行数を見積もる。「期待するchunkあたりの行数 ± 10% 」の値におさまっていたら、レンジを確定させます。

初期に仮定したレンジが広すぎたパターンの例)

EXPLAIN SELECT COUNT(*) FROM `t`.`pkint_sparse_tbl`
WHERE `pk_int` BETWEEN 20854261 AND 21369182 ORDER BY `pk_int`

まとめ

MySQL Shell の dumpInstance で使われる、chunk ロジックには3種類ある
- chunk_integer_column - constant_step
- chunk_integer_column - adaptive_step
- chunk_non_integer_column
意図したサイズに分割してバックアップされるよう、がんばって実装されていた