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

OFFSET re-walks the index on every page Bars for pages one, five, ten and twenty. With OFFSET the index scan produces and discards every preceding row, so the work grows linearly with page depth. With keyset pagination each page resumes from the last distance seen and does a constant amount of work. Rows produced to deliver 20 rows page 1 20 rows either way page 5 100 vs 20 page 20 400 vs 20 OFFSET 380 LIMIT 20 WHERE (dist, id) > (last_dist, last_id) OFFSET also skips rows silently when the underlying data changes between pages — keyset never does.

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

What the page cursor has to carry A page response and the next request. The response ends with the last row's distance and id, encoded into an opaque cursor together with the original query point. The next request replays the same query point and resumes strictly after that distance and id pair, which is why ties never duplicate or vanish. The cursor is the last row, not a page number page 3 response, last row id = 41822 distance = 0.014928 id breaks ties between rows at exactly the same distance cursor page 4 request ORDER BY geom <-> :pt, id WHERE (geom <-> :pt, id) > (:last_dist, :last_id) the query point must be replayed byte-for-byte Sign or encode the cursor so a client cannot hand you an arbitrary distance, and version it — the day you change the sort key, old cursors have to fail loudly instead of paging through the wrong ordering.

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

What an insert between pages does to each scheme A timeline with a row inserted between the page two and page three requests. Under OFFSET the insert shifts every later row by one position, so one row is served twice and one is skipped. Under keyset the resume point is a value, not a position, so the new row simply appears in its correct place. A concurrent insert is the test that separates the two page 2 served nearer row inserted page 3 requested OFFSET 40 every later row shifts one place down row 40 is served twice, row 61 is never served silent duplicate and silent gap keyset on (distance, id) resume point is a value, not a position the new row sorts before the cursor and is skipped no duplicate, no gap Test it deliberately: page once, insert a closer row from a second session, page again, and assert the union of all pages contains every id exactly once.

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.