Selecting best row in each group based on two columns

Question

Suppose we have the following table, where each row represents a submission a user made during a programming contest, id is an auto-increment primary key, probid identifies the problem the submission was made to, score is the number of points the submission earned for the problem, and date is the timestamp when the submission was made. Each user can submit as many times as they want to the same problem:

+----+----------+--------+-------+------------+
| id | username | probid | score |    date    |
+----+----------+--------+-------+------------+
|  1 | brian    |      1 |     5 | 1542766686 |
|  2 | alex     |      1 |    10 | 1542766686 |
|  3 | alex     |      2 |     5 | 1542766901 |
|  4 | brian    |      1 |    10 | 1542766944 |
|  5 | jacob    |      2 |    10 | 1542766983 |
|  6 | jacob    |      1 |    10 | 1542767053 |
|  7 | brian    |      2 |     8 | 1542767271 |
|  8 | jacob    |      2 |    10 | 1542767456 |
|  9 | brian    |      2 |     7 | 1542767522 |
+----+----------+--------+-------+------------+

In order to rank the contestants, we need to determine the best submission each user made to each problem. The "best" submission is the one with the highest score, with ties broken by submission ID (i.e., if the user got the same score on the same problem twice, we only care about the earlier of the two submissions). This would yield a table like the following:

+----------+--------+----+-------+------------+
| username | probid | id | score |    date    |
+----------+--------+----+-------+------------+
| alex     |      1 |  2 |    10 | 1542766686 |
| alex     |      2 |  3 |     5 | 1542766901 |
| brian    |      1 |  4 |    10 | 1542766944 |
| brian    |      2 |  7 |     8 | 1542767271 |
| jacob    |      1 |  6 |    10 | 1542767053 |
| jacob    |      2 |  5 |    10 | 1542766983 |
+----------+--------+----+-------+------------+

How can I write a query to accomplish this?

I added the [tag:greatest-n-per-group] tag. This is a common type of question, and techniques to solve it have been posted many times. — Bill Karwin, Nov 21 '18 at 03:32

score 0 · Answer 1 · edited Nov 21 '18 at 02:41

0

SELECT username , probid , id , score , `date`
FROM tableName
ORDER BY username, score DESC, ID

edited Nov 21 '18 at 02:41

Nick

138,499
22
57
95

answered Nov 21 '18 at 02:33

DoubleM

454
1
3
11

Adding some explanation would make this answer more useful. – Sagar Zala Nov 21 '18 at 05:11

score 0 · Answer 2 · edited Nov 21 '18 at 02:47

0

Using MySQL-8.0 or MariaDB-10.2 or later:

SELECT username, probid, id, score, `date`
FROM (
    SELECT username, probid, id, score, `date`,
           ROW_NUMBER() over (
                 PARTITION BY username,probid
                 ORDER BY score DESC) as `rank`
    FROM tablename
) as tmp
WHERE tmp.`rank` = 1

edited Nov 21 '18 at 02:47

Nick

138,499
22
57
95

answered Nov 21 '18 at 02:40

danblack

12,130
2
22
41

You really should check your code before posting. Lost count of how many typos I've corrected. – Nick Nov 21 '18 at 02:49
sorry @Nick. Thanks for fixing. – danblack Nov 21 '18 at 02:50
I want answer but see your code really same with me.. Here is fiddle for you.. https://www.db-fiddle.com/f/9HXkNFbDMDjPgKbpcbtRXc/0 – dwir182 Nov 21 '18 at 02:51

Nick · Answer 3 · 2018-11-21T04:51:14.350

This query will work on versions of MySQL prior to 8.0 as well. The LEFT JOIN removes duplicate scores, ensuring that equal scores only have the lowest date in the result set for a given score. Then the WHERE clause ensures that we have the maximum score for a given user/problem combination:

SELECT t1.username, t1.probid, t1.id, t1.score, t1.date
FROM tablename t1
LEFT JOIN tablename t2
    ON t2.username = t1.username AND
       t2.probid = t1.probid AND
       t2.score = t1.score AND
       t2.date < t1.date
WHERE t2.id IS NULL AND
      t1.score = (SELECT MAX(score) FROM tablename t3 WHERE t3.username = t1.username AND t3.probid = t1.probid)
ORDER BY t1.username, t1.probid

Update

It's almost certainly more efficient to JOIN the table to a list of maximum scores per user per problem first rather than computing the MAX value for each row in the result table. This query does that instead:

SELECT t1.username, t1.probid, t1.id, t1.score, t1.date
FROM tablename t1
JOIN (SELECT username, probid, MAX(score) AS score
      FROM tablename
      GROUP BY username, probid) t2
    ON t2.username = t1.username AND 
       t2.probid = t1.probid AND 
       t2.score = t1.score
