2

I'm trying to speed up the following query in postgres:

select MAX(msg."timestamp") AS latestDate, msg.channel_id from message msg group by msg.channel_id

the explain is as such:

Finalize GroupAggregate  (cost=1000.63..2442779.42 rows=305 width=24)
  Group Key: channel_id
  ->  Gather Merge  (cost=1000.63..2442770.27 rows=1220 width=24)
        Workers Planned: 4
        ->  Partial GroupAggregate  (cost=0.57..2441624.90 rows=305 width=24)
              Group Key: channel_id
              ->  Parallel Index Only Scan using message_channel_id_timestamp on message msg  (cost=0.57..2243767.89 rows=39570792 width=24)
JIT:
  Functions: 6
  Options: Inlining true, Optimization true, Expressions true, Deforming true

The DDL for the table is as such:

CREATE TABLE public.message (
    message_pgid bigserial NOT NULL,
    id uuid NOT NULL,
    "timestamp" timestamptz NOT NULL,
    "content" text NOT NULL,
    channel_id uuid NOT NULL,
    CONSTRAINT message_pk PRIMARY KEY (message_pgid),
    CONSTRAINT message_un UNIQUE (channel_id, id)
);
CREATE INDEX message_channel_id_idx ON public.message USING btree (channel_id);
CREATE INDEX message_channel_id_timestamp ON public.message USING btree (channel_id, "timestamp");
CREATE INDEX message_id ON public.message USING btree (id);
CREATE INDEX message_timestamp_idx ON public.message USING btree ("timestamp");


-- public.message foreign keys
ALTER TABLE public.message ADD CONSTRAINT channel_fk FOREIGN KEY (channel_id) REFERENCES public.channel(id) DEFERRABLE;
ALTER TABLE public.message ADD CONSTRAINT message_fk FOREIGN KEY (user_id) REFERENCES public."user"(id);

and finally, the explain analyze:

Finalize GroupAggregate  (cost=1000.63..2442779.42 rows=305 width=24) (actual time=7631.501..7673.692 rows=597 loops=1)
  Group Key: channel_id
  ->  Gather Merge  (cost=1000.63..2442770.27 rows=1220 width=24) (actual time=7631.383..7673.511 rows=1667 loops=1)
        Workers Planned: 4
        Workers Launched: 4
        ->  Partial GroupAggregate  (cost=0.57..2441624.90 rows=305 width=24) (actual time=305.736..6125.479 rows=333 loops=5)
              Group Key: channel_id
              ->  Parallel Index Only Scan using message_channel_id_timestamp on message msg  (cost=0.57..2243767.89 rows=39570792 width=24) (actual time=0.557..4938.221 rows=31656633 loops=5)
                    Heap Fetches: 32082
Planning Time: 4.032 ms
JIT:
  Functions: 18
  Options: Inlining true, Optimization true, Expressions true, Deforming true
  Timing: Generation 12.315 ms, Inlining 193.685 ms, Optimization 122.739 ms, Emission 100.570 ms, Total 429.309 ms
Execution Time: 7684.655 ms  

