Definition
- OFFSET cost –
LIMIT n OFFSET mforces the database to read and discard allmpreceding rows before returning the page, so cost grows as O(m). - Keyset pagination –
WHERE id > :last_seen ORDER BY id LIMIT nuses an index seek to jump directly to the start of the page, so cost is O(log n) at any depth. - Stability – OFFSET shifts under concurrent inserts (duplicates or skips); keyset is anchored to a real key.
- Trade-off – keyset gives next/previous navigation, not arbitrary jump-to-page-N.
- Composite cursor – for multi-column ordering, use a row-value comparison like
(created_at, id) > (:last_ts, :last_id).
Rajesh wants page five hundred of his transaction history at National Bank of India. With OFFSET, the clerk counts past ten thousand transactions one by one and throws them away just to hand over the next ten. With keyset, Rajesh says "continue from the last transaction I saw," and the clerk uses the index to jump straight there: just as fast on page five hundred as on page one.
Understanding the Concepts
Why does OFFSET get slower on deep pages?
The database cannot magically start at row ten thousand. It must produce the sorted stream, count through the first m rows, discard them all, and only then emit the next n.
-- Page 1: fast (discard 0 rows)
SELECT * FROM transactions
ORDER BY txn_id
LIMIT 10 OFFSET 0;
-- Page 1000: slow (discard 9990 rows)
SELECT * FROM transactions
ORDER BY txn_id
LIMIT 10 OFFSET 9990;
-- The DB reads and throws away 9990 rows every time this page is requested
Page depth vs response time (OFFSET):
Page 1: 2 ms (discard 0 rows)
Page 100: 45 ms (discard 990 rows)
Page 1000: 380 ms (discard 9990 rows)
Page 10000: 3800 ms (discard 99990 rows)
Cost grows linearly: O(offset)
How does keyset pagination work?
Instead of skipping rows, remember the sort key of the last row shown and ask for everything after it.
-- First page
SELECT * FROM transactions
WHERE account_id = 1001
ORDER BY txn_id
LIMIT 10;
-- Returns txn_id: 101, 102, ..., 110
-- Last seen: txn_id = 110
-- Next page (keyset)
SELECT * FROM transactions
WHERE account_id = 1001
AND txn_id > 110 -- seek past the last seen key
ORDER BY txn_id
LIMIT 10;
-- Index seek to txn_id > 110, read 10 rows
-- Same speed on page 1 or page 10000
Why is keyset O(log n)?
If txn_id is indexed, the database performs a B-tree descent to find the entry just after the cursor value and reads forward. It never touches the preceding rows.
B-tree index on txn_id:
┌───────┐
│ 500 │
└───┬───┘
┌─────┴─────┐
│ │
┌──▼──┐ ┌──▼──┐
│ 200 │ │ 800 │
└──┬──┘ └─────┘
│
┌──▼──┐
│ 110 │ ◄── seek here for txn_id > 110
└──┬──┘
│
Read next 10 leaf entries: 111, 112, ..., 120
Cost: O(log n) tree descent + O(page_size) leaf read
Same cost at any depth!
How does OFFSET behave under concurrent inserts?
Inserting rows while a user paginates shifts everything.
Offset pagination with concurrent inserts:
Page 1: rows 1-10
-- New row inserted at position 5 --
Page 2: rows 11-20
Row 10 appears AGAIN on page 2! (duplicate)
Keyset pagination with concurrent inserts:
Page 1: rows 1-10, cursor = id 10
-- New row inserted --
Page 2: WHERE id > 10
New rows after id 10 appear naturally, no duplicates
How do you handle multi-column ordering?
For ordering by a timestamp with an id tie-breaker, use a composite cursor.
-- Composite cursor: (created_at, txn_id)
SELECT * FROM transactions
WHERE account_id = 1001
AND (created_at, txn_id) > ('2026-06-15 10:00:00', 500)
ORDER BY created_at, txn_id
LIMIT 10;
This requires a composite index:
CREATE INDEX idx_txn_acct_date_id
ON transactions (account_id, created_at, txn_id);
How do you implement keyset pagination in Java?
Rajesh implements cursor-based pagination for the transaction history API at National Bank of India.
package com.bank.repository;
import java.sql.*;
import java.util.List;
import java.util.ArrayList;
public class TransactionRepository {
public record TransactionPage(
List<Transaction> items, Long nextCursor
) {}
public TransactionPage getPage(Connection conn, long accountId,
Long afterTxnId, int pageSize)
throws SQLException {
String sql;
if (afterTxnId == null) {
sql = "SELECT txn_id, amount, created_at FROM transactions "
+ "WHERE account_id = ? ORDER BY txn_id LIMIT ?";
} else {
sql = "SELECT txn_id, amount, created_at FROM transactions "
+ "WHERE account_id = ? AND txn_id > ? ORDER BY txn_id LIMIT ?";
}
List<Transaction> items = new ArrayList<>();
try (PreparedStatement ps = conn.prepareStatement(sql)) {
int idx = 1;
ps.setLong(idx++, accountId);
if (afterTxnId != null) {
ps.setLong(idx++, afterTxnId);
}
ps.setInt(idx, pageSize);
try (ResultSet rs = ps.executeQuery()) {
while (rs.next()) {
items.add(new Transaction(
rs.getLong("txn_id"),
rs.getBigDecimal("amount"),
rs.getTimestamp("created_at")
));
}
}
}
Long nextCursor = items.isEmpty() ? null
: items.get(items.size() - 1).txnId();
return new TransactionPage(items, nextCursor);
}
public record Transaction(
long txnId, java.math.BigDecimal amount, Timestamp createdAt
) {}
}
How does the API expose the cursor?
package com.bank.controller;
import org.springframework.web.bind.annotation.*;
@RestController
@RequestMapping("/api/accounts/{accountId}/transactions")
public class TransactionController {
@GetMapping
public TransactionRepository.TransactionPage listTransactions(
@PathVariable long accountId,
@RequestParam(required = false) Long after,
@RequestParam(defaultValue = "20") int pageSize) {
return txnRepo.getPage(conn, accountId, after, pageSize);
}
// Client calls: GET /api/accounts/1001/transactions?after=500&pageSize=20
}
What is the trade-off of keyset pagination?
Keyset gives next/previous navigation, not arbitrary jump-to-page-500. For infinite-scroll feeds, transaction histories, and APIs, that is exactly what you want.
| Feature | OFFSET | Keyset |
|---|---|---|
| Deep page speed | O(offset) | O(log n) |
| Concurrent insert stability | Duplicates/skips | Stable |
| Jump to page N | Yes | No (next/prev only) |
| Implementation | Simple | Requires cursor tracking |
| Best for | Small datasets, admin UI | Large datasets, APIs, feeds |
What should a senior engineer know?
- The cursor must be on a unique, ordered column or a unique composite.
- A composite index matching the cursor columns is required for efficient seeks.
- For descending order, use
WHERE (created_at, id) < (:last_ts, :last_id)andORDER BY created_at DESC, id DESC. - Consider encoding the cursor as an opaque base64 token so clients cannot tamper with it.
- GraphQL and Relay connections use this pattern with
afterandfirstparameters.
Visual Overview
OFFSET pagination: Keyset pagination: SELECT ... LIMIT 10 OFFSET 9990 SELECT ... WHERE id > 110 LIMIT 10 ┌──────────────────────┐ ┌──────────────────────┐ │ Read row 1 │ │ B-tree seek to 110 │ │ Read row 2 │ │ Read row 111 │ │ ... │ │ Read row 112 │ │ Read row 9990 │ │ ... │ │ (all discarded!) │ │ Read row 120 │ │ Return rows 9991-10000│ │ Return rows 111-120 │ └──────────────────────┘ └──────────────────────┘ Cost: O(9990) Cost: O(log n + 10) Slow on deep pages Same speed at any depth
Key Takeaway
Offset pagination gets slower on deep pages because the database cannot skip ahead. For LIMIT 10 OFFSET 10000, it must read and discard all ten thousand preceding rows before returning the next ten. That waste grows linearly with the offset, so page one is instant but page one thousand crawls.
Keyset pagination fixes this by replacing the offset with a WHERE condition on the last-seen key. Instead of skipping rows, the database performs a B-tree seek directly to the cursor and reads only the page. The cost is O(log n) at any depth, identical whether on page one or page one million.
The cursor must be on a unique, ordered column or a unique composite, backed by a matching index. The trade-off is that keyset gives next/previous navigation rather than arbitrary jump-to-page-N, which is exactly right for transaction histories, feeds, and APIs. Keyset also handles concurrent inserts correctly because it is anchored to a real key rather than a row count.
At the National Bank of India, Rajesh's multi-year transaction history loaded instantly on the first pages but stalled for seconds once he scrolled deep. Replacing offset with keyset pagination anchored on the transaction id pair made deep pages as fast as the first page.
Remember one sentence: OFFSET re-reads everything before the page while keyset seeks straight to it, so keyset stays fast at any depth.
---