Slow query / wrong query plan for SORT BY LIMIT LEFT JOIN

Question

I have a following 3 tables a,b,c all with compound unique key (application_id, tid) however all those tables are not related with foreign key (it's a limitation of our solution). All tables has indices for (application_id, tid) and timestamp columns.

My current problem is strange query times with listing sorted by timestamp. When I am asking for table a and left joining with b my query time is quite poor (see query and query plan below) but when left joining with c query is fast as expected (see next)

Joining b:

SELECT a.application_id, a.timestamp, b.dua, b.dpr
FROM applications AS a
         LEFT JOIN features AS b ON b.application_id = a.application_id AND b.tid = a.tid
WHERE a.tid = '00010-1'
ORDER BY a.timestamp DESC, a.application_id DESC

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                                                                                                      |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|Limit  (cost=187051.77..187051.82 rows=21 width=127) (actual time=4579.007..4579.017 rows=21 loops=1)                                                                                                           |
|  Output: i.application_id, i.timestamp, b.dua, b.dpr                                                                                                                                     |
|  ->  Sort  (cost=187051.77..187542.06 rows=196115 width=127) (actual time=4579.006..4579.012 rows=21 loops=1)                                                                                                  |
|        Output: i.application_id, i.timestamp, b.dua, b.dpr                                                                                                                               |
|        Sort Key: i.t DESC, i.application_id DESC                                                                                                                                                              |
|        Sort Method: top-N heapsort  Memory: 28kB                                                                                                                                                               |
|        ->  Hash Right Join  (cost=45786.40..181764.20 rows=196115 width=127) (actual time=313.709..4503.010 rows=195204 loops=1)                                                                               |
|              Output: i.application_id, i.timestamp, b.dua, b.dpr                                                                                                                         |
|              Hash Cond: ((b.tid = i.tid ) AND (b.application_id = i.application_id))                                                                                                                |
|              ->  Bitmap Heap Scan on public.b  (cost=14548.92..139604.43 rows=180366 width=122) (actual time=95.169..1133.541 rows=181194 loops=1)                                                    |
|                    Output: b.dua, b.dpr, b.application_id, b.tid                                                                                                                  |
|                    Recheck Cond: (b.tid = '00010-1'::text)                                                                                                                                                  |
|                    Rows Removed by Index Recheck: 58154                                                                                                                                                        |
|                    Heap Blocks: exact=33962 lossy=53026                                                                                                                                                        |
|                    ->  Bitmap Index Scan on b_pkey  (cost=0.00..14503.83 rows=180366 width=0) (actual time=85.135..85.136 rows=181207 loops=1)                                                          |
|                          Index Cond: (b.tid = '00010-1'::text)                                                                                                                                              |
|              ->  Hash  (cost=26379.75..26379.75 rows=196115 width=51) (actual time=218.276..218.276 rows=195204 loops=1)                                                                                       |
|                    Output: i.application_id, i.timestamp, i.tid                                                                                                                                           |
|                    Buckets: 65536  Batches: 8  Memory Usage: 2692kB                                                                                                                                            |
|                    ->  Bitmap Heap Scan on public.a i  (cost=14184.31..26379.75 rows=196115 width=51) (actual time=46.996..137.642 rows=195204 loops=1)                                     |
|                          Output: i.application_id, i.timestamp, i.tid|
|                          Recheck Cond: (i.tid = '00010-1'::text)                                                                                                                                 |
|                          Heap Blocks: exact=9724                                                                                                                                                               |
|                          ->  Bitmap Index Scan on "a_idx"  (cost=0.00..14135.28 rows=196115 width=0) (actual time=45.295..45.295 rows=222169 loops=1)|
|                                Index Cond: (i.tid = '00010-1'::text)                                                                                                                             |
|Planning time: 0.845 ms                                                                                                                                                                                         |
|Execution time: 4579.093 ms                                                                                                                                                                                     |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Joining c:

SELECT a.application_id, a.timestamp
     , c.fs , c.pds
FROM a
         LEFT JOIN c ON a.application_id = c.application_id AND a.tid = c.tid
WHERE a.tid = '00010-1'
ORDER BY a.timestamp DESC, a.application_id DESC
LIMIT 21;


+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                                                                                                      |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|Limit  (cost=89302.01..89302.07 rows=21 width=53) (actual time=714.657..714.669 rows=21 loops=1)                                                                                                                |
|  Output: i.application_id, i.t, c.fs, c.pds                                                                                                                                              |
|  ->  Sort  (cost=89302.01..89792.30 rows=196115 width=53) (actual time=714.656..714.660 rows=21 loops=1)                                                                                                       |
|        Output: i.application_id, i.timestamp, c.fs, c.pds                                                                                                                                        |
|        Sort Key: i.t DESC, i.application_id DESC                                                                                                                                                              |
|        Sort Method: top-N heapsort  Memory: 27kB                                                                                                                                                               |
|        ->  Hash Right Join  (cost=62593.93..84014.44 rows=196115 width=53) (actual time=344.028..674.053 rows=195208 loops=1)                                                                                  |
|              Output: i.application_id, i.t, c.fs, c.pds                                                                                                                                  |
|              Hash Cond: ((c.tid = i.tid) AND (c.application_id = i.application_id))                                                                                                                |
|              ->  Bitmap Heap Scan on public.c c  (cost=31356.46..44628.14 rows=181655 width=57) (actual time=99.070..192.647 rows=181196 loops=1)                                                 |
|                    Output: c.fs, c.pds, c.application_id, c.tid                                                                                                                           |
|                    Recheck Cond: (c.tid = '00010-1'::text)                                                                                                                                                  |
|                    Heap Blocks: exact=5373                                                                                                                                                                     |
|                    ->  Bitmap Index Scan on c_pkey  (cost=0.00..31311.04 rows=181655 width=0) (actual time=97.912..97.912 rows=181196 loops=1)                                                    |
|                          Index Cond: (c.tid = '00010-1'::text)                                                                                                                                              |
|              ->  Hash  (cost=26379.75..26379.75 rows=196115 width=51) (actual time=244.532..244.532 rows=195208 loops=1)                                                                                       |
|                    Output: i.application_id, i.timestamp, i.tid
|                    Buckets: 65536  Batches: 8  Memory Usage: 2693kB                                                                                                                                            |
|                    ->  Bitmap Heap Scan on public.a i  (cost=14184.31..26379.75 rows=196115 width=51) (actual time=52.118..155.189 rows=195208 loops=1)                                     |
|                          Output: i.application_id, i.timestamp, i.tid                                                                                                                                     |
|                          Recheck Cond: (i.tid = '00010-1'::text)                                                                                                                                 |
|                          Heap Blocks: exact=9724                                                                                                                                                               |
|                          ->  Bitmap Index Scan on "a_idx"  (cost=0.00..14135.28 rows=196115 width=0) (actual time=50.129..50.129 rows=222173 loops=1)|
|                                Index Cond: (i.tid = '00010-1'::text)                                                                                                                             |
|Planning time: 0.346 ms                                                                                                                                                                                         |
|Execution time: 714.749 ms                                                                                                                                                                                      |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Both tables B and C has relatively same # of rows (300k) but their performance is quite different. What I figure out from query plan the reason to blame is Sequential scanning of B table but I can't understand why query plan doesn't resolve A first (will end with 21 rows) and then try to left join the rest (rows from C or B).

Can you please advise any tunning parameter I can change to improve first query? Or hint me how to rewrite query to benefit from SORT and LIMIT? So far I have discovered that If I provide any other condition for table a.

Thanks in advance for any help

UPDATE(s): Query and query plans has been obfuscated due to my company's policy and table a is alias so in query plan it's also referenced as i

Jan

Answer 1

If you had an index which could fetch the rows in order after applying the restriction, then it should automatically do the query the way you want. So

create index on applications (tid, timestamp, application_id)

If you don't want to build the specialized index, you could still write the query to get it to process "a" first using a CTE:

WITH t as (select * from applications where tid='00010-1'
ORDER BY a.timestamp DESC, a.application_id DESC LIMIT 21)  
SELECT a.application_id, a.timestamp, b.dua, b.dpr
FROM t AS a
LEFT JOIN features AS b ON b.application_id = a.application_id AND b.tid = a.tid
ORDER BY a.timestamp DESC, a.application_id DESC

Looking at the plans you already have, both the lossy blocks for the bitmap heap scan and the 8 batches for the hash join indicate your work_mem might be substantially too low for the queries you are doing. Also, the data for table B is substantially more scattered about than for table C (87,000 versus 5400 blocks, for about the same number of rows), although this is unlikely to fully explain the difference in timing.

Finally, 9.6 is pretty old (although still supported). There have been many performance improvements since then. If you spend a lot of time worrying about performance, you should plan to upgrade sooner rather than later.