Topic 16

Pagination, Filtering, Sorting

Data

GET /orders?page=400 on a table that gains fifty rows a minute returns a page that overlaps the one before it and skips rows the client never sees, and the database counts 20,000 rows to throw them away before it finds the fifty it will return. Offset pagination lies under writes and costs more the further it goes. Cursor pagination does neither, at the price of a stricter contract: next and previous only, sorted by a key with an index and a tiebreaker. The organizer's order list is where Stagedoor learned the difference, on the night an export was "missing orders" that were in the database the whole time.

The three features of this topic, pagination, filtering and sorting, are one feature seen from three sides: which rows, in what order, starting where. Each one is a query the database will run 3,000 times a second at on-sale, and the API should offer only the versions of it that the indexes can answer. Every parameter the client can send is a query plan the service has committed to, whether or not anyone looked at it.

Why Offset Lies

OFFSET 20000 LIMIT 50 is position-based. It asks for the rows at positions 20,001 to 20,050 in the sorted result, and positions move. An order inserted before position 20,000 between two requests shifts every later row down by one, so page 401 begins with the row that ended page 400, and the client shows it twice. A refund that deletes a row, or a filter that stops matching one, shifts them up, and a row is skipped that no page will ever show. The client cannot detect either case, because each page is internally consistent; only the pair of pages disagrees, and the client never holds both.

The cost is the other half. Postgres has no way to find position 20,000 except by producing the 20,000 rows before it and discarding them, so the work per page grows with the page number. Page 1 of the order list reads 50 rows; page 400 reads 20,050 to return 50, and the organizer's dashboard that pages to the end reads the table's rows in a triangular sum. PostgreSQL Deep Dive, Chapter 9, has the planner's view of it; from the application's side the shape is enough: the deeper the page, the slower it gets, on a table that only grows.

The Cursor

A cursor page returns an opaque next_cursor that encodes the sort key of its last row, and the next request asks for the rows after that key. Nothing is positional, so an insert or a delete elsewhere in the table changes nothing about where the next page starts. And the query is an index range scan that reads exactly the fifty rows it returns, at page 1 and at page 4,000 alike.

The keyset query behind GET /orders: a range on the index, at any depth

-- index: (event_id, created_at DESC, id DESC)
SELECT public_id, status, total_cents, created_at
FROM   orders
WHERE  event_id = $1
AND    (created_at, id) < ($2, $3)      -- the cursor: last row's key on the previous page
ORDER BY created_at DESC, id DESC
LIMIT  51;                              -- one extra row: if it exists, has_more is true

The query asks for the orders of one event whose key sorts before the key of the last row the client saw, in the same order the index is built in, fifty at a time. The comparison is on the pair of created_at and id, not on created_at alone, and the pair is what makes the cursor correct: two orders created in the same second have the same timestamp, and if the page boundary fell between them a cursor on the timestamp alone would either repeat both or skip both. The id breaks the tie, because it is unique, so every row has a distinct position in the order and a boundary can fall between any two. The 51st row is fetched and not returned; its existence is the has_more flag, and it costs one index step instead of a count.

The Sort Key Is the Cursor's Contract

The cursor works only on the order the query sorts by, because it encodes a position in that order. That is the stricter contract, and the book states it instead of pretending it away: a sortable field is one with an index in that order and a unique tiebreaker beside it. Stagedoor's order list sorts by creation time, newest first, and nothing else. "Sort by any column" is an offset feature, and it was an offset feature that produced a full sort of 184,233 rows per page the first time an organizer clicked the title column. A second sort order is a second index and a second cursor encoding, added on purpose when a screen needs it and paid for on every insert from then on.

Two ways to page, and what each one promises

Offset?page=400

Jump to any page, sort by anything. Reads 20,050 rows to return 50. Repeats and skips rows under concurrent writes, and the client cannot tell.

Cursor?cursor=eyJ...

Next and previous only, sorted by an indexed key with a tiebreaker. Reads 51 rows at any depth. Correct while the table changes underneath it.

has_moreinstead of total

One extra row fetched and dropped. A count of the filtered set is 90 percent of the query's cost and is shown in grey.

Filtering

?status=paid&event_id=8812 arrives as typed query parameters through the request model of Topic 14: status is the enum, event_id is a positive integer, and anything else is a 422. Each accepted filter maps to a predicate on an indexed column, and the set of filters the API offers is the set of predicates the indexes can serve. A filter on an unindexed column is a full scan that gets slower every month, and offering it in the API is a promise the database cannot keep at on-sale. The organizer's list filters by event, by status and by a date range on created_at, because those are the three the composite index covers; a filter by buyer email is a search, not a filter, and it is a different endpoint with a different index behind it.

Counts Are Expensive

