Increased LIMIT results in performance degradation

Question

This appears to be a variation of a common problem where a small change to the LIMIT clause in a query changes the query plan to one that has vastly inferior performance. In this case, I have two tables in a PostgreSQL 13 database:

1. assets that has ~140 rows;
2. asset_data that has ~141 million rows.

My query is as follows:

SELECT
    a.dp as dp,
    a.at as at,
    a.dt as dt,
    a.it as it,
    a.ai as ai,
    ad.idt as idt,
    ad.data as data
FROM assets a
JOIN asset_data ad ON a.id = ad.asset_id_fk
WHERE 
    a.dp = 'kr' 
    AND a.at = 'fr' 
    AND a.dt = 'oh' 
    AND a.it = '1m' 
    AND a.ai = 'st'
ORDER BY idt desc
LIMIT 8000

There is an index on idt.

When the limit is 8000 it simply uses the idt index to do the sorting; when the limit 9000 it performs the sorting after the join.

The net performance goes from 3 seconds to almost 12 minutes.

After reading a few of these types of questions I tried a VACUUM ANALYZE and that changed the query plan but not in any way that mattered.

Updates:

1. I have also tried setting the statistics for the idt and asset_id_fk columns to be 1000 but that didn't work and it's not obvious to me that it should have worked.

2. idt is not unique on its own

3. idt + asset_id_fk is unique and has a corresponding constraint

4. Only one row is returned from the assets table

5. There is an index on the combination of asset_id_fk and idt

6. There is an index on idt alone

Any advice on the appropriate way to fix this?

CREATE TABLE statement:

CREATE TABLE IF NOT EXISTS public.asset_data
(
    id integer NOT NULL GENERATED BY DEFAULT AS IDENTITY ( INCREMENT 1 START 1 MINVALUE 1 MAXVALUE 2147483647 CACHE 1 ),
    dp character varying(40) COLLATE pg_catalog."default",
    at character varying(40) COLLATE pg_catalog."default",
    it character varying(10) COLLATE pg_catalog."default",
    ai character varying(40) COLLATE pg_catalog."default",
    idt timestamp without time zone NOT NULL,
    data jsonb NOT NULL,
    inserted timestamp without time zone DEFAULT now(),
    updated timestamp without time zone DEFAULT now(),
    dt character varying(20) COLLATE pg_catalog."default",
    asset_id_fk integer NOT NULL DEFAULT 1,
    CONSTRAINT asset_data_pkey PRIMARY KEY (id),
    CONSTRAINT asset_data_1_idx UNIQUE (dp, at, it, idt, dt, ai),
    CONSTRAINT idx_asset_data_2_unique UNIQUE (asset_id_fk, idt)
)

CREATE INDEX IF NOT EXISTS asset_data_it_aif_idx
    ON public.asset_data (idt, asset_id_fk);

CREATE INDEX IF NOT EXISTS idx_asset_data_asset_fk
    ON public.asset_data (asset_id_fk);

CREATE INDEX IF NOT EXISTS idx_asset_data_asset_fk_idt_index
    ON public.asset_data (asset_id_fk, idt);

CREATE INDEX IF NOT EXISTS idx_asset_data_idt_idx
    ON public.asset_data (idt);

EXPLAIN ANALYZE with limit of 8000:

Limit  (cost=0.57..4170458.87 rows=8000 width=173) (actual time=0.160..3677.025 rows=8000 loops=1)
  Buffers: shared hit=61448 read=14657 dirtied=756
  ->  Nested Loop  (cost=0.57..507975375.06 rows=974426 width=173) (actual time=0.159..3675.290 rows=8000 loops=1)
        Join Filter: (a.id = ad.asset_id_fk)
        Rows Removed by Join Filter: 474053
        Buffers: shared hit=61448 read=14657 dirtied=756
        ->  Index Scan Backward using idx_asset_data_idt_idx on asset_data ad  (cost=0.57..505855992.43 rows=141291824 width=146) (actual time=0.051..3437.070 rows=482053 loops=1)
              Buffers: shared hit=61446 read=14657 dirtied=756
        ->  Materialize  (cost=0.00..5.27 rows=1 width=35) (actual time=0.000..0.000 rows=1 loops=482053)
              Buffers: shared hit=2
              ->  Seq Scan on assets a  (cost=0.00..5.26 rows=1 width=35) (actual time=0.052..0.067 rows=1 loops=1)
                    Filter: (((dp)::text = 'kr'::text) AND ((at)::text = 'fr'::text) AND ((dt)::text = 'oh'::text) AND ((it)::text = '1m'::text) AND ((ai)::text = 'st'::text))
                    Rows Removed by Filter: 144
                    Buffers: shared hit=2
