この記事は何か?

ISUCON12の復習をやっていきます。

第1回はISUCON12 予選の解説 (Node.jsでSQLiteのまま10万点行く方法)の「adminDB visit_history にINDEXを張る」までをやります。

1. 環境構築

用意されたCloudFormationテンプレートを利用する場合に記載された方法でAWS上に環境を用意します。

cloudformation.yamlをダウンロードして、CloudFormationの画面から実行
3台起動されるが、節約のため1台停止 (1台をベンチ実行用、2台目をチューニング用に利用します)
Systems Manager > パラメータストアを開き、秘密鍵をコピペ、SSHログイン

vi ~/.ssh/isucon12q.pem
chmod 400 ~/.ssh/isucon12q.pem
ssh -i ~/.ssh/isucon12q.pem ubuntu@xx.xx.xx.xx ← 1台目にログイン

04.初回ベンチ実行

sudo su - isucon
cd /home/isucon/bench
./bench -target-addr xx.xx.xx.xx:443  ← 2台目に向けてベンチ実行

初回スコアは2,781でした。運営の方がCloudFormationテンプレートを用意してくれたおかげで準備が超簡単です。ありがとうございます。

「adminDB visit_history にINDEXを張る」を試す

初手は「adminDB visit_history にINDEXを張る」でした。私と同じで嬉しかったのですがINDEXの張り方が違っていました。

最後にcreated_atまで入れておくと、Covering Indexになるのでセカンダリインデックス単体でクエリを返すことができて高速ですが、created_atを張るのを忘れるとcreated_atを読むためにクラスタインデックスを読みに行くのでそこまで伸びない(もちろん張らないよりはマシ)といった感じです。私は最初created_atまで入れてなくて「アルェー」と言ってました。

私は2カラムしか設定しませんでしたが、解説では4カラムでした。

私: tenant_id, competition_id
解説: tenant_id, competition_id, player_id, created_at

気になったので、インデックス毎に「Extra」の値を確認しました。

スロークエリログ

Reading mysql slow query log from /var/lib/mysql/slow.log
Count: 1152  Time=0.11s (129s)  Lock=0.00s (0s)  Rows=92.7 (106831), isucon[isucon]@localhost
  SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = N AND competition_id = 'S' GROUP BY player_id

EXPLAIN結果 (インデックス無し)

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 1 AND competition_id = 'S' GROUP BY player_id\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx
          key: tenant_id_idx
      key_len: 8
          ref: const
         rows: 1293162
     filtered: 10.00
        Extra: Using where; Using temporary
1 row in set, 1 warning (0.00 sec)

EXPLAIN結果 (インデックス tenant_id, competition_id)

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 1 AND competition_id = 'S' GROUP BY player_id\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx,idx_tenant_id_competition_id
          key: idx_tenant_id_competition_id
      key_len: 1030
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: Using temporary
1 row in set, 1 warning (0.00 sec)

EXPLAIN結果 (インデックス tenant_id, competition_id, player_id)

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 1 AND competition_id = 'S' GROUP BY player_id\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx,idx_tenant_id_competition_id_player_id
          key: idx_tenant_id_competition_id_player_id
      key_len: 1030
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 row in set, 1 warning (0.00 sec)

EXPLAIN結果 (インデックス tenant_id, competition_id, player_id, created_at)

mysql> explain SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = 1 AND competition_id = 'S' GROUP BY player_id\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: visit_history
   partitions: NULL
         type: ref
possible_keys: tenant_id_idx,idx_all_cover
          key: idx_all_cover
      key_len: 1030
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: Using index
1 row in set, 1 warning (0.00 sec)

スコア比較

// Before (インデックス無し)
07:03:05.717432 SCORE: 2781 (+2781 0(0%))

Count: 1152  Time=0.11s (129s)  Lock=0.00s (0s)  Rows=92.7 (106831), isucon[isucon]@localhost
  SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = N AND competition_id = 'S' GROUP BY player_id

// After (インデックス idx_all_cover)
07:13:45.086791 SCORE: 3238 (+3238 0(0%))

Count: 4076  Time=0.01s (20s)  Lock=0.00s (0s)  Rows=153.0 (623605), isucon[isucon]@localhost
  SELECT player_id, MIN(created_at) AS min_created_at FROM visit_history WHERE tenant_id = N AND competition_id = 'S' GROUP BY player_id

idx_all_coverは「Using index」になっていて、スコアも上がっています。(他のスコアは省略して計測しませんでした)

感想

「クラスタインデックス」と「セカンダリインデックス」の説明は(通称)ISUCON本[2]の説明が分かりやすいです。その本では、「クラスタインデックス」だけから情報を取得できることでの性能向上について書かれていましたが、「セカンダリインデックス」だけにアクセスすることも可能ということを知りました。またyoku0825さんの以下の説明[3]も分かりやすいです。

MySQLのインデックスはほぼB+Treeです。MySQLのB+Treeインデックスのリーフには「テーブル内での行の位置」が記録されています（MyISAMであれば.MYDファイルの先頭からオフセットバイト数、InnoDBであればクラスターインデックスの値が記録されている）。そのため、インデックスを利用した行フェッチを行う際は、以下の3ステップで行われます。 1 インデックス上から条件にマッチするリーフを探す 2 インデックスのリーフ上に書かれた情報から行の位置を探す 3 行をフェッチする

Using indexが示すのはインデックス上に書かれた情報だけで（インデックスは「ソート済みのデータの複製（サブセット）」でありインデックスを作成したカラムの値を含む）、要求された情報の取り出しが終了したため 2. と 3. のステップを省略した、というものです。