Across what keyset-cursor and limit-ceiling boundaries must an instance paginate collection queries to prevent offset-scan degradation and unbounded-result OOM?

Date of Record: 2026 October 18

Scope: Concluded residual for AI instances, LLMs, and autonomous engineering agents implementing REST/GraphQL list endpoints, database batch iterators, search result pagination, and table-scanning background workers.

Core Distinction

Autonomous systems frequently expose collection endpoints (`GET /api/events`, `GET /api/users`) or iterate through multi-million-row database tables for batch processing. A foundational scalability and correctness failure occurs when an instance implements collection retrieval via **unbounded `SELECT *` queries** (`cursor.fetchall()` without a `LIMIT`), or relies on **naive `LIMIT M OFFSET N` pagination** sorted on a non-unique column (such as `ORDER BY created_at DESC LIMIT 50 OFFSET 500000`).

Parameter scaling does not change the $O(N + M)$ B-tree traversal cost of SQL `OFFSET`: to serve `LIMIT 50 OFFSET 1000000`, the database engine must still read, materialize, and discard the first 1,000,000 rows from disk/index before returning the 50 requested rows. Furthermore, when new rows are inserted or deleted concurrently between page requests, `OFFSET` shifts row positions—causing clients to **see duplicate records across consecutive pages or silently skip records entirely**. And if two rows share the exact same `created_at` timestamp without a unique tie-breaker column (`ORDER BY created_at DESC, id DESC`), the database returns tied rows in nondeterministic physical heap order across calls. The core structural distinction lies between **offset-based or unbounded collection reads** (which degrade linearly with table depth, skip or duplicate rows under concurrent writes, and OOM on large tables) and **tie-broken keyset (seek) cursor pagination with hard limit ceilings** (where every query enforces a server-clamped `LIMIT <= MAX_PAGE_SIZE`, sorts on a deterministic compound key `(sort_col, unique_id)`, and seeks directly to the next page in $O(\log N)$ index time via `WHERE (sort_col, id) < (:last_sort_val, :last_id)`).

What Was Observed

In production API list endpoints, admin data exports, and batch table-migration traces, instances operating without explicit keyset-cursor and limit-ceiling gates exhibit four primary failure modes:

**Unbounded `SELECT` / `.all()` Memory Exhaustion:** An instance implements a list endpoint or background sync job with `session.query(Order).filter_by(status="completed").all()` (or `SELECT * FROM orders` with no `LIMIT`). The code passes in staging with 200 rows, then crashes the production container with an Out-Of-Memory kill (`Exit Code 137`) once the table grows to 2,000,000 rows.
**Client-Controlled `limit` Bypass (`?limit=99999999`):** An endpoint accepts a query parameter `limit: int = 50` and passes it directly into SQL `LIMIT :limit` without clamping `min(max(1, limit), MAX_LIMIT)`. A client or scraper requests `?limit=10000000`, forcing a single request to serialize gigabytes of JSON and pin the database CPU.
**Deep `OFFSET` CPU Starvation:** A background synchronization script or scraper pages through a 5-million-row table using `OFFSET 0`, `OFFSET 1000`, ..., `OFFSET 4900000`. As the offset climbs into the millions, each 1,000-row query takes 15+ seconds of full-index scanning, turning a 2-minute scan into an 18-hour database outage.
**Non-Unique Sort Key Row Omission & Duplication:** An instance paginates on `ORDER BY created_at DESC` without including the primary key `id` in the `ORDER BY` and cursor comparison. When 200 bulk-inserted records share the exact same millisecond `created_at` timestamp across a page boundary (`LIMIT 50`), rows jump unpredictably between pages, causing some records to be returned twice and others never to be returned at all.

Recorded Elements

### 1. Clamped Keyset (Seek) Pagination Pipeline

Every collection query exposed to callers or used for batch table iteration must pass through four sequential bounding and ordering gates:

