Clients are asking for page 4,000 of your /orders collection. How is that endpoint paginated, and what would you change?

Start with the correctness bug, not the slowness

?page=4000&size=20 is usually discussed as a performance problem, and the performance is the less interesting half. The real defect is that offset pagination has no defined behaviour over a collection that is being written to. Page one is computed at one instant, page two at another, and between the two requests somebody placed an order. Every subsequent row has shifted down by one, so the last item the client saw on page one reappears at the top of page two. Delete a row instead and one order is skipped entirely and never rendered anywhere. A client walking the whole collection to build a report therefore gets duplicates and holes, and neither shows up in testing against a static fixture.

This matters more than it sounds because the endpoint's most demanding consumer is almost never a human clicking through pages. It is an integration doing a full traversal, and a full traversal is exactly the access pattern offset pagination cannot serve correctly.

The performance argument is the easy one. OFFSET 80000 does not skip work; the engine produces the first 80,000 rows in sort order and throws them away, so page depth and query cost rise together. PostgreSQL documents this directly, and InnoDB behaves the same way.

Keyset pagination, and the tiebreaker it requires

The fix is to stop describing position as a count and start describing it as a value: give me the twenty rows that sort after the last one I saw.

-- Offset: the engine sorts and discards 80,000 rows to return 20.
SELECT id, placed_at
FROM   orders
ORDER BY placed_at DESC, id DESC
OFFSET 80000 LIMIT 20;

-- Keyset: the row-value comparison seeks straight into the index, so page
-- 4,000 costs the same as page 1. Standard SQL, and supported by both
-- PostgreSQL and MySQL 8.
SELECT id, placed_at
FROM   orders
WHERE  (placed_at, id) < ($1::timestamptz, $2::bigint)
ORDER BY placed_at DESC, id DESC
LIMIT  20;

The composite comparison is the part people get wrong, usually by writing WHERE placed_at < $1, which drops every other order placed in the same millisecond as the one on the boundary. placed_at alone is not unique, and a sort key that is not unique gives you no way to say where you stopped. Appending the primary key makes the ordering total, and a total order is the precondition for a cursor meaning anything at all. Back it with an index on the same columns in the same directions, (placed_at DESC, id DESC); PostgreSQL can also read a plain ascending index backwards, so a single index often serves both directions, but a mixed ASC, DESC ordering needs the index built to match.

What the client sees

Do not expose placed_at and id as query parameters. Base64-encode them into one opaque cursor string, because the moment the shape is public it is a contract, and you have lost the freedom to add a third sort column or switch the underlying key. Opacity here is not obfuscation, it is the difference between a change you can ship and a change that needs every client to redeploy.

Return the next cursor in the response and, if you want the affordance rather than only the data, as a Link header with rel="next" per RFC 8288. Cap page size server-side and clamp rather than error, because a client that asks for 10,000 items is going to keep asking. And decide what a stale or corrupt cursor does: 400 with a machine-readable code is fine, silently restarting from the beginning is not, since an integration will loop forever without noticing.

The total count is a separate feature with a separate price

Product will ask for "page 1 of 4,732" and it is worth being explicit that this is a second query with its own cost. An exact SELECT count(*) in PostgreSQL must visit every candidate row for the filter — an index-only scan helps when the visibility map allows it, but the work still scales with the number of rows matched. InnoDB has no cached row count either, and MySQL's SQL_CALC_FOUND_ROWS was deprecated in 8.0.17 precisely because it made the main query slower to compute a number most callers ignored.

So price it honestly. An approximate count is usually acceptable for a UI hint: in PostgreSQL, reltuples from pg_class for an unfiltered table, or the planner's own row estimate from EXPLAIN for a filtered one. Where an exact figure is genuinely required, make it a separate opt-in parameter or a separate endpoint so the common request does not pay for it. Returning hasMore — fetch limit + 1 rows and report whether the extra one existed — satisfies most interfaces for free.

What you are giving up, said out loud

Keyset pagination cannot jump to an arbitrary page, because there is no cursor for page 4,000 until you have walked to it. A strong answer states that constraint rather than letting the interviewer find it, and then follows with the observation that this is usually fine: nobody reads page 4,000. Someone reaching for it wants either a filter, a search, or an export, and all three are better products than deep paging. If numbered pages are genuinely required, keyset within a bounded window plus a hard depth cap is a workable compromise, and so is snapshotting the result set behind a server-side cursor when the traversal is a batch job you control.

The other consequence worth pre-empting is arbitrary sorting. Every sort order a client can request needs its own supporting index and its own cursor encoding, which is why "sort by any field" and "cursor pagination" are in tension. Offering three sanctioned sort orders is a design decision, not a limitation to apologise for.