Pagination Optimization

Hook: Pagination looks harmless until the table gets big; then the database has to “skip a mountain to read a few rows.” Interviewers love this because it tests indexing, ordering, and real-world performance all at once.

Question: How do you optimize pagination in SQL so it stays fast and correct on large tables?

Answer: The main trick is to avoid large OFFSET values on big tables. OFFSET/LIMIT is easy to write, but the database still reads and discards the skipped rows, so deep pages get slower and slower. A faster pattern is keyset pagination (also called seek pagination), where you use the last row from the previous page as a cursor and ask for “rows after this point” using the same sort columns plus a unique tie-breaker.

Interview-Ready Answer: I optimize pagination by using a stable ORDER BY and a composite index on the sort columns, then prefer keyset pagination over large OFFSETs. With keyset pagination, I pass the last row’s sort values as a cursor, so the database can seek directly to the next page instead of scanning and discarding thousands of rows. I still use OFFSET for small tables or rare admin screens, but for high-traffic feeds and catalogs, keyset pagination is usually the better choice because it keeps page latency roughly constant.

What pagination really costs

Pagination is not just about showing fewer rows. The database still has to find the correct slice of the sorted result set. If the sort order is not indexed well, it may sort a large set first; if you use a large OFFSET, it may walk past many rows before returning anything useful.

Offset pagination vs keyset pagination

How keyset pagination works under the hood

1. The client asks for the first page with a clear order, such as ORDER BY created_at DESC, id DESC.
2. The database uses a B-tree index if available. A B-tree is a sorted tree structure that lets the engine jump close to the right place quickly.
3. The query returns the first LIMIT rows in that order.
4. The application stores the last row’s sort values as a cursor, for example (created_at, id).
5. For the next page, the query asks for rows < that cursor in the same order, again with LIMIT.
6. The engine can seek near the cursor and read only the next handful of rows instead of scanning everything before them.

That is why keyset pagination usually feels fast even when the table grows. The amount of work stays close to the page size, not the page number.

Why the index matters

For fast pagination, the ORDER BY and the index should agree. A good default pattern is an index that starts with the sort columns and ends with a unique tie-breaker such as id. The tie-breaker matters because many rows can share the same timestamp or score. Without it, the order is not fully deterministic, and rows can jump between pages.

For example, if you sort by created_at DESC only, two rows with the same timestamp may appear on different pages in one request and then swap order on the next request. Adding id DESC makes the order stable.

When to use each approach

• Use OFFSET/LIMIT when the dataset is small, the page count is shallow, or the UI truly needs “go to page 17.”
• Use keyset pagination for endless feeds, search results, order histories, and anything that must stay fast under load.
• If the product needs total pages, be careful: COUNT(*) on a huge table can also be expensive. Many systems cache counts or show an approximate number instead.

Performance notes and realistic numbers

• OFFSET 100000 LIMIT 20 can force the database to walk past 100,000 rows just to return 20. That is why deep pages get slower.
• Keyset pagination is typically closer to O(limit) after the index seek, while OFFSET behaves like O(offset + limit).
• If the sort is not indexed, the database may sort many rows first, which can become O(n log n) work.
• Extra memory is usually small for both patterns, but a bad sort can spill to disk if the working set is large.

Important edge cases

• Duplicate sort values: always add a unique tie-breaker like id.
• Mutable sort columns: if you paginate by updated_at, rows can move between pages as they change.
• Inserts and deletes: offset pages can shift under your feet, causing duplicates or missing rows when data changes between requests.
• Backward paging: often implemented by reversing the sort order and using the first row of the current page as the cursor.
• Random page jumps: keyset is great for “next/previous,” but not ideal if users must jump directly to page 500.

Memory model: Offset pagination is “start from the front and count.” Keyset pagination is “open the book to the bookmark.” That is the mental picture to remember in an interview.

Real-World Example: Imagine an e-commerce product catalog with millions of items. The home page shows the newest products first, and users keep scrolling. At first, LIMIT 20 OFFSET 0 works fine. But once users reach deeper pages, the API starts taking seconds because each request makes the database skip more and more rows.

A production fix is to sort by created_at DESC, id DESC, add the matching index, and return a cursor with the last item on each page. The app then asks for “the next 20 products after this cursor,” which keeps response times stable even as the catalog grows.

What goes wrong: A common outage is a feed endpoint using OFFSET 50000 during a traffic spike. The database CPU climbs, slow query logs fill with the same pagination query, and the app begins timing out with 504 errors. Users see spinning loaders, missing items, or repeated products because the order is not stable or the offset shifts when new rows are inserted.

Follow-up & Tricky Questions:

• Why is OFFSET slow even with an index? Because the database still must walk past the skipped rows to reach the requested page. The index helps find rows in order, but it does not magically make “skip 100,000 rows” free.
• When is OFFSET pagination acceptable? It is fine for small tables, admin tools, or rare pages where the dataset is tiny and page jumps matter more than speed. The key is that the cost must stay low enough for the expected data size.
• How do you paginate backward? Reverse the sort direction and use the first row of the current page as the cursor, then flip the results back in the application if needed. This keeps the same index-friendly pattern.
• What index should you create? Usually a composite index on the sort columns plus a unique tie-breaker, such as (created_at DESC, id DESC). That gives the optimizer a path that matches the order you ask for.
• How do you show total pages? Either run COUNT(*), cache the count, or show an approximate total. On very large tables, counting everything on every request can be as expensive as the page query itself.
• Gotcha: Is keyset pagination always better? No. It is better for sequential browsing, but it is not ideal when users need to jump to an arbitrary page number. The right answer depends on the UI.
• Gotcha: Can I sort by a non-unique column only? Not safely. If the sort key is not unique, rows with the same value can repeat or disappear between pages. Add a tie-breaker so the order is total and stable.
• Gotcha: What if rows change between requests? Then offset pagination can shift badly, and keyset pagination can still move rows if you sort by a mutable column. For highly dynamic data, prefer an immutable ordering key or a consistent snapshot when possible.

Common Mistakes:

• Using large OFFSETs for everything. Fix: Switch to keyset pagination for deep browsing and hot paths.
• Sorting by a non-unique column only. Fix: Add a unique tie-breaker like id so the order is deterministic.
• Forgetting the matching index. Fix: Index the same columns used in ORDER BY and cursor comparison.
• Ignoring data changes between requests. Fix: Expect inserts, deletes, and updates to shift pages; design the API around stable cursors.

Memory Hook: OFFSET is a librarian counting from the front of the shelf; keyset is a bookmark that opens right where you left off.

Cheat Sheet:

• OFFSET/LIMIT is simple but gets slower as the offset grows.
• Keyset pagination uses the last row as a cursor.
• Always include a unique tie-breaker in the sort order.
• Create a composite index that matches the paging order.
• Use COUNT(*) carefully; it can be expensive on huge tables.
• Best use case: feeds, search results, and endless scrolling.

Practice Tasks:

1. Rewrite a query that uses OFFSET 1000 into keyset pagination using a cursor.
2. Add a tie-breaker to a non-deterministic sort and test how the results change.
3. Compare the query plan for a paginated query before and after adding the matching index.