paulserban.eu

Writing Edition

Paul Serban

Writing, snippets & book notes

Vol. 2026

How to Design High-Performance Pagination Algorithms for APIs and Databases

Step-by-step guide to building efficient, scalable pagination in modern architectures

Introduction

Pagination is one of those deceptively simple problems in software engineering. On the surface, it looks like a solved problem - split your data into pages, hand the client a page number, done. But as soon as your dataset crosses millions of rows, or your API starts serving thousands of concurrent users, the cracks appear fast. Response times balloon. Database servers start sweating. Users notice.

The real challenge with pagination isn't retrieving a page of data. It's doing so in a way that remains fast, correct, and consistent at scale - and doing it without hiding complexity from the engineers who need to maintain it. Every pagination strategy encodes a set of assumptions about your data model, access patterns, and consistency requirements. Choose the wrong one and you'll be rewriting it under production load.

This article walks through the major pagination strategies - offset-based, keyset (seek), and cursor-based - analyzes their performance characteristics, and gives you the tools to pick and implement the right approach for your system. The examples are in TypeScript, Python, and SQL, reflecting realistic production patterns rather than academic toy code.

The Core Problem with Naive Pagination

The simplest pagination pattern you can write is offset pagination: give me rows N through N+page_size. In SQL, that looks like LIMIT 20 OFFSET 200. Every major ORM exposes this natively. It maps cleanly onto the mental model of numbered pages. It's also, in many cases, a slow-motion disaster.

The fundamental issue is what databases must do to answer an offset query. Even though you want rows 200-220, the database typically has to identify and skip over the first 200 rows before it can return the ones you actually need. On a table with no relevant index ordering, that means a full or partial scan. On a table with 50 million rows and a user browsing to page 5000, the database walks through 100,000 rows just to throw them away. The OFFSET clause is not a pointer into a pre-sorted list; it's a count of rows to discard. The deeper you page, the more expensive each query becomes - a property known as deep pagination degradation.

Data Consistency Under Concurrent Writes

There's a second, subtler problem: offset pagination is not stable under concurrent writes. Imagine a user loads page 3 of a result set. While they're reading it, another process inserts a new row near the top of the ordering. By the time the user requests page 4, every subsequent row has shifted by one position in the offset calculation. The user will either see a duplicate (a row they already saw on page 3) or silently skip a row. Neither outcome is acceptable in most applications, and this problem has no clean fix within the offset model.

This isn't a theoretical edge case. Any system where rows are inserted, deleted, or have their sort-key updated while users are paginating will exhibit this behavior. Order history feeds, audit logs, social timelines, and search results are all susceptible. The practical consequence is that offset-based pagination is only truly safe on static, append-only, or infrequently mutated datasets - a narrower set of use cases than most engineers assume when they reach for it.

Pagination Strategies: A Technical Deep Dive

Offset Pagination

Offset pagination is the default and it's worth understanding precisely when it works. If your dataset is small (under ~100,000 rows), your ordering column is indexed, and you never paginate past the first few hundred pages, offset pagination is fine. The simplicity is genuine: it's trivially reversible (you can jump to any page number directly), easy to implement, and universally supported.

The performance model deteriorates predictably. PostgreSQL, MySQL, and most other relational databases must resolve the full sorted result set up to the offset point. Even with an index on the sort column, the optimizer must traverse the index leaf nodes from the beginning to find the offset position. This is O(offset) in the number of rows to skip. Benchmarks on PostgreSQL show that a query with OFFSET 100000 on an indexed column can be 10-50x slower than the equivalent query with OFFSET 0 on a table with several million rows, depending on row width, index type, and buffer cache state.

Keyset (Seek) Pagination

Keyset pagination - also called the seek method - eliminates the offset entirely by using the last-seen value of the sort key as the starting point for the next page. Instead of OFFSET 200, you say: give me the next 20 rows where created_at is less than '2024-03-15T12:34:56Z' (or greater than, depending on sort direction). The database can now use the index to seek directly to that position and scan forward from there, discarding nothing.

