Execution plan favorize joins over sort

Question

recently I ran into an issue on our production server (Pg 9.6) and even though I found solution for my problem I would like to understand better the reason behind it. For easier explanation I am using dummy data and tables. Let's have following settings:

We have 2 tables a,b both with compound key and 1:1 relation (IF id+brand exists in b => it exists in a, not otherwise).

CREATE TABLE a (
    id text NOT NULL,
    brand text NOT NULL,
    timestamp BIGINT NOT NULL,
    PRIMARY KEY (id, brand)
);
CREATE TABLE b (
   id text NOT NULL,
   brand text NOT NULL,
   timestamp BIGINT NOT NULL,
   PRIMARY KEY (id, brand)
);

CREATE INDEX ON a (timestamp);
CREATE INDEX ON b (timestamp);

I ran into some performance problem in case when I am searching for latest rows with this query (please note that times from execution plans are synthetic, in real case it takes 8 seconds and more):

SELECT *
FROM a
LEFT JOIN b ON a.id = b.id AND a.brand = b.brand
WHERE a.brand = 'SA-00010-1'
ORDER BY a.timestamp DESC, a.id DESC
LIMIT 20 

+---------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                             |
+---------------------------------------------------------------------------------------------------------------------------------------+
|Limit  (cost=35161.94..35161.99 rows=20 width=143) (actual time=533.962..533.970 rows=20 loops=1)                                      |
|  Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                              |
|  ->  Sort  (cost=35161.94..35650.70 rows=195506 width=143) (actual time=533.960..533.961 rows=20 loops=1)                             |
|        Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                        |
|        Sort Key: a."timestamp" DESC, a.id DESC                                                                                        |
|        Sort Method: top-N heapsort  Memory: 30kB                                                                                      |
|        ->  Hash Right Join  (cost=13269.70..29959.59 rows=195506 width=143) (actual time=135.707..462.819 rows=195314 loops=1)        |
|              Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                  |
|              Hash Cond: ((b.brand = a.brand) AND (b.id = a.id))                                                                       |
|              ->  Seq Scan on public.b  (cost=0.00..8427.11 rows=196452 width=51) (actual time=0.019..100.077 rows=195314 loops=1)     |
|                    Output: b.id, b.brand, b."timestamp"                                                                               |
|                    Filter: (b.brand = 'SA-00010-1'::text)                                                                             |
|                    Rows Removed by Filter: 173495                                                                                     |
|              ->  Hash  (cost=8427.11..8427.11 rows=195506 width=51) (actual time=135.422..135.422 rows=195314 loops=1)                |
|                    Output: a.id, a.brand, a."timestamp"                                                                               |
|                    Buckets: 65536  Batches: 8  Memory Usage: 2814kB                                                                   |
|                    ->  Seq Scan on public.a  (cost=0.00..8427.11 rows=195506 width=51) (actual time=0.017..79.168 rows=195314 loops=1)|
|                          Output: a.id, a.brand, a."timestamp"                                                                         |
|                          Filter: (a.brand = 'SA-00010-1'::text)                                                                       |
|                          Rows Removed by Filter: 173495                                                                               |
|Planning time: 0.523 ms                                                                                                                |
|Execution time: 534.025 ms                                                                                                             |
+---------------------------------------------------------------------------------------------------------------------------------------+

The issue here is that DB is firstly joing a with b table (which in my real case scenario is somehow slow), sort the results and drop everything but first 20 rows. The case happens even when I am creating foreign key in table b which relates to a

The solution for my problem was solved with following query where I force DB to lookup those 20 rows from a first and then let DB join results with rows in b table

WITH a AS (
    SELECT a.id, a.brand, a.timestamp
    FROM a
    WHERE a.brand = 'SA-00010-1'
    ORDER BY a.timestamp DESC, a.id DESC
    LIMIT 20
)
SELECT *
FROM a
LEFT JOIN b ON a.id = b.id AND a.brand = b.brand
WHERE a.brand = 'SA-00010-1'
ORDER BY a.timestamp DESC, a.id DESC
LIMIT 20

