Case: Implement Pagination
A hundred products fit on one page; ten thousand do not; ten million change the algorithm. Pagination derived from "show a slice of a list" — slice an array, then LIMIT / OFFSET, then a cursor — with the trigger for each level named.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
The product list is getting long and someone says "add pagination". What is pagination as a concept, and how do you know which of its three well-known mechanisms the current version justifies?
The catalog page renders every product in one list. It is fine today. You have been told it will not be fine, and every article you open argues that offset pagination is wrong and cursors are right, without saying at what size that becomes true for you.
Implement cursor pagination because the articles say it is the correct one. Base64 an id, add after and limit parameters, teach the frontend to keep the cursor — the full thing, so it never has to be redone.
A day later there is a cursor scheme, and the catalog has a hundred products that fit on one page. Nothing was measured; the decision was made on vocabulary, and the cursor cannot do the one thing the founder asked for: "jump to page 7".
- A day later there is a cursor scheme, and the catalog has a hundred products that fit on one page. Nothing was measured; the decision was made on vocabulary, and the cursor cannot do the one thing the founder asked for: "jump to page 7".
- The concept was never stated, so "page" means three different things in three places: an index in the URL, an offset in the query and a chunk in the component. The bug "page 2 shows one product from page 1" has no definition to check against.
- The rules — page size has a maximum, an out-of-range page is empty not an error, the order must be stable for the pages to be disjoint — were never written, so the first one discovered (unstable order) is discovered as a duplicate row on a scrolled list.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Define pagination as a concept: given an ordered collection and a position, return a bounded slice and enough information to ask for the next one. Two words carry everything — "ordered" and "position" — and each mechanism is a different answer to what "position" means.
- Derive the state and find that pagination has almost none of its own: the collection belongs to the catalog; the position belongs to the request. The one thing pagination must own is the ordering, because two pages from different orders are not pages of the same list.
- Write the rules and the examples at three sizes. At a size where the whole list fits in memory, position is an index and the slice is an array operation. When the list lives in a database, position is an offset and the database does the slicing. When the offset itself costs a scan or the list changes under the reader, position becomes a cursor — the last seen key.
- Annotate what each level costs and name the reading that moves you up: the array slice is O(page) after O(n) to load; OFFSET is O(offset + page) in the database; a keyed cursor is O(page) with an index. Climb when the reading, not the article, says so (Complexity, Annotated Not Asserted).
Meaning and state — what "position" means changes with the level
Pagination owns almost no state: the ordering and the maximum page size. Everything else is borrowed. The ordering is where the rules live, and it is where the derivation earns its keep: "order by name" is not an order when two products share a name, and pages from a non-total order can overlap. The rule below is the one that keeps the pages disjoint.
The decomposition splits the concept into the parts that stay fixed across every mechanism and the one part — position — that each mechanism reinterprets.
- └A total ordering— without it pages overlap or skiptestable Sorting the same data twice gives the same sequence; two products with equal names appear in id order.
- └A bounded page sizetestable size 0 and size above the maximum are rejected; size at the maximum returns exactly that many when available.
- ├A position— the part each mechanism reinterprets
- └Index into an in-memory arraytestable page(index 10, size 10) returns products[10..20) of the sorted array.
- └Offset in a database querytestable LIMIT 10 OFFSET 10 under the same ORDER BY returns the same ten products as the array oracle.
- └Key of the last item seentestable page(after = last key) returns the ten items that sort after it, and does so even when a product was inserted before that key.
- └A "next" answertestable A full page returns a next position; a short or empty page returns none.
The oracle test is the leaf that ties the levels together: every mechanism must produce the same pages as the array slice on the same ordered data.
rule The ordering used to slice the collection is the same for every page and never places two items at the same position.
↓ becomes validation Sort by the chosen key and then by a unique tiebreak (the id); reject a page request that changes the ordering between pages.
order = by (product.name, product.id) -- id breaks ties; the order is total page n and page n+1 are computed under the same order
Examples, the four-line slice, and the trace
The array slice is the concept with nothing else in the way. It is also the oracle: whatever the database does at ten thousand products, it must produce the pages that this function produces on the same sorted data. Keep it; it is a test, not a draft.
The state change shows what the operation changes — which is nothing in the collection, and one thing in the caller's hand: the position. Pagination is a read; a version that mutates the collection has the concept wrong.
sorted = [p0 … p99]; caller holds position 10
sorted unchanged; caller holds items [p10 … p19] and position 20
- inputsorted has length 100; index = 100, size = 10
- lookupslice [100 .. min(110, 100)) → the empty range
- branchindex + size < length? 110 < 100 is false → next = none
- mutationnone
- output{ items: [], next: none } — an empty page, not an error; the client stops asking
1function page(sorted, index, size):2 if size <= 0 or size > MAX_PAGE: reject "bad page size"3 items = sorted[index .. min(index + size, length(sorted)))4 next = index + size if index + size < length(sorted) else none5 return { items, next }O(size) after the sort; the sort is O(n log n) once. The cost is loading and sorting n — which is the reading that moves the list into the database.
The ladder, each rung with its reading
Three mechanisms, three definitions of position, and a trigger between each pair. The ladder is what the articles omit: not which mechanism is best, but what has to be observed before the next one is justified. The whyLadder in the search case did the same for engines; here it is the ladder itself that carries the reasons.
The API shape follows the mechanism, and the API is a contract clients will depend on — which is the strongest argument for choosing carefully, and the reason the cursor camp has a real case (Pagination: Choosing How Lists End and Cursor Pagination: An Opaque Bookmark, Not a Position in APIs).
- A hundred products — slice an arrayLoad all, sort once, slice by index; the function above. — The list fits in memory and loads faster than it renders; anything more is a mechanism without a reason.
- Ten thousand — LIMIT / OFFSETThe database sorts and slices under the same ORDER BY with the tiebreak; page numbers and a total are available. — Loading ten thousand rows to show ten costs more than asking for ten; the array slice becomes the oracle test (Offset Pagination: Simple, Jumpable, and Lying Under Writes in APIs; Pagination That Survives a Large Table in Backend).
- Ten million — keyed cursor
WHERE (name, id) > (?, ?) ORDER BY name, id LIMIT ?, with a composite index on (name, id); the cursor is the last key seen. — A deep OFFSET has been measured scanning offset rows before returning any, or rows inserted while reading have been observed shifting between pages (Composite Indexes and the Leftmost-Prefix Rule in Database). - Either mechanism, chosen by productOffsets where "jump to page n" and a total are requirements; cursors where stability under change is; sometimes both on different screens. — The last decision is not about size at all; it is about what the screen has to let a person do.
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Pagination = A way of handing a long ordered list to a reader in bounded pieces, such that walking every piece visits each item once.
- Does a page have identity? No. A page is a view, not a thing: page 3 today and page 3 after an insert are different sets of items with the same label. What has identity is the position in the list — and that is the difference between an offset and a cursor.
- Who owns it? The reader. Two readers on the same list hold different positions; the list itself belongs to whoever owns the items and knows nothing about pages.
- How long does it exist? One page request — unless the reader is walking the whole list, in which case the position must survive between requests, which is exactly what a page token is for.
- Should it survive reload? The position should be shareable as a URL — ?page=3 or ?after=token — so that a reload lands where the reader was. Whether the items under that position are still the same is the concurrency question, not the identity question.
- Does it depend on the order of the list? Entirely. Pagination without a total order is undefined: two requests for the same page can return different items even with no writes. The sort key is part of the concept, not a detail.
- itemsordered collectionkeepThe thing being paged; the concept only reads it.
- orderBya total order — a key that is unique per itemkeepWithout a deterministic order, "the next page" means nothing.
- pageSizeinteger, 1 ≤ size ≤ maxkeepHow many items a reader gets at once; bounded so a client cannot ask for everything.
- pageNumberinteger ≥ 1dependsThe reader's position, as the naive design expresses it.
- cursoropaque token encoding the last seen sort keydependsA position that stays put when the list changes.
- totalCountintegerderiveThe UI wants "page 3 of 12".
- hasMorebooleanderiveThe reader must know whether to ask again.
- read Page by number — the items at positions (pageNumber − 1) × size … pageNumber × size − 1, and whether more exist
- read Next page by cursor — the next size items after the cursor, and the cursor for the page after
- read Count — the number of items, from which "page 3 of 12" follows
- • Pages never overlap.
- • An item is never skipped or repeated when the list changes between requests.
- • The order is total.
- • Page size is bounded.
- • A page past the end is empty, not an error.
How to do it
Most important first.
- Write the meaning and underline "ordered" — then write the ordering down as a rule with a tiebreak, because "order by price" with equal prices is not an order and pages from it overlap.
- Challenge the state: the collection (belongs to the catalog), the position (belongs to the request), the page size (an input with a maximum — a rule), the total count (depends — offset pagination can show it, cursors usually cannot, and it costs a count query).
- Write the operation: page(collection, position, size) → items plus a "next position" or nothing. Write its errors: size ≤ 0, size above maximum; and its non-errors: a position past the end returns an empty page (Normal, Edge, Invalid).
- Write examples at each size: a hundred products, page 2 of 10; ten thousand, offset 9,990 of 10; ten million, after the last key you saw.
- Implement the array slice first — it is the whole concept in four lines and it is the test oracle for the later mechanisms: for any size, page(db) must equal page(array) on the same ordered data.
- Write the trigger for each next level next to the level, and measure before moving (Measure Before You Optimize).
Worked on a concrete problem
The move has to produce something. This is what it produced.
- Meaning: a bounded slice of an ordered collection plus a way to ask for the next slice. State owned by pagination: the ordering rule (name, then id as tiebreak) and the maximum page size. Not owned: the products, the requested position.
- Rules: page size is between one and the maximum; consecutive pages are disjoint and together cover the list — which is only true if the order is total and stable; a position past the end is an empty page, not an error; the ordering used for page n is the ordering used for page n + 1.
- Examples, a hundred products: page(products, index 10, size 10) → products[10..20) and next = 20; page(products, index 100, size 10) → [] and next = none; page(products, index 0, size 0) → rejected. Ten thousand: the same examples against LIMIT 10 OFFSET 10; ten million: page(after = "mouse-4711", size 10) → the ten products whose (name, id) sorts after that key.
- Trigger readings, written next to the levels: the array slice stops when loading the whole list costs more than the render — the list has moved to a database. OFFSET stops when a deep page is measurably slower than a shallow one, or when a product inserted while the shopper reads pushes a row from page 3 onto page 4. The cursor is what remains.
- The array slice, four lines of pseudocode, became the oracle: a test generates a thousand products, pages them by array slice and by database query with the same ordering, and asserts the two sequences of pages are identical. The oracle caught the tiebreak bug — equal names, unstable order — before any user did.
How you know it worked
What now exists that did not before, and what question you can now ask.
- The ordering is written down with a tiebreak, and the "pages are disjoint" rule is a test rather than an assumption.
- You can say what "position" means in your current version — index, offset or key — and what it will mean in the next one.
- The array slice exists and is used as the oracle for the database version.
- You can name the reading — deep-page latency, rows shifting between pages — that would move you to a cursor, and you have not moved before seeing it.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?What is the ordering, and does it have a tiebreak that makes it total?
- ?What does "position" mean in this version — an index, an offset, or a key?
- ?What does a page cost at today's size, and which reading would say the mechanism is no longer enough?
- ?Can the array slice serve as the oracle for the database version — and does it?
- ?Does the product need "jump to page n" — the requirement that decides between offset and cursor more than size does?
What can go wrong
- The cursor is built first, on vocabulary, and "jump to page 7" — a requirement offset pagination gives for free — has to be re-implemented on top of it.
- The offset version is kept past the reading: page 900 takes seconds, the trigger was never written down, and the product team learns about it from an analytics dashboard nobody opens.
- The ordering is left implicit ("whatever the database returns"), and the pages overlap or skip on the first day the table has a concurrent insert.
- Starting with the array slice means one certain rewrite when the list moves to a database — mitigated by the slice becoming the test oracle rather than being thrown away.
- Offset pagination gives page numbers and a total; cursors give stable pages under change; neither gives both, and the choice is a product decision the derivation surfaces but cannot make.
- A total ordering with a tiebreak needs an index over both columns once the data is in a database — an index that exists only for pagination.
- "Offset pagination is wrong." It is O(offset + page) and unstable under inserts, which is wrong at some sizes and rates and exactly right at others; the article that says "wrong" without a size is a slogan, and this lesson makes it falsifiable.
- "Pagination is a frontend concern." The frontend renders pages; the ordering and the slicing must happen where the data is, or the frontend loads ten million rows to show ten (Pagination From the Interface Backwards in Frontend covers the rendering half).
- "A cursor is an encoded offset." A cursor is a key — the last item you saw — and that is why pages after it are stable when rows are inserted before it. Encoding an offset as a cursor gives cursor syntax with offset behaviour.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- ILLUSTRATIVEA hundred, ten thousand and ten million products, page size 10, the key "mouse-4711" and the thousand-product oracle test are invented for the shape of the argument; the crossover points are measurements.
- SCALE-SPECIFICThe array slice is right while the list fits in memory and loads faster than it renders; OFFSET is right while deep pages are not measurably slower and rows do not shift between pages; the cursor is right after either reading — and the lesson says so at each level.
- CONTESTEDMany practitioners argue for cursor pagination from the first version on the grounds that offset pagination is never stable under concurrent writes, that the rewrite is expensive once clients depend on page numbers, and that a cursor API is barely harder to build; the strongest form of that view is that stability is a correctness property and not a scale property. The lesson's answer is that "jump to page n" and a visible total are product requirements offsets serve and cursors do not, so the choice is not purely technical.
Where the depth lives
This domain asks the question and hands the answer off by name.