Can PostgreSQL use indexes of both columns in a query condition and order by clause in a single query?

Question

I'm running PostgreSQL 11 with shared_buffers set to 3 GB on my Mac. I have a table job with 5 million rows. The table structure is

                           Table "public.job"
   Column   |           Type           | Collation | Nullable | Default
------------+--------------------------+-----------+----------+---------
 id         | uuid                     |           | not null |
 name       | text                     |           |          |
 created_on | timestamp with time zone |           |          |
 updated_on | timestamp with time zone |           |          |
Indexes:
    "job_pkey" PRIMARY KEY, btree (id)
    "job_created_on_idx" btree (created_on)
    "job_name_idx" btree (name)
    "job_updated_on_idx" btree (updated_on)
    "job_updated_on_name_compound_asc_idx" btree (updated_on, upper(name))
    "job_updated_on_name_compound_desc_idx" btree (updated_on DESC, upper(name))

Note I've created compound index on updated_on and name columns.

When I running query select name, created_on from job where created_on >= '2023-10-08 00:00:00+08'::timestamp with time zone AND created_on < '2023-10-16 00:00:00+08' ORDER BY updated_on ASC, UPPER(name::text) ASC limit 25, PostgreSQL uses the compound index job_updated_on_name_compound_asc_idx and took more than 4 seconds.

Execution plan

Limit  (cost=0.43..102.29 rows=25 width=61) (actual time=4549.668..4550.235 rows=25 loops=1)
   Buffers: shared hit=4859940
   ->  Index Scan using job_updated_on_name_compound_asc_idx on job  (cost=0.43..416764.16 rows=102293 width=61) (actual time=4549.667..4550.230 rows=25 loops=1)
         Filter: ((created_on >= '2023-10-08 00:00:00+08'::timestamp with time zone) AND (created_on < '2023-10-16 00:00:00+08'::timestamp with time zone))
         Rows Removed by Filter: 4828894
         Buffers: shared hit=4859940
 Planning Time: 0.218 ms
 Execution Time: 4550.260 ms

There's an index on the created_on column, but it's not used. I can force PostgreSQL to use the index of created_on column by appending id to the order by clause. The query is select name, created_on from job where created_on >= '2023-10-08 00:00:00+08'::timestamp with time zone AND created_on < '2023-10-16 00:00:00+08' ORDER BY updated_on ASC, UPPER(name::text) ASC, id limit 25;. This time, PostgreSQL uses the index on the created_on column and returns the result very fast.

Execution plan