The performance benefit is dramatic and consistent. A keyset query takes roughly the same time at page 5000 as at page 1, because the cost is always proportional to the page size, not the page depth. The index seek is O(log N) and the scan is O(page_size). This is why keyset pagination is the preferred strategy for high-volume, deep-pagination scenarios - it's the approach used internally by most large-scale data systems, even when exposing a different API surface to clients.

The trade-off is that keyset pagination requires a stable, unique sort key. If you're sorting by created_at and two rows share the exact same timestamp, the boundary condition is ambiguous and you may skip or repeat rows. The canonical solution is to use a composite key: (created_at, id), where id is guaranteed unique. This composite forms an unambiguous total ordering that the database can seek into precisely.

Cursor-Based Pagination

Cursor-based pagination is often conflated with keyset pagination, but they're distinct concepts. A cursor is an opaque token returned to the client that encodes pagination state; keyset is a specific mechanism for implementing that state efficiently. In practice, most well-designed cursor APIs use keyset queries under the hood - the cursor is simply a base64-encoded or encrypted representation of the last-seen sort key values.

The opacity of the cursor is not an accident. Exposing raw created_at + id values in your API surface creates a coupling between your pagination logic and your data model. If you later change your sort strategy or add a new tiebreaker column, you've broken clients that were constructing their own cursor values. An opaque token lets you change the internal encoding without changing the API contract, as long as existing cursors remain decodable for their expected lifetime.

Cursor-based pagination also enables important features: bidirectional pagination (both forward and backward cursors), relative stability under writes (the cursor points to a specific row, not a position-in-offset), and easier distributed pagination across shards or replicas. Major APIs including GitHub's GraphQL API, Stripe, Slack, and Shopify all use cursor-based pagination for these reasons.

Time-Based and Hybrid Approaches

A common variant in event-driven and time-series systems is time-range pagination: rather than paginating by position within a result set, you paginate by time window. Give me all events between timestamp A and timestamp B, then increment the window. This works well for immutable append-only logs where time is the natural partition boundary, and it pairs effectively with time-partitioned tables in PostgreSQL or TimescaleDB, where each query can be routed directly to the relevant partition.

The limitation is that time windows are not guaranteed to contain a consistent number of records. A busy window might return 10,000 rows while a quiet window returns 5. For UX-facing pagination (users browsing pages), this is usually unacceptable. For backend data pipelines, ETL processes, or analytics exports, it can be ideal - the client doesn't care about page uniformity, only about completeness and correctness.

Implementation Examples

Keyset Pagination in TypeScript (Node.js + PostgreSQL)

The following example demonstrates a production-ready keyset pagination function using pg (node-postgres) with a composite sort key. The function returns both the page data and a next-page cursor.

import { Pool } from 'pg';

interface PaginationCursor {
  createdAt: string;
  id: string;
}

interface PageResult<T> {
  data: T[];
  nextCursor: string | null;
  hasMore: boolean;
}

function encodeCursor(cursor: PaginationCursor): string {
  return Buffer.from(JSON.stringify(cursor)).toString('base64url');
}

function decodeCursor(token: string): PaginationCursor {
  return JSON.parse(Buffer.from(token, 'base64url').toString('utf-8'));
}