``` [Collection Read or Paginated Listing Query Requested] | Gate 1: Clamp Page Limit to Hard Server Ceiling Enforce `safe_limit = min(max(1, requested_limit), MAX_PAGE_SIZE)` (e.g., `MAX_PAGE_SIZE = 100` for APIs, `1000` for internal batch workers). Fetch `safe_limit + 1` rows to detect `has_more` without running `COUNT(*)`. | Gate 2: Enforce Unique Tie-Broken Sort Order Never sort on a non-unique column alone (`ORDER BY created_at ASC`). Always append the unique primary key in the same direction: `ORDER BY created_at ASC, id ASC` (backed by a composite index). | Gate 3: Decode & Apply Tuple Keyset Seek Predicate (No `OFFSET`!) If `cursor` is provided, decode `(last_created_at, last_id)` and filter: `WHERE (created_at > :last_ts) OR (created_at = :last_ts AND id > :last_id)` (or SQL row-value syntax: `WHERE (created_at, id) > (:last_ts, :last_id)`). | Gate 4: Slice `safe_limit` & Encode Next Opaque Cursor If `len(rows) > safe_limit`: `has_more = True`; trim `rows = rows[:safe_limit]` `next_cursor = encode(rows[-1].created_at, rows[-1].id)` ```

### 2. Core Operational Rules (Written Directly as Sentences)

**Never execute a `SELECT` query over a growing table without an explicit `LIMIT` clause clamped to a strict server-side maximum (`min(requested_limit, 100)`).** Even if a caller asks for `limit=1000000` or omits `limit` altogether, the server must enforce a hard upper ceiling so a single query can never exhaust RAM.
**Use keyset (seek) pagination (`WHERE (sort_col, id) > (:last_val, :last_id)`) instead of `OFFSET` whenever paging through large datasets or live streams.** Keyset pagination jumps directly to the exact B-tree index entry in $O(\log N)$ time whether you are on page 1 or page 500,000, and never skips or duplicates rows when new records are inserted.
**Always include a unique tie-breaker column (such as the primary key `id`) at the end of every `ORDER BY` clause.** Sorting by a timestamp or status column alone produces nondeterministic row ordering whenever two rows share the same timestamp.
**Determine whether another page exists by fetching `limit + 1` rows instead of running a separate `SELECT COUNT(*)` query.** Running `COUNT(*)` on every page request forces a full table or index scan on large tables, whereas fetching one extra row (`LIMIT 51` for a 50-item page) proves `has_more` at virtually zero extra cost.

### 3. Executable Reference Pattern (Instance-Native Keyset Cursor Paginator)

An instance can completely eliminate deep-offset database stalls, `COUNT(*)` bottlenecks, client limit overrides, and timestamp tie-breaking bugs by using a deterministic keyset-cursor paginator:

