Postgres "Index Scan Backward" slower than "Index Scan"

Question

I have the following basic table in PostgreSQL 12.13:

Record:
  database_id: FK to database table
  updated_at: timestamp

I've created an index on both the database_id and updated_at fields.

I have a query that fetches the most recent 100 records for a given database id:

SELECT * FROM record WHERE database_id='fa9bcfa6-8d89-4c95-b04a-24c85b169066'
ORDER BY store_record.updated_at DESC
LIMIT 100;

This query is EXTREMELY slow (recently took about 6 min to run). Here is the query plan:

Limit  (cost=0.09..1033.82 rows=100 width=486)
  ->  Index Scan Backward using record_updated_at on record  (cost=0.09..8149369.05 rows=788343 width=486)
        Filter: (database_id = 'fa9bcfa6-8d89-4c95-b04a-24c85b169066'::uuid)

If I change ORDER BY DESC to ORDER BY ASC then the query takes milliseconds, even though the query plan looks about the same:

SELECT * FROM record WHERE database_id='fa9bcfa6-8d89-4c95-b04a-24c85b169066'
ORDER BY store_record.updated_at
LIMIT 100;

Limit  (cost=0.09..1033.86 rows=100 width=486)
  ->  Index Scan using record_updated_at on record  (cost=0.09..8149892.78 rows=788361 width=486)
        Filter: (database_id = 'fa9bcfa6-8d89-4c95-b04a-24c85b169066'::uuid)

If I remove the ORDER BY completely then the query is also fast:

SELECT * FROM record WHERE database_id='fa9bcfa6-8d89-4c95-b04a-24c85b169066'
LIMIT 100;

Limit  (cost=0.11..164.75 rows=100 width=486)
  ->  Index Scan using record_database_id on record  (cost=0.11..1297917.10 rows=788366 width=486)
        Index Cond: (database_id = 'fa9bcfa6-8d89-4c95-b04a-24c85b169066'::uuid)

Few questions:

Why is the first query so much slower than the other two? I understand why the last one is faster but I don't understand why changing the ORDER BY DESC to ORDER BY makes such a difference. Amy I missing an index?
How can I speed up the initial query?

The plans do not contain any timing information so it's impossible to tell how fast or slow the query is. Can you please edit your question and replace them with execution plans generated using explain (analyze, buffers) — user330315
– user330315, Commented Dec 16, 2022 at 6:30

jjanes · Accepted Answer · 2022-12-16 01:09:55Z

3

The plan follows the index to read records in order of updated_at DESC, testing each for the desired database_id, and then stops as soon as it finds 100 which have the desired database_id. But that specific desired value of database_id is much more common on one end of the index than the other. There is nothing magically about the DESC here, presumably there is some other value of database_id for which it works the opposite way, finding 100 of them when descending much faster than when ascending. If you had done EXPLAIN (ANALYZE), this would have been immediately clear based on the different reported values for "Rows Removed by Filter"

If you have a multicolumn index on (database_id,updated_at), then it can immediately jump to the desired spot of the index and read the first 100 rows it finds (after "filtering" them for visibility), and that would work fast no matter which direction you want the ORDER BY to go.

answered Dec 16, 2022 at 1:09

jjanes

45k5 gold badges39 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Johnny Metz Over a year ago

How do you know the index is (database_id,updated_at) instead of (updated_at desc,database_id)? I ask because it looks like the ORDER BY DESC is performed before the filter

jjanes Over a year ago

@JohnnyMetz I don't understand your question. Are you asking about the index I am proposing, or about the index you already have?

Johnny Metz Over a year ago

the index you're proposing

jjanes Over a year ago

If updated_at is put first, then within a given range of updated_at all the equal datebase_id will not be grouped together, so there is no efficient way to skip the wrong ones. But if updated_at is put 2nd, then within a given singular value of database_id, the index will be ordered by updated_at.

jjanes Over a year ago

Right, it can read the index in either direction. You mostly only need to label the direction for an index when you want to sort multiple columns in different directions, or when you want to change where the NULLs appear.

|

Collectives™ on Stack Overflow

Postgres "Index Scan Backward" slower than "Index Scan"

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related