async function fetchOrdersPage(
  pool: Pool,
  userId: string,
  limit: number,
  cursorToken?: string
): Promise<PageResult<Order>> {
  // Request one extra row to determine if there are more pages
  const fetchLimit = limit + 1;

  let query: string;
  let params: unknown[];

  if (cursorToken) {
    const cursor = decodeCursor(cursorToken);
    query = `
      SELECT id, user_id, total, created_at
      FROM orders
      WHERE user_id = $1
        AND (created_at, id) < ($2::timestamptz, $3::uuid)
      ORDER BY created_at DESC, id DESC
      LIMIT $4
    `;
    params = [userId, cursor.createdAt, cursor.id, fetchLimit];
  } else {
    query = `
      SELECT id, user_id, total, created_at
      FROM orders
      WHERE user_id = $1
      ORDER BY created_at DESC, id DESC
      LIMIT $2
    `;
    params = [userId, fetchLimit];
  }

  const result = await pool.query<Order>(query, params);
  const rows = result.rows;

  const hasMore = rows.length > limit;
  const data = hasMore ? rows.slice(0, limit) : rows;

  let nextCursor: string | null = null;
  if (hasMore && data.length > 0) {
    const last = data[data.length - 1];
    nextCursor = encodeCursor({
      createdAt: last.created_at.toISOString(),
      id: last.id,
    });
  }

  return { data, nextCursor, hasMore };
}

Notice the composite (created_at, id) condition in the WHERE clause. PostgreSQL can use a composite index on (created_at DESC, id DESC) to execute this as a single seek-and-scan, making it consistently fast regardless of how deep into the dataset the cursor points.

Cursor API Response Schema (TypeScript)

For a REST API, the response envelope should be explicit about pagination metadata without leaking implementation details:

interface PaginatedResponse<T> {
  data: T[];
  pagination: {
    nextCursor: string | null;
    prevCursor: string | null;
    hasNextPage: boolean;
    hasPrevPage: boolean;
    pageSize: number;
  };
}

The prevCursor field supports backward pagination - navigating to a previous page from an arbitrary point in the result set. Backward pagination with keyset queries requires reversing the comparison operator and the sort direction, then reversing the returned rows. It's more complex to implement correctly but is essential for any UI that allows bidirectional navigation.

Offset Pagination with Safety Guardrails (Python + SQLAlchemy)

When offset pagination is appropriate - small datasets, admin dashboards, infrequently mutated data - you can add guardrails to prevent accidental deep pagination from degrading performance:

from dataclasses import dataclass
from typing import Generic, TypeVar, List
from sqlalchemy.orm import Session
from sqlalchemy import select, func

T = TypeVar("T")

MAX_ALLOWED_OFFSET = 10_000
DEFAULT_PAGE_SIZE = 20
MAX_PAGE_SIZE = 100


@dataclass
class OffsetPage(Generic[T]):
    data: List[T]
    total: int
    page: int
    page_size: int
    total_pages: int


def paginate_offset(
    session: Session,
    query,
    page: int,
    page_size: int = DEFAULT_PAGE_SIZE,
) -> OffsetPage:
    if page < 1:
        raise ValueError("Page number must be >= 1")
    if page_size > MAX_PAGE_SIZE:
        raise ValueError(f"Page size cannot exceed {MAX_PAGE_SIZE}")

    offset = (page - 1) * page_size

    if offset > MAX_ALLOWED_OFFSET:
        raise ValueError(
            f"Offset {offset} exceeds maximum allowed ({MAX_ALLOWED_OFFSET}). "
            "Use cursor-based pagination for deep traversal."
        )

    total = session.scalar(select(func.count()).select_from(query.subquery()))
    rows = session.scalars(query.offset(offset).limit(page_size)).all()
    total_pages = (total + page_size - 1) // page_size

    return OffsetPage(
        data=list(rows),
        total=total,
        page=page,
        page_size=page_size,
        total_pages=total_pages,
    )

The MAX_ALLOWED_OFFSET guard forces engineers to make a conscious decision when they need deep pagination, rather than letting a bad pattern silently scale until it causes an incident.

Trade-offs and Common Pitfalls

The Total Count Problem

One of the most frequently overlooked trade-offs in pagination design is the cost of returning a total record count alongside each page. This is so common in UI patterns - "Page 3 of 47", "Showing 41-60 of 934 results" - that engineers often include it without questioning the cost. On large tables, SELECT COUNT(*) with a non-trivial WHERE clause can be just as slow as the offset query itself, or slower. PostgreSQL's MVCC model means counts require a full visibility scan in the worst case.