Settings: effective_cache_size = '1507160kB'
Planning:
  Buffers: shared hit=4
Planning Time: 0.445 ms
Execution Time: 3679.005 ms

EXPLAIN ANALYZE with limit of 9000:

Limit  (cost=4269756.79..4269779.29 rows=9000 width=173) (actual time=700091.606..700094.588 rows=9000 loops=1)
  Buffers: shared hit=133 read=1538340, temp read=74205 written=112013
  ->  Sort  (cost=4269756.79..4272192.85 rows=974426 width=173) (actual time=700091.604..700093.738 rows=9000 loops=1)
        Sort Key: ad.idt DESC
        Sort Method: external merge  Disk: 304680kB
        Buffers: shared hit=133 read=1538340, temp read=74205 written=112013
        ->  Nested Loop  (cost=0.57..4200885.77 rows=974426 width=173) (actual time=1.190..693283.441 rows=1687735 loops=1)
              Buffers: shared hit=133 read=1538340
              ->  Seq Scan on assets a  (cost=0.00..5.26 rows=1 width=35) (actual time=0.032..0.050 rows=1 loops=1)
                    Filter: (((dp)::text = 'kr'::text) AND ((at)::text = 'fr'::text) AND ((dt)::text = 'oh'::text) AND ((it)::text = '1m'::text) AND ((ai)::text = 'st'::text))
                    Rows Removed by Filter: 144
                    Buffers: shared hit=2
              ->  Index Scan using idx_asset_data_asset_fk on asset_data ad  (cost=0.57..4190011.91 rows=1086860 width=146) (actual time=1.151..691172.001 rows=1687735 loops=1)
                    Index Cond: (asset_id_fk = a.id)
                    Buffers: shared hit=131 read=1538340
Settings: effective_cache_size = '1507160kB'
Planning:
  Buffers: shared hit=4
Planning Time: 0.317 ms
Execution Time: 700245.659 ms

Update 2:

After switching to the following query:

SELECT a.dp, a.at, a.dt, a.it, a.ai, ad.idt, ad.data
FROM  (
   SELECT a.id, a.dp, a.at, a.dt, a.it, a.ai
   FROM   assets a
   WHERE  a.dp = 'kr' 
   AND    a.at = 'fr' 
   AND    a.dt = 'oh' 
   AND    a.it = '1m' 
   AND    a.ai = 'st'
   LIMIT  1  -- make sure the planner understands
   ) a
JOIN   asset_data ad ON ad.asset_id_fk = a.id
ORDER  BY ad.idt DESC
LIMIT  8000;

The only difference is that the query plan switches between 9000 and 10000:

Limit  (cost=0.57..4206410.37 rows=9000 width=173) (actual time=0.139..432.265 rows=9000 loops=1)
  Buffers: shared hit=82159
  ->  Nested Loop  (cost=0.57..507975395.07 rows=1086860 width=173) (actual time=0.138..431.358 rows=9000 loops=1)
        Join Filter: (a.id = ad.asset_id_fk)
        Rows Removed by Join Filter: 533354
        Buffers: shared hit=82159
        ->  Index Scan Backward using idx_asset_data_idt_idx on asset_data ad  (cost=0.57..505856012.43 rows=141291824 width=146) (actual time=0.049..164.873 rows=542354 loops=1)
              Buffers: shared hit=82158
        ->  Materialize  (cost=0.00..5.28 rows=1 width=35) (actual time=0.000..0.000 rows=1 loops=542354)
              Buffers: shared hit=1
              ->  Subquery Scan on a  (cost=0.00..5.27 rows=1 width=35) (actual time=0.032..0.035 rows=1 loops=1)
                    Buffers: shared hit=1
                    ->  Limit  (cost=0.00..5.26 rows=1 width=35) (actual time=0.032..0.033 rows=1 loops=1)
                          Buffers: shared hit=1
                          ->  Seq Scan on assets a_1  (cost=0.00..5.26 rows=1 width=35) (actual time=0.031..0.032 rows=1 loops=1)
                                Filter: (((dp)::text = 'kr'::text) AND ((at)::text = 'fr'::text) AND ((dt)::text = 'oh'::text) AND ((it)::text = '1m'::text) AND ((ai)::text = 'st'::text))
                                Rows Removed by Filter: 96
                                Buffers: shared hit=1
