Efficient query to get greatest value per group from big table

Question

Given the table:

    Column    |            Type             
 id           | integer                     
 latitude     | numeric(9,6)                
 longitude    | numeric(9,6)                
 speed        | integer                     
 equipment_id | integer                     
 created_at   | timestamp without time zone
Indexes:
    "geoposition_records_pkey" PRIMARY KEY, btree (id)

The table has 20 million records that is not, relatively speaking, a large number. But it makes sequential scans slow.

How can I get the last record (max(created_at)) of each equipment_id?

I've tried both the following queries, with several variants that I've read through many answers of this topic:

select max(created_at),equipment_id from geoposition_records group by equipment_id;

select distinct on (equipment_id) equipment_id,created_at 
  from geoposition_records order by equipment_id, created_at desc;

I have also tried creating btree indexes for equipment_id,created_at but Postgres finds that using a seqscan is faster. Forcing enable_seqscan = off is of no use either since reading the index is as slow as the seq scan, probably worse.

The query must run periodically returning always the last.

Using Postgres 9.3.

Explain/analyze (with 1.7 million records):

set enable_seqscan=true;
explain analyze select max(created_at),equipment_id from geoposition_records group by equipment_id;
"HashAggregate  (cost=47803.77..47804.34 rows=57 width=12) (actual time=1935.536..1935.556 rows=58 loops=1)"
"  ->  Seq Scan on geoposition_records  (cost=0.00..39544.51 rows=1651851 width=12) (actual time=0.029..494.296 rows=1651851 loops=1)"
"Total runtime: 1935.632 ms"

set enable_seqscan=false;
explain analyze select max(created_at),equipment_id from geoposition_records group by equipment_id;
"GroupAggregate  (cost=0.00..2995933.57 rows=57 width=12) (actual time=222.034..11305.073 rows=58 loops=1)"
"  ->  Index Scan using geoposition_records_equipment_id_created_at_idx on geoposition_records  (cost=0.00..2987673.75 rows=1651851 width=12) (actual time=0.062..10248.703 rows=1651851 loops=1)"
"Total runtime: 11305.161 ms"

Answer 1

Index

A plain multicolumn B-tree index should work after all:

CREATE INDEX foo_idx
ON geoposition_records (equipment_id, created_at DESC NULLS LAST);

Why DESC NULLS LAST?

• Unused index in range of dates query

It's safe to assume you have an equipment table? Then performance won't be a problem:

Correlated subquery

Based on this equipment table, run a lowly correlated subquery to great effect:

SELECT equipment_id
     , (SELECT created_at
        FROM   geoposition_records
        WHERE  equipment_id = eq.equipment_id
        ORDER  BY created_at DESC NULLS LAST
        LIMIT  1) AS latest
FROM   equipment eq;

For a small number of rows in the equipment table (57 judging from your EXPLAIN ANALYZE output), that's very fast.

LATERAL join in Postgres 9.3+

SELECT eq.equipment_id, r.latest
FROM   equipment eq
LEFT   JOIN LATERAL (
   SELECT created_at
   FROM   geoposition_records
   WHERE  equipment_id = eq.equipment_id
   ORDER  BY created_at DESC NULLS LAST
   LIMIT  1
   ) r(latest) ON true;

Detailed explanation:

• Optimize GROUP BY query to retrieve latest record per user

Performance similar to the correlated subquery.

Function

If you can't talk sense into the query planner (which shouldn't occur), a function looping through the equipment table is certain to do the trick. Looking up one equipment_id at a time uses the index.

CREATE OR REPLACE FUNCTION f_latest_equip()
  RETURNS TABLE (equipment_id int, latest timestamp)
  LANGUAGE plpgsql STABLE AS
$func$
BEGIN
   FOR equipment_id IN
      SELECT e.equipment_id FROM equipment e ORDER BY 1
   LOOP
      SELECT g.created_at
      FROM   geoposition_records g
      WHERE  g.equipment_id = f_latest_equip.equipment_id
                           -- prepend function name to disambiguate
      ORDER  BY g.created_at DESC NULLS LAST
      LIMIT  1
      INTO   latest;

      RETURN NEXT;
   END LOOP;
END  
$func$;

Makes for a nice call, too:

SELECT * FROM f_latest_equip();

Performance comparison:

