Pagination Needs a Stable Order

A financial report encoded two sort rules as one string:

lowercased customer name + "-" + customer identifier

Sharded tests with concurrently created identifiers exposed unreliable output. The correction stopped asking a compound string to express precedence. It compared names directly and consulted the stable customer identifier only when the names matched.

The retained diff does not prove that equal names alone caused the failing order. It does expose the rule every paginator depends on: the primary comparison, tie-breaker, and comparison semantics must be explicit, and each row needs exactly one reproducible position.

Sorting is not total until ties have somewhere to go

Ordering by a non-unique value defines groups, not a sequence:

ORDER BY customer_name

Within each equal-name group, the database or collection may return rows in any order compatible with the query. A current execution plan, insertion pattern, or in-memory source order can make the output appear stable for months. None is part of the contract.

Add an immutable unique tie-breaker:

ORDER BY customer_name, customer_id

Now any two distinct rows compare differently. The ordering is total.

The tie-breaker must use the same comparison rules every time. If names use case-insensitive natural comparison in one layer and byte comparison in another, a cursor generated by one layer may not describe the order used by the next.

Null placement also belongs in the contract. So do locale, collation, and sort direction. “Name ascending” is incomplete if any of those can vary.

Offset pagination trusts the rows before the page

Offset pagination asks the data source to skip a number of rows:

ORDER BY id
LIMIT 50 OFFSET 100

The page boundary means “whatever follows the first 100 rows when this query runs.” If a new row is inserted before that boundary, a row from the previous page can move onto the next one. If an earlier row disappears, an unseen row can move into the skipped region.

Consider this first page:

source: [10, 20, 30, 40]
page 1 with offset 0: [10, 20]

Insert 15 before reading page two:

source: [10, 15, 20, 30, 40]
page 2 with offset 2: [20, 30]

Row 20 appears twice. Deletion can produce the opposite error and skip a row.

Offset pagination is still reasonable for small, mostly static result sets where numbered pages matter more than exact traversal. Its weakness is not that offsets are forbidden. It is that position is defined by a changing prefix.

A cursor must encode the actual order

Keyset pagination resumes after the last ordered value:

WHERE id > :last_id
ORDER BY id
LIMIT 50

After page [10, 20], the next query begins after 20. Inserting 15 no longer duplicates 20. The new row is behind the cursor and is intentionally outside this forward traversal.

For a composite order, the cursor must carry every ordered component:

WHERE
    customer_name > :last_name
    OR (
        customer_name = :last_name
        AND customer_id > :last_id
    )
ORDER BY customer_name, customer_id
LIMIT 50

A cursor containing only customer_name cannot distinguish two equal-name rows. A cursor containing only customer_id does not describe the requested name order.

Descending and mixed-direction orders require matching comparison operators. The cursor is not an arbitrary token attached to the response. It is a serialized position in one declared total order.

Opaque cursor encoding can keep the API flexible, but the decoded values, directions, filters, and version still need validation. Signing a cursor can prevent clients from changing that state; it cannot repair an incomplete order.

Stable traversal is not automatically a fixed data set

Keyset pagination avoids movement before the cursor. It does not stop new rows from appearing after it.

For an endless feed, that may be correct. The reader continues forward and sees new work. For a finite export, migration, or backfill, the same behavior can prevent completion or mix records from different logical snapshots.

The retained archive backfill captures a high-water identifier before planning:

WHERE id > :cursor
  AND id <= :high_water
ORDER BY id
LIMIT :batch_size

Rows created after that upper bound belong to a later run. The current run has a finite target even while writes continue.

This is not a database snapshot in the transaction-isolation sense. Rows below the high-water mark can still be updated or deleted unless the source contract prevents it. If their mutable contents matter, the design needs version checks, fingerprints, copied snapshots, or another reconciliation mechanism.

A resumable backfill needs durable progress

An in-memory cursor disappears with the process. A queue retry may then repeat a batch or start from a value inferred from incomplete side effects.

The retained design persists:

• the fixed high-water identifier;
• immutable selection criteria;
• the exclusive planning cursor;
• each batch’s first and last identifier;
• source row counts;
• source fingerprints; and
• the run and batch states.

Cursor advancement and batch creation happen in one transaction under a locked run record. Another planner can proceed only if the cursor still equals the value it expected.

That makes the cursor evidence, not merely an optimization:

planned through identifier 300
batches cover 1..100, 101..200, 201..300
source count and fingerprints recorded

The design was chosen for a source expected to grow beyond one hundred million rows. The retained history establishes that planning assumption and the resulting controls. It does not provide a published offset-versus-keyset runtime benchmark, so the argument does not invent one.

Filters belong to the cursor’s contract

A cursor created for one query is unsafe for another:

page 1:
    division = north
    created_at >= January 1

page 2:
    division = all
    created_at >= February 1

Even if both use the same ordered identifier, the second cursor no longer describes the skipped result set.

Interactive APIs can embed a digest of filters and order in an opaque cursor, then reject a cursor when the request changes. Backfills can persist immutable criteria with the run. Either way, changing the predicate starts a new traversal.

Authorization is part of the predicate too. A cursor must not grant access to a row which the current request cannot read, and a changed authorization scope may invalidate the old traversal.

Different readers need different pagination contracts

There is no single best paginator.

Use offset pagination when:

• the result set is small or sufficiently static;
• readers need direct numbered-page navigation;
• modest movement between pages is acceptable; and
• the count and deep-offset costs are measured and acceptable.

Use keyset pagination when:

• forward or backward traversal is enough;
• the result set changes frequently;
• deep pages would require large skips; or
• duplicate and missing rows across pages matter.

Add a high-water bound when:

• one run must finish against a finite population;
• new rows should belong to a later run; and
• the ordered key can define that upper frontier.

For arbitrary user-selected sorting, some orders may not support cursor pagination efficiently or correctly. Falling back to offset pagination can be more honest than pretending a cursor supports an order it does not encode.

The fixture changes the source between pages

The DATA-09 fixture begins with duplicate display names in two different source orders. Name-only sorting preserves the inherited tie order and produces different output. Adding the identifier produces one result.

It then inserts a row between offset pages and reproduces the duplicate. A keyset traversal resumes after the last identifier without repeating it. Finally, a high-water bound excludes rows added beyond the finite run.

The fixture operates on synthetic in-memory arrays. It demonstrates ordering semantics, not a database query plan, concurrency guarantee, or production performance measurement.

Every page boundary is a data contract

Before paginating, write down:

filters
authorization scope
ordered columns
comparison rules
null placement
directions
unique tie-breaker
cursor encoding and version
finite high-water bound, if any

Then test equal sort values and mutate the source between page requests.

A page size tells the system how many rows to return. The order and cursor tell it which rows those are. If either is incomplete, pagination does not merely look unstable. It loses the ability to say where one page ends and the next begins.