Keyset pagination needs the sort key in the cursor

Keyset pagination, the cursor kind, is the right way to page through a large list. Instead of “skip 2000 rows and take 20”, which gets slower the deeper you go and shifts under you when rows are inserted, you say “give me the 20 rows after this one”, carrying a cursor that points at the last row you saw. Fast at any depth, stable under inserts. I like it a lot. I also implemented it wrong in an instructive way.

The version that worked#

Paging by creation time, the cursor encoded the last row’s timestamp and its id, and the query said: give me rows where the timestamp is before the cursor’s, or the timestamp is equal and the id is after. That composite comparison is the whole trick. The timestamp does the ordering, and the id breaks ties so two rows with the same timestamp cannot straddle a page boundary and get skipped or repeated. Fetch one more than the page size to know whether there is a next page, and you are done.

The version that quietly lied#

Then the list grew a “sort by” option: rating, file size, whatever the user picked. And the cursor still only carried the timestamp and the id. So when someone sorted by file size, the query had no real cursor value to compare against, the file size of the last row was simply not in the cursor. The code degraded to a predicate that was effectively “file size is non-negative or id compares less”, which is to say, no real keyset filter at all.

Nothing threw. The first page looked fine. But because the cursor could not actually locate “the last file size I saw”, the boundaries between pages were wrong: rows near the edge got skipped or shown twice, especially wherever several rows shared a file size (which is common, sizes are not unique). It is the exact bug keyset pagination exists to prevent, reintroduced by a cursor that did not carry enough information to do its job.

A keyset cursor has to contain the actual value you are ordering by, plus a unique tiebreaker. If it only carries the tiebreaker, it cannot find its place in any other ordering, and it silently falls back to skipping and duplicating.

The fix, and the general rule#

Generalising keyset pagination across arbitrary sort fields means the cursor has to be built from whatever field the sort is on: its value, plus a guaranteed-unique column (usually the primary key) to break ties. Sort by file size, the cursor carries file size and id. Sort by rating, it carries rating and id. The comparison is always the same shape, “sort value past the cursor, or equal and tiebreaker past the cursor”, but the sort value is whatever you are actually ordering on.

The wider lesson is about non-unique sort columns in general. The moment you order by something that can repeat, you need a unique tiebreaker in both the ordering and the cursor, or your page boundaries are built on sand. And this is a failure that passes every quick test, because page one always looks right. You only see it when you page deep enough to land on a boundary in the middle of a run of equal values, which is exactly the case a five-row test fixture never hits.

For the person scrolling the list, that shows up as records silently missing or shown twice, the kind of gap nobody catches until a customer swears something was there yesterday.