Selecting First/Least/Max Row per Group in SQL

Here are some common SQL problems, all of which have related solutions:

• How do I find the most recent log entry for each program?
• How do I find the most popular item from each category?
• How do I find the top score for each player?

In general, these types of “select the extreme from each group” queries can be solved with the same techniques. I’ll explain how to do that in this article, including the harder problem of selecting the top N entries, not just the top 1.

As a sample table for the following examples we will use a simple three column table:

Selecting the maximum row from each group

Let’s say I want to select the most recent log entry for each program, or the most recent changes in an audit table, or something of the sort. This question comes up over and over on IRC channels and mailing lists. I’ll re-phrase the question in terms of fruits. I want to select the cheapest fruit from each type. Here’s the desired result:

There are a few common solutions to this problem. All involve two steps: finding the desired value of price, and then selecting the rest of the row based on that.

One common solution is a so-called self-join. Step one is to group the fruits by type (apple, cherry, etc.) and choose the minimum price:

SELECT   type, MIN(price) AS min_price
FROM     fruits
GROUP BY type;

Results:

Step two is to select the rest of the row by joining these results back to the same table. Since the first query is grouped, it needs to be put into a subquery so it can be joined against the non-grouped table:

SELECT f.type, f.variety, f.price
FROM   (
           SELECT   type, MIN(price) as minprice
           FROM     fruits
           GROUP BY type
       ) AS x
           INNER JOIN
       fruits AS f
           ON f.type  = x.type     AND
              f.price = x.minprice;

Which results in:

Another common way to do this is with a correlated subquery. This can be much less efficient, depending on how good your system’s query optimiser is. You might find it clearer though.

SELECT f.type, f.variety, f.price
FROM   fruits
WHERE  price = (SELECT MIN(price)
                FROM   fruits AS f
                WHERE  f.type = fruits.type);

Which results in:

Both queries are logically equivalent, though they may not perform the same.

Select the top N rows from each group

This is a slightly harder problem to solve. Finding a single row from each group is easy with SQL’s aggregate functions (MIN(), MAX() and so on). Finding the first several rows from each group is not possible with that method because aggregate functions only return a single value. Still, it is possible to do.

Let’s say I want to select the two cheapest fruits from each type. Here’s a first try:

SELECT type, variety, price
FROM   fruits
WHERE  price = (SELECT MIN(price)
                FROM fruits AS f
                WHERE f.type = fruits.type) OR
       price = (SELECT MIN(price)
                FROM fruits AS f
                WHERE f.type = fruits.type AND
                      price  > (SELECT MIN(price)
                                FROM   fruits AS f2
                                WHERE  f2.type = fruits.type));

Which results in:

Yuck! That can be written as a self-join, but it’s just as bad (I will leave that as an exercise for you reader). This gets worse as you go to higher numbers (top 3, top 4…). There are other ways to phrase the statement, but they all boil down to the same thing, and they’re all pretty unwieldy and inefficient.

There’s a better way: select the variety from each type where the variety is no more than the second-cheapest of that type.

This is elegant, and lets you vary N without rewriting your query (a very good thing!), but it’s functionally the same as the previous query. Both are essentially a quadratic algorithm relative to the number of varieties in each type. And again, some query optimizers may not do well with this and make it quadratic with respect to the number of rows in the table overall (especially if no useful index is defined), and the server might get clobbered. Are there better ways? Can it be done with one pass through the data, instead of the many passes required by a correlated subquery? You know it can, or I wouldn’t be writing this, now would I?

SELECT type, variety, price
FROM   fruits
WHERE  (SELECT count(*)
        FROM   fruits AS f
        WHERE  f.type = fruits.type AND f.price < fruits.price) <= 2;