total: 184233 on every page requires counting the whole filtered set on every page, and the count is a scan of everything the filter matches, which on the organizer's list is the whole order history of the event. The page returned fifty rows in two milliseconds and spent forty more counting rows it did not return, so the dashboard could show a number in grey that nobody reads. The book returns has_more by default and offers the number separately: GET /orders/count with the same filters, cached for a minute in Redis under Chapter 9's rules, for the one dashboard widget that wants it. A count that is sixty seconds stale is fine on a dashboard and unaffordable on every page.

Page Size and Limits

The default page is 50 rows and the maximum is 200, enforced at the edge with a 422 for anything above it. A client that wants everything pages; that is the contract, and a client that cannot page is a client that will eventually ask for 100,000 rows in one response and find out what the instance's memory limit is. The organizer's CSV export, which does want every order, is not a ?limit=1000000. It is a job of Chapter 8: the request returns 202 with a status URL, the worker pages through the cursor at 200 rows a step, writes the file, and emails a link. The API has one shape for a page and one for a bulk export, and the second never runs inside a request.

Offset vs Cursor

Offset supports jumping to page N and sorting by any column. It costs the database a number of rows proportional to the offset on every request, and it is wrong under concurrent writes: rows repeat and rows vanish, and the client cannot detect either. Use it for a small, static admin table where "page 7 of 12" is the feature and nothing is inserting.

Cursor supports next and previous only, sorted by an indexed key with a unique tiebreaker. It costs one page of rows at any depth and it is correct while the table changes underneath it. Every public list that changes, orders, events, tickets, gets a cursor, and the sort orders it offers are the indexes it has.

Common Mistakes

Offset on a live table — rows are duplicated and skipped between pages while buyers check out, the client cannot detect it, and the support ticket says "the export is missing orders" that were in the database the whole time.
A cursor without a tiebreaker — two orders created in the same second sit on either side of a page boundary, and a cursor on the timestamp alone shows both twice or neither at all.
Offering sort on every column — the first ?sort=title from an organizer with 184,233 orders is a full sort per page, on every page, with no index to help.
total on every page — the count is 90 percent of the query's cost, it scans the whole filtered set to produce it, and the client renders the number in grey.
No maximum page size — one client asks for 100,000 rows, the response is built in memory, and the instance's memory limit is the only thing that stops it, on both instances, at once.
A filter on an unindexed column — the API promised a predicate the database answers with a full scan, and the endpoint gets slower every month until the on-sale when it does not answer at all.

Best Practices

Use cursor pagination on every list that changes, keyed on a composite sort key with a unique tiebreaker and backed by an index in the same order.
Offer only the sorts and filters the indexes support, as typed query parameters through the request model, and reject the rest with a 422.
Return has_more from one extra fetched row by default, and serve counts from a separate endpoint cached for a minute.
Cap page size at 200 at the edge and route every bulk export to a worker job that pages through the same cursor.
Add a second sort order only with its own index and its own cursor encoding, when a screen needs it, and charge the insert cost knowingly.

Comparable toolsRelay connection spec GraphQL's cursors, the same idea with edgesStripe starting_after, GitHub Link headers: public cursor APIsDjango CursorPagination, Spring Data keyset scrolling: the framework supportPostgreSQL Deep Dive Chapter 9, the planner's view of OFFSET

Knowledge Check

An organizer pages through orders with ?page=400 while buyers are checking out. Why does the client see a row twice?

An insert before the offset shifts every later row by one position
The replica served page 401 from a snapshot older than the one for page 400
Postgres returns the rows in a different physical order on each request
The seat-map cache in Redis served a stale copy of the order list

The cursor compares the pair (created_at, id) rather than created_at alone. What goes wrong without the id?

The index cannot be used, so every page becomes a full scan of the event's orders
The cursor cannot be encoded, because a timestamp alone is not a valid opaque value
Two orders created in the same second straddle a page boundary and one is repeated or lost
The list can only be sorted ascending, because a descending cursor needs an integer key

What does OFFSET 20000 LIMIT 50 cost the database compared to a cursor at the same depth?

The same 50 rows, plus one seek to position 20,000 that the index answers in constant time
20,050 rows read and 20,000 discarded, against 51 rows read for the cursor
A count of the whole table first, then 50 rows, against a count of the page for the cursor
The same work, because the planner rewrites a deep offset into a keyset range internally

Why does Stagedoor return has_more on every page and serve total only from a separate cached endpoint?

Because a count under concurrent inserts is never accurate, so it is only reported approximately
Because total does not fit the Problem Details shape, and the count endpoint returns a plain number
Because a cursor response cannot carry a total, since the cursor already encodes the row's position
Because counting the filtered set costs far more than the page itself, and one extra row answers has_more

You got correct