Settings: effective_cache_size = '1507160kB'
Planning Time: 0.322 ms
Execution Time: 432.904 ms

Limit  (cost=4278529.50..4278554.50 rows=10000 width=173) (actual time=702389.569..702392.909 rows=10000 loops=1)
  Buffers: shared hit=350 read=1538221, temp read=74241 written=112019
  ->  Sort  (cost=4278529.50..4281246.65 rows=1086860 width=173) (actual time=702389.568..702392.118 rows=10000 loops=1)
        Sort Key: ad.idt DESC
        Sort Method: external merge  Disk: 304704kB
        Buffers: shared hit=350 read=1538221, temp read=74241 written=112019
        ->  Nested Loop  (cost=0.57..4200885.78 rows=1086860 width=173) (actual time=1.267..695545.975 rows=1687836 loops=1)
              Buffers: shared hit=350 read=1538221
              ->  Limit  (cost=0.00..5.26 rows=1 width=35) (actual time=0.071..0.074 rows=1 loops=1)
                    Buffers: shared hit=1
                    ->  Seq Scan on assets a  (cost=0.00..5.26 rows=1 width=35) (actual time=0.071..0.071 rows=1 loops=1)
                          Filter: (((dp)::text = 'kr'::text) AND ((at)::text = 'fr'::text) AND ((dt)::text = 'oh'::text) AND ((it)::text = '1m'::text) AND ((ai)::text = 'st'::text))
                          Rows Removed by Filter: 96
                          Buffers: shared hit=1
              ->  Index Scan using idx_asset_data_asset_fk on asset_data ad  (cost=0.57..4190011.91 rows=1086860 width=146) (actual time=1.190..693414.817 rows=1687836 loops=1)
                    Index Cond: (asset_id_fk = a.id)
                    Buffers: shared hit=349 read=1538221
Settings: effective_cache_size = '1507160kB'
Planning Time: 0.301 ms
Execution Time: 702526.728 ms

Answer 1

Looking at an excerpt from your first plan:

->  Index Scan Backward using idx_asset_data_idt_idx on asset_data ad  (cost=0.57..505855992.43 rows=141291824 width=146) (actual time=0.051..3437.070 rows=482053 loops=1)
    Buffers: shared hit=61446 read=14657 dirtied=756

It read 482053/(61446+14657) = 6.33 rows per buffer access. But its cost estimate was 505855992.43/141291824 = 3.58 per row, which is only slightly less than the default value of 4 for random_page_cost. So it it thought it was only going to find about 1 row per buffer. This problem doesn't explain the entirety of the poor cost estimate, but certainly explains enough of it to be highly important.

This suggests that your physical row ordering is moderately correlated on the idt column but that the planner does not know that. What is the value of pg_stats.correlation for that column? Does it seem like an accurate estimate? Maybe the degree of correlation differs over different parts of the table, so that it can't get an estimate which is accurate overall. In that case, partitioning might be helpful, or just running CLUSTER on the table.

Answer 2

Whatever else you do, create a multicolumn index on asset_data:

CREATE INDEX asset_data_asset_id_fk_idt_idx ON asset_data(asset_id_fk, idt DESC);

You later disclosed an index on (asset_id_fk, idt), which is good, but my index with matching sort order is better. Consider replacing idx_asset_data_asset_fk_idt_index with my index. You typically don't need idx_asset_data_asset_fk additionally, either. See:

• Is a composite index also good for queries on the first field?

Just like asset_data_it_aif_idx already covers most everything that idx_asset_data_idt_idx can bring to the table.

