Are ORDER BY clause & ROW_NUMBER duplicating functionality when I need top n queries

Question

I have a table that tracks violations for a student. I want to count the number of violations and select top 2 violators from each class. The query would look like this

SELECT *
FROM
  ( SELECT "people"."id", "name", "class",
    ROW_NUMBER() OVER (PARTITION BY "class" ORDER BY COUNT("violation") DESC) AS "v"
    FROM "people"
    INNER JOIN "discipline" on ("discipline"."people_id" = "people"."id")
    GROUP BY "people"."id", "name", "class"
  ) AS "v_table"
WHERE v < 3

The query seems inefficient because it sorts the count first with ORDER BY and then assigns a ROW_NUMBER. If I already have it sorted over a partition, how can I skip the ROW_NUMBER assignment & get the top 2.

Update : Adding data tables & SQL fiddle (actually violation column is redundant, simply an entry in discipline table means that there's been a violation. If I remove it, should the Count be done on "discipline"."people_id"? like this )

Discipline                     People       
-------------------------      --------------
id  people_id  violation       id  name  class                    
1   1          True            1   Rob   A                 
2   1          True            2   Jen   B                 
3   2          True            3   Tom   C                
4   3          True            4   Ted   A                 
5   4          True            5   Tim   A            
6   1          True            ...                               
7   4          True         
...                                   

Using PostgreSQL 9.3

Answer 1

First, to answer the questions implied in the comments, that the assignment of row numbers with the ROW_NUMBER() aggregate seems inefficient because we already have the COUNT(violation) numbers:

This is needed because the COUNT numbers can be different for each partition (class). Since we want the 2 top numbers (for each class), we can't find a useful condition for that. With the row numbers, we can use the WHERE v < 3 which gives us the top 2.

In version 9.3, the LATERAL joins were added in Postgres, which are similar to the CROSS and OUTER APPLY of SQL-Server. With this new kind of join, you can write a query that uses the COUNT numbers and a TOP 2 for each partition. Whether it is more or less efficient, you can test:

WITH classes AS
  ( SELECT DISTINCT class
    FROM people
  ) 
                             -- if you have a "classes" table, skip the above lines
SELECT 
    v.id, v.name, c.class,
    v.violations
FROM
    classes AS c,
  LATERAL 
    ( SELECT p.id, p.name,
             COUNT(d.violation) AS violations
      FROM people AS p
        INNER JOIN discipline AS d
          ON d.people_id = p.id
      WHERE p.class = c.class 
      GROUP BY p.id, p.name
      ORDER BY violations DESC
      LIMIT 2
  ) AS v
ORDER BY
    c.class, v.violations DESC ;

Tested at SQL-Fiddle

Answer 2

For tables with more than a hand full of classes, I don't expect the LATERAL version to come close in performance, since it has to run one lateral subquery per class. Your version with a subquery (or a similar one with a CTE) will probably be faster.

count(*)

As for your additional question.

If I remove it [violation], should the count be done on "discipline"."people_id"?

Yes, that would be the correct alternative, especially for a LEFT JOIN since it will distinguish between 0 and 1 matches in discipline. However, since we have an INNER JOIN and we are also excluding v < 3 anyway, this distinction is irrelevant here.

Generally, count(*) is slightly faster than count(col), since checking for the existence of a row is enough and the column does not have to be tested for NULL in addition.

Alternative

Other advice:

• I suggest to use your primary key columns for the query. Simplifies GROUP BY. Works for PostgreSQL 9.1 or later. Detailed explanation and source in this related answer on SO.
  Per documentation:

  Functional Dependencies

  PostgreSQL recognizes functional dependency (allowing columns to be omitted from GROUP BY) only when a table's primary key is included in the GROUP BY list. The SQL standard specifies additional conditions that should be recognized.

• Use proper names for your columns (people_id, not id) to make your life simpler.

Demonstrating the CTE alternative:

WITH cte AS (
   SELECT p.*
         ,row_number() OVER (PARTITION BY p.class ORDER BY COUNT(d.*) DESC) AS v
   FROM   people     p
   JOIN   discipline d USING (people_id)
   GROUP  BY p.people_id -- pk is enough
  )
SELECT *
FROM   cte
WHERE  v < 3;

Probably, the subquery is a bit faster, but test it.

Faster

If performance is what you are after, I suggest to aggregate first, then join. That's typically faster, if you query the whole table or most of it.

SELECT *
FROM  (
   SELECT class
         ,row_number() OVER (PARTITION BY class ORDER BY violations DESC) AS rn
         ,violations
         ,people_id
         ,name
   FROM   people p
   JOIN  (
      SELECT people_id, count(*) AS violations
      FROM   discipline
      GROUP  BY 1
      ) d USING (people_id)
   ) sub
WHERE  rn < 3
ORDER  BY class, rn;

How to break ties?

What if 3 students in one class have 4 strikes against them? Two arbitrary students would be picked this way. Define what to do and adapt your query. You may want to use rank() instead of row_number() or add more ORDER BY items as tiebreaker. Related answer:
PostgreSQL equivalent for TOP n WITH TIES: LIMIT “with ties”?

SQL Fiddle demonstrating both.