There are several practical approaches to this problem. First, for estimates, PostgreSQL exposes reltuples in pg_class which is a statistical approximation updated by autovacuum - suitable for showing "about 10,000 results" without precision. Second, for exact counts on filtered queries, a separate cached count query with a TTL can reduce per-request cost significantly when the underlying data changes infrequently. Third - and most importantly - you should question whether exact counts are actually necessary for the UX. Many successful pagination UIs (including Google Search) show only approximate counts or have dropped exact totals entirely. Cursor-based APIs often omit totals by design, surfacing only hasNextPage.

Inconsistent Sort Keys and Duplicate Values

Keyset pagination breaks down when the sort key is not unique. If you paginate by price and multiple products share the same price, the WHERE price < $last_price condition will skip or duplicate records at page boundaries depending on how the condition falls. The fix is always to add a unique tiebreaker - typically the primary key - to form a composite sort key. But many engineers add this only after observing the bug in production.

The situation is more subtle with NULL values. SQL comparison operators treat NULL as unknown, so WHERE created_at < NULL returns no rows. If your sort column is nullable, you need an explicit strategy for where NULL values land in the ordering - typically via NULLS LAST or NULLS FIRST in the ORDER BY, with corresponding handling in the WHERE clause for the keyset boundary condition.

Index Coverage and Sort Alignment

A keyset query performs well only when the database can satisfy the query using an index - both for the seek and for the scan. If your ORDER BY clause doesn't align with an available index, the database will sort the filtered result set in memory, negating the keyset advantage. For composite sort keys, the index must exactly match the column order and sort directions. An index on (created_at DESC, id DESC) does not automatically satisfy a query ordering by (created_at ASC, id ASC).