Limit  (cost=52190.61..52193.52 rows=25 width=77) (actual time=125.192..138.055 rows=25 loops=1)
   Buffers: shared hit=42788
   ->  Gather Merge  (cost=52190.61..62136.44 rows=85244 width=77) (actual time=125.191..138.049 rows=25 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared hit=42788
         ->  Sort  (cost=51190.58..51297.14 rows=42622 width=77) (actual time=119.359..119.362 rows=20 loops=3)
               Sort Key: updated_on, (upper(name)), id
               Sort Method: top-N heapsort  Memory: 30kB
               Worker 0:  Sort Method: top-N heapsort  Memory: 31kB
               Worker 1:  Sort Method: top-N heapsort  Memory: 31kB
               Buffers: shared hit=42788
               ->  Parallel Bitmap Heap Scan on job  (cost=2512.94..49987.82 rows=42622 width=77) (actual time=19.915..109.984 rows=36562 loops=3)
                     Recheck Cond: ((created_on >= '2023-10-08 00:00:00+08'::timestamp with time zone) AND (created_on < '2023-10-16 00:00:00+08'::timestamp with time zone))
                     Heap Blocks: exact=24557
                     Buffers: shared hit=42738
                     ->  Bitmap Index Scan on job_created_on_idx  (cost=0.00..2487.36 rows=102293 width=0) (actual time=16.909..16.909 rows=109685 loops=1)
                           Index Cond: ((created_on >= '2023-10-08 00:00:00+08'::timestamp with time zone) AND (created_on < '2023-10-16 00:00:00+08'::timestamp with time zone))
                           Buffers: shared hit=395
 Planning Time: 0.168 ms
 Execution Time: 138.115 ms

The difference of execution time becomes larger if the database is busy on updating a large column of rows.

The compound index was created to improve sorting performance and is very useful in some cases. Because my system generates the SQL dynamically based on the user selection, so the query condition and sorting can vary. In this specific case, adding id to the order by clause to avoid using a compound index can improve performance, but maybe in some other cases using the compound index is better, so I cannot just simply remove the compound index.

I also checked the pg_stats table and here's the result:

  attname   | inherited | n_distinct | most_common_vals
------------+-----------+------------+------------------
 id         | f         |         -1 |
 name       | f         |         -1 |
 created_on | f         |  -0.908167 |
 updated_on | f         |         -1 |

I have two questions:

1. For the above query, it's obviously using the index of created_on is better. Why does PostgreSQL choose the compound index of the order by clause? Is there anything I can configure on PostgreSQL to let it use the correct index?
2. It looks like PostgreSQL won't use both indexes of columns in the query condition and order by. It's Filter under the compound index although the column used in the Filter is indexed. Is it possible for PostgreSQL to use the compound index for order by and the index for the query condition column together in a single query?

Answer 1

It appears that the created_on and updated_on column are highly correlated with each other. But PostgreSQL has no mechanism for knowing that. It implicitly assumes they are uncorrelated. There is nothing you can do about this assumption in any released or in-development version of PostgreSQL.

It assumes it will need to filter out about 25/102293 of the 5 million rows, or about 1200 of them, before it can stop the index scan. But since the entire early part of the index scan is discarded (at great cost) by the created_on filter condition, it actually has to filter out 4859940 rows before if finds the 25 to keep. So the estimation is off by a factor of about 4000.

If your columns follow the intuitive semantics implied by their names, a row cannot be updated before it was created so the created_on >= '2023-10-08 00:00:00+08' condition also implies an updated_on >= '2023-10-08 00:00:00+08'. If you manually supply this inferred condition, then the scan gets to skip the entire early part of the index, and becomes very fast in my hands. The planner won't supply this inference for you, not even if you have a CHECK constraint which would theoretically allow it to do so, but maybe you can change your app to automatically generate that inference for you.

Based on the fact that "Rows Removed by Filter" is about equal to "Buffers: shared hit" in your first plan, it is evident that physical order of rows in the table is not strongly correlated with the timestamp columns. So by following the table in index order, it has to jump all over the table. Even though your shared_buffers is large enough that everything is in memory, this is still quite slow. Part of that is probably that unpinning and repinning buffers is an expensive operation, and part is probably that doing it this way trashes your CPU cache, and main memory is very much slower than CPU cache. Validating this, if I CLUSTER the table using job_updated_on_name_compound_asc_idx, the query becomes about 10x faster in my hands. Alternatively if I just add created_on into the index to make it (updated_on, upper(name), created_on) then it gets to filter out the created_on values just using the index without having to visit the table, and that too makes it much faster. This latter is perhaps the best option, is it the index will maintain itself and it can be created concurrently with other operations, neither of which applies to CLUSTER.

In this specific case, adding id to the order by clause to avoid using compound index can improve performance

Note that this trick stopped working in v13, where incremental sort was added. At that point, it will happily use the index for primary ordering, then use an incremental sort to reorder just the ties to obtain the overall order. If you want to manually force the index not to be used, a safer approach is to make the first column in the ORDER BY be a dummy expression which doesn't match the index:

ORDER BY (updated_on + interval '0') ASC, UPPER(name::text) ASC 

Some future version of PostgreSQL might become smart enough to see through this trick and so still use the "wrong" index, but none of the current or in-dev versions are there yet.

To directly address your 2nd question, no, it won't combine indexes in that way, one to do filtering and the other to do ordering. The code used to combine indexes is the bitmap code, and that loses any ordering. It should be possible to add a node type which does a regular index scan (which maintains order) but to attach to it a populated bitmap used for filtering. I think it would only require programming (i.e. no changes to the on-disk representation of the data) but it would still be a lot of work and no one has done it. I have thought about it a few times, but made no concrete attempts at it. It would also be a rather innovative kind of node, and I suspect it would hard to get it accepted into the code base for that reason. Also, in your case it would probably not be any more effective than it already would be to just add the "filtering" column as the last column onto the definition of the existing ordering-index. (I think the real use of this code would be when the bitmap getting attached is itself the result of combining multiple indexes, which does not seem to be the case for you)