Posted at

SQLで「greatest-n-per-group」問題(グループごとに最大値の行を求める)

More than 1 year has passed since last update.

スタックオーバーフローで「Greatest-N-Per-Group」として知られている問題があります。割とよくある問題で名前までついてるとのことなので、理解するついでにまとめてみます。

どういう問題かというと…


グループごとに、最大の値を持つ行を求める

例えば、次のような得点データpointsテーブルがあります。

id
name
point

1
太郎
50

2
花子
30

3
太郎
40

4
花子
60

それぞれの名前の最大得点のある行を求める、という話です。


それはMAX()とGROUP BYでは?

よくあるシンプルなSQLですね。こんなの。

SELECT MAX(point) AS max_point, name 

FROM points
GROUP BY name

これで各自の最大値は分かります。

max_point
name

50
太郎

60
花子

でも、


最大値を持つ「」の情報が欲しい!

今回知りたいのは、「最大値の行」です。

例えば、こんな結果です。

max_point
id
name

50
1
太郎

60
4
花子

この例だと「最大値とそのidが知りたい」という場合です。これを、SQLで求める方法になります。StackOverflowには、大量のSQLが紹介されているので、その中から気になったSQLを紹介します。


サブクエリを使う方法

最大値を持つテーブルをサブクエリで作って結合する方法です。

SELECT MAX(x.point) AS max_point, x.id, x.name

FROM points x
JOIN (
SELECT p.name, MAX(point) AS max_point
FROM points p
GROUP BY p.name ) y -- 最大値を持つテーブル
ON (y.name=x.name AND y.max_point=x.point)
GROUP BY x.id, x.name

テーブルyが最大値を持ってます。これに対して、最大値と名前の条件(y.name=x.name AND y.max_point=x.point)で結合することで、欲しい行の情報を取得してます。

ある意味、一番素直にSQLを書いた感じでしょうか。

参考


自分自身とJOINする

最初は?でしたが、意外と分かりやすいかも、と思った方法です。

SELECT x.id, x.name, x.point 

FROM points x
LEFT OUTER JOIN points y -- 自分自身と結合
ON(y.name = x.name AND y.point > x.point)
WHERE y.id IS NULL

自分自身とJOINします(最初がx、JOINするテーブルがyです)。

JOINする条件に、名前が一致することと、最大値y.point > x.pointの条件があります。これがあるので、最大値の行だけジョインする相手がいないので、y.id IS NULLで引っ張ってこれる、というわけです。

参考


Where In句を使う方法

こんな方法があるのか!?

SELECT * 

FROM points
WHERE (name, point) IN (
SELECT name, MAX(point)
FROM points
GROUP BY name
)

StackOverflowでも、知らなかったとの声が。MySql、Oracle、PostgreSQL、DB2で動いたとのコメントあり。SQLiteは動かなかったと。自分はMySQLとPostgreSQLで動くのを確認できました。

参考


PostgreSQLのDISTINCT ONを使う方法

こちらも、こんな方法があるのか!?と思った方法です。ただしPostgreSQL限定のようですね。

SELECT DISTINCT ON(name)

id, name, point
FROM points
ORDER BY name, point DESC, id

DISTINCT ONを使って名前をユニーク、つまり一行のみ取得するようにします。その上で、名前・得点の高い順に並べると、一番得点の高い行が取得できる仕組みですね。これだと同じ得点の場合は、一行だけ取得することになるのでしょう。

参考


With句とRow_Number()を使う方法

With句とはSQL99で導入された構文で、サブクエリなどのネストが読みやすくなるとのこと。PostgreSQLではWith句に対応済み、MySQLも8.0から使えるという話なので学んでおきたいところ…

WITH ranking AS (

SELECT p.id, p.point, p.name,
ROW_NUMBER() OVER(
PARTITION BY p.name ORDER BY p.point DESC) AS point_rank
FROM points p
)
SELECT r.*
FROM ranking r
WHERE r.point_rank = 1

まず、With句でrankingを定義してます。ここで、ROW_NUMBER() ... AS point_rankとしています。各行ごとに番号を振ってるんですね。

行番号については、OVER(PARTITION BY ... ORDER BY ...)を使うことで、名前ごとに1から振っていて、さらにポイントで並べてます。これで名前ごとで一番高いポイントの行がpoint_rank=1となるので、簡単に絞りこめると。SQLすごい。

参考


最後に

よくあることですが、書き終わってからググったら日本語のgreatest-n-per-groupの情報がありました。さらに「グループごとに最大値の行を取得」でググると結構ヒットするようです。

今回は最大値を求めるSQLでしたが、最小値の場合でも使えます。同じ得点がある場合、全部取得にするか一行に絞り込むかなど、色んなバリエーションがあります。


パフォーマンス

本来は各SQLのパフォーマンス比較が欲しいですが、今回はやってません(このページに測定した結果があります)。

データ数やDBによって結果は異なりそうなので、毎回試すべきと思われます。パフォーマンスが絶対に必要なら別に結果テーブルを作成(マテリアルビューとか?)するのもありなんじゃないでしょうか。


With句について

これを書くことで、With句とPARTITION OVERが少しわかった気がします。書くといい事がある。