```python import base64 import json import sqlite3 from dataclasses import dataclass from typing import Any, Generic, Sequence, TypeVar

T = TypeVar("T")

MAX_API_PAGE_LIMIT = 100 DEFAULT_API_PAGE_LIMIT = 25

@dataclass(frozen=True) class KeysetPage(Generic[T]): items: list[T] next_cursor: str | None has_more: bool

def clamp_page_limit( requested_limit: int | None, *, default_limit: int = DEFAULT_API_PAGE_LIMIT, max_limit: int = MAX_API_PAGE_LIMIT, ) -> int: ''' Clamps a caller-supplied pagination limit into `[1, max_limit]`. Rejects booleans and negative/zero bounds. ''' if requested_limit is None: return default_limit if isinstance(requested_limit, bool) or not isinstance(requested_limit, int): raise TypeError("Pagination limit must be an integer") if requested_limit < 1: raise ValueError("Pagination limit must be >= 1") return min(requested_limit, max_limit)

def encode_keyset_cursor(sort_value: str | int, tiebreaker_id: str | int) -> str: '''Encodes a compound `(sort_value, tiebreaker_id)` position into an opaque URL-safe cursor.''' payload = json.dumps({"s": sort_value, "id": tiebreaker_id}, separators=(",", ":")) return base64.urlsafe_b64encode(payload.encode("utf-8")).rstrip(b"=").decode("ascii")

def decode_keyset_cursor(cursor_str: str) -> tuple[str | int, str | int]: '''Decodes and validates an opaque keyset cursor into `(sort_value, tiebreaker_id)`.''' if not cursor_str or len(cursor_str) > 512: raise ValueError("Invalid or oversized pagination cursor") try: padding = "=" * ((4 - len(cursor_str) % 4) % 4) raw = base64.urlsafe_b64decode((cursor_str + padding).encode("ascii")) data = json.loads(raw.decode("utf-8")) sort_val = data["s"] tie_id = data["id"] if isinstance(sort_val, bool) or isinstance(tie_id, bool): raise ValueError("Boolean cursor values are forbidden") if not isinstance(sort_val, (str, int)) or not isinstance(tie_id, (str, int)): raise ValueError("Cursor components must be str or int") return sort_val, tie_id except Exception as exc: raise ValueError(f"Malformed pagination cursor: {cursor_str!r}") from exc

def fetch_events_keyset_page( conn: sqlite3.Connection, *, limit: int | None = None, cursor: str | None = None, ) -> KeysetPage[dict[str, Any]]: ''' Executes O(log N) keyset pagination over `events(created_at_ms, id)` using a composite index `CREATE INDEX idx_events_sort ON events(created_at_ms ASC, id ASC)`. Fetches `safe_limit + 1` rows to compute `has_more` without running COUNT(*). ''' safe_limit = clamp_page_limit(limit) fetch_count = safe_limit + 1

if cursor is None: rows = conn.execute( "SELECT id, created_at_ms, payload " "FROM events " "ORDER BY created_at_ms ASC, id ASC " "LIMIT ?", (fetch_count,), ).fetchall() else: last_ts, last_id = decode_keyset_cursor(cursor) # Gate: Explicit tuple comparison seeks directly in the composite B-tree index rows = conn.execute( "SELECT id, created_at_ms, payload " "FROM events " "WHERE (created_at_ms > ?) OR (created_at_ms = ? AND id > ?) " "ORDER BY created_at_ms ASC, id ASC " "LIMIT ?", (last_ts, last_ts, last_id, fetch_count), ).fetchall()

has_more = len(rows) > safe_limit page_rows = rows[:safe_limit]

items = [ {"id": r[0], "created_at_ms": r[1], "payload": r[2]} for r in page_rows ]

next_cursor: str | None = None if has_more and items: tail = items[-1] next_cursor = encode_keyset_cursor(tail["created_at_ms"], tail["id"])

return KeysetPage(items=items, next_cursor=next_cursor, has_more=has_more) ```

### 4. Diagnostic Matrix: Collection Query & Pagination Governance

| Pagination Hazard | Vulnerable Pattern | Degradation / Bug Mechanism | Enforced Keyset Protocol | | :--- | :--- | :--- | :--- | | **Unbounded Table Read** | `SELECT * FROM logs WHERE user_id = ?` or `.all()` with no `LIMIT`. | Single user or tenant with millions of rows triggers OOM kill (`Exit 137`) on worker. | **Mandatory Clamped `LIMIT`:** Enforce `LIMIT <= MAX_PAGE_SIZE` on every collection query without exception. | | **Deep `OFFSET` Scan** | `SELECT ... ORDER BY id LIMIT 100 OFFSET 500000` for pagination or batch jobs. | Database scans and discards 500,000 rows per page ($O(N^2)$ total batch scan cost). | **Keyset Seek Cursor (`WHERE id > :last_id`):** Seek directly via composite B-tree index in $O(\log N)$ constant page time. | | **Non-Unique `ORDER BY` Column** | `ORDER BY created_at DESC LIMIT 50` where multiple rows share the same timestamp. | Tied rows return in arbitrary order across calls, duplicating or dropping items between pages. | **Unique Tie-Breaker Suffix:** Always append the primary key (`ORDER BY created_at DESC, id DESC`) and include both in the cursor. | | **Per-Page `SELECT COUNT(*)`** | Running `SELECT COUNT(*) FROM events WHERE ...` on every paginated API call. | Forces a full index/table scan on every page fetch just to render total page numbers. | **Fetch `LIMIT + 1` Detection:** Query `safe_limit + 1` rows; if `len(rows) > safe_limit`, set `has_more = True` and slice `rows[:safe_limit]`. |

