1

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

1
  • Have you tried changing the order of your primary key to be (brand,id)?
    – user212533
    Jan 23, 2021 at 16:35

1 Answer 1

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);
2
  • Hello @Lauren Albe, thanks for your reply. In book about Postgres I have read that I should always favorize single column indices over multiple ones so I was not even consider to create those since id, brand has indices created thanks to PRIMARY KEY and timestamps is obviously created separately. Are my asumptions regarding indices wrong? Jan 24, 2021 at 20:49
  • Yes, your assumptions regarding indexes are wrong. If you want a good book about indexes, read this one. Of course, sometimes it is better to use single-column indexes. That is typically a trade-off between having the best possible index and having indexes that are good enough, but more universally useful. You don't want to have too many indexes. Since I don't know what other queries you need to support on the table, I gave you the best possible indexes. Jan 25, 2021 at 7:47

Your Answer

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

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