SQL
greatest-n-per-group

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

スタックオーバーフローで「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が少しわかった気がします。書くといい事がある。