LEFT JOIN tablename t3
    ON t3.username = t1.username AND
       t3.probid = t1.probid AND
       t3.score = t1.score AND
       t3.date < t1.date
WHERE t3.id IS NULL
ORDER BY t1.username, t1.probid

Output (for both queries):

username    probid  id  score   date
alex        1       2   10      1542766686
alex        2       3   5       1542766901
brian       1       4   10      1542766944
brian       2       7   8       1542767271
jacob       1       6   10      1542767053
jacob       2       5   10      1542766983

Updated Demo on SQLFiddle

score 0 · Answer 4 · answered Nov 21 '18 at 04:55

In pre-MySQL 8.0.2, we can emulate Row_Number() functionality using User-defined Variables. In this technique, we firstly get the data in a particular order (depends on the problem statement at hand).

In your case, within a partition of probid and username, we need to rank scores in descending order, with the row having lower timestamp value given higher priority (to break the ties). So, we will ORDER BY probid, username, score DESC, date ASC.

Now, we can use this result-set as a Derived Table, and determine the row number. It will be like a Looping technique (which we use in application code, eg: PHP). We would store the previous row values in the User-defined variables, and use conditional CASE .. WHEN expressions to check the current row's value(s) against the previous row. And, then assign row number accordingly.

Eventually, we will consider only those rows where row number is 1, and (if required), sort it by username and probid.

Query

SELECT dt2.username,
       dt2.probid,
       dt2.id,
       dt2.score,
       dt2.date
FROM   (SELECT @rn := CASE
                        WHEN @un = dt1.username
                             AND @pid = dt1.probid THEN @rn + 1
                        ELSE 1
                      end          AS row_no,
               @un := dt1.username AS username,
               @pid := dt1.probid  AS probid,
               dt1.id,
               dt1.score,
               dt1.date
        FROM   (SELECT id,
                       username,
                       probid,
                       score,
                       date
                FROM   your_table
                ORDER  BY username,
                          probid,
                          score DESC,
                          date ASC) AS dt1
               CROSS JOIN (SELECT @un := '',
                                  @pid := 0,
                                  @rn := 0) AS user_init_vars) AS dt2
WHERE  dt2.row_no = 1  
ORDER BY dt2.username, dt2.probid;

Result

| username | probid | id  | score | date       |
| -------- | ------ | --- | ----- | ---------- |
| alex     | 1      | 2   | 10    | 1542766686 |
| alex     | 2      | 3   | 5     | 1542766901 |
| brian    | 1      | 4   | 10    | 1542766944 |
| brian    | 2      | 7   | 8     | 1542767271 |
| jacob    | 1      | 6   | 10    | 1542767053 |
| jacob    | 2      | 5   | 10    | 1542766983 |

View on DB Fiddle

This is an interesting article on variables from the MySQL dev team which is worth reading: https://mysqlserverteam.com/row-numbering-ranking-how-to-use-less-user-variables-in-mysql-queries/. Basically they suggest you can't rely on them for this type of functionality. — Nick, Nov 22 '18 at 23:53
@Nick well I have experimented with them quite a bit. There is a reason that I always do explicit ordering in a subquery (derived table) first, and then use variables in outer subquery. This ensures reliability. The article is about using `order by` in the same query block which also evaluates user variables in the `select` clause, and I have seen its unreliability. Thanks for the article though, as I was looking for some sort of documentation which explain this behaviour. — Madhur Bhaiya, Nov 23 '18 at 04:11
@Nick I was trying to implement `LEAD()` function using variables. Initially tried this: https://www.db-fiddle.com/f/rdPgxKC7UphoHxwU5VAVeB/1 Even with explicit sorting done in inner subquery, it did not work when I tried to sort again in outer subquery. I had to move sorting to outermost (3rd level) subquery. This worked: https://www.db-fiddle.com/f/rdPgxKC7UphoHxwU5VAVeB/0 So basically, we should avoid using `order by` and evaluation of variables in `select` together in the same subquery block. — Madhur Bhaiya, Nov 23 '18 at 04:48
I think that is the way to avoid problems (as much as possible); the only problem though is that if you sort in an inner subquery there's no guarantee that the MySQL optimiser won't decide that it doesn't actually need to sort. I've seen that happen in one query that I tried to use and eventually had to resort to all sorts of horrible JOINs to make the query work. — Nick, Nov 23 '18 at 05:13
@Nick Do you have a ready example of that behaviour ? I also fear that this might happen in some edge case. Will be interesting to look at. Nevertheless, with 8.0 version, over the time, we should not have a need to use variables in such problems — Madhur Bhaiya, Nov 23 '18 at 05:15
Unfortunately I didn't save that example. If I come across another one, I'll create a fiddle and post a link here. As you say, 8.0 will come to our rescue eventually! — Nick, Nov 23 '18 at 05:31

Selecting best row in each group based on two columns

4 Answers4

Linked