Planner not using index order to sort the records using CTE

Question

I am trying to pass some ids into an in-clause on a sorted index with the same order by condition but the query planner is explicitly sorting the data after performing index search. below are my queries.

Generate a temporary table.

SELECT a.n/20 as n, md5(a.n::TEXT) as b INTO temp_table 
From generate_series(1, 100000) as a(n);

create an index

CREATE INDEX idx_temp_table ON temp_table(n ASC, b ASC);

In below query, planner uses index ordering and doesn't explicitly sorts the data.(expected)

EXPLAIN ANALYSE
SELECT * from 
temp_table WHERE n = 10
ORDER BY  n, b
limit 5;

Query Plan

QUERY PLAN Limit  (cost=0.42..16.07 rows=5 width=36) (actual time=0.098..0.101 rows=5 loops=1)   
          ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..1565.17 rows=500 width=36) (actual time=0.095..0.098 rows=5 loops=1)
            Index Cond: (n = 10)
            Heap Fetches: 5 Planning time: 0.551 ms Execution time: 0.128 ms

but when i use one or more ids from a cte and pass them in clause then planner only uses index to fetch the values but explicitly sorts them afterwards (not expected).
```
EXPLAIN ANALYSE
WITH cte(x) AS (VALUES (10))
SELECT * from temp_table 
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;
```
then planner uses below query plan

QUERY PLAN

QUERY PLAN
Limit  (cost=85.18..85.20 rows=5 width=37) (actual time=0.073..0.075 rows=5 loops=1)
  CTE cte
    ->  Values Scan on "*VALUES*"  (cost=0.00..0.03 rows=2 width=4) (actual time=0.001..0.002 rows=2 loops=1)
  ->  Sort  (cost=85.16..85.26 rows=40 width=37) (actual time=0.072..0.073 rows=5 loops=1)
        Sort Key: temp_table.n, temp_table.b
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Nested Loop  (cost=0.47..84.50 rows=40 width=37) (actual time=0.037..0.056 rows=40 loops=1)
              ->  Unique  (cost=0.05..0.06 rows=2 width=4) (actual time=0.009..0.010 rows=2 loops=1)
                    ->  Sort  (cost=0.05..0.06 rows=2 width=4) (actual time=0.009..0.010 rows=2 loops=1)
                          Sort Key: cte.x
                          Sort Method: quicksort  Memory: 25kB
                          ->  CTE Scan on cte  (cost=0.00..0.04 rows=2 width=4) (actual time=0.004..0.005 rows=2 loops=1)
              ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..42.02 rows=20 width=37) (actual time=0.012..0.018 rows=20 loops=2)
                    Index Cond: (n = cte.x)
                    Heap Fetches: 40
Planning time: 0.166 ms
Execution time: 0.101 ms

I tried putting an explicit sorting while passing the ids in where clause so that sorted order in ids is maintained but still planner sorted explicitly

EXPLAIN ANALYSE
WITH cte(x) AS (VALUES (10))
SELECT * from temp_table 
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;

Query plan

QUERY PLAN
Limit  (cost=42.62..42.63 rows=5 width=37) (actual time=0.042..0.044 rows=5 loops=1)
  CTE cte
    ->  Result  (cost=0.00..0.01 rows=1 width=4) (actual time=0.000..0.000 rows=1 loops=1)
  ->  Sort  (cost=42.61..42.66 rows=20 width=37) (actual time=0.042..0.042 rows=5 loops=1)
        Sort Key: temp_table.n, temp_table.b
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Nested Loop  (cost=0.46..42.28 rows=20 width=37) (actual time=0.025..0.033 rows=20 loops=1)
              ->  HashAggregate  (cost=0.05..0.06 rows=1 width=4) (actual time=0.009..0.009 rows=1 loops=1)
                    Group Key: cte.x
                    ->  Sort  (cost=0.03..0.04 rows=1 width=4) (actual time=0.006..0.006 rows=1 loops=1)
                          Sort Key: cte.x
                          Sort Method: quicksort  Memory: 25kB
                          ->  CTE Scan on cte  (cost=0.00..0.02 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=1)
              ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..42.02 rows=20 width=37) (actual time=0.014..0.020 rows=20 loops=1)
                    Index Cond: (n = cte.x)
                    Heap Fetches: 20
