Select one value from a group based on order from other columns

Question

Problem

Suppose I have this table tab (fiddle available).

| g | a | b |     v |
---------------------
| 1 | 3 | 5 |   foo |
| 1 | 4 | 7 |   bar |
| 1 | 2 | 9 |   baz |
| 2 | 1 | 1 |   dog |
| 2 | 5 | 2 |   cat |
| 2 | 5 | 3 | horse |
| 2 | 3 | 8 |   pig |

I'm grouping rows by g, and for each group I want one value from column v. However, I don't want any value, but I want the value from the row with maximal a, and from all of those, the one with maximal b. In other words, my result should be

| 1 |   bar |
| 2 | horse |

Current solution

I know of a query to achieve this:

SELECT grps.g,
(SELECT v FROM tab
 WHERE g = grps.g
 ORDER BY a DESC, b DESC
 LIMIT 1) AS r
FROM (SELECT DISTINCT g FROM tab) grps

Question

But I consider this query rather ugly. Mostly because it uses a dependant subquery, which feels like a real performance killer. So I wonder whether there is an easier solution to this problem.

Expected answers

The most likely answer I expect to this question would be some kind of add-on or patch for MySQL (or MariaDB) which does provide a feature for this. But I'll welcome other useful inspirations as well. Anything which works without a dependent subquery would qualify as an answer.

If your solution only works for a single ordering column, i.e. couldn't distinguish between cat and horse, feel free to suggest that answer as well as I expect it to be still useful to the majority of use cases. For example, 100*a+b would be a likely way to order the above data by both columns while still using only a single expression.

I have a few pretty hackish solutions in mind, and might add them after a while, but I'll first look and see whether some nice new ones pour in first.

---

Benchmark results

As it is pretty hard to compare the various answers just by looking at them, I've run some benchmarks on them. This was run on my own desktop, using MySQL 5.1. The numbers won't compare to any other system, only to one another. You probably should be doing your own tests with your real-life data if performance is crucial to your application. When new answers come in, I might add them to my script, and re-run all the tests.

• 100,000 items, 1,000 groups to choose from, InnoDb:
  1. 0.166s for MvG (from question)
  2. 0.520s for RichardTheKiwi
  3. 2.199s for xdazz
  4. 19.24s for Dems (sequential sub-queries)
  5. 48.72s for acatt
• 100,000 items, 50,000 groups to choose from, InnoDb:
  1. 0.356s for xdazz
  2. 0.640s for RichardTheKiwi
  3. 0.764s for MvG (from question)
  4. 51.50s for acatt
  5. too long for Dems (sequential sub-queries)
• 100,000 items, 100 groups to choose from, InnoDb:
  1. 0.163s for MvG (from question)
  2. 0.523s for RichardTheKiwi
  3. 2.072s for Dems (sequential sub-queries)
  4. 17.78s for xdazz
  5. 49.85s for acatt

So it seems that my own solution so far isn't all that bad, even with the dependent subquery. Surprisingly, the solution by acatt, which uses a dependent subquery as well and which I therefore would have considered about the same, performs much worse. Probably something the MySQL optimizer can't cope with. The solution RichardTheKiwi proposed seems to have good overall performance as well. The other two solutions heavily depend on the structure of the data. With many groups small groups, xdazz' approach outperforms all other, whereas the solution by Dems performs best (though still not exceptionally good) for few large groups.

Answer 1

This way doesn't use sub-query.

SELECT t1.g, t1.v
FROM tab t1
LEFT JOIN tab t2 ON t1.g = t2.g AND (t1.a < t2.a OR (t1.a = t2.a AND t1.b < t2.b))
WHERE t2.g IS NULL

Explanation:

The LEFT JOIN works on the basis that when t1.a is at its maximum value, there is no s2.a with a greater value and the s2 rows values will be NULL.

Answer 2

SELECT g, a, b, v
  FROM (
            SELECT *, 
                   @rn := IF(g = @g, @rn + 1, 1) rn, 
                   @g := g
              FROM (select @g := null, @rn := 0) x, 
                   tab
          ORDER BY g, a desc, b desc, v
       ) X
 WHERE rn = 1;

Single pass. All the other solutions look O(n^2) to me.

Answer 3

Many RDBMS have constructs that are particularly suited to this problem. MySQL isn't one of them.

This leads you to three basic approaches.

• Check each record to see if it is one you want, using EXISTS and a correlated sub-query in an EXISTS clause. (@acatt's answer, but I understand that MySQL doesn't always optimise this very well. Ensure that you have a composite index on (g,a,b) before assuming that MySQL won't do this very well.)

• Do a half cartesian product to full-fill the same check. Any record which does not join is a target record. Where each group ('g') is large, this can quickly degrade performance (If there are 10 records for each unique value of g, this will yield ~50 records and discard 49. For a group size of 100 it yields ~5000 records and discard 4999), but it is great for small group sizes. (@xdazz's answer.)

• Or use multiple sub-queries to determine the MAX(a) and then the MAX(b)...

Multiple sequential sub-queries...

SELECT
  yourTable.*
FROM
  (SELECT g,    MAX(a) AS a FROM yourTable GROUP BY g   ) AS searchA
INNER JOIN
  (SELECT g, a, MAX(b) AS b FROM yourTable GROUP BY g, a) AS searchB
    ON  searchA.g = searchB.g
    AND searchA.a = searchB.a
INNER JOIN
  yourTable
    ON  yourTable.g = searchB.g
    AND yourTable.a = searchB.a
    AND yourTable.b = searchB.b

Depending on how MySQL optimises the second sub-query, this may or may not be more performant than the other options. It is, however, the longest (and potentially least maintainable) code for the given task.

Assuming an composite index on all three search fields (g, a, b), I would presume it to be best for large group sizes of g. But that should be tested.

For small group sizes of g, I'd go with @xdazz's answer.

EDIT

There is also a brute force approach.

• Create an identical table, but with an AUTO_INCREMENT column as an id.
• Insert your table into this clone, ordered by g, a, b.
• The id's can then be found with SELECT g, MAX(id).
• This result can then be used to look-up the v values you need.

This is unlikely to be the best approach. If it is, it is effectively a condmenation of MySQL's optimiser's ability to deal with this type of problem.

That said, every engine has it's weak spots. So, personally, I try everything until I think I understand how the RDBMS is behaving and can make my choice :)

EDIT

Example using ROW_NUMBER(). (Oracle, SQL Server, PostGreSQL, etc)

SELECT
  *
FROM
(
  SELECT
    ROW_NUMBER() OVER (PARTITION BY g ORDER BY a DESC, b DESC) AS sequence_id,
    *
  FROM
    yourTable
)
  AS data
WHERE
  sequence_id = 1

Answer 4

This can be solved using a correlated query:

SELECT g, v
FROM tab t
WHERE NOT EXISTS (
    SELECT 1
    FROM tab
    WHERE g = t.g
        AND a > t.a
        OR (a = t.a AND b > t.b)
    )