Beyond OFFSET: Keyset Pagination in PostgreSQL That Actually Scales

Posted on

Offset pagination is the first thing everyone learns and the first thing that falls over in production. The product manager asks for infinite scroll, someone writes LIMIT 20 OFFSET 40000, and six months later the reviews endpoint takes two seconds and the database is spending most of its CPU throwing away rows nobody will ever see. The fix — keyset (cursor) pagination — is well known but rarely implemented well. Done right, it’s stable under concurrent inserts, uses indexes all the way down, and survives schema evolution. Done wrong, it silently breaks sorting or returns the same page twice.

This post walks through both strategies in PostgreSQL, why offsets degrade linearly, how to build a robust multi-column keyset cursor, and the edge cases — filtering plus sorting, NULLs, and API design — that determine whether your cursor scheme survives contact with a real product.

Why OFFSET Degrades

OFFSET doesn’t seek — it walks. OFFSET 100000 LIMIT 20 makes the planner produce (at least conceptually) 100,020 rows and discard the first 100,000. With an index, each page costs O(offset); total pagination over N rows costs O(N²/page_size). The canonical reference on LIMIT behavior is the PostgreSQL LIMIT clause documentation, and the cost shows up immediately in EXPLAIN:

EXPLAIN ANALYZE
SELECT id, created_at, title FROM orders
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 100000;

On a ten-million-row table, that query reads over a hundred thousand index entries plus heap fetches and throws nearly all of them away. Worse, OFFSET is unstable under concurrent writes: insert ten new rows at the top between page fetches, and every subsequent page shifts — the user sees duplicates and misses records entirely. For a feed UI, that’s the bug users report as “the app showed me the same post twice.”

OFFSET is still the right choice in narrow cases: small, bounded datasets (admin tables with a few thousand rows), and jump-to-page-N UIs where users genuinely navigate by number. Outside those, keyset pagination wins on every axis that matters at scale.

Keyset Pagination: The Single-Column Case

The idea: instead of telling the database how many rows to skip, tell it where the last page ended. The query becomes a range scan:

SELECT id, created_at, title FROM orders
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;

Two details make this correct rather than almost-correct. First, the tiebreaker: created_at is a timestamp, and timestamps collide constantly (bulk imports, defaults with second precision). Without the secondary key, rows sharing a timestamp can be skipped or duplicated across page boundaries. The pair (created_at, id) is unique as long as id is, so the sort order is total and pages tile the table exactly.

Second, the row-value comparison. PostgreSQL compares tuple (a, b) < (x, y) lexicographically — equivalent to (a < x) OR (a = x AND b < y). That is precisely “strictly after this position in the sort order.” The comparison operators are documented on the comparison functions page. Note the direction flip: the WHERE uses < while ORDER BY uses DESC, because “next page” means “lower sort position.”

Supporting the query needs a matching composite index, per the multicolumn index docs:

CREATE INDEX idx_orders_feed ON orders (created_at DESC, id DESC);

With that index, every page is an index-range scan that touches exactly 20 entries (plus heap fetches). Page 5,000 costs the same as page 1 — the defining property that OFFSET can never offer.

Multi-Column Keysets With Filters

Real endpoints sort by something other than insert time and filter at the same time: “my open tickets by priority, newest first.” The cursor must then encode the full sort key, and the index must lead with the filter columns:

SELECT id, status, priority, created_at
FROM tickets
WHERE org_id = :org
  AND (priority, created_at, id) < (:last_priority, :last_created_at, :last_id)
ORDER BY priority DESC, created_at DESC, id DESC
LIMIT 20;

CREATE INDEX idx_tickets_feed ON tickets (org_id, priority DESC, created_at DESC, id DESC);

The rule generalizes: cursor key = filter-leading index columns + sort columns + unique tiebreaker, in the exact order of the ORDER BY. Every column you add makes the index wider and the cursor bigger, which is a real argument for keeping sort schemes simple — a sortable created_at plus tiebreaker covers most product needs.

The planner confirms the win. With the composite index and the row-value predicate, EXPLAIN shows an Index Scan with Index Cond covering the range — a planner behavior analyzed in detail in the row estimation examples in the docs. Without the row-value syntax, a hand-written OR expansion can confuse the planner into a worse plan; prefer the tuple comparison.

Encoding the Cursor

Exposing raw IDs and timestamps in URLs invites clients to tamper with them. The standard practice is an opaque token: serialize the key columns to JSON, base64-encode, hand to the client, decode on the next request. The cursor is stateless — all state lives in the token — which is what makes keyset pagination horizontally scalable.

A minimal Go implementation of the encode/decode round trip, using the struct tag conventions of encoding/json:

package feed

import (
	"encoding/base64"
	"encoding/json"
	"errors"
	"fmt"
	"time"
)

type Cursor struct {
	CreatedAt time.Time `json:"created_at"`
	ID        int64     `json:"id"`
}

func EncodeCursor(c Cursor) string {
	b, err := json.Marshal(c)
	if err != nil {
		return ""
	}
	return base64.RawURLEncoding.EncodeToString(b)
}