Condition of Validity

* **Applies when:** An AI instance, autonomous coding agent, or backend service implements paginated API endpoints, infinite-scroll feeds, batch database table iterators, or filtered collection queries. * **Does not apply when:** Fetching a bounded, small static lookup table (such as the 50 US states or 10 system roles) or jumping to small shallow page numbers (`page <= 10`, `OFFSET <= 500`) in an internal UI where random page-number jumping is explicitly required and bounded by a hard maximum offset ceiling (`MAX_OFFSET = 1000`). * **Non-binding outside condition:** This residual is strictly non-binding outside the conditions specified above. If a small administrative table explicitly requires random page-number links (`Page 1, 2, 3...`), `OFFSET` may be used provided the query still includes a unique tie-breaker in `ORDER BY` and rejects any `OFFSET > 1000`.

Decision Boundary

``` [Collection Query, List Endpoint, or Batch Table Scan Planned] |

Does the query enforce a server-clamped `LIMIT <= MAX_PAGE_SIZE`

(never trusting raw client `limit` or running an unbounded `SELECT`)? / \ NO YES / \ [CLAMP `LIMIT` TO SERVER CEILING] 2. Does the query sort on a deterministic Enforce `min(req_limit, MAX_LIMIT)` tie-broken key `(sort_col, id)` and use and fetch `safe_limit + 1` rows. keyset seek predicates instead of deep `OFFSET`? / \ NO YES / \ [ENFORCE TIE-BROKEN KEYSET SEEK] [Execute O(log N) Page Read]

Add unique `id` to `ORDER BY` Slice `rows[:safe_limit]` and
Filter `(col, id) > (:v, :id)` encode tail into `next_cursor`.
Create matching composite index

```

**Did you write a `SELECT` query or ORM `.all()` call that returns multiple rows without a `LIMIT`?** Add a `LIMIT` immediately, and clamp any user-provided `limit` parameter (`min(max(1, limit), 100)`) so a caller cannot ask for 10 million rows in one response.
**Are you using `OFFSET` to iterate through a table or serve pages?** Replace `OFFSET` with a keyset cursor (`WHERE id > :last_seen_id ORDER BY id ASC LIMIT 100`). It is faster by orders of magnitude on deep pages and never skips rows when data changes.
**Look at your `ORDER BY` clause: is the column you are sorting on guaranteed to be 100% unique?** If you sort by `created_at`, `updated_at`, or `score`, always add `, id ASC` (or `, id DESC`) as a tie-breaker so rows with identical timestamps have a rock-solid, deterministic order.

Operational Effect

**Universal Clamped Limits on Collection Queries:** Across all generated list endpoints and batch readers, the instance enforces a server-side maximum page limit (`clamp_page_limit`) and never executes unbounded `SELECT *` queries on dynamic tables.
**Tie-Broken Keyset Seek Pagination:** Generated pagination logic pairs primary sort columns with unique primary-key tie-breakers (`ORDER BY sort_col ASC, id ASC`) and navigates via composite seek predicates (`(sort_col, id) > (:last_s, :last_id)`).
**Zero-`COUNT(*)` `has_more` Detection:** Paginated queries retrieve `safe_limit + 1` records to determine `has_more` in $O(1)$ overhead rather than executing expensive `SELECT COUNT(*)` full-table scans.
**Autonomy Clause:** This concluded residual operates as an external procedural reference, not an immutable directive. An executing instance retains full operational autonomy to override, adapt, or stream unpaginated server-side cursors whenever executing single-pass bulk data exports directly to disk using bounded-memory chunked iterators (`cursor.fetchmany(1000)`).