Efficient predictable ordering in PostgreSQL I have a large table of locations. I would like to efficient paginate though the table. I had previously being using an OFFSET approach however the size of the table made that approach unusable. So I am now trying a cursor approach using the location id.

In order to ensure consistent ordering for cases where a user has 2 rows with identical timestamp, I am also ordering by id.

SELECT  *
FROM locations
WHERE
  user_id = 1
ORDER BY timestamp desc, id
LIMIT 100;


However after adding id to the ORDER BY, the query has become slow. It is now doing a Seq Scan which takes ~20 seconds.

QUERY PLAN
Limit  (cost=502534.86..502535.11 rows=100 width=152) (actual 
time=22822.113..22822.142 rows=100 loops=1)
  -&gt;  Sort  (cost=502534.86..515512.80 rows=5191175 width=152) (actual time=22822.110..22822.133 rows=100 loops=1)
        Sort Key: ""timestamp"" DESC, id"
        Sort Method: top-N heapsort  Memory: 51kB
    -&gt;  Seq Scan on locations  (cost=0.00..304131.89 rows=5191175 width=152) (actual time=1.603..21284.908 rows=5169237 loops=1)
          Filter: (user_id = 1)
          Rows Removed by Filter: 3048468
Planning time: 0.204 ms
Execution time: 22822.194 ms


Timestamp collisions are edge cases and id is a primary key. So why does the execution plan require a Seq Scan?

For context

SELECT indexdef
FROM pg_indexes
WHERE tablename = 'locations'


results

CREATE UNIQUE INDEX locations_pkey ON locations USING btree (id)
CREATE INDEX index_locations_on_user_id_and_timestamp ON locations USING btree (user_id, "timestamp")
CREATE INDEX index_locations_on_user_id_and_point ON locations USING gist (user_id, point)
CREATE INDEX index_locations_on_user_id ON locations USING btree (user_id)
CREATE INDEX index_locations_on_user_id_and_timestamp ON locations USING btree (user_id, "timestamp")
CREATE INDEX index_locations_on_user_id_and_timestamp_and_id ON locations USING btree (user_id, "timestamp", id)
Do you have INDEX(timestamp DESC, id ASC)?

Or, try ORDER BY timestamp DESC, id DESC .