3

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

  • What do you mean with "have it sorted over a partition"? Do you have the COUNT(violation) values stored somewhere? – ypercubeᵀᴹ Jul 11 '14 at 19:29
  • Won't COUNT followed by ORDER BY inside OVER() count the values first and then sort them in descending order over partition class before passing it on to the ROW_NUMBER function? The latter simply assigns a consecutive numeric id. Excuse my ignorance, since I'm new to SQL & trying to wrap my head around the concepts. – click Jul 11 '14 at 19:31
  • Yes, the OVER with ORDER BY will sort the COUNT values (already calculated by the GROUP BY). – ypercubeᵀᴹ Jul 11 '14 at 19:32
  • Then since the values are already sorted, how can I eliminate the step of assigning ROW_NUMBER and simply get the top 2 values from that sorted list (for each partition) – click Jul 11 '14 at 19:33
  • 1
    Ah, ok. It's readable if you use "view on depesz" to show it on explain.depesz.com. SQLFiddle's default query plan output is nearly illegible due to lack of indenting. So this should help: explain.depesz.com/s/bzz4 – Craig Ringer Jul 12 '14 at 5:14
4

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

  • Thank you for explaining in detail. I'll have to do some reading to understand the solution. Don't have enough rep to vote up yet. I couldn't interpret from the docs if COUNT inside the OVER() clause is done independently for each PARTITION or over entire table. – click Jul 12 '14 at 10:10
3

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.

  • You say pk is enough in GROUP BY & it works & makes sense. I've been reading everywhere that all columns other than aggregates are required in GROUP BY. When is this restriction waived? Can you cite a source. – click Jul 13 '14 at 14:03
  • 2
    @click: With Postgres 9.1. What you've been reading is true in principal, but the SQL standard requires that functionally dependend columns shall be recognized and Postgres partly implemented that in v9.1. – Erwin Brandstetter Jul 13 '14 at 14:20
  • @click: I would be very interested how the query variants perform in your installation and which is fastest. If you don't mind, could you add another answer (for better readability)? With details for your setup: exact version (9.3.?), cardinalities (number of rows), number of classes, typical number of violations per student, ... Test with EXPLAIN ANALYZE and take the best result from a couple of runs for each ... – Erwin Brandstetter Jul 13 '14 at 14:25
  • I'll get a realistic data set from client soon which would be good to test both the methods. I'll update the results accordingly . – click Jul 13 '14 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.