Pagination Strategies for REST APIs

Every production dataset eventually exceeds what a network packet, a client runtime, or a database query can handle in a single round trip. When an endpoint returns unconstrained lists of resources, it creates an immediate vulnerability: a sudden spike in table volume or a burst of concurrent requests can saturate memory buffers, spike database CPU utilization, and degrade client responsiveness.

Pagination is the standard architectural remedy. Yet, in many production systems, pagination is treated as a superficial API formatting concern—adding ?page=2 or ?limit=20 to query parameters and appending an OFFSET clause to a SQL query.

This surface-level mental model masks a fundamental reality: API pagination is fundamentally a storage engine access pattern exposed over HTTP.

A pagination strategy directly dictates how relational B-Trees or document storage engines traverse on-disk indexes, how database shared buffer caches retain memory pages, and whether clients observe consistent records when concurrent writes mutate the underlying dataset. Choosing the wrong strategy leads to severe query latency cliffs, phantom records, skipped items, and silent data omission in production data pipelines.

This guide explores the three primary REST API pagination paradigms—offset-based, keyset/cursor-based, and time-window pagination—analyzing their database mechanics, consistency guarantees, index requirements, and operational tradeoffs. We then implement a production-grade TypeScript cursor paginator with composite PostgreSQL indexing, demonstrating how to eliminate pagination drift and achieve constant-time index traversal.

---

The Three Core Pagination Paradigms

Understanding pagination begins by comparing the three distinct mechanisms engines use to partition and traverse ordered records:

1. Offset-Based Pagination (limit and offset)
2. Keyset / Cursor-Based Pagination (cursor and limit)
3. Time-Window / Chunk-Based Pagination (start_time and end_time)

+-----------------------------------------------------------------------------+
|                          API PAGINATION PARADIGMS                           |
+-----------------------------------------------------------------------------+
|                                                                             |
| 1. OFFSET-BASED: Skip N rows, return K rows                                 |
|    Client: GET /api/v1/orders?limit=20&offset=100000                        |
|    Database: Scans 100,020 rows, discards 100,000, returns 20               |
|    Cost: O(N + K) - Degrades linearly with page depth                       |
|                                                                             |
| 2. KEYSET / CURSOR: Filter by unique position, return K rows                |
|    Client: GET /api/v1/orders?limit=20&cursor=eyJ0IjoxNzU...                |
|    Database: B-Tree index seek directly to cursor tuple, reads 21 rows     |
|    Cost: O(log M + K) - Constant seek time regardless of depth             |
|                                                                             |
| 3. TIME-WINDOW: Slice by explicit temporal boundaries                       |
|    Client: GET /api/v1/events?start_time=2026-09-01T00:00Z&end_time=...     |
|    Database: Partition pruning + range scan on indexed timestamps          |
|    Cost: Proportional to event density within the defined interval          |
|                                                                             |
+-----------------------------------------------------------------------------+

---

Paradigm 1: Offset-Based Pagination (limit and offset)

Offset pagination is the most intuitive pattern to implement. The client specifies how many records it wants (limit) and how many records to skip (offset), or alternatively a page index (page = (offset / limit) + 1):

-- Fetch page 5000 with 20 items per page
SELECT id, customer_id, total_amount_cents, created_at
FROM orders
ORDER BY created_at DESC
LIMIT 20 OFFSET 100000;

While convenient for prototyping, offset pagination suffers from two severe architectural flaws in production: $O(N)$ database degradation and pagination window drift.

1. $O(N)$ Database Degradation and Buffer Cache Churn

A relational database engine cannot magically jump to row number 100,000 in an ordered result set. Because deleted records leave gaps, updates rearrange tuple locations, and multi-version concurrency control (MVCC) maintains multiple physical row versions, the database cannot perform arithmetic on physical storage offsets.

To fulfill OFFSET 100000 LIMIT 20, the storage engine must:

1. Traverse the index (or perform a sequential table scan).
2. Read and evaluate 100,020 matching index entries or heap rows off disk or shared buffers.
3. Discard the first 100,000 rows.
4. Return only the remaining 20 rows to the client.

The computational complexity of accessing page $P$ with limit $K$ is $O(N + K)$, where $N = (P - 1) \times K$. As clients navigate deeper into the dataset, latency scales linearly with $N$.