If asset_data.data is a narrow column, it can pay to INCLUDE the column in the index to allow index-only scans - but not for a big JSON column like you disclosed:

CREATE INDEX asset_data_incl_idx ON asset_data(asset_id_fk, idt DESC) INCLUDE (data);

Since you know that only a single asset matches the WHERE clause, this query makes sure that Postgres understands, and does not switch to an inferior plan (combine with above index!):

SELECT a.dp, a.at, a.dt, a.it, a.ai, ad.*
FROM   assets a
CROSS  JOIN LATERAL (
   SELECT ad.idt, ad.data
   FROM   asset_data ad
   WHERE  ad.asset_id_fk = a.id
   ORDER  BY ad.idt DESC
   LIMIT 8000             --  same as (relatively small!) outer limit
   ) ad
WHERE  a.dp = 'kr' 
AND    a.at = 'fr' 
AND    a.dt = 'oh' 
AND    a.it = '1m' 
AND    a.ai = 'st'
ORDER  BY ad.idt DESC
LIMIT  8000;

I threw in a LATERAL query to make sure. My previously suggested query would still allow Postgres to fall for an inferior plan if server config and column stats are deceiving.

Or try this bare minimum query. Should be fastest:

SELECT ad.idt, ad.data
FROM   asset_data ad
WHERE  ad.asset_id_fk = (  -- single value guaranteed! else error.
         SELECT a.id
         FROM   asset a
         WHERE  a.dp = 'kr' 
         AND    a.at = 'fr' 
         AND    a.dt = 'oh' 
         AND    a.it = '1m' 
         AND    a.ai = 'st'
         )
ORDER  BY ad.idt DESC
LIMIT  8000;

Not returning dp, at, ... since they are bound to be the same as your input (which you obviously know already). So we only still need the asset to produce the id.

Or you let Postgres know about selectivity of your filters by adding a UNIQUE constraint on asset(dp, at, dt, it, ai). Then your original query shouldn't result in a bad query plan, either.

Asides

Since you already store all of these columns in asset, drop the redundant storage from asset_data. Rename asset_id_fk to just asset_id. Clean up related names. A consistent naming convention for your indexes wouldn't hurt. And add a FOREIGN KEY constraint to enforce referential integrity:

ALTER TABLE asset_data
ADD CONSTRAINT asset_data_asset_id_fkey FOREIGN KEY (asset_id) REFERENCES asset (id);

Clustering the big table on my suggested index would help a lot:

CLUSTER asset_data USING asset_data_asset_id_fk_idt_idx;

See:

• Configuring PostgreSQL for read performance

You may also want to put in some work to improve server configuration and column statistics.

Related:

• Keep PostgreSQL from sometimes choosing a bad query plan
• Optimize a query with small LIMIT, predicate on one column and order by another
• Postgres sometimes uses inferior index for WHERE a IN (...) ORDER BY b LIMIT N

Answer 3

tldr; Since I know the most common query pattern, I'm just going to remove all the indexes except the one I want to force the query planner to use it and I'm going to update the application code to do two queries instead of doing a join because the query planner simply refuses to acknowledge anything telling it that a subquery will return a single row.

Details:

Alright, after a bunch of experimentation, here is what I've come up with. A lot of this is supposition because I don't know what's actually going on under the hood, but the results are the results.

Some context first: the data is time series data, and idt is short for interval datetime, which, under optimal conditions, is basically equivalent to an inserted timestamp.

The first problem was likely that, due to multiple migrations and bulk changes, the rows were not physically inserted in the optimal order, which caused the query planner to ignore the fact that the index was sorted and try to do the sort after the join...if the limit was moved from, say, 9000 rows to 10000 rows. This was a bad plan.

jjanes answer explaining a little about clustering, correlation statistics and physical insertion aspects led me to researching that info a little more. Since Edwin included some similar commands (clustering on the asset_id_fk and idt columns) led me to try those first since I could just copy paste them.

After clustering on an index on the asset_id_fk and idt columns and probably reindexing and vacuum analyze, the correlation statistics updated to be correlated with the asset_id_fk as expected.

This sped up the queries but did not change the query plan. The increase in speed is not surprising since everything was already sorted (I think). However, given the typical operation of the table (insertions based on the idt column), I don't think this clustering method would have been scaleable without regular reclusterings.