As you can see, even with a btree index, the operation still takes 7.6 seconds, most of which is spent in the parallel index only scan. I'm kinda at a loss as to how to speed this up further. the index has a relative size of 5.7G, and I give my instance 6GB of ram, which should be more than enough for a btree max search. I've set my settings according to pgtune (https://pgtune.leopard.in.ua/).

Is there anything I'm missing on the face of things?

1 Answer 1

3

Unfortunately postgres does not implement (yet) the index scan type you need to optimize this query automatically, so it will scan the whole index.

It is capable of using an index on (a,b) to optimize "max(b) WHERE a=..." and also "WHERE a=... ORDER BY b DESC LIMIT 1" which returns the entire row with highest value of b (this can be more useful than just the max() if you actually want other columns). But that's just for one value of a, or several in a nested loop, not for the whole table as you're doing.

Assuming you have a separate table "channels" with primary key "channel_id" which is referenced by your table messages, it is easy to emulate this manually.

Postgres knows how to find the row you want using a index if you ask for only one value of channel_id. So the trick is to do that for each value of channel_id, using either a dependent subquery (if you only want the max() column) or a LATERAL join (if you also want other columns, like the contents of the latest message).

This results in an index scan on messages per value of channel_id. So the time is on O(number of channels * log(number of messages)) which should be muuuuch faster than scanning the whole messages table. In addition it only hits pages with the most recent messages, so it doesn't trash your cache.

Create test data:

CREATE UNLOGGED TABLE messages( ts INT NOT NULL, channel_id INT NOT NULL );
INSERT INTO messages SELECT n,n%1000 FROM generate_series(1,1000000) n;
CREATE INDEX ON messages( channel_id, ts );

CREATE UNLOGGED TABLE channels ( channel_id INT PRIMARY KEY );
INSERT INTO channels SELECT DISTINCT channel_id FROM messages;
VACUUM ANALYZE;

Slow queries which read the entire table (or index):

-- SLOW
EXPLAIN ANALYZE SELECT channel_id, max(ts) FROM messages GROUP BY channel_id;

 Finalize GroupAggregate  (cost=11734.85..11988.20 rows=1000 width=8) (actual time=58.321..60.128 rows=1000 loops=1)
   Group Key: channel_id
   ->  Gather Merge  (cost=11734.85..11968.20 rows=2000 width=8) (actual time=58.315..59.871 rows=3000 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Sort  (cost=10734.83..10737.33 rows=1000 width=8) (actual time=54.080..54.119 rows=1000 loops=3)
               Sort Key: channel_id
               Sort Method: quicksort  Memory: 56kB
               Worker 0:  Sort Method: quicksort  Memory: 56kB
               Worker 1:  Sort Method: quicksort  Memory: 56kB
               ->  Partial HashAggregate  (cost=10675.00..10685.00 rows=1000 width=8) (actual time=53.872..53.958 rows=1000 loops=3)
                     Group Key: channel_id
                     Batches: 1  Memory Usage: 129kB
                     Worker 0:  Batches: 1  Memory Usage: 129kB
                     Worker 1:  Batches: 1  Memory Usage: 129kB
                     ->  Parallel Seq Scan on messages  (cost=0.00..8591.67 rows=416667 width=8) (actual time=0.009..16.164 rows=333333 loops=3)
 Planning Time: 0.167 ms
 Execution Time: 60.236 ms

-- SLOW
EXPLAIN ANALYZE SELECT channel_id, max(ts) 
FROM channels JOIN messages USING (channel_id)
GROUP BY channel_id;

 Finalize GroupAggregate  (cost=12860.74..13114.09 rows=1000 width=8) (actual time=94.136..96.019 rows=1000 loops=1)
   Group Key: channels.channel_id
   ->  Gather Merge  (cost=12860.74..13094.09 rows=2000 width=8) (actual time=94.131..95.758 rows=3000 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Sort  (cost=11860.72..11863.22 rows=1000 width=8) (actual time=92.507..92.542 rows=1000 loops=3)
               Sort Key: channels.channel_id
               Sort Method: quicksort  Memory: 56kB
               Worker 0:  Sort Method: quicksort  Memory: 56kB
               Worker 1:  Sort Method: quicksort  Memory: 56kB
               ->  Partial HashAggregate  (cost=11800.89..11810.89 rows=1000 width=8) (actual time=92.299..92.386 rows=1000 loops=3)
                     Group Key: channels.channel_id
                     Batches: 1  Memory Usage: 129kB
                     Worker 0:  Batches: 1  Memory Usage: 129kB
                     Worker 1:  Batches: 1  Memory Usage: 129kB
                     ->  Hash Join  (cost=27.50..9717.56 rows=416667 width=8) (actual time=0.154..58.426 rows=333333 loops=3)
                           Hash Cond: (messages.channel_id = channels.channel_id)
                           ->  Parallel Seq Scan on messages  (cost=0.00..8591.67 rows=416667 width=8) (actual time=0.004..16.329 rows=333333 loops=3)
                           ->  Hash  (cost=15.00..15.00 rows=1000 width=4) (actual time=0.143..0.143 rows=1000 loops=3)
                                 Buckets: 1024  Batches: 1  Memory Usage: 44kB
                                 ->  Seq Scan on channels  (cost=0.00..15.00 rows=1000 width=4) (actual time=0.006..0.060 rows=1000 loops=3)
 Planning Time: 0.127 ms
 Execution Time: 96.066 ms

Much faster query that finds the latest row for each channel_id immediately using the index, using a dependent subquery which selects max(ts):

-- FAST
EXPLAIN ANALYZE SELECT channel_id, 
(SELECT max(ts) FROM messages m WHERE m.channel_id=c.channel_id) 
FROM channels c;

 Seq Scan on channels c  (cost=0.00..482.00 rows=1000 width=8) (actual time=0.023..7.308 rows=1000 loops=1)
   SubPlan 2
     ->  Result  (cost=0.46..0.47 rows=1 width=4) (actual time=0.007..0.007 rows=1 loops=1000)
           InitPlan 1 (returns $1)
             ->  Limit  (cost=0.42..0.46 rows=1 width=4) (actual time=0.007..0.007 rows=1 loops=1000)
                   ->  Index Only Scan using messages_channel_id_ts_idx on messages m  (cost=0.42..32.42 rows=1000 width=4) (actual time=0.007..0.007 rows=1 loops=1000)
                         Index Cond: ((channel_id = c.channel_id) AND (ts IS NOT NULL))
                         Heap Fetches: 0
 Planning Time: 0.072 ms
 Execution Time: 7.349 ms

Variant using LATERAL which has the following advantages: can return more columns from message in case you need them, and can return the latest or N latest messages (just change the LIMIT) per channel.

EXPLAIN ANALYZE SELECT * FROM channels c
LEFT JOIN LATERAL (
 SELECT * FROM messages m WHERE m.channel_id=c.channel_id
 ORDER BY ts DESC LIMIT 1) USING(channel_id);


 Nested Loop Left Join  (cost=0.42..492.00 rows=1000 width=8) (actual time=0.085..10.320 rows=1000 loops=1)
   ->  Seq Scan on channels c  (cost=0.00..15.00 rows=1000 width=4) (actual time=0.019..0.109 rows=1000 loops=1)
   ->  Subquery Scan on unnamed_subquery  (cost=0.42..0.47 rows=1 width=8) (actual time=0.010..0.010 rows=1 loops=1000)
         Filter: (c.channel_id = unnamed_subquery.channel_id)
         ->  Limit  (cost=0.42..0.45 rows=1 width=8) (actual time=0.010..0.010 rows=1 loops=1000)
               ->  Index Only Scan using messages_channel_id_ts_idx on messages m  (cost=0.42..29.93 rows=1000 width=8) (actual time=0.009..0.009 rows=1 loops=1000)
                     Index Cond: (channel_id = c.channel_id)
                     Heap Fetches: 0
 Planning Time: 0.313 ms
 Execution Time: 10.411 ms

LATERAL JOIN syntax is a bit weird. If you want a row for a channel_id which has no messages, you need to use LEFT JOIN, and that requires a join condition (USING(channel_id)). But because it's a LATERAL JOIN, the right table in the join is dependent on the left row, so this condition is already specified in it. So there's a bit of duplication.

8
  • Wait so if I'm following correctly, even though the index is a btree, my query will still go through the entire thing?!
    – tuskiomi
    Dec 23, 2023 at 16:06
  • 1
    Yes, "index only scan" in your query means it's reading only the index, not the table. If the index has all the columns you need (this is the case here) it's faster to read the index instead of the table, which is much larger due to all the other columns... But it reads the entire index! (see rows=39570792 in explain analyze, and there's no "Index Cond" mentioned). Still faster than reading the whole table, but well.
    – bobflux
    Dec 23, 2023 at 16:34
  • With the last 2 queries in my answer it will actually use the index for... well, for indexing lol. Since you have ~300 channel_id's it should not take more than a few milliseconds.
    – bobflux
    Dec 23, 2023 at 16:37
  • 1
    Pretty much. First, the index contains all the information needed to extract the list of distinct keys without reading it all, just by skipping from one key to the next. But that's not implemented, so it has to read it all to get the list of keys. Solution to that first problem is is to pull the list of keys from another table. Even if that feature was implemented it would still be slower than just reading the small "channels" table which already has everything needed.
    – bobflux
    Dec 23, 2023 at 17:48
  • 1
    Second problem, it can use the index to find the last ts for ONE key. But to find the last ts for the whole list of keys, it can't use an indexed search. So you have to make a query that gets it for ONE key (uses index), in a loop (lateral join), so it gets all keys. LATERAL is also a convenient way to get the whole row with the latest message, if you need it, which max() won't do. You could also use DISTINCT ON but it reads the whole index too, doesn't use it for searching, so it would be slow. Nice speedup btw!
    – bobflux
    Dec 23, 2023 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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