+---------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                             |
+---------------------------------------------------------------------------------------------------------------------------------------+
|Limit  (cost=13638.42..13638.43 rows=1 width=163) (actual time=80.982..80.985 rows=20 loops=1)                                         |
|  Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                              |
|  CTE a                                                                                                                                |
|    ->  Limit  (cost=13629.46..13629.51 rows=20 width=51) (actual time=80.761..80.770 rows=20 loops=1)                                 |
|          Output: a_1.id, a_1.brand, a_1."timestamp"                                                                                   |
|          ->  Sort  (cost=13629.46..14118.22 rows=195506 width=51) (actual time=80.760..80.766 rows=20 loops=1)                        |
|                Output: a_1.id, a_1.brand, a_1."timestamp"                                                                             |
|                Sort Key: a_1."timestamp" DESC, a_1.id DESC                                                                            |
|                Sort Method: top-N heapsort  Memory: 27kB                                                                              |
|                ->  Seq Scan on public.a a_1  (cost=0.00..8427.11 rows=195506 width=51) (actual time=0.041..59.052 rows=195314 loops=1)|
|                      Output: a_1.id, a_1.brand, a_1."timestamp"                                                                       |
|                      Filter: (a_1.brand = 'SA-00010-1'::text)                                                                         |
|                      Rows Removed by Filter: 173495                                                                                   |
|  ->  Sort  (cost=8.91..8.92 rows=1 width=163) (actual time=80.982..80.983 rows=20 loops=1)                                            |
|        Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                        |
|        Sort Key: a."timestamp" DESC, a.id DESC                                                                                        |
|        Sort Method: quicksort  Memory: 30kB                                                                                           |
|        ->  Nested Loop Left Join  (cost=0.42..8.90 rows=1 width=163) (actual time=80.808..80.965 rows=20 loops=1)                     |
|              Output: a.id, a.brand, a."timestamp", b.id, b.brand, b."timestamp", a."timestamp", a.id                                  |
|              ->  CTE Scan on a  (cost=0.00..0.45 rows=1 width=72) (actual time=80.775..80.791 rows=20 loops=1)                        |
|                    Output: a.id, a.brand, a."timestamp"                                                                               |
|                    Filter: (a.brand = 'SA-00010-1'::text)                                                                             |
|              ->  Index Scan using b_pkey on public.b  (cost=0.42..8.44 rows=1 width=51) (actual time=0.008..0.008 rows=1 loops=20)    |
|                    Output: b.id, b.brand, b."timestamp"                                                                               |
|                    Index Cond: ((a.id = b.id) AND (a.brand = b.brand) AND (b.brand = 'SA-00010-1'::text))                             |
|Planning time: 0.265 ms                                                                                                                |
|Execution time: 81.038 ms                                                                                                              |
+---------------------------------------------------------------------------------------------------------------------------------------+

It may seem that first query is only a bit slower but in my real case it's 20x times and the problem cascades with multiple LEFT JOINs (SELECT * FROM a LEFT JOIN b LEFT JOIN c etc...). I know that leaving SORT as last in query execution makes sense because of LEFT JOINs but in this case favorize SORT and resolving a first brings huge speed-up.

One can argue that DB can't know the relation but existence of PRIMARY KEY (or FOREIGN KEY in my other tables) can hint Postgres that prefering sort would result in faster query...

So here lies my question. Is there any way how to advice DB to prefer sorting over joining for my first query? Did I overlook something with table structuring?

Thanks you for reading all this through and thank in advance for your hints Jan

Answer 1

You need indexes

• to support the WHERE condition and the ORDER BY clause on a
• on the join condition on b

Then you can get a fast nested loop join.

In your case, that would be

CREATE INDEX ON a (brand, timestamp, id);
CREATE INDEX ON b (id, brand);