nurettin nurettin - 7 months ago 40
SQL Question

Optimize groupwise maximum query

select *
from records
where id in ( select max(id) from records group by option_id )


This query works fine even on millions of rows. However as you can see from the result of explain statement:

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=30218.84..31781.62 rows=620158 width=44) (actual time=1439.251..1443.458 rows=1057 loops=1)
-> HashAggregate (cost=30218.41..30220.41 rows=200 width=4) (actual time=1439.203..1439.503 rows=1057 loops=1)
-> HashAggregate (cost=30196.72..30206.36 rows=964 width=8) (actual time=1438.523..1438.807 rows=1057 loops=1)
-> Seq Scan on records records_1 (cost=0.00..23995.15 rows=1240315 width=8) (actual time=0.103..527.914 rows=1240315 loops=1)
-> Index Scan using records_pkey on records (cost=0.43..7.80 rows=1 width=44) (actual time=0.002..0.003 rows=1 loops=1057)
Index Cond: (id = (max(records_1.id)))
Total runtime: 1443.752 ms


(cost=0.00..23995.15 rows=1240315 width=8)
<- Here it says it is scanning all rows and that is obviously inefficient.

I also tried reordering the query:

select r.* from records r
inner join (select max(id) id from records group by option_id) r2 on r2.id= r.id;

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------

Nested Loop (cost=30197.15..37741.04 rows=964 width=44) (actual time=835.519..840.452 rows=1057 loops=1)
-> HashAggregate (cost=30196.72..30206.36 rows=964 width=8) (actual time=835.471..835.836 rows=1057 loops=1)
-> Seq Scan on records (cost=0.00..23995.15 rows=1240315 width=8) (actual time=0.336..348.495 rows=1240315 loops=1)
-> Index Scan using records_pkey on records r (cost=0.43..7.80 rows=1 width=44) (actual time=0.003..0.003 rows=1 loops=1057)
Index Cond: (id = (max(records.id)))
Total runtime: 840.809 ms


(cost=0.00..23995.15 rows=1240315 width=8)
<- Still scanning all rows.

I tried with and without index on
(option_id)
,
(option_id, id)
,
(option_id, id desc)
, none of them had any effect on the query plan.


Is there a way of executing a groupwise maximum query in Postgres without scanning all rows?

What I am looking for, programmatically, is an index which stores the maximum id for each
option_id
as they are inserted into the records table. That way, when I query for maximums of option_ids, I should only need to scan index records as many times as there are different option_ids.

I've seen
select distinct on
answers all over SO from high ranking users (thanks to @Clodoaldo Neto for giving me keywords to search for). Here's why it doesn't work:

create index index_name on records(option_id, id desc)

select distinct on (option_id) *
from records
order by option_id, id desc
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=0.43..76053.10 rows=964 width=44) (actual time=0.049..1668.545 rows=1056 loops=1)
-> Index Scan using records_option_id_id_idx on records (cost=0.43..73337.25 rows=1086342 width=44) (actual time=0.046..1368.300 rows=1086342 loops=1)
Total runtime: 1668.817 ms


That's great, it's using an index. However using an index to scan all ids doesn't really make much sense. According to my executions, it is in fact slower than a simple sequential scan.

Interesting enough, MySQL 5.5 is able to optimize the query simply using an index on
records(option_id, id)


mysql> select count(1) from records;

+----------+
| count(1) |
+----------+
| 1086342 |
+----------+

1 row in set (0.00 sec)

mysql> explain extended select * from records
inner join ( select max(id) max_id from records group by option_id ) mr
on mr.max_id= records.id;

+------+----------+--------------------------+
| rows | filtered | Extra |
+------+----------+--------------------------+
| 1056 | 100.00 | |
| 1 | 100.00 | |
| 201 | 100.00 | Using index for group-by |
+------+----------+--------------------------+

3 rows in set, 1 warning (0.02 sec)

Answer

Assuming relatively few rows in options for many rows in records.

Typically, you would have a look-up table options that is referenced from records.option_id, ideally with a foreign key constraint. If you don't, I suggest to create one to enforce referential integrity:

CREATE TABLE options (
  option_id int  PRIMARY KEY
, option    text UNIQUE NOT NULL
);

INSERT INTO options
SELECT DISTINCT option_id, 'option' || option_id -- dummy option names
FROM   records;

Then we have no need to emulate a loose index scan any more and this becomes very simple and fast. Correlated subqueries can use a plain index on (option_id, id).

SELECT option_id
      ,(SELECT max(id)
        FROM   records
        WHERE  option_id = o.option_id
       ) AS max_id
FROM   options o
ORDER  BY 1;

This includes options with no match in table records. You get NULL for max_id, which can easily remove such rows in an outer SELECT if needed.

Or (same result):

SELECT option_id
     , (SELECT id
        FROM   records
        WHERE  option_id = o.option_id
        ORDER  BY id DESC NULLS LAST
       ) AS max_id
FROM   options o
ORDER  BY 1;

May be a bit faster. The subquery uses the sort order DESC NULLS LAST - same as the aggregate function max() which ignores NULL values. Sorting just DESC would have NULL first:

So, the perfect index for this:

CREATE INDEX on records (option_id, id DESC NULLS LAST);

Doesn't matter much while columns are defined NOT NULL.

There can still be a sequential scan on the small table options, that's just the fastest way to fetch all rows. The ORDER BY may bring in an index (only) scan to fetch pre-sorted rows.
The big table records is only accessed via (bitmap) index scan - or, if possible, index-only scan.

SQL Fiddle showing two index-only scans for the simple case.

Or use LATERAL joins for a similar effect in Postgres 9.3+:

Comments