CODEWITHSUNDEEP
postgresql
benmmurphy
benmmurphy

Reputation: 2505

Forcing Postgresql to use Merge Append

Say I have the following tables and indices:

 create table inbound_messages(id int, user_id int, received_at timestamp);
 create table outbound_messages(id int, user_id int, sent_at timestamp);
 create index on inbound_messages(user_id, received_at);
 create index on outbound_messages(user_id, sent_at);

Now I want to pull out the last 20 messages for a user, either inbound or outbound in a specific time range. I can do the following and from the explain it looks like PG walks back both indices in 'parallel' so it minimises the amount of rows it needs to scan.

explain select * from (select id, user_id, received_at as time from inbound_messages union all select id, user_id, sent_at as time from outbound_messages) x where user_id = 5 and time between '2018-01-01' and '2020-01-01' order by user_id,time desc limit 20;

 Limit  (cost=0.32..16.37 rows=2 width=16)
   ->  Merge Append  (cost=0.32..16.37 rows=2 width=16)
         Sort Key: inbound_messages.received_at DESC
         ->  Index Scan Backward using inbound_messages_user_id_received_at_idx on inbound_messages  (cost=0.15..8.17 rows=1 width=16)
               Index Cond: ((user_id = 5) AND (received_at >= '2018-01-01 00:00:00'::timestamp without time zone) AND (received_at <= '2020-01-01 00:00:00'::timestamp without time zone))
         ->  Index Scan Backward using outbound_messages_user_id_sent_at_idx on outbound_messages  (cost=0.15..8.17 rows=1 width=16)
               Index Cond: ((user_id = 5) AND (sent_at >= '2018-01-01 00:00:00'::timestamp without time zone) AND (sent_at <= '2020-01-01 00:00:00'::timestamp without time zone))

For example it could do something crazy like find all the matching rows in memory, and then sort the rows. Lets say there were millions of matching rows then this could take a long time. But because it walks the indices in the same order we want the results in this is a fast operation. It looks like the 'Merge Append' operation is done lazily and it doesn't actually materialize all the matching rows.

Now we can see postgres supports this operation for two distinct tables, however is it possible to force Postgres to use this optimisation for a single table.

Lets say I wanted the last 20 inbound messages for user_id = 5 or user_id = 6.

explain select * from inbound_messages where user_id in (6,7) order by received_at desc limit 20;

Then we get a query plan that does a bitmap heap scan, and then does an in-memory sort. So if there are millions of messages that match then it will look at millions of rows even though theoretically it could use the same Merge trick to only look at a few rows.

 Limit  (cost=15.04..15.09 rows=18 width=16)
   ->  Sort  (cost=15.04..15.09 rows=18 width=16)
         Sort Key: received_at DESC
         ->  Bitmap Heap Scan on inbound_messages  (cost=4.44..14.67 rows=18 width=16)
               Recheck Cond: (user_id = ANY ('{6,7}'::integer[]))
               ->  Bitmap Index Scan on inbound_messages_user_id_received_at_idx  (cost=0.00..4.44 rows=18 width=0)
                     Index Cond: (user_id = ANY ('{6,7}'::integer[]))

We could think of just adding (received_at) as an index on the table and then it will do the same backwards scan. However, if we have a large number of users then we are missing out on a potentially large speedup because we are scanning lots of index entries that would not match the query.

Upvotes: 4

Views: 1060

Answers (1)

Kannan Muthukkaruppan
Kannan Muthukkaruppan

Reputation: 585

The following approach should work as a way of forcing Postgres to use the "merge append" plan when you are interested in most recent messages for two users from the same table.

[Note: I tested this on YugabyteDB (which is based on Postgres)- so I expect the same to apply to Postgres also.]

explain select * from (
           (select * from inbound_messages where user_id = 6 order by received_at DESC)
           union all
           (select * from inbound_messages where user_id = 7 order by received_at DESC)
        ) AS result order by received_at DESC limit 20;

which produces:

-------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.01..3.88 rows=20 width=16)
   ->  Merge Append  (cost=0.01..38.71 rows=200 width=16)
         Sort Key: inbound_messages.received_at DESC
         ->  Index Scan Backward using inbound_messages_user_id_received_at_idx on inbound_messages  (cost=0.00..17.35 rows=100 width=16)
               Index Cond: (user_id = 6)
         ->  Index Scan Backward using inbound_messages_user_id_received_at_idx on inbound_messages inbound_messages_1  (cost=0.00..17.35 rows=100 width=16)
               Index Cond: (user_id = 7)

Upvotes: 3

Related Questions