db<>fiddle here
_{Old sqlfiddle}

Answer 2

Attempt 1

If

1. I have a separate equipment table, and
2. I have an index on geoposition_records(equipment_id, created_at desc)

then the following works for me:

select id as equipment_id, (select max(created_at)
                            from geoposition_records
                            where equipment_id = equipment.id
                           ) as max_created_at
from equipment;

I wasn't able to force PG to do a fast query to determine both the list of equipment_ids and the related max(created_at). But I'm going to try again tomorrow!

Attempt 2

I found this link: http://zogovic.com/post/44856908222/optimizing-postgresql-query-for-distinct-values Combining this technique with my query from attempt 1, I get:

WITH RECURSIVE equipment(id) AS (
    SELECT MIN(equipment_id) FROM geoposition_records
  UNION
    SELECT (
      SELECT equipment_id
      FROM geoposition_records
      WHERE equipment_id > equipment.id
      ORDER BY equipment_id
      LIMIT 1
    )
    FROM equipment WHERE id IS NOT NULL
)
SELECT id AS equipment_id, (SELECT MAX(created_at)
                            FROM geoposition_records
                            WHERE equipment_id = equipment.id
                           ) AS max_created_at
FROM equipment;

and this works FAST! But you need

1. this ultra-contorted query form, and
2. an index on geoposition_records(equipment_id, created_at desc).

Answer 3

Decided to write an answer. The simplest solution I could find is:

    SELECT
        * 
    FROM
        geoposition_records 
    WHERE
        NOT EXISTS (
            SELECT
                1 
            from
                geoposition_records rg 
            WHERE
                geoposition_records.equipment_id = equipment_id 
                AND  geoposition_records.created_at < created_at
        )

For my application it seems to be efficient because previously some complicated JOIN was used and queries took tens of seconds while with this approach They completed subjectively immediately. Didn't do a formal benchmark.

I wonder though if there has been done any comparison of the different greatest value per group approaches available against different databases and table structures.

Credits to https://stackoverflow.com/a/25694562/520567

Answer 4

equipment_id, created_at is the secondary index you need for this.

(equipment_id, created_at, id would be identical, as the primary key is always included implicitly.)

Then, create groups of the equipment_ids, and use a dependent subquery to get the latest row for each group.

SELECT r.*

-- Step 1: Start by obtaining the groupwise maximums
FROM
(
    SELECT (
        -- Step 1b: Find the ID of the group maximum by seeking in the new index
        SELECT id
        FROM geoposition_records
        WHERE r.equipment_id = r.groups.equipment_id
        ORDER BY r.equipment_id DESC, r.created_at DESC, r.id DESC
        LIMIT 1
    ) AS id

    -- Step 1a: Find the groups by seeking through the new index
    FROM geoposition_records AS groups
    GROUP BY groups.equipment_id
) AS maxes

-- Step 2: For each group, join the max row by ID
-- This neatly separates any potential followup logic from the groupwise-max tactics
INNER JOIN geoposition_records r ON r.id = maxes.id
;

Because this achieves efficiency using only basic building blocks, it is portable across most RDBMSes. Be sure to have the required index.

Why does this work [optimally]?

Imagine leafing through the physical phone book, finding the last entry for each town, i.e. the entry with that town's alphabetically greatest name. How would you do it?

You would start at the very end. The very last entry in the book is the group maximum of the last town. It is the first result row that you encounter.

For each subsequent desired result row, you would binary search backwards, to the next-greatest town. At the point where the current town transitions into its predecessor, there is the predecessor's last row (alphabetically greatest name), i.e. your next result row. Repeat until no more towns.

Loosely speaking, the phone book is like a secondary index on { Town, Name, PhoneNumber }, with PhoneNumber serving as the primary key. (I'm simplifying things for agument's sake, pretending phone numbers are assigned to one person and names form a single column.)

You are effectively doing a reverse seek through the index. By repeatedly jumping to the next town efficiently (thanks to binary search or a B-tree structure), the work is constrained by the number of result rows rather than the total number of rows. This is asymptotically optimal. And thanks to the reverse traversal direction, each town you encounter "starts" with its greatest row, your target. That is important: imagine the absurd amount of needless work if you'd have to scan all rows for a town.

Changing the solution to a groupwise-min is as trivial as changing the traversal direction, i.e. from DESC to ASC.