この記事には続きがあります
MySQL で簡単に出来そうで出来ない SQL に「グループ内の上位 N 件を抽出する SQL」があります。年に 1 回ぐらいこの問題について考え、毎回同じ結論になり「あれー去年も同じこと考えた気がするなー」となっているので、来年も同じことを考えるであろう自分に向けてメモを残しておきます。
なお、この内容は MySQL 5.5.19 で試しています*1。
(2012/07/26 追記：テストデータを増やした、users の name が抽出されていないのを修正)
テストデータ
drop table if exists groups; drop table if exists users; create table groups ( gid int not null primary key auto_increment ); create table users ( uid int not null primary key auto_increment, gid int not null, name varchar(64), val int not null ); insert into groups values (null); insert into groups select null from groups; insert into groups select null from groups; insert into groups select null from groups; insert into groups select null from groups; set @val = 0; insert into users select null, gid, rand(), (@val:=@val+1) from groups; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; insert into users select null, gid, rand(), (@val:=@val+1) from users; create index idx on users (gid, val); select count(*) from groups; /* 16 行 */ select count(*) from users; /* 1048576 行 */ select count(*) from users group by gid; /* 各 65536 行 */
条件
以下のとおり前提及び抽出条件で検索を行います。
- users テーブルから gid ごとに val の昇順の上位 10 行を抽出する
- 同値の 10 位が複数存在する場合はそれら全て抽出する。よって、グループごとの行数が 10 行以上になることもある
- gid ごとの users の行数は 10 よりも十分多い
- 結果はソートされていなくてもいい*2
考え方
3 番目の条件により users テーブルを全表走査するよりも、gid ごとに 10 行ずつ抽出した方が低コストだと推測出来ます。
全表走査の場合は users テーブルの 1048576 行が走査されるのに対して、gid ごとに 10 行ずつであれば、理想的には 16 * 10 = 160 行しか走査されないことになります*3。
なお、ある SQL がどのようにテーブルを走査するかは explain である程度判断できますが、explain だけだと情報が不足している場合もあります。そのような場合は「show status like 'handle%'」でハンドラの実行回数のステータス情報を表示すると、より詳細な情報が得られることがあります。
show status でハンドラの実行回数を表示する
flush status; show status like 'handle%';
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 0 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 0 |
| Handler_read_key | 0 |
| Handler_read_next | 0 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 0 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
最初に「flush status」としているのは「show status」で表示されるステータス情報をクリアするためです。次に「show status」を実行したときは前回の「flush status」から、どのハンドラが、何回実行されたか、が表示されます。今回の場合は何もしていないのですべての値が 0 になっています。
なお、MySQL のバージョンによっては「show status」だけで「Handler_write」が増加する場合があります。そのような場合には表示される「Handler_write」の値から引き算して考える必要があります。
試しに適当な SQL を「show status」で見てみます。
flush status; select * from users limit 10; show status like 'handle%';
show status の結果（値が 0 の行は除外）
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_read_first | 1 |
| Handler_read_key | 2 |
| Handler_read_rnd_next | 10 |
Handler_commit や Handler_read_key が 2 になったり、Handler_read_rnd_next が 10 になる理由は良くわかっていないのですが、これは以下のような意味になります。
- users テーブルの先頭の行を走査（Handler_read_first * 1）
- ↑の続きを順番に10 行（9 行？）走査（Handler_read_rnd_next * 10）
次のように、セカンダリインデックス順に走査する SQL の場合は・・・
flush status; select gid, val from users where gid = 1 order by gid, val limit 10; show status like 'handle%';
show status の結果（値が 0 の行は除外）
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_read_key | 3 |
| Handler_read_next | 9 |
やっぱり Handler_read_key が 3 になる理由はよくわかりませんが、これは概ね次のような意味です。
- users テーブルのセカンダリインデックスから gid = 1 である最初の行を検索（Handler_read_key * 1）
- ↑で検索した行から順番に 9 行を走査（Handler_read_next * 9）
Handler_read_rnd_next と Handler_read_next の違いはテーブルスキャンかインデックススキャンかの違いですが、innodb の場合テーブルスキャンは主キーのインデックススキャンのようなものなので余り違いは無いと思われます。
相関サブクエリを使う方法
それでは「グループ内の上位 N 件を抽出する SQL」を考えていきます。
まずはじめに相関サブクエリを使う方法を試してみます。次のように、サブクエリでグループごとの上位 10 番目の val を取得して、WHERE 句の条件に使用します。もしサブクエリの結果が null の場合は、グループのユーザが 10 人に足りていないということなので、常に true となるように ifnull で振り分けています。
select * from users A where val <= ifnull( ( select B.val from users B where B.gid = A.gid order by B.gid, B.val limit 9,1 ), val )
explain の結果
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | PRIMARY | A | ALL | NULL | NULL | NULL | NULL | 1048281 | Using where |
| 2 | DEPENDENT SUBQUERY | B | ref | idx | idx | 4 | test.A.gid | 58237 | Using where; Using index |
「DEPENDENT SUBQUERY」は相関サブクエリなので、外側のクエリの行数だけ実行されています。よって 1048281 * 58237 = 61048740597 行ぐらいの走査が発生している見積りになります。ただし実際にはそこまで行数は多くありません*4。
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 2097154 |
| Handler_read_last | 0 |
| Handler_read_next | 9437184 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 1048577 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
内訳は次の通りです（Handler_commit はよくわからないので除く）。
| users の全表走査 | Handler_read_first * 1 Handler_read_key * 2 Handler_read_rnd_next * 1048577 |
| ↑の各行について users のセカンダリインデックスの gid 指定による走査 | Handler_read_key * 3 Handler_read_next * 9 ・・・が、1048576 回 |
Handler_read_key の計算が合いませんが、概ねこの通りだと思われます。
大体 1 + 2097154 + 9437184 + 1048577 = 12582916 行程度の走査が行われていることになります。前述の通り、理想的にはたった 160 行程度でいいはずなので、この方法は理想との乖離が激しすぎます。
ただのサブクエリと相関サブクエリの合わせ技
↑の方法は users の各行ごとに相関サブクエリが実行されていました。サブクエリの内容は「グループ内の10番目の val の値を取得」なので、本来ならサブクエリはグループの数（16）だけの回数でいいはずでした。
次はそれを改善して、相関サブクエリの実行回数が少なくなるようにしてみました。users ではなく、groups の各行ごとに相関サブクエリを実行し、その結果のサブクエリと users を結合しています。
select A.* from ( select G.gid, ( select B.val from users B where B.gid = G.gid order by B.gid, B.val limit 9,1 ) AS val from groups G ) T inner join users A on A.gid = T.gid and A.val <= T.val
explain の結果
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | PRIMARY | |
ALL | NULL | NULL | NULL | NULL | 16 | |
| 1 | PRIMARY | A | ref | idx | idx | 4 | T.gid | 58237 | Using where |
| 2 | DERIVED | G | index | NULL | PRIMARY | 4 | NULL | 16 | Using index |
| 3 | DEPENDENT SUBQUERY | B | ref | idx | idx | 4 | test.G.gid | 58237 | Using where; Using index |
「DEPENDENT SUBQUERY」の外側の rows が 16 なので、走査する行数はかなり減っています。
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 51 |
| Handler_read_last | 0 |
| Handler_read_next | 1048736 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 17 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 16 |
この内訳は・・・
groups の主キーの全走査 |
Handler_read_first * 1 Handler_read_key * 2 Handler_read_next * 16 |
↑の各行について users のセカンダリインデックスの gid 指定による走査 |
Handler_read_key * 3 Handler_read_next * 9 ・・・が、16 回 |
↑の結果をテンポラリテーブルに書き込み |
Handler_write * 16 |
↑のテンポラリテーブルを順番に走査 |
Handler_read_rnd_next * 16 |
↑の各行について users のセカンダリインデックスの gid 指定による走査 |
Handler_read_key * 3 Handler_read_next * 65536 ・・・が、16 回 |
Handler_read_key や Handler_read_rnd_next の計算が合いませんが、概ねこのとおりだと思います。
先ほどの相関サブクエリだけを使った方法と比べると走査行数はかなり少なくなりましたが、まだまだ理想の値よりは大きいです。
どこに問題があるのかを show status の内訳から考えてみると・・・一番最後の「Handler_read_next * 65536」がダメな気がします。ここは「特定の gid かつ val が特定値以上」の users を検索して結果は大体 10 行、のクエリなので、インデックスを使用すれば大体 10 行程度の走査でどうにかなりそうに思います。例えば次のような SQL では・・・
select @gid:=gid, @val:=val from users where gid = 1 order by gid, val limit 9,1; select * from users where gid = @gid and val <= @val order by gid, val;
2 番目の SQL だけを見てみると・・・
explain の結果
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | users | range | idx | idx | 8 | NULL | 10 | Using where |
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 0 |
| Handler_read_key | 3 |
| Handler_read_last | 0 |
| Handler_read_next | 10 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 0 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
となり、10 行 + α程度の走査しか発生しません。
一方、同じ結果が予想される次のような SQL の場合・・・
create temporary table tmp as select gid, val from users where gid = 1 order by gid, val limit 9,1; select * from users A inner join tmp B on A.gid = B.gid AND A.val <= B.val;
2 番目の SQL の・・・
explain の結果
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | B | ALL | NULL | NULL | NULL | NULL | 1 | |
| 1 | SIMPLE | A | ref | idx | idx | 4 | test.B.gid | 58237 | Using where |
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 6 |
| Handler_read_last | 0 |
| Handler_read_next | 65536 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 2 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
users の gid = 1 である行がすべて走査されています。range のような条件でテーブル結合を行うことは出来ないようです。
ユーザ変数を用いる方法
なお、異なるアプローチとして、ユーザ変数を用いた次のような方法も考えられます。
set @gid = null, @val = null, @rnk = 0, @num = 0; select @gid := gid as gid, @rnk as rnk, uid, name, @val := val as val from users force index (idx) where ( @num := if(@gid <> gid, 1, @num + 1) ) is not null and ( @rnk := if(@val <=> val, @rnk, @num) ) is not null and @rnk <= 10 order by users.gid, users.val
explain の結果
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | users | index | NULL | idx | 8 | NULL | 1049595 | Using where |
show status の結果
| Variable_name | Value |
|---|---|
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 2 |
| Handler_read_last | 0 |
| Handler_read_next | 1048576 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 0 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
users テーブルの idx インデックスを上から順番に走査しただけです。これまでのどの方法よりも良い結果ですが・・・この方法はインデックスのありなしで結果が変わったりするのであまり良くないように個人的には思います。
まとめ
1 番目の「相関サブクエリを使う方法」は、致命的にダメなので論外です。
2 番目の「ただのサブクエリと相関サブクエリの合わせ技」と 3 番目の「ユーザ変数を用いる方法」であれば、グループの数がそれほど多くないのであれば（＝サブクエリが生成するテンポラリテーブルが十分に小さいのであれば）それほどコストは変わりません。なんとなく force index はしたくないので、2番目の方法の方がいいような気がします。
また、3 番目の方法の場合、走査回数は users テーブルの行数であることは明らかですが、2 番目の方法は MySQL の進化によってより良い実行計画に置き換わる可能性がある・・・かもしれません。
というわけで、普通は 2 番目の方法が良いと思います。
groups の行数に対して users の行数がさらに大きいのであれば、アプリケーションレイヤで groups の行数だけループで回すのがきっと一番速いです。
