Somebody reported seeing the same item twice while paging through a list. There was nothing in the logs, the query was ordinary, so I spent an afternoon looking for a bug in the application. The bug is in the paging itself, needing no concurrency drama to reproduce: 1 insert is enough.
The setup is a table of a million rows with an index on the sort key, pages of 20. Page 1 comes back as ids 1 to 20. Then 1 row arrives that sorts before all of them, which is the ordinary case of somebody backdating an entry. Then page 2 is fetched the usual way.
The offset page starts with 20, a row the reader has already seen. Row 40 never appears at all. The key based page returns 21 to 40. Nobody is at fault: the offset query correctly returns rows 21 to 40 of the current ordering, which is 1 row longer at the front than it was when page 1 was drawn.
That is the part that took me the afternoon. I was looking for a race, a caching layer, a wrong sort. There is nothing to find. The scheme itself has the property that anything inserted or deleted ahead of your position shifts everything behind it, so a reader who pages slowly sees repeats after inserts and silently skips rows after deletes.
The speed, since everybody talks about that instead
At the front of the list the offset query is the quicker one, 1.483 milliseconds against 1.774. That is worth saying out loud, because it is why nobody changes anything: on the pages that people actually open, the simple version wins.
By 100000 rows deep it costs 10.8 milliseconds and by 900000 it costs 69.5, while the key based query has not moved off 1.5. The plan explains it in 1 line: to return 20 rows the database reads 900020 of them, then throws away everything before the offset. The key based query reads exactly 20.
Crawling the whole table makes the shape obvious. In pages of 20 there are 50000 pages. The offset version reads 20 rows more on each one than on the last, so the total comes to about 25 billion row reads for a table of a million rows. The key based version reads 20 rows per page and finishes at a million. That is arithmetic rather than a measurement. It is the same arithmetic the plan showed on 1 page: the cost of a page is the position of that page.
An export job is exactly this. It walks every page once, politely, in a loop somebody wrote in an afternoon, turning a table scan into a quadratic one without a single line of the code looking wrong.
What I did not check
Paging by key needs a unique tiebreaker. Mine is the primary key next to the timestamp. Without it, rows sharing a sort value land on both sides of a page boundary. I did not measure that, though I expect it to reproduce the duplicate in a different way.
The mirror of this bug, a delete ahead of your position silently skipping a row, I reasoned about rather than ran. The practical cost of key based paging is real too: you cannot jump to page 57, only forward and back, so any interface with numbered pages is asking for the scheme that miscounts.
The narrow claim is about what to fix first. The speed argument only applies to depths most applications never reach. The correctness argument applies on page 2.