Planning time: 0.167 ms
Execution time: 0.074 ms

Can anyone explain why planner is using an explicit sort on the data? Is there a way to by pass this and make planner use the index sorting order so additional sorting on the records can be saved. In production, we have similar case but size of our selection is too big but only a handful of records needs to fetched with pagination. Thanks in anticipation!

. . If you use the in clause without a CTE, what is the query plan? I suspect that is the issue, not the CTE. If so, you might be able to fix the problem using exists. — Gordon Linoff
@GordonLinoff query works fine an uses index order when i pass values in in clause for eg. n IN (10,11) or n IN (10). — sumit
CTEs have been changed in v12. In PostgreSQL v12, you get the plan you want given your example. (I don't know what it would do with your true query of interest, of couse) — jjanes

wildplasser wildplasser · Accepted Answer · 2020-02-05T15:26:07

It is actually a decision made by the planner, with a larger set of values(), Postgres will switch to a smarter plan, with the sort done before the merge.

select version();

\echo +++++ Original

EXPLAIN ANALYSE
WITH cte(x) AS (VALUES (10))
SELECT * from temp_table
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;

\echo +++++ TEN Values
EXPLAIN ANALYSE
WITH cte(x) AS (VALUES (10),(11),(12),(13),(14),(15),(16),(17),(18),(19)
        )
SELECT * from temp_table
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;

\echo ++++++++ one row from table

EXPLAIN ANALYSE
WITH cte(x) AS (SELECT n FROM temp_table WHERE n = 10)
SELECT * from temp_table
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;

\echo ++++++++ one row from table TWO ctes

EXPLAIN ANALYSE
WITH val(x) AS (VALUES (10))
,  cte(x) AS (
        SELECT n FROM temp_table WHERE n IN (select x from val)
        )
SELECT * from temp_table
WHERE n IN ( SELECT x from cte)
ORDER BY  n, b
limit 5;

Resulting plans:

                                                version                                                
-------------------------------------------------------------------------------------------------------
 PostgreSQL 11.3 on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 4.8.4-2ubuntu1~14.04.4) 4.8.4, 64-bit
(1 row)

+++++ Original
                                                                      QUERY PLAN                                                                      
------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=13.72..13.73 rows=5 width=37) (actual time=0.197..0.200 rows=5 loops=1)
   CTE cte
     ->  Result  (cost=0.00..0.01 rows=1 width=4) (actual time=0.001..0.001 rows=1 loops=1)
   ->  Sort  (cost=13.71..13.76 rows=20 width=37) (actual time=0.194..0.194 rows=5 loops=1)
         Sort Key: temp_table.n, temp_table.b
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Nested Loop  (cost=0.44..13.37 rows=20 width=37) (actual time=0.083..0.097 rows=20 loops=1)
               ->  HashAggregate  (cost=0.02..0.03 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1)
                     Group Key: cte.x
                     ->  CTE Scan on cte  (cost=0.00..0.02 rows=1 width=4) (actual time=0.007..0.008 rows=1 loops=1)
               ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..13.14 rows=20 width=37) (actual time=0.058..0.068 rows=20 loops=1)
                     Index Cond: (n = cte.x)
                     Heap Fetches: 20
 Planning Time: 1.328 ms
 Execution Time: 0.360 ms
(15 rows)

+++++ TEN Values
                                                                      QUERY PLAN                                                                       
-------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.91..89.11 rows=5 width=37) (actual time=0.179..0.183 rows=5 loops=1)
   CTE cte
     ->  Values Scan on "*VALUES*"  (cost=0.00..0.12 rows=10 width=4) (actual time=0.001..0.007 rows=10 loops=1)
   ->  Merge Semi Join  (cost=0.78..3528.72 rows=200 width=37) (actual time=0.178..0.181 rows=5 loops=1)
         Merge Cond: (temp_table.n = cte.x)
         ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..3276.30 rows=100000 width=37) (actual time=0.030..0.123 rows=204 loops=1)
               Heap Fetches: 204
         ->  Sort  (cost=0.37..0.39 rows=10 width=4) (actual time=0.023..0.023 rows=1 loops=1)
               Sort Key: cte.x
               Sort Method: quicksort  Memory: 25kB
               ->  CTE Scan on cte  (cost=0.00..0.20 rows=10 width=4) (actual time=0.003..0.013 rows=10 loops=1)
 Planning Time: 0.197 ms
 Execution Time: 0.226 ms