func DecodeCursor(s string) (Cursor, error) {
	var c Cursor
	if s == "" {
		return c, nil // empty cursor = first page
	}
	b, err := base64.RawURLEncoding.DecodeString(s)
	if err != nil {
		return c, fmt.Errorf("invalid cursor: %w", err)
	}
	if err := json.Unmarshal(b, &c); err != nil {
		return c, fmt.Errorf("invalid cursor: %w", err)
	}
	if c.ID == 0 {
		return c, errors.New("cursor missing id")
	}
	return c, nil
}

And the query layer, with pgx:

func (r *OrderRepo) Page(ctx context.Context, cur feed.Cursor, limit int) ([]Order, feed.Cursor, error) {
	rows, err := r.db.Query(ctx, `
		SELECT id, created_at, title FROM orders
		WHERE (created_at, id) < ($1, $2)
		ORDER BY created_at DESC, id DESC
		LIMIT $3`, cur.CreatedAt, cur.ID, limit+1)
	if err != nil {
		return nil, feed.Cursor{}, err
	}
	defer rows.Close()

	var orders []Order
	for rows.Next() {
		var o Order
		if err := rows.Scan(&o.ID, &o.CreatedAt, &o.Title); err != nil {
			return nil, feed.Cursor{}, err
		}
		orders = append(orders, o)
	}
	if err := rows.Err(); err != nil {
		return nil, feed.Cursor{}, err
	}

	var next feed.Cursor
	if len(orders) > limit {
		last := orders[limit-1]
		orders = orders[:limit]
		next = feed.Cursor{CreatedAt: last.CreatedAt, ID: last.ID}
	}
	return orders, next, nil
}

Three implementation details worth stealing. The limit+1 fetch is the cheapest way to know whether another page exists — no COUNT(*), which would defeat the entire purpose. The next cursor is built from the last returned row, not the extra row. And rows.Err() is checked after the loop, because rows.Next() can terminate on an error as well as on exhaustion.

Edge Cases That Break Naive Keysets

  • NULLs in sort columns. In PostgreSQL, NULL sorts last in ASC and first in DESC by default, and the tuple comparison (a, b) < (x, y) treats NULL specially — comparisons involving NULL return NULL, which the WHERE clause treats as false, so rows with NULL sort columns silently vanish mid-pagination. Either declare the column NOT NULL (best), or use NULLS NOT DISTINCT-aware schemes and explicit COALESCE in both ORDER BY and WHERE — consistently, in both.
  • Non-unique sort columns without a tiebreaker. Already covered, but it bears repeating because it’s the most common production bug: any duplicated sort value skips rows. Always end the key with a unique column.
  • Sort schemes changing after launch. Cursors embed the scheme they were minted with. If you change sort columns, old cursors either break or — worse — silently mean something different. Version the token ({"v":2,"sort":"priority","key":...}) so the server can reject or translate unknown versions.
  • Timestamps and timezone stability. Encode timestamps in UTC with fixed precision. A cursor minted from a timestamptz and decoded into a naive timestamp in a different session timezone produces off-by-hours pages that are miserable to debug.
  • Insert-heavy feeds and “new rows appear.” Keyset pagination is immune to page-shifting, which is its core advantage — new rows appear only on refresh/requery of page one, and existing pages never change. That’s usually the behavior users want; make it explicit in API docs.

Total Counts, Page Numbers, and API Design

Keyset pagination gives up two things clients ask for: total page counts and jump-to-page. Total counts require COUNT(*) over the full filtered set — expensive, and a lie anyway under concurrent writes. The pragmatic answers:

  • “Has more” instead of counts. The limit+1 trick gives you a boolean for free. Most feed UIs only need it.
  • Approximate counts from pg_class.reltuples (updated by autovacuum/ANALYZE) when a display count is unavoidable — “about 12,400 results” costs nothing compared to an exact count.
  • Hypermedia links over exposed keys. Return next_cursor (and prev_cursor when you support backward traversal via reversed comparison and ORDER BY) and let clients treat the token as a black box, the way server-side cursors abstract position in the protocol layer.

Backward pagination is a symmetric problem: reverse every comparison and every ORDER BY direction, and fetch the row before the first row of the current page to build the previous cursor. Teams that skip this on v1 end up bolting it on painfully — worth shipping from day one.

Wrapping Up

The decision rule is simple. Small admin tables where users jump between pages: OFFSET is fine. Anything user-facing, anything scrollable, anything over a few thousand rows: keyset pagination with a unique tiebreaker, a matching composite index, an opaque versioned cursor token, and “has more” instead of counts. The implementation is a few dozen lines, every page costs an index seek instead of an O(n) walk, and the class of “duplicate/missing row” bugs that plague offset-based feeds disappears entirely. The LIMIT documentation and the multicolumn index guide cover the remaining planner details if you want to go deeper.

Leave a Reply

Your email address will not be published. Required fields are marked *