Further, the fact that the query plan wasn't fixed was a red flag.

So I decided to instead cluster on the idt column using an index on only that column. After the clustering/reindex/vacuum analyze the correlation statistics updated as expected and it was completely correlated with the idt column.

And, lo and behold, the query plan correctly used the idt index for sorting and this held up through at least 150k rows instead of just 10k. I ran several experiments with the following queries:

SELECT
    a.dp as dp,
    a.at as at,
    a.dt as dt,
    a.it as it,
    a.ai as ai,
    ad.idt as idt,
    ad.data as data
FROM assets a
JOIN asset_data ad ON a.id = ad.asset_id_fk
WHERE 
    a.dp = 'kr' 
    AND a.at = 'fr' 
    AND a.dt = 'oh' 
    AND a.it = '1m' 
    AND a.ai = 'st'
ORDER BY idt desc
LIMIT 150000

SELECT 
  a.dp, 
  a.at, 
  a.dt, 
  a.it, 
  a.ai, 
  ad.idt, 
  ad.data
FROM  (
   SELECT 
     a.dp, 
     a.at, 
     a.dt, 
     a.it, 
     a.ai
   FROM   assets a
   WHERE 
    a.dp = 'kr' 
    AND a.at = 'fr' 
    AND a.dt = 'oh' 
    AND a.it = '1m' 
    AND a.ai = 'st'
   ) a
JOIN   asset_data ad ON ad.asset_id_fk = a.id
ORDER  BY ad.idt DESC
LIMIT  150000;

In both cases they took about 2:40 to complete.

I ran a second experiment because I noticed that basically every time Edwin said X would do Y, it actually didn't. Nothing he said would "inform" the query planner that the subqueries would return a single row actually did. To test this out, I simply replaced the WHERE conditions with the specific id of the asset I wanted, so these were the queries:

SELECT
    a.dp as dp,
    a.at as at,
    a.dt as dt,
    a.it as it,
    a.ai as ai,
    ad.idt as idt,
    ad.data as data
FROM assets a
JOIN asset_data ad ON a.id = ad.asset_id_fk
WHERE a.id = '133'
ORDER BY idt desc
LIMIT 150000

SELECT 
  a.dp, 
  a.at, 
  a.dt, 
  a.it, 
  a.ai, 
  ad.idt, 
  ad.data
FROM  (
   SELECT 
     a.dp, 
     a.at, 
     a.dt, 
     a.it, 
     a.ai
   FROM   assets a
   WHERE a.id = '133'
   ) a
JOIN   asset_data ad ON ad.asset_id_fk = a.id
ORDER  BY ad.idt DESC
LIMIT  150000;

These changed query plans depending on the asset.

Some used the index on the asset_id_fk and idt columns then did a join to the assets table and a sort after the join. These were really fast (they took seconds).

Some used the index on the idt column, did a gather merge strategy, then did the join with the asset table. These took about 50 seconds.

Looking at the row count for the assets, this was probably a reasonable change in query plan but I obviously can't verify since I can't force a query plan. Regardless, this took significantly less time in all cases.

My next experiment was the same as the above but I dropped the index on the idt column. For the asset with the larger number of rows, this forced the query planner to use the index on the asset_id_fk and idt columns and the sorting was done using the index.

This query took about 40 seconds and, even cooler, seemed to result in some caching because the second run took less than one second.

My last experiment was the same as the above but instead of using the asset id, I used the multiple query parameters. This resulted in the query planner not making the optimizations for the asset with the larger number of rows and thus taking long enough that I stopped it (more than 2:40).

My conclusions are as follows:

1. As far as I can tell, the query planner simply ignores any attempt to tell it that a query will return one row if the table is small enough.

2. In situations like this, the better option is to simply do two queries...one for the id from the small table and a second query that doesn't involve a join.

3. The PostgreSQL query planner can be shockingly dumb and unpredictable at times and if you've ever googled "how to force postgresql to use a particular index" and felt the responses of "the query planner will do a better job than you" were condescending and unsupported by evidence, congratulations, you're probably right. Doing a fairly simple join like this should not require so much work to get it to work reliably and predictably.