遅いクエリを「何ページにアクセスするか」で見積もれるようになる

• 行数ではなく、ページ数でコストが決まる
• かかる時間の大部分は、ディスクから読むページの数で決まる

環境: RDS db.t4g.medium（2 vCPU / 4GB）・buffer pool 1.5GB・テーブル約4.5GB

• TEXT 列を含む行を1000件読む → TEXT 1万文字で約1.4秒、800文字で約18ms
• 同じ約9.5万行を読む処理 → 1回目31秒、2回目5秒
• UPDATE した直後に読む → 速い

今日の話で、これを説明します

• MySQL は サーバー層 と ストレージエンジン層 に分かれている
• InnoDB は後者。データの保存と読み書きを担う

データの置き場所

• テーブルスペース — ディスク上のデータファイル（既定ではテーブルごとに1つ）。データそのもの
• buffer pool — メモリ。ページのキャッシュ・書き換えたページの置き場

• InnoDB の読み書きの単位はページ（既定 16KB）
• テーブルスペースは 16KB のページが並んだもの
• ディスクからは必ずページ丸ごと読む。ページの中で行を探すのは、読んだあとのメモリ上の仕事

→ 1行だけ欲しくても、その行を含むページ全体（16KB）を読む

• 根ノード → 中間ノード → リーフの3段ほど（ノード1つがページ1つ）
• リーフには、インデックスの種類に応じたデータが入っている
• リーフ同士は、前後のページ番号でキー順につながっている
• 例: リーフ1 にキー 1〜80、リーフ2 にキー 81〜160、リーフ3 にキー 161〜240 …

• InnoDB のテーブルは、主キーのB+ツリー（クラスタインデックス）のこと。リーフに行データそのものが入っている
• フルスキャン（EXPLAIN の type=ALL）→ 根から先頭のリーフまで探索し、以降はリーフ間のリンクを順に読む

• セカンダリインデックスのリーフに入っているのは「インデックスの値 ＋ 主キー」
• 行の残りの列が欲しければ、その主キーでクラスタインデックスを引き直す

SELECT * FROM orders WHERE user_id = 99;

1. user_id のインデックスで、該当する id を集める
2. その id でクラスタインデックスを引く

架空の orders テーブルで考える
orders: 主キー id・1行約200バイト・INDEX(user_id) あり
1ページに約80行（16,000 ÷ 200）

SELECT * FROM orders WHERE id BETWEEN 1 AND 1000;
1000 ÷ 80 ＝ 12.5
→ 約13ページ（連続）

① id を集める
SELECT * FROM orders WHERE user_id = 99;（該当1000件）
1件（user_id ＋ id）約20バイト → 1ページ約800件
→ 約2ページ

② クラスタインデックスを引く
集めた id ごとに、クラスタインデックスを引く
→ 最悪約1000ページ（飛び飛び）

SELECT id, created_at FROM orders WHERE user_id = 99;
（INDEX(user_id, created_at)）

必要な列がセカンダリのリーフに全部ある
→ 約2ページ（通常はクラスタインデックスを読まない）

同じ1000行でも、読み方で約13ページにも約1000ページにもなる

• 1行の最大サイズは、ページの半分より少し小さい
  • 16,000 ÷ 2 ＝ 約8,000バイト
• 超えると、長い可変長列から順にoverflow ページに格納する
  • off-page column
• リーフには、overflow ページを指すポインタだけが残る

日本語は1文字約3バイト・ほかの列は合わせて約100バイトとして、行全体の大きさで判定する

• 800文字: 100 ＋ 2,400 ＝ 2,500バイト → リーフ
• 2000文字: 100 ＋ 6,000 ＝ 6,100バイト → リーフ
• 3000文字: 100 ＋ 9,000 ＝ 9,100バイト > 8,000 → overflow 1ページ
• 1万文字: 100 ＋ 30,000 > 8,000 → 30,000 ÷ 16,000 ≒ 1.9 → overflow 約2ページ

クエリ: TEXT を含む行を ORDER BY id で1000件ずつ読む
TEXT 以外の列は約100バイト（仮定）
→ 800文字で約18ms、1万文字で約1.4秒

TEXT はリーフに収まる
→ 約170ページ（連続）
実測: 約18ms

TEXT は overflow ページへ
→ リーフ数ページ ＋ overflow 約2000ページ（1枚ずつ読む）
実測: 約1.4秒

• 例: articles テーブル。id・title など合わせて約100バイト ＋ TEXT 列 body
• id の範囲で1000行を、body を読まないクエリ（SELECT id, title）で読む
• overflow ページを読みに行くのは、その列を SELECT（WHERE などで参照）したときだけ

→ body を読まないなら、短い body のほうが読むページが多くなる

