読者です 読者をやめる 読者になる 読者になる

グループ内の上位 N 件を抽出する SQL がうまく書けない

この記事には続きがあります


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 行 */

条件

以下のとおり前提及び抽出条件で検索を行います。

  1. users テーブルから gid ごとに val の昇順の上位 10 行を抽出する
  2. 同値の 10 位が複数存在する場合はそれら全て抽出する。よって、グループごとの行数が 10 行以上になることもある
  3. gid ごとの users の行数は 10 よりも十分多い
  4. 結果はソートされていなくてもいい*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 の行数だけループで回すのがきっと一番速いです。

*1:たまたま手元にあった 5.5 系

*2:show status の表示をわかりやすくするため

*3:実際には同点10位が無い場合で 16 * 11 = 176 行 でしょうか

*4:limit を無視して見積もられているため