(13 rows)
++++++++ one row from table
                                                                       QUERY PLAN                                                                       
--------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=14.39..58.52 rows=5 width=37) (actual time=0.168..0.173 rows=5 loops=1)
   CTE cte
     ->  Index Only Scan using idx_temp_table on temp_table temp_table_1  (cost=0.42..13.14 rows=20 width=4) (actual time=0.010..0.020 rows=20 loops=1)
           Index Cond: (n = 10)
           Heap Fetches: 20
   ->  Merge Semi Join  (cost=1.25..3531.24 rows=400 width=37) (actual time=0.167..0.170 rows=5 loops=1)
         Merge Cond: (temp_table.n = cte.x)
         ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..3276.30 rows=100000 width=37) (actual time=0.025..0.101 rows=204 loops=1)
               Heap Fetches: 204
         ->  Sort  (cost=0.83..0.88 rows=20 width=4) (actual time=0.039..0.039 rows=1 loops=1)
               Sort Key: cte.x
               Sort Method: quicksort  Memory: 25kB
               ->  CTE Scan on cte  (cost=0.00..0.40 rows=20 width=4) (actual time=0.012..0.031 rows=20 loops=1)
 Planning Time: 0.243 ms
 Execution Time: 0.211 ms
(15 rows)

++++++++ one row from table TWO ctes
                                                                          QUERY PLAN                                                                          
--------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=14.63..58.76 rows=5 width=37) (actual time=0.224..0.229 rows=5 loops=1)
   CTE val
     ->  Result  (cost=0.00..0.01 rows=1 width=4) (actual time=0.001..0.001 rows=1 loops=1)
   CTE cte
     ->  Nested Loop  (cost=0.44..13.37 rows=20 width=4) (actual time=0.038..0.052 rows=20 loops=1)
           ->  HashAggregate  (cost=0.02..0.03 rows=1 width=4) (actual time=0.007..0.007 rows=1 loops=1)
                 Group Key: val.x
                 ->  CTE Scan on val  (cost=0.00..0.02 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=1)
           ->  Index Only Scan using idx_temp_table on temp_table temp_table_1  (cost=0.42..13.14 rows=20 width=4) (actual time=0.029..0.038 rows=20 loops=1)
                 Index Cond: (n = val.x)
                 Heap Fetches: 20
   ->  Merge Semi Join  (cost=1.25..3531.24 rows=400 width=37) (actual time=0.223..0.226 rows=5 loops=1)
         Merge Cond: (temp_table.n = cte.x)
         ->  Index Only Scan using idx_temp_table on temp_table  (cost=0.42..3276.30 rows=100000 width=37) (actual time=0.038..0.114 rows=204 loops=1)
               Heap Fetches: 204
         ->  Sort  (cost=0.83..0.88 rows=20 width=4) (actual time=0.082..0.082 rows=1 loops=1)
               Sort Key: cte.x
               Sort Method: quicksort  Memory: 25kB
               ->  CTE Scan on cte  (cost=0.00..0.40 rows=20 width=4) (actual time=0.040..0.062 rows=20 loops=1)
 Planning Time: 0.362 ms
 Execution Time: 0.313 ms
(21 rows)

Beware of CTEs!.

For the planner, CTEs are more or less black boxes, and very little is known about expected number of rows, statistics distribution, or ordering inside.

In cases where CTEs result in a bad plan (the original question is not such a case), a CTE can often be replaced by a (temp) view, which is seen by the planner in its full naked glory.

Update

Starting with version 11, CTEs are handled differently by the planner: if they do not have side effects, they are candidates for being merged with the main query. (but is still a good idea to check your query plans)

Planner not using index order to sort the records using CTE

2 Answers

Beware of CTEs!.

Update