Keyset Pagination for KNN Result Sets

Serving a “nearest stores” list one page at a time looks trivial until the second page arrives with a store the customer already saw. This page sits under the broader KNN nearest neighbor query patterns, and it addresses one narrow failure: paginating an index-ordered <-> nearest-neighbour scan stably. The dataset is a retail store locator — a stores table typed geometry(Point, 4326) — and the goal is to walk outward from a customer coordinate, twenty nearest stores per page, without the naive OFFSET that re-scans and reshuffles the list on every request.

Problem Statement

The store-finder endpoint returns the closest branches to a shopper’s location. The first page is fast: an ORDER BY geom <-> point LIMIT 20 rides the GiST index and returns in a couple of milliseconds. The trouble is page two. The obvious OFFSET 20 LIMIT 20 re-runs the entire ordered traversal, throws away the first twenty rows it just computed, and only then returns rows twenty-one through forty. Cost climbs with every page, and — worse for correctness — any store inserted, deleted, or relocated between requests slides the offset window and produces duplicated or skipped branches. A keyset (seek) approach fixes both problems by paging on the last row’s (distance, id) pair instead of a positional row count.

Why the Naive Approach Fails

Here is the version that ships in most first drafts:

python
# Anti-pattern: OFFSET re-scans the whole KNN ordering on every page
def fetch_page_offset(conn, lon, lat, page, page_size=20):
    sql = """
        SELECT id, name,
               geom <-> ST_SetSRID(ST_MakePoint(%(lon)s, %(lat)s), 4326) AS dist
        FROM stores
        ORDER BY dist
        LIMIT %(limit)s OFFSET %(offset)s;
    """
    with conn.cursor() as cur:
        cur.execute(sql, {"lon": lon, "lat": lat,
                          "limit": page_size, "offset": page * page_size})
        return cur.fetchall()

Two things go wrong. First, OFFSET is computed, not skipped cheaply: to serve page 50 the engine walks the index for the first 1,000 nearest stores and discards 980 of them. The per-page work grows linearly with the page number, so deep pages get progressively slower even though each returns the same twenty rows.

Second, and more insidious, the ordering is recomputed from scratch on every call. If a new pop-up store is inserted nearer the customer than the current page-two boundary between the two requests, every downstream row shifts one slot outward. The row that was position 40 becomes position 41, and page three re-serves it. Delete a store instead and a branch silently vanishes from the sequence. The offset is a count into a moving list, and the list moves.

You cannot repair this by holding a server-side cursor open across HTTP requests either — a stateless API has nowhere to keep the transaction alive, and a WITH HOLD cursor per user does not scale.

Production-Ready Implementation

The stable approach carries a cursor token — the (dist, id) of the last row on the previous page — and seeks strictly past it. The ORDER BY geom <-> point, id still drives the KNN index scan; the row-comparison predicate in the WHERE clause prunes the prefix that was already served.

python
import base64
import json
import psycopg
from psycopg.rows import dict_row

DSN = "postgresql://app:secret@10.0.2.7:5432/retail"
PAGE_SIZE = 20


def _encode_cursor(dist: float, store_id: int) -> str:
    """Opaque token the client echoes back for the next page."""
    raw = json.dumps({"d": dist, "i": store_id}).encode("utf-8")
    return base64.urlsafe_b64encode(raw).decode("ascii")


def _decode_cursor(token: str) -> tuple[float, int]:
    raw = base64.urlsafe_b64decode(token.encode("ascii"))
    obj = json.loads(raw)
    return float(obj["d"]), int(obj["i"])


def fetch_nearest_stores(lon: float, lat: float,
                         cursor_token: str | None = None,
                         page_size: int = PAGE_SIZE) -> dict:
    """
    Return one page of nearest stores to (lon, lat), ordered by distance.

    Distances are in SRS units (degrees for EPSG:4326 geometry) and are used
    only for ordering and as the seek key. The GiST index on stores(geom)
    drives the ordered scan; the WHERE row-comparison skips the served prefix.
    """
    point = "ST_SetSRID(ST_MakePoint(%(lon)s, %(lat)s), 4326)"

    if cursor_token is None:
        # First page: no seek predicate, pure ordered KNN scan.
        where = ""
        params = {"lon": lon, "lat": lat, "limit": page_size}
    else:
        last_dist, last_id = _decode_cursor(cursor_token)
        # Seek strictly past (last_dist, last_id) in the (distance, id) order.
        where = f"""
            WHERE (geom <-> {point}) > %(last_dist)s
               OR ( (geom <-> {point}) = %(last_dist)s AND id > %(last_id)s )
        """
        params = {"lon": lon, "lat": lat, "limit": page_size,
                  "last_dist": last_dist, "last_id": last_id}

    sql = f"""
        SELECT id, name,
               geom <-> {point} AS dist
        FROM stores
        {where}
        ORDER BY geom <-> {point}, id
        LIMIT %(limit)s;
    """

    with psycopg.connect(DSN, row_factory=dict_row) as conn:
        with conn.cursor() as cur:
            cur.execute(sql, params)
            rows = cur.fetchall()

    next_token = None
    if len(rows) == page_size:
        tail = rows[-1]
        next_token = _encode_cursor(float(tail["dist"]), tail["id"])

    return {"rows": rows, "next_cursor": next_token}

The seek predicate reads as “distance greater than the last one, or the same distance but a higher id”. That is exactly the lexicographic successor of the previous page’s final row under the (dist, id) ordering. Because the ORDER BY clause is unchanged, PostgreSQL keeps using the GiST-accelerated <-> traversal: it walks the index tree in ascending distance and simply discards leaf rows that fail the filter until it reaches the seek point, then emits the next twenty.

