Pagination, Ranking Stability, and the Shuffling Result Set

A result list of a million matches presents perhaps twenty at a time, and the reader moves through it with a next-page control. The mechanism behind that control is the quietest part of a search interface and one of the hardest to get right, because it has to reconcile two conflicting requirements: the list should not re-shuffle between page one and page two, and the index behind it is being written to continuously.

The offset-and-limit contract

The simplest pagination model is two parameters: an offset, the number of results to skip, and a limit, the number to return. Page three of a twenty-per-page list is offset forty with limit twenty. The engine sorts the candidate set by score, skips the first forty, and returns the next twenty. The interface reconstructs the page from the offset, so any page is addressable by a single pair of numbers.

The cost model is the first surprise. Skipping is not free. A deep offset forces the engine to evaluate and discard every result before it, so page five hundred costs the retrieval of ten thousand results that are then thrown away. In an inverted-index engine the sort of the candidate set dominates, and deep pagination turns what looks like a constant-time “skip” into a sort whose size grows with the offset. Most systems cap the depth for exactly this reason, commonly refusing offsets beyond some multiple of ten thousand, and the interface then limits how far a reader can page.

The arithmetic makes the point concrete. With a page size of twenty, page one retrieves and ranks twenty results, page one hundred retrieves and ranks two thousand, and page five hundred retrieves ten thousand. The work is linear in the offset, so the interface’s guarantee of addressable pages is bought at a cost that grows without bound in the depth, and no amount of index tuning removes it: the engine cannot know which twenty results are the five-hundredth page without first establishing the order of the ten thousand that precede them. The cap is therefore not an arbitrary restriction but a bound on the linear cost.

Why the list re-shuffles

The more visible defect is instability. If the reader pages forward and the index receives new documents in between, the candidate set on the next request is not the set that produced page one. A new high-scoring document shifts every offset, and the reader sees duplicates and gaps: the result that was at the bottom of page one now appears at the top of page two, and one result is skipped entirely. The offset model has no memory of the previous page, so it cannot defend against this.

The classic mitigation is a snapshot of the ranking, taken at the first request and reused for subsequent pages. The engine captures the full ordered list, or the parameters that produced it, and pages over the snapshot rather than over the live index. The reader sees a stable list, at the cost of a ranking that does not reflect the newest documents. There is a second cost: a snapshot large enough to cover deep paging consumes memory on the engine, which is why snapshot paging is typically offered only for shallow depths and the interface falls back to offset paging beyond them.

The snapshot can be cheaper than a full materialization. Instead of storing every result, the engine stores the query and its timestamp, and re-executes the same query against a frozen view of the index at that timestamp, which a versioned index can serve without copying. This trades the memory of a materialized list for the cost of keeping index versions around, and the choice between the two is itself a space-time trade that differs from one engine to another. What the reader perceives is the same in either case: a page-two that is consistent with page-one.

Cursor pagination as an alternative

A cursor replaces the offset with an opaque token that identifies a position in a specific sort order. The first request returns a cursor for the last item seen; the next request sends that cursor and receives the items after it. Because the position is identified by the item’s sort key rather than by a numeric offset, inserts and deletions that occur before the cursor do not shift it. A document deleted before the cursor has already been seen and is simply skipped; a document inserted after the cursor is seen on a later page.

The cursor’s correctness depends on the sort key being unique and total. If the sort is by a non-unique field, such as a relevance score that many documents tie on, a cursor built from the score alone cannot distinguish between tied documents and the next page will either skip one or repeat one. The standard fix is to append a unique tiebreaker, conventionally the document identifier, so the cursor is the pair of sort key and id, and the next-page query filters on the pair lexicographically. This is the same tie-breaking concern that appears wherever an ordered stream is paged, and it is why cursor implementations carry the tiebreaker explicitly rather than assuming the sort is unique.

The cursor model trades addressability for stability. A cursor is meaningless outside the specific query and sort order that produced it, so the interface cannot jump directly to page five by number, and cannot persist a cursor for later reuse against a different sort. It is the right model for an infinite-scroll feed, where the reader only ever moves forward and the sort order is fixed, and the wrong model for a result list where the reader may change the sort or share a link to a specific page.

The tension that runs through all three models, offset, snapshot, and cursor, is between a live ranking and a stable one. The offset is stable only if the index is static; the snapshot is stable but stale; the cursor is stable under mutation but tied to a single order. A search interface chooses among them per feature, and the choice leaks into what the reader can do: how deep they can page, whether the list shifts under them, and whether a page can be bookmarked. Pagination is the place where the index’s write path and the interface’s read path meet, and every option is a compromise between the two.

That compromise also bears on the presentation layers built above it. A grouping pass that collapses near-duplicates must itself be stable across pages, or a group that was collapsed on page one will reappear expanded on page two and the reader will see the same document twice. Pagination therefore has to be decided before grouping, not after, and the offset or cursor chosen for the raw list constrains how the grouped and deduplicated list can be sliced into pages without double-counting. The same ordering constraint applies to any layer that removes or folds results, because a fold that is not itself page-stable introduces exactly the duplicates and gaps that pagination exists to prevent.