This seems obvious stated plainly, but in practice, index drift - where query patterns evolve after the initial schema is set - causes many subtle performance regressions. The fix is to treat indexes as first-class API artifacts: document which index a given pagination query depends on, add regression tests that verify query plans (PostgreSQL's EXPLAIN output can be parsed and asserted in test suites), and include index definitions in your migration files with clear comments.

API Versioning and Cursor Lifetime

Opaque cursors seem like they decouple clients from internals, but they create a different kind of coupling: a cursor serialized today must remain decodable tomorrow. If you change the cursor encoding (add a field, change the hash function, alter the structure), any client holding an old cursor will receive an error on their next request. This is a breaking change in the same way a field removal is.

The practical implication is that cursor formats should be versioned. Including a version byte or prefix in the encoded token lets you decode old formats alongside new ones during a transition period. You should also document and enforce cursor expiry: a cursor is a snapshot of a position in a dataset, and holding it indefinitely may reference rows that have since been deleted or moved. A reasonable TTL of 24-72 hours, communicated in the API documentation, prevents both server-side complexity and client-side confusion.

Best Practices for Production Systems

Always Use a Composite Unique Sort Key

Never build a keyset pagination query on a single non-unique column. Even columns that appear unique in practice - like email in a users table - can have edge cases in data migrations or bulk imports. The only safe approach is to use a primary key (UUID or integer ID) as the final tiebreaker in a composite key. Enforce this as a code review standard, not a guideline.

Additionally, ensure your composite index precisely matches the ORDER BY direction. Write integration tests that execute EXPLAIN ANALYZE on your pagination queries and assert the presence of an Index Scan or Index Only Scan node. A Seq Scan or Sort in the query plan is a performance bug.

Encapsulate Pagination Logic in a Shared Layer

Pagination is infrastructure, not business logic. It belongs in a shared data access layer - a repository class, a generic query builder extension, a middleware function - rather than being re-implemented in each endpoint or service. Re-implementation is where subtle bugs enter: one endpoint uses <= where it should use <, another forgets the tiebreaker column, a third encodes the cursor in a different format.

A single, well-tested pagination abstraction with a narrow interface (pass in a query, get back a page and a cursor) makes pagination behavior consistent, testable, and auditable across your codebase. When you need to upgrade your cursor format or fix a boundary condition bug, you fix it in one place.

Protect Against Abuse and Misconfiguration

Pagination endpoints are natural targets for both accidental abuse (a client that loops through all pages as fast as possible) and intentional scraping. Apply rate limiting at the API gateway level, scoped by user or API key. Set hard limits on page_size - accepting an arbitrary limit=100000 from a client is a denial-of-service vector. Return clear, consistent error messages when pagination parameters are invalid, with enough detail for a developer to self-correct but not so much that you expose internals.

For internal pagination in background jobs or data pipelines, use explicit batching loops with configurable batch sizes and built-in backpressure. A job that blindly pages through 50 million rows as fast as possible can starve production queries on a shared read replica. Sleep intervals, replica routing, and connection pool limits all belong in your pagination job framework.

Monitor Deep Pagination and Slow Queries

Add observability to your pagination queries. Log the cursor depth (either as an offset equivalent or as the approximate age of the cursor's reference row), the query execution time, and the number of rows returned. Set alerting thresholds on p99 query latency for your pagination endpoints. If you see latency increasing linearly with cursor age, it's a sign that your keyset index isn't being used correctly.

For databases with query sampling capabilities - PostgreSQL's pg_stat_statements, MySQL's Performance Schema, or cloud-native equivalents - configure dashboards that surface your slowest pagination queries weekly. Pagination regressions are rarely acute incidents; they're slow degradations that compound over months as datasets grow. Visibility is the only reliable prevention.

Design for Eventual Consistency in Distributed Systems

In distributed systems - microservices with separate databases, multi-region setups, read replicas with replication lag - pagination correctness becomes significantly harder. A cursor encoding a position in the primary's dataset may resolve to a different position on a replica, or the referenced row may not yet exist on the replica at all. Reads from replicas can also return different row orderings for the same query at different moments, causing apparent instability in pagination sequences.

The safest approach is to route all pagination reads for a given user session to a single replica or the primary for the session's duration, using session affinity at the load balancer or connection pool level. Alternatively, encode enough context in the cursor to detect and handle replication inconsistencies gracefully - returning an error and instructing the client to restart from the beginning is better than silently serving inconsistent data.

Key Takeaways

Here are five concrete steps you can apply immediately:

  1. Audit your existing pagination queries with EXPLAIN ANALYZE. Identify any that use OFFSET with values over 1,000 and measure their execution time. These are your highest-priority refactoring candidates.
  2. Replace high-offset queries with composite keyset queries. Add (sort_column DESC, id DESC) indexes, update your WHERE clauses to use row value comparisons, and measure the latency improvement.
  3. Wrap cursor values in an opaque, versioned token. Base64url-encode a JSON struct containing the sort key values and a version identifier. This decouples your API from your internal ordering logic.
  4. Add hard limits to page size and enforce a maximum offset cap in your data access layer. Treat these as non-negotiable defaults, overridable only by explicitly designed internal-use endpoints.
  5. Set up monitoring on pagination query latency, scoped by cursor depth. A dashboard that shows query time vs. approximate page depth will catch keyset index failures before they become user-visible incidents.

Analogies and Mental Models

The bookmark analogy: Offset pagination is like finding your place in a book by counting pages from the front every time. Keyset pagination is like using a bookmark - you open directly to where you left off, regardless of how thick the book is. The moving train: Imagine paginating through a live data feed as riding a train and trying to count how many stations you've passed. If the train moves while you count, your count drifts. A cursor is like a GPS coordinate - it doesn't care how many stations there are; it just tells you your exact current position. The phone book seek: A sequential scan with offset is reading a phone book from "Aaron" every time someone asks for the next page starting from "Smith." Keyset pagination is opening directly to the "S" section and scanning forward. The index is the divider tabs; the composite sort key is the full name entry.

These analogies aren't perfect - no analogy survives contact with distributed systems - but they communicate the essential intuition: position-by-count is fragile and slow; position-by-reference is stable and fast.

80/20 Insight

If you take only one structural change away from this article, make it this: replace OFFSET N with a composite keyset condition WHERE (sort_col, id) < (last_sort_val, last_id). That single change eliminates deep-pagination degradation entirely, removes the data consistency hazard under concurrent writes, and works well even on datasets with hundreds of millions of rows. The cursor encoding, the API design, the total count optimization - all of those matter, but this is the load-bearing change that produces 80% of the performance benefit.

The second most impactful practice is composite index alignment. The keyset query only works fast if the database can execute it as an index seek. An hour spent verifying your index definitions and asserting them in tests will prevent months of latency investigations later.

Everything else - cursor versioning, bidirectional pagination, time-range variants, distributed consistency handling - is important in context, but context-dependent. The keyset substitution and index alignment are universally applicable.

Conclusion

Pagination is a foundational API and database pattern that carries hidden complexity far beyond its surface simplicity. The offset model is convenient and almost universally understood, but it degrades predictably under load and becomes unsafe under concurrent mutation. Keyset pagination resolves both problems at the cost of requiring a well-designed sort key and an aligned index. Cursor-based APIs provide the right abstraction layer for exposing this efficiently to clients while preserving the flexibility to evolve internal ordering strategies.

The right pagination strategy is never purely a technical choice - it involves your data model, your access patterns, your consistency requirements, and the latency budgets your users actually experience. An admin dashboard with 5,000 rows and no deep pagination need is not the same problem as a social feed with 100 million events. Apply the analysis in this article to your specific context rather than defaulting to whichever pattern you learned first.

Pagination, done well, is invisible. Users never notice that you've efficiently streamed a billion rows to their browser in 20-row increments. The measure of a good pagination implementation is the absence of incidents, the flatness of your latency graphs as your dataset grows, and the absence of "why are these pages slow?" in your sprint retrospectives.

References

  1. PostgreSQL Documentation - LIMIT and OFFSET: https://www.postgresql.org/docs/current/queries-limit.html - Official documentation on query limiting behavior, including offset performance characteristics.
  2. Markus Winand - "Use The Index, Luke" - The Seek Method: https://use-the-index-luke.com/sql/partial-results/fetch-next-page - A definitive practical resource on keyset pagination, including execution plan analysis and composite index design.
  3. GitHub GraphQL API - Pagination Docs: https://docs.github.com/en/graphql/overview/resource-limitations - GitHub's documentation on cursor-based pagination in their GraphQL API, including connection/edge conventions.
  4. Stripe API - Pagination: https://stripe.com/docs/api/pagination - Stripe's cursor-based list pagination pattern, a widely-referenced production example.
  5. Slack API - Cursor-Based Pagination: https://api.slack.com/docs/pagination - Slack's documentation of their cursor pagination model, including cursor lifetime and encoding considerations.
  6. PostgreSQL Documentation - pg_stat_statements: https://www.postgresql.org/docs/current/pgstatstatements.html - For monitoring slow pagination queries in production.
  7. PostgreSQL Documentation - Row Constructor Comparisons: https://www.postgresql.org/docs/current/functions-comparisons.html#ROW-WISE-COMPARISON - Official documentation on composite row value comparisons used in keyset queries.
  8. Martin Kleppmann - Designing Data-Intensive Applications (O'Reilly, 2017) - Chapters on replication lag, consistency models, and distributed query patterns are directly relevant to paginating across replicas.
  9. MySQL Documentation - LIMIT Optimization: https://dev.mysql.com/doc/refman/8.0/en/limit-optimization.html - MySQL's guidance on how the optimizer handles LIMIT and ORDER BY, and when indexes are used.
  10. AWS Blog - Best Practices for Paginating DynamoDB Results: https://aws.amazon.com/blogs/database/ - DynamoDB's LastEvaluatedKey pattern is a native implementation of cursor-based pagination in a NoSQL context and provides useful comparison context.