A store inserted between requests can only ever appear at a distance/id position the client has not yet reached, or one it has already passed — never on a page boundary it has already crossed. The token is anchored to values that belong to a specific row, not to a count, so the sequence is stable under concurrent writes.

Configuration and Tuning Knobs

Setting Recommended value Effect on keyset KNN paging
page_size 20–50 Rows per request. Small pages keep each <-> scan cheap; the seek makes deep pages no more expensive than shallow ones.
work_mem 8MB–32MB Rarely the bottleneck here — a LIMIT 20 KNN scan sorts almost nothing. Keep it modest so concurrent connections do not multiply memory.
random_page_cost 1.1 (SSD) Keeps the planner on the GiST index scan rather than a sequential scan plus sort.
prepare_threshold (psycopg 3) 5 Lets psycopg auto-prepare the seek statement so repeated pages reuse one plan. Keep the SQL string identical across pages.

Because the query text differs between the first page (no WHERE) and subsequent pages (with the seek predicate), the driver prepares two distinct plans — that is fine and intended. Do not string-format the coordinates into the SQL; the %(lon)s bind parameters keep the statement text stable so plan caching actually engages.

If you expose this behind a connection pooler such as PgBouncer in transaction mode, keyset paging is a natural fit: each page is a single, self-contained statement with no server-side state to preserve between requests.

Verification Steps

1. Confirm the ordered scan still uses the index on a seek page:

sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, geom <-> ST_SetSRID(ST_MakePoint(-71.0589, 42.3601), 4326) AS dist
FROM stores
WHERE (geom <-> ST_SetSRID(ST_MakePoint(-71.0589, 42.3601), 4326)) > 0.0142
   OR ( (geom <-> ST_SetSRID(ST_MakePoint(-71.0589, 42.3601), 4326)) = 0.0142
        AND id > 8134 )
ORDER BY geom <-> ST_SetSRID(ST_MakePoint(-71.0589, 42.3601), 4326), id
LIMIT 20;

The plan must contain Index Scan using your stores GiST index, not Seq Scan followed by Sort. A sequential scan here means the SRID of the query point does not match the column, or the index is missing.

2. Assert page boundaries neither duplicate nor drop rows:

python
def assert_stable_pagination(lon, lat, pages=10):
    seen = set()
    token = None
    for _ in range(pages):
        page = fetch_nearest_stores(lon, lat, token)
        ids = [r["id"] for r in page["rows"]]
        assert not (set(ids) & seen), f"Duplicate store across pages: {set(ids) & seen}"
        seen.update(ids)
        token = page["next_cursor"]
        if token is None:
            break
    print(f"Walked {len(seen)} unique stores with no duplicates")

3. Verify distances are non-decreasing across the concatenated pages — the last distance of one page must be less than or equal to the first distance of the next:

python
prev_max = -1.0
token = None
while True:
    page = fetch_nearest_stores(lon, lat, token)
    for r in page["rows"]:
        assert float(r["dist"]) >= prev_max, "Ordering broke across a page boundary"
        prev_max = float(r["dist"])
    token = page["next_cursor"]
    if not token:
        break

Gotchas Checklist

  • Always include the id tiebreak in both the ORDER BY and the seek predicate. Distances tie constantly — two branches in the same shopping plaza can round to identical values, and floating-point equality is fragile. Without the deterministic secondary key the seek cannot distinguish served from unserved rows at a distance tie, and the boundary duplicates or skips them.

  • The cursor token holds a distance in SRS units, not metres. For geometry(Point, 4326) the <-> value is in degrees. It is a valid seek key because it is used purely for ordering, but never render it to the shopper as a distance. Compute ST_Distance on a geography cast of the twenty returned rows if you need to display metres or miles.

  • Keep the query point identical to the token’s origin. The (dist, id) seek key is only meaningful relative to the exact coordinate that produced it. If the client re-centres the map and sends a new lon/lat, discard the old cursor and start from page one — a token from one origin is nonsense against another.

  • Treat the token as opaque and validate it. Base64-encode it and reject malformed input server-side. A client that hand-crafts a last_dist far larger than any real distance will simply get an empty page, which is harmless, but decoding untrusted JSON without bounds still deserves a guard.

  • A missing or stale GiST index collapses the whole scheme. The seek only stays cheap because the ORDER BY <-> rides the index. After a bulk store import, run VACUUM ANALYZE stores so the planner keeps choosing the index scan; a sequential scan plus sort would make every page an O(n log n) operation. See advanced GiST indexing and optimization for maintenance cadence.

Frequently Asked Questions

Why does OFFSET produce duplicate stores between pages?

OFFSET counts rows from the top of a freshly computed ordering on every request. If a store is inserted or its geometry is updated between page one and page two, every row shifts by one position, so the boundary row reappears on the next page. A keyset seek anchors on the last row’s own values instead of a positional count, so concurrent writes cannot shift the anchor.

Can the KNN GiST index still be used when I add a WHERE clause on distance?

Yes. The ordered index scan is driven by the ORDER BY geom <-> point clause. The extra distance predicate in the WHERE clause is applied as a filter while the scan walks the tree in ascending distance order, so the planner still reports an Index Scan rather than a sort over a sequential scan.

Do I need id in the ORDER BY if distances are already unique?

Yes, always include the id tiebreak. Two stores at the same measured distance are common with rounded coordinates, and floating-point distance values are not reliably unique. Without a deterministic secondary key the seek predicate cannot tell which equal-distance rows have already been served, and a page boundary can duplicate or skip them.