Under high concurrency or web-crawler activity, deep offset queries force large numbers of index and heap pages into the database buffer cache (such as PostgreSQL's shared_buffers), evicting hot, frequently accessed pages. This creates database-wide cache churn, degrading the throughput of unrelated transactional queries.

Evaluating this query plan in PostgreSQL using EXPLAIN (ANALYZE, BUFFERS) reveals the hidden cost:

Limit  (cost=15423.85..15426.94 rows=20 width=64) (actual time=142.312..142.338 rows=20 loops=1)
  Buffers: shared hit=8420 read=1485
  ->  Index Scan using idx_orders_created_at on orders (cost=0.43..154238.50 rows=1000000 width=64) (actual time=0.082..136.814 rows=100020 loops=1)
        Buffers: shared hit=8420 read=1485
Planning Time: 0.184 ms
Execution Time: 142.381 ms

Notice that the engine spent over 136 milliseconds scanning 100,020 rows and touched 9,905 shared memory buffers—merely to discard 99.98% of them.

2. Pagination Window Drift (Phantom Records and Skipped Data)

Offset pagination assumes the underlying table remains frozen between sequential HTTP requests. In high-throughput systems where records are continuously inserted or deleted, this assumption collapses.

Consider a mobile feed showing orders sorted newest to oldest (ORDER BY created_at DESC):

WINDOW DRIFT UNDER CONCURRENT INSERTIONS

Initial State (User requests Page 1: LIMIT 4 OFFSET 0):
  [Row A] -> Item 1 (Returned)
  [Row B] -> Item 2 (Returned)
  [Row C] -> Item 3 (Returned)
  [Row D] -> Item 4 (Returned)
  --------------------------- Page 1 Boundary
  [Row E] -> Item 5
  [Row F] -> Item 6

Concurrent Event:
  A new order [Row NEW] is inserted at the top of the table.

User requests Page 2 (LIMIT 4 OFFSET 4):
  Database offsets 4 rows from the current top:
  Row NEW (Offset 0 - Skipped)
  Row A   (Offset 1 - Skipped)
  Row B   (Offset 2 - Skipped)
  Row C   (Offset 3 - Skipped)
  --------------------------- Offset 4 Boundary
  [Row D] -> Item 5 (Returned AGAIN!)  <-- Duplicate item displayed to user
  [Row E] -> Item 6 (Returned)
  [Row F] -> Item 7 (Returned)

• Under concurrent insertions: New records pushed to the top shift all existing rows downward. When the client requests the next offset window, the last item from the previous page is pushed into the current page, resulting in duplicate items.
• Under concurrent deletions: If a record on page 1 is deleted or soft-deleted while the user reads it, subsequent records shift upward. When the client fetches page 2, the first item of page 2 shifts into the skipped offset range and is completely missed.

For financial ledgers, audit trails, and automated synchronizers, silent record skipping violates data integrity guarantees.

Viable Use Cases for Offset Pagination

Despite these limitations, offset pagination remains acceptable when:

• The dataset has low cardinality (e.g., fewer than a few thousand rows).
• The table is static or mutated exclusively in controlled batch windows.
• The user interface explicitly requires random access jumping to arbitrary page numbers (e.g., an internal back-office admin grid requiring "Jump directly to Page 18").

---

Paradigm 2: Keyset / Cursor-Based Pagination (cursor and limit)

Keyset pagination (often referred to as cursor-based pagination) replaces numeric row offsets with a stable reference point based on the ordering columns of the dataset.

Instead of asking the database to "skip 100,000 rows", the client asks the database to "return the next 20 rows that appear strictly after this specific item":

-- Keyset seek query using composite coordinates (created_at, id)
SELECT id, customer_id, total_amount_cents, created_at
FROM orders
WHERE (created_at, id) < ('2026-09-17T08:30:00.000Z'::timestamptz, 'b2d88a10-2d88-4c92-8092-91f868adbc01'::uuid)
ORDER BY created_at DESC, id DESC
LIMIT 21;

1. Constant-Time B-Tree Traversal: $O(\log M + K)$

When backed by a matching composite B-Tree index, keyset pagination transforms the query from an expensive scan-and-discard operation into an index seek:

1. The database traverses the B-Tree index from root to leaf to find the exact key matching ('2026-09-17T08:30:00.000Z', 'b2d88a10...') in $O(\log M)$ operations, where $M$ is the total row count of the index.
2. From that exact leaf node, the storage engine reads sequentially along the index leaf pointers for exactly $K + 1$ entries.
3. It fetches only the corresponding $K + 1$ heap tuples.

Regardless of whether the client is requesting the 1st page or the 100,000th page, the database reads only $K + 1$ index entries. The latency curve is flat.

OFFSET SCAN VS KEYSET B-TREE SEEK

1. OFFSET SCAN: LIMIT 20 OFFSET 100,000
   [Root]
     │
     ├──> [Branch 1] ──> [Leaf] Scan... Discard
     ├──> [Branch 2] ──> [Leaf] Scan... Discard
     ├──> ... (Scans and discards 100,000 rows across buffer cache)
     └──> [Branch N] ──> [Leaf] Finally reads 20 rows. High I/O overhead.

2. KEYSET SEEK: WHERE (created_at, id) < (T, ID) LIMIT 20
   [Root]
     │ (Direct logarithmic binary search traversal)
     ▼
   [Branch]
     │
     ▼
   [Leaf Node (T, ID)] ──> Reads immediate next 20 leaf pointers.
                           Zero discarded rows. Negligible I/O.

2. Total Immunity to Pagination Drift

Because keyset filtering uses deterministic inequalities anchored to immutable row values, insertions or deletions elsewhere in the table do not affect pagination stability:

• If 50 new orders are inserted at the top of the table with timestamps newer than the cursor, they evaluate to false against the condition created_at < cursor_timestamp. They are ignored.
• If a row before or after the cursor is deleted, the cursor still points to the exact coordinate boundary. No records are skipped, and no records are duplicated.

Keyset Tradeoffs

Keyset pagination introduces specific design constraints:

• No Random Page Access: Clients cannot jump directly to "Page 14" without traversing sequentially from page 1 through 13.
• Strict Ordering Requirements: Every query must be deterministically sorted using a unique, immutable tiebreaker.
• Index Coupling: The database must possess an index whose column sequence precisely matches the ORDER BY clause.

---

Paradigm 3: Time-Window / Chunk-Based Pagination (start_time and end_time)

Time-window pagination bounds queries by explicit chronological intervals rather than row limits:

SELECT id, event_type, payload, occurred_at
FROM audit_events
WHERE occurred_at >= '2026-09-17T00:00:00Z'
  AND occurred_at < '2026-09-17T01:00:00Z'
ORDER BY occurred_at ASC;

Partition Pruning in Analytical and Event Storage

High-volume append-only workloads—such as security audit logs, payment webhooks, telemetry events, and financial ledgers—are typically stored in table partitions organized by time ranges (e.g., PostgreSQL declarative range partitioning by day or month):

CREATE TABLE audit_events (
    id UUID NOT NULL,
    event_type VARCHAR(64) NOT NULL,
    occurred_at TIMESTAMPTZ NOT NULL,
    payload JSONB
) PARTITION BY RANGE (occurred_at);

When an API client queries by explicit time boundaries, the database optimizer executes partition pruning. Physical partitions outside the queried interval are excluded before any disk blocks are read.

Tradeoffs: Non-Uniform Density and Chunk Overflow

The primary challenge of time-window pagination is variable event density:

• A payment API during peak business hours might record 80,000 events within a one-hour window.
• The same API during off-peak hours might record only 12 events.

If a client requests a fixed time window that spans an unexpected traffic surge, the payload can exceed gateway memory limits. Consequently, resilient production designs often combine time windows with secondary keyset pagination (e.g., WHERE occurred_at >= $start AND occurred_at < $end AND (occurred_at, id) > ($cursor_time, $cursor_id) LIMIT 100).

---

Architectural Comparison Matrix

The following matrix evaluates each pagination strategy across eight architectural dimensions:

| Architectural Dimension | Offset-Based (limit/offset) | Keyset / Cursor (cursor/limit) | Time-Window (start/end) | | :--- | :--- | :--- | :--- | | Speed at Page 1 | Fast ($O(K)$) | Fast ($O(\log M + K)$) | Fast ($O(\log M + K)$) | | Speed at Page 1,000+ | Degrades linearly ($O(N + K)$) | Constant seek ($O(\log M + K)$) | Constant seek within window | | Drift Resilience | Poor (vulnerable to duplicate/skipped items) | High (fully deterministic boundary) | High (isolated temporal slice) | | Random Page Access | Supported ("Jump to page 25") | Not supported (sequential only) | Temporal jumping supported | | Index Requirements | Single index on sort column | Composite B-Tree index with tiebreaker | Index on timestamp / partitioned table | | Query Complexity | Simple SQL construct | Moderate (tuple comparison & cursors) | Moderate (time parsing & bounds checking) | | Buffer Cache Impact | Severe buffer cache eviction at depth | Minimal (touches only requested rows) | Localized to queried partitions | | Ideal Production Use Case | Admin grids, static catalogs, low volume | Mobile feeds, infinite scroll, high-scale APIs | Audit trails, metric exports, event streams |

---

Database Indexing and the Tiebreaker Invariant

Implementing keyset pagination requires understanding how database storage engines resolve equality and ordering.

The Myth of Unique Timestamps

A common backend mistake is sorting keyset pagination solely by a timestamp column:

-- DANGEROUS: Timestamps alone are non-deterministic
SELECT id, title, created_at
FROM articles
WHERE created_at < '2026-09-17T08:00:00.000Z'
ORDER BY created_at DESC
LIMIT 20;

In high-concurrency systems, multiple records routinely share identical millisecond or microsecond timestamps. Batch jobs, bulk imports, and concurrent worker threads frequently insert dozens of rows within the exact same database transaction timestamp.

If multiple records share the exact timestamp of the cursor boundary:

1. The database cannot guarantee a stable ordering among identical keys.
2. The inequality created_at < cursor_timestamp skips all other rows sharing that timestamp.
3. If the query uses <=, the client may fetch the same records repeatedly, creating an infinite pagination loop.

TIMESTAMP COLLISION FAILURE MODE

Database Records:
  Row 1: created_at = 10:00:00.120, id = 101
  Row 2: created_at = 10:00:00.100, id = 102  <-- Page 1 ends here (cursor = 10:00:00.100)
  Row 3: created_at = 10:00:00.100, id = 103  <-- Same timestamp!
  Row 4: created_at = 10:00:00.100, id = 104  <-- Same timestamp!
  Row 5: created_at = 10:00:00.050, id = 105

Client requests Page 2 with WHERE created_at < '10:00:00.100':
  Row 3 and Row 4 are silently skipped because their created_at is NOT LESS THAN 10:00:00.100!
  Result: Silent data loss.

The Mandatory Composite Tiebreaker

To guarantee deterministic ordering, keyset queries must include a secondary column that is guaranteed to be globally unique—such as an auto-incrementing integer primary key, a UUIDv7, or an internal monotonic sequence.

The ordering specification becomes a composite tuple: (created_at, id).

Row-Value Constructors vs Boolean Disjunctions

In ANSI SQL:1992 and modern engines (including PostgreSQL 9.6+ and MySQL 8.0+), row-value constructors express multi-column keyset conditions cleanly:

WHERE (created_at, id) < ($cursor_created_at, $cursor_id)
ORDER BY created_at DESC, id DESC

For databases or query generators with incomplete support for row-value comparisons on multi-column indexes, the logically equivalent expanded boolean disjunction must be used:

WHERE (created_at < $cursor_created_at)
   OR (created_at = $cursor_created_at AND id < $cursor_id)
ORDER BY created_at DESC, id DESC

Performance Note: Modern PostgreSQL optimizers treat (a, b) < ($1, $2) as an index range condition, matching a composite B-Tree index scan directly. In contrast, complex OR trees can occasionally prevent the planner from using an index efficiently unless written carefully.

Production PostgreSQL DDL Schema

To support keyset pagination with zero disk seeks, the database index must match both the sorting columns and their directionality:

-- Production Orders Table
CREATE TABLE orders (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    customer_id UUID NOT NULL,
    total_amount_cents BIGINT NOT NULL,
    status VARCHAR(32) NOT NULL DEFAULT 'pending',
    created_at TIMESTAMPTZ NOT NULL DEFAULT clock_timestamp()
);

-- 1. Composite B-Tree index for global descending pagination
-- Both columns must specify DESC to match index traversal order
CREATE INDEX idx_orders_created_at_id 
ON orders (created_at DESC, id DESC);

-- 2. Filtered composite index for tenant- or customer-scoped pagination
CREATE INDEX idx_orders_customer_created_at_id 
ON orders (customer_id, created_at DESC, id DESC);

By indexing (created_at DESC, id DESC), the B-Tree leaf pages are stored in physical sort order. PostgreSQL traverses the index in forward sequence, eliminating the need for an in-memory Sort node in the execution plan.

---

Opaque Cursor Architecture & Protocol Design

Exposing raw database column values directly in query parameters—such as ?last_created_at=2026-09-17&last_id=102—creates tight coupling between the client and internal database schema.

Why Cursors Must Be Opaque

1. Schema Decoupling: An API should treat its database storage format as a private implementation detail. If you later transition from an auto-incrementing integer id to a sortable UUIDv7 or change a timestamp column, exposing raw columns breaks external API clients.
2. Tamper Resistance: When parameters are exposed individually, clients attempt to synthesize their own navigation logic, passing invalid timestamp-id pairs that violate index constraints.
3. Multi-Column Flexibility: Keyset navigation may involve complex sorting (e.g., priority, score, timestamp, and ID). Encoding these fields into a single opaque string gives consumers a single, uniform parameter to manage: ?cursor=....

Cursor Anatomy: Base64URL Serialization

An opaque cursor is typically a URL-safe Base64-encoded JSON or protocol buffer payload:

OPAQUE CURSOR ENCODING WORKFLOW

1. Application State Payload:
   {
     "t": 1758097800000,                           // Timestamp (epoch milliseconds)
     "id": "b2d88a10-2d88-4c92-8092-91f868adbc01", // Tiebreaker primary key
     "v": 1                                         // Schema version
   }
                           │
                           ▼ JSON Stringify
   '{"t":1758097800000,"id":"b2d88a10-2d88-4c92-8092-91f868adbc01","v":1}'
                           │
                           ▼ Base64URL Encode (RFC 4648)
   "eyJ0IjoxNzU4MDk3ODAwMDAwLCJpZCI6ImIyZDg4YTEwLTJkODgtNGM5Mi04MDkyLTkxZjg2OGFkYmMwMSIsInYiOjF9"

The cursor payload includes:

• t: The primary sort value (e.g., epoch milliseconds to avoid timezone parsing anomalies).
• id: The unique tiebreaker identifier.
• v: A schema version integer, allowing the server to evolve its cursor encoding over time without invalidating active sessions.

The $N+1$ Query Pattern (Eliminating COUNT(*))

A common anti-pattern in paginated APIs is computing the total number of records on every page request:

-- EXPENSIVE ANTI-PATTERN: Forces full index or table scan
SELECT COUNT(*) FROM orders;

In MVCC databases like PostgreSQL, COUNT(*) cannot read a cached table counter because row visibility depends on the current transaction snapshot. It must scan the entire index or heap, destroying pagination performance on large tables.

Furthermore, API clients consuming paginated feeds rarely require an exact count of hundreds of thousands of items. They simply need to know: "Is there another page available?"

The $N+1$ Query Pattern determines page availability with zero extra database queries:

1. The client requests a page with limit = 20.
2. The server queries the database with LIMIT 21 (requested_limit + 1).
3. If the database returns 21 rows:
   • More data exists: has_more = true.
   • The server drops the 21st record and returns the first 20 records in the response payload.
   • The server serializes the sort attributes of the 20th record into next_cursor.
4. If the database returns 20 or fewer rows:
   • End of dataset reached: has_more = false, next_cursor = null.

N+1 FETCH PATTERN (Client requests limit=4)

Database Query: LIMIT 5
Database Returns 5 records: [Row 1, Row 2, Row 3, Row 4, Row 5]

Application Processing:
  - Rows returned (5) > limit (4) ==> has_more = true
  - Discard Row 5 from response data
  - Slice [Row 1, Row 2, Row 3, Row 4] for response
  - next_cursor = encode(Row 4.created_at, Row 4.id)

Payload returned to client:
  {
    "data": [Row 1, Row 2, Row 3, Row 4],
    "pagination": {
      "has_more": true,
      "next_cursor": "eyJ0IjoxNzU4MDk3ODAwMDAw..."
    }
  }

---

REST API Protocol Design: Link Headers vs JSON Envelopes

REST APIs convey pagination state through two primary mechanisms:

1. RFC 8288 Web Linking (Link Headers)

Standardized by RFC 8288 (formerly RFC 5988), the API emits HTTP headers specifying hypermedia navigation links with standard relationship attributes (rel="next", rel="prev"):

HTTP/1.1 200 OK
Content-Type: application/json
Link: <https://api.example.com/v1/orders?cursor=eyJ0IjoxNz...&limit=20>; rel="next",
      <https://api.example.com/v1/orders?cursor=eyJ0IjoxNz...&limit=20&direction=backward>; rel="prev"

[
  { "id": "b2d88a10-...", "total_amount_cents": 12500 }
]

• Advantages: Keeps the JSON response payload purely focused on the resource array. Compliant with strict REST architectural hypermedia constraints.
• Disadvantages: Harder for frontend JavaScript developers to parse (requires header extraction) and less intuitive than inline JSON structures.

2. Structured JSON Response Envelope

The most prevalent modern industry pattern embeds items and pagination metadata within a unified JSON envelope:

{
  "data": [
    {
      "id": "b2d88a10-2d88-4c92-8092-91f868adbc01",
      "customer_id": "99f868ad-4c92-8092-2d88-b2d88a10bc01",
      "total_amount_cents": 12500,
      "status": "completed",
      "created_at": "2026-09-17T08:30:00.000Z"
    }
  ],
  "pagination": {
    "limit": 20,
    "has_more": true,
    "has_previous": false,
    "next_cursor": "eyJ0IjoxNzU4MDk3ODAwMDAwLCJpZCI6ImIyZDg4YTEwLTJkODgtNGM5Mi04MDkyLTkxZjg2OGFkYmMwMSIsInYiOjF9",
    "prev_cursor": null
  }
}

This envelope pattern provides explicit type safety for TypeScript and mobile SDKs while making debugging straightforward in developer tools.

---

Bidirectional Keyset Traversal Mechanics

Supporting backward navigation (before / prev_cursor) in keyset pagination introduces a non-trivial algorithmic requirement: order clause inversion.

The Order Inversion Problem

Assume the API default sort order is descending (ORDER BY created_at DESC, id DESC).

When a client wants to navigate backward from a cursor:

1. The target records are chronologically newer than the cursor.
2. If we simply evaluate WHERE (created_at, id) > ($cursor_time, $cursor_id) with ORDER BY created_at DESC, id DESC LIMIT 21, the database will scan all the way from the newest records in the entire table down to the cursor. We would fetch the first page of the dataset instead of the immediate preceding page.
3. To fetch the immediate preceding records, the SQL query must invert the sort direction to ascending:

   WHERE (created_at, id) > ($cursor_time, $cursor_id)
   ORDER BY created_at ASC, id ASC
   LIMIT 21;
   

4. The database returns the immediate predecessor records in ascending order (oldest to newest).
5. Before returning the records to the client, the application layer must reverse the array in memory so that the client consistently receives records sorted in the expected descending order.

BIDIRECTIONAL TRAVERSAL LOGIC

Default Order: DESCENDING [Row 1 (Newest), Row 2, Row 3, Row 4, Row 5 (Oldest)]

Current View (Page 2): [Row 3, Row 4]
Client clicks "Previous Page" (using Row 3 as cursor):

1. SQL Query for PREVIOUS:
   WHERE (created_at, id) > (Row 3.created_at, Row 3.id)
   ORDER BY created_at ASC, id ASC   <-- INVERT ORDER TO SEEK IMMEDIATE PREDECESSORS
   LIMIT 3 (limit + 1)

2. Database Returns (ASC):
   [Row 2, Row 1]

3. Application Reverses Array:
   [Row 1, Row 2]                    <-- RESTORES CONSISTENT DESCENDING PRESENTATION

---

Concrete TypeScript Implementation: CursorPaginator

The following production-ready TypeScript implementation demonstrates:

1. Type-safe Base64URL cursor serialization and deserialization.
2. Parameterized keyset SQL generation with composite ordering and the $N+1$ fetch pattern.
3. Bidirectional traversal with order inversion and in-memory array reversal.

import { Buffer } from "node:buffer";

/**
 * Structured cursor payload representing the exact boundary position.
 */
export interface CursorPayload {
  t: number;      // Epoch millisecond timestamp of the primary sort key
  id: string;     // Unique identifier tiebreaker
  v: number;      // Schema version
}

/**
 * Standard pagination request parameters.
 */
export interface PaginationParams {
  limit?: number;
  cursor?: string;
  direction?: "forward" | "backward";
}

/**
 * Unified JSON response envelope.
 */
export interface PaginatedResponse<T> {
  data: T[];
  pagination: {
    limit: number;
    hasMore: boolean;
    hasPrevious: boolean;
    nextCursor: string | null;
    prevCursor: string | null;
  };
}

/**
 * Parameterized SQL query structure.
 */
export interface ParameterizedQuery {
  text: string;
  values: unknown[];
}

/**
 * Generic interface for records supporting timestamp-keyset pagination.
 */
export interface IdentifiableRecord {
  id: string;
  created_at: Date | string;
}

export class CursorPaginator {
  private static readonly DEFAULT_LIMIT = 20;
  private static readonly MAX_LIMIT = 100;
  private static readonly CURRENT_VERSION = 1;

  /**
   * Encodes sort attributes into an opaque Base64URL cursor token.
   */
  public static encodeCursor(date: Date | string, id: string): string {
    const timestamp = typeof date === "string" ? new Date(date).getTime() : date.getTime();
    
    if (Number.isNaN(timestamp)) {
      throw new Error("Invalid date provided for cursor encoding");
    }

    const payload: CursorPayload = {
      t: timestamp,
      id,
      v: this.CURRENT_VERSION,
    };

    const json = JSON.stringify(payload);
    return Buffer.from(json, "utf8").toString("base64url");
  }

  /**
   * Decodes and validates an opaque Base64URL cursor token.
   */
  public static decodeCursor(cursor: string): CursorPayload {
    try {
      const decodedJson = Buffer.from(cursor, "base64url").toString("utf8");
      const parsed = JSON.parse(decodedJson) as CursorPayload;

      if (
        typeof parsed !== "object" ||
        parsed === null ||
        typeof parsed.t !== "number" ||
        typeof parsed.id !== "string" ||
        typeof parsed.v !== "number" ||
        Number.isNaN(parsed.t)
      ) {
        throw new Error("Malformed cursor schema");
      }

      return parsed;
    } catch {
      throw new Error("Invalid or unparseable pagination cursor");
    }
  }

  /**
   * Normalizes client request parameters against safety bounds.
   */
  public static normalizeParams(params: PaginationParams): {
    limit: number;
    cursorPayload: CursorPayload | null;
    direction: "forward" | "backward";
  } {
    const rawLimit = params.limit ?? this.DEFAULT_LIMIT;
    const limit = Math.min(Math.max(1, rawLimit), this.MAX_LIMIT);
    const direction = params.direction === "backward" ? "backward" : "forward";
    const cursorPayload = params.cursor ? this.decodeCursor(params.cursor) : null;

    return { limit, cursorPayload, direction };
  }

  /**
   * Generates a parameterized SQL keyset query with N+1 fetch limits.
   * 
   * @param tableName Name of the target table
   * @param params Client pagination parameters
   * @param whereClause Additional filtering conditions (e.g. "customer_id = $1")
   * @param initialValues Parameter values corresponding to whereClause
   */
  public static buildQuery(
    tableName: string,
    params: PaginationParams,
    whereClause = "",
    initialValues: unknown[] = []
  ): ParameterizedQuery {
    const { limit, cursorPayload, direction } = this.normalizeParams(params);
    const fetchLimit = limit + 1; // N+1 pattern to determine has_more

    const values = [...initialValues];
    const predicates: string[] = [];

    if (whereClause.trim()) {
      predicates.push(whereClause.trim());
    }

    let sortOrder = "DESC";

    if (cursorPayload) {
      const cursorDate = new Date(cursorPayload.t).toISOString();
      const timeParamIndex = values.length + 1;
      const idParamIndex = values.length + 2;

      values.push(cursorDate, cursorPayload.id);

      if (direction === "forward") {
        // Forward: seeking records strictly older than the cursor boundary
        predicates.push(`(created_at, id) < ($${timeParamIndex}::timestamptz, $${idParamIndex})`);
        sortOrder = "DESC";
      } else {
        // Backward: seeking records strictly newer than the cursor boundary
        predicates.push(`(created_at, id) > ($${timeParamIndex}::timestamptz, $${idParamIndex})`);
        sortOrder = "ASC"; // Inverted order to scan immediate preceding neighbors
      }
    }

    const whereString = predicates.length > 0 ? `WHERE ${predicates.join(" AND ")}` : "";
    const limitParamIndex = values.length + 1;
    values.push(fetchLimit);

    const sql = `
      SELECT id, created_at, customer_id, total_amount_cents, status
      FROM ${tableName}
      ${whereString}
      ORDER BY created_at ${sortOrder}, id ${sortOrder}
      LIMIT $${limitParamIndex};
    `.trim();

    return { text: sql, values };
  }

  /**
   * Processes the raw N+1 database rows into a structured paginated envelope.
   */
  public static processResults<T extends IdentifiableRecord>(
    rows: T[],
    params: PaginationParams
  ): PaginatedResponse<T> {
    const { limit, cursorPayload, direction } = this.normalizeParams(params);

    const hasMoreInQueryDirection = rows.length > limit;
    const items = hasMoreInQueryDirection ? rows.slice(0, limit) : [...rows];

    // If we paginated backward, the database returned rows sorted ASC.
    // We reverse them to restore consistent descending chronological presentation.
    if (direction === "backward") {
      items.reverse();
    }

    let hasMore = false;
    let hasPrevious = false;

    if (direction === "forward") {
      hasMore = hasMoreInQueryDirection;
      hasPrevious = cursorPayload !== null;
    } else {
      // When paginating backward:
      // 'hasMoreInQueryDirection' indicates whether items exist further back (i.e. newer items)
      hasPrevious = hasMoreInQueryDirection;
      hasMore = true;
    }

    const firstItem = items[0];
    const lastItem = items[items.length - 1];

    const nextCursor = hasMore && lastItem
      ? this.encodeCursor(lastItem.created_at, lastItem.id)
      : null;

    const prevCursor = hasPrevious && firstItem
      ? this.encodeCursor(firstItem.created_at, firstItem.id)
      : null;

    return {
      data: items,
      pagination: {
        limit,
        hasMore,
        hasPrevious,
        nextCursor,
        prevCursor,
      },
    };
  }
}

---

Production Operational Checklist & Anti-Patterns

Before publishing or migrating an API pagination contract, audit your implementation against these common production failure modes:

Critical Anti-Patterns to Avoid

• Unbounded Page Limits: Permitting clients to specify ?limit=100000. Even with keyset indexing, transmitting massive serialized JSON payloads saturates application memory and client DOM renderers. Enforce an immutable MAX_LIMIT (e.g., 100).
• Unindexed Sorting Expressions: Executing ORDER BY score, created_at without a matching multi-column index. In PostgreSQL, this forces an external disk-merge sort (Sort Method: external merge Disk), increasing latency from milliseconds to tens of seconds.
• Single-Column Non-Unique Keyset Seeks: Filtering with WHERE created_at < $cursor without a unique tiebreaker, creating non-deterministic sorting and silent record omission during timestamp collisions.
• Full Table Counts on Large Datasets: Issuing SELECT COUNT(*) FROM table on millions of records to compute total pages. Replace page totals with boolean has_more indicators calculated via the $N+1$ fetch pattern.
• Exposing Internal Identifiers in Query Strings: Exposing database-specific IDs directly in query parameters instead of opaque tokens, preventing backend teams from refactoring primary key strategies.

---

Production Verification Checklist

1. [ ] Index Alignment: Does a composite B-Tree index exist whose column order and sort direction (ASC/DESC) precisely match the query's ORDER BY clause?
2. [ ] Unique Tiebreaker Enforced: Is a unique column (e.g., primary key id or UUIDv7) included as the final element in both the ORDER BY clause and composite index?
3. [ ] Execution Plan Verified: Has the query plan been verified in staging using EXPLAIN (ANALYZE, BUFFERS) to confirm an Index Scan or Index Only Scan without in-memory or on-disk sort steps?
4. [ ] Opaque Base64URL Cursors: Are cursor payloads serialized as opaque, URL-safe Base64 strings with schema versioning?
5. [ ] $N+1$ Fetch Pattern Implemented: Does the query request limit + 1 rows to calculate has_more without issuing a secondary COUNT(*) query?
6. [ ] Bidirectional Inversion Handled: Does backward pagination invert SQL ordering and reverse the application-layer array to preserve uniform item presentation?
7. [ ] Graceful Boundary Handling: Does the system return an empty array with has_more: false and next_cursor: null when the end of a dataset is reached?
8. [ ] Input Sanitization: Are invalid, corrupted, or tampered cursor strings rejected with a structured 400 Bad Request rather than causing an unhandled 500 Internal Server Error?

---

Conclusion & Strategic Decision Matrix

Designing a robust pagination strategy requires selecting the right storage access pattern for your system's consistency and scale requirements:

• Use Offset-Based Pagination when building internal administrative tools or back-office dashboards where datasets remain small (under 50,000 records) and operators explicitly require direct jumping to arbitrary page numbers.
• Use Keyset / Cursor-Based Pagination for all high-volume, public-facing REST APIs, mobile feeds, real-time activity streams, and infinite-scrolling user interfaces where data consistency, low latency, and predictable database I/O are mandatory.
• Use Time-Window Pagination for append-only audit trails, telemetry logs, event streaming pipelines, and analytical exports aligned with physical database partitioning.

By implementing opaque composite keyset cursors backed by targeted B-Tree indexes, you eliminate pagination drift, decouple client contracts from database internals, and ensure your API delivers consistent, constant-time performance regardless of dataset growth.