• リーフの1行は 100 ＋ ポインタ20 ＝ 120バイトと小さい
• SELECT id, title は約8ページ

• リーフの1行は 100 ＋ 6,000 ＝ 6,100バイトと大きい
• SELECT id, title でも約500ページ

→ body が短い2000文字のほうが、SELECT id, title で500ページと多い（逆転）
遅くなる原因は大きい列ではなく、あくまで読むページ数
リーフに収まる長さの列は、SELECT しなくてもリーフのページと一緒に読み込まれる

ページを置いておくメモリ領域

• キャッシュ: 一度読んだページを残し、次はディスクへ行かずに済ませる
• バッファ: 書き換えたページを、すぐにはテーブルスペースに書かずに置いておく

「アクセスするページ数」と「ディスクから読むページ数」は別

LRU: しばらく使われていないページから追い出す

buffer pool 1.5GB に対して、4.5GB のテーブルをフルスキャンすると

• スキャンしたページで buffer pool が埋まる
• アプリが使うページも、スキャン中にアクセスされなければ追い出される
• しかもスキャンしたページは一度しか使われないことが多い

→ InnoDB はこうならないよう工夫している（次のスライド）

LRU リストを2つに分ける

• new 側 — 最近また使われたページ
• old 側 — 追い出し候補

1. ディスクから読んだページは、old 側の頭に入る
2. old 側のページに、1秒以上たってからもう一度アクセスがあると、new 側の頭へ移る
3. アクセスされないページは、後から入るページに押されて尾まで行き、追い出される

最初のアクセスから1秒未満の再アクセスでは new へ移さない。行を順に読むあいだ、同じページへのアクセスは短時間に集中する

例: フルスキャンで、1ページに80行

1. ページ1を読む → old 側の頭へ
2. ページ1の80行を続けて読む（すべて1秒未満）
3. それ以降、ページ1には戻らない

→ new 側へ移らず、ページ1は old 側のまま追い出される。このフルスキャンでは new 側のページは押し出されない

• 1回目31秒・2回目5秒
  • 1回目: buffer pool に無いページをディスクから読む
  • 2回目: ページが buffer pool に残っているので、ディスクから読まずに済む
• UPDATE した直後は速い
  • 変更は必ず buffer pool の上で行う → 直後はページが buffer pool にある

• コストは行数ではなくアクセスするページ数
  • セカンダリ経由では、引き直す行がクラスタインデックスの別々のページにあることが多い
  • 行がページの半分を超えると、長い可変長列は overflow ページに格納。読むかは SELECT する列しだい
• かかる時間の大部分は、ディスクから読むページの数で決まる
  • buffer pool にあるページは、ディスクから読むより桁違いに速い
  • フルスキャンで読んだページは old 側に入り、new 側を追い出しにくい

orders（主キー id・1行約200バイト）に INDEX(user_id) がある。どちらも1000行を返す

• A: SELECT * FROM orders WHERE id BETWEEN 1 AND 1000;
• B: SELECT * FROM orders WHERE user_id = 99;
  • user_id=99 の注文は1000件。id は連続していない

A と B は、それぞれ何ページくらいアクセスする？

• A: 16,000 ÷ 200 ＝ 80行/ページ → 1000 ÷ 80 ＝ 12.5 → 約13ページ
• B: セカンダリ約2ページ ＋ 引き直し最悪1000ページ ＝ 約1002ページ
  • 1行ごとに別のリーフページにある、最悪の場合を数えている

articles（DYNAMIC）。ほかの列は合わせて約100バイト、body（TEXT）はどの行も日本語約2000文字

• A: SELECT id, title FROM articles WHERE id BETWEEN 1 AND 1000;
• B: SELECT * FROM articles WHERE id BETWEEN 1 AND 1000;

A と B は、それぞれ何ページくらいアクセスする？

• 100 ＋ 2000 × 3 ＝ 6,100バイト → 半分（約8,000）に届かないので body はリーフの中
• 16,000 ÷ 6,100 ≒ 2.6 → 2行/ページ → 1000 ÷ 2 ＝ 500 → A も B も約500ページ

buffer pool に無い100ページを読むクエリ。1回0.1秒で終わる。これを3回実行する

• 1回目: 0秒
• 2回目: 0.3秒
• 3回目: 5秒

それぞれ終わったとき、100ページは LRU リストのどこにいる？

• 1回目 → old の頭。ディスクから読んだページは old の頭に入る
• 2回目 → old のまま。buffer pool から読めるが、最初のアクセスから1秒未満なので new 側へ移らない
• 3回目 → new の頭。1秒以上たってからのアクセスなので new 側へ移る

（ほかのアクセスが無い場合）