Implementing Cursor-Based Pagination for Spatial Queries

Step-by-step guide to replacing OFFSET/LIMIT with keyset cursor pagination in FastAPI and PostGIS: GiST index alignment, Base64 cursor encoding, stable ORDER BY, and edge-case handling.

← Back to Spatial Pagination & Cursor Strategies

Replace OFFSET/LIMIT with a deterministic keyset cursor so PostGIS bounding-box queries page in constant time regardless of dataset depth.

Context & When to Use

OFFSET-based pagination asks PostgreSQL to materialize the entire filtered result set, sort it, discard the first N rows, then return the next batch. For spatial workloads this is doubly expensive: the GiST index that accelerates && or ST_DWithin cannot skip scanned tuples, so query latency grows linearly as page depth increases. At page 500 of a 20-row page, the database discards 9 980 rows on every request.

Keyset pagination eliminates that waste. Instead of skipping rows, the API decodes a cursor representing the last returned row’s primary key, applies a WHERE id > :cursor_id clause, and lets the B-tree index jump straight to that boundary. Query cost becomes proportional to the page size — not the page number. This is the technique described in Spatial Pagination & Cursor Strategies and the right choice whenever your API must serve deep, stable pages of spatial features.

Use this approach when:

  • The result set has more than ~1 000 features and clients page forward sequentially (maps, exports, feeds).
  • Concurrent writes are possible between page requests — offset drift produces duplicate or missing rows, keyset traversal does not.
  • You want your geospatial API architecture to stay stateless: the cursor encodes all resume state so the server stores nothing between requests.

It is not the right tool when clients need random page access (jump to page 47), because keyset traversal is inherently forward-only. For random access, materialize result sets into Redis or accept the offset trade-off on bounded datasets.

Data Flow Overview

The diagram below shows how a single paginated request moves through the stack, from the decoded cursor through the dual-index query to the encoded next cursor in the response.

Cursor-based pagination data flow in FastAPI + PostGISSequence diagram showing: client sends GET /locations?bbox=…&cursor=BASE64, FastAPI decodes cursor to uuid, PostGIS GiST index filters by bounding box, B-tree index applies WHERE id > cursor_id ORDER BY id LIMIT n, rows returned, next cursor encoded and sent in JSON response.ClientFastAPI RoutePostGIS / GiSTB-tree IndexGET /locations?cursor=BASE64decode cursor → uuidgeom && bboxGiST bbox pre-filterid > cursor_idB-tree range scanrows (LIMIT n)encode next_cursorJSON + next_cursor1234567

Schema & Index Prerequisites

Your PostGIS table needs two indexes: a GiST index for the spatial pre-filter, and a B-tree index for keyset traversal. Both must exist before the query planner can execute the pattern efficiently.

CREATE TABLE locations (
    id          UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    name        TEXT NOT NULL,
    geom        GEOMETRY(Point, 4326) NOT NULL,
    created_at  TIMESTAMPTZ DEFAULT NOW()
);

-- Spatial pre-filter: GiST accelerates the && bounding-box operator
CREATE INDEX idx_locations_geom ON locations USING GIST (geom);

-- Keyset traversal: B-tree enables WHERE id > :cursor_id as a range scan
CREATE INDEX idx_locations_id   ON locations (id);

If your workload sorts by distance (ORDER BY geom <-> :origin), also create a compound index on (geom, id) so the planner can resolve the KNN scan and the tiebreaker without a separate sort step.

Runnable Implementation

The endpoint below is production-ready with SQLAlchemy 2.0 async, Pydantic v2, and URL-safe Base64 cursor encoding. The spatial pre-filter uses && (bounding-box overlap, GiST-accelerated), and pagination relies on id > :cursor_id.

import base64
import json
from typing import Optional, List

from fastapi import FastAPI, Query, Depends, HTTPException
from pydantic import BaseModel
from sqlalchemy import text
from sqlalchemy.ext.asyncio import AsyncSession, create_async_engine, async_sessionmaker

DATABASE_URL = "postgresql+asyncpg://user:password@localhost/gisdb"
engine = create_async_engine(DATABASE_URL, pool_size=10, max_overflow=5)
AsyncSessionLocal = async_sessionmaker(engine, expire_on_commit=False)

app = FastAPI()


# ── Models ────────────────────────────────────────────────────────────────────

class LocationOut(BaseModel):
    id: str
    name: str
    geom_wkt: str   # WKT for API transport; swap ST_AsGeoJSON for GeoJSON output
    created_at: str

class PagedLocations(BaseModel):
    items: List[LocationOut]
    next_cursor: Optional[str] = None  # absent → caller is on the last page


# ── Cursor helpers ────────────────────────────────────────────────────────────

def encode_cursor(row_id: str) -> str:
    """Encode a UUID string to a URL-safe Base64 cursor token."""
    payload = json.dumps({"id": row_id}).encode()
    return base64.urlsafe_b64encode(payload).decode()

def decode_cursor(token: str) -> dict:
    """Decode and validate a cursor token; raises 400 on any tampering."""
    try:
        payload = base64.urlsafe_b64decode(token.encode()).decode()
        data = json.loads(payload)
        if "id" not in data:
            raise ValueError("missing id key")
        return data
    except Exception:
        raise HTTPException(status_code=400, detail="Invalid cursor token")


# ── Dependency ────────────────────────────────────────────────────────────────

async def get_db():
    async with AsyncSessionLocal() as session:
        yield session


# ── Route ─────────────────────────────────────────────────────────────────────

@app.get("/locations", response_model=PagedLocations)
async def list_locations(
    bbox: str = Query(
        ...,
        description="Spatial filter: minx,miny,maxx,maxy (EPSG:4326)",
        example="-0.5,51.3,0.2,51.6",
    ),
    cursor: Optional[str] = Query(None, description="Opaque continuation token from previous page"),
    limit: int = Query(20, ge=1, le=200),
    db: AsyncSession = Depends(get_db),
):
    # 1. Parse and validate the bounding box
    try:
        minx, miny, maxx, maxy = map(float, bbox.split(","))
    except (ValueError, TypeError):
        raise HTTPException(status_code=400, detail="bbox must be minx,miny,maxx,maxy")

    # 2. Build the keyset WHERE clause depending on cursor presence
    if cursor:
        cursor_data = decode_cursor(cursor)
        sql = text("""
            SELECT
                id::text        AS id,
                name,
                ST_AsText(geom) AS geom_wkt,
                created_at::text AS created_at
            FROM locations
            WHERE geom && ST_MakeEnvelope(:minx, :miny, :maxx, :maxy, 4326)
              AND id > :cursor_id::uuid   -- keyset resume; B-tree range scan
            ORDER BY id ASC
            LIMIT :limit
        """)
        params = {
            "minx": minx, "miny": miny, "maxx": maxx, "maxy": maxy,
            "cursor_id": cursor_data["id"],
            "limit": limit,
        }
    else:
        sql = text("""
            SELECT
                id::text        AS id,
                name,
                ST_AsText(geom) AS geom_wkt,
                created_at::text AS created_at
            FROM locations
            WHERE geom && ST_MakeEnvelope(:minx, :miny, :maxx, :maxy, 4326)
            ORDER BY id ASC
            LIMIT :limit
        """)
        params = {"minx": minx, "miny": miny, "maxx": maxx, "maxy": maxy, "limit": limit}

    # 3. Execute and map rows
    result = await db.execute(sql, params)
    rows = result.mappings().all()
    items = [LocationOut(**row) for row in rows]

    # 4. Emit next_cursor only when the page is full (signals more pages exist)
    next_cursor = encode_cursor(items[-1].id) if len(items) == limit else None

    return PagedLocations(items=items, next_cursor=next_cursor)

Key Parameters & Options

ParameterTypeDefaultNotes
bboxstrrequiredminx,miny,maxx,maxy in EPSG:4326. Drives ST_MakeEnvelope; the wider the box, the more rows the GiST scan touches.
cursorstrNoneURL-safe Base64 token. Absent on first page; clients pass back whatever next_cursor the API returns.
limitint20Capped at 200. Larger values increase individual query cost but reduce round-trip count for bulk consumers.
ORDER BYSQLid ASCMust be deterministic. Replace id with a composite key if you sort by distance — always append id as a tiebreaker.
ST_MakeEnvelopeSQL—Fourth argument must match the geometry column’s SRID (4326 here). Mismatches produce silent wrong results, not errors.
pool_sizeengine10Size the connection pool relative to your concurrent request volume; spatial queries hold connections longer than simple CRUD.

Gotchas & Failure Modes

  • Floating-point sort instability. Sorting purely by ST_Distance or the <-> operator produces ties for co-located points. The planner may resolve ties differently on each call, causing rows to appear on two consecutive pages or be skipped entirely. Always append , id ASC as the final sort key and encode both the distance and id in the cursor.

  • SRID mismatch in ST_MakeEnvelope. If the geometry column stores data in EPSG:3857 (Web Mercator) but the envelope is built in 4326, the bounding box silently misses or over-selects features. Check with SELECT Find_SRID('public', 'locations', 'geom') before going live.

  • Cursor decoded but index not used. If EXPLAIN ANALYZE shows a sequential scan after adding the cursor, the planner may have decided the filtered row count makes an index scan more expensive. Run ANALYZE locations to refresh table statistics and set random_page_cost = 1.1 on SSD-backed instances to steer the planner back to the index.

  • Limit exactly equals result count on the last page. If the last page happens to contain exactly limit rows, the API emits a next_cursor that resolves to an empty page. Clients must handle an empty items list as the true end-of-stream signal, or you can reduce the internal query limit to limit + 1 and use the extra row only as a lookahead sentinel without including it in the response.

  • URL encoding of the Base64 token. Standard Base64 uses + and /, which must be percent-encoded in query strings. The implementation above uses urlsafe_b64encode, which substitutes - and _ instead — safe to pass in a URL without additional encoding. Mixing the two variants corrupts the cursor silently.

Verification

Run this against a local PostGIS instance to confirm both indexes are used:

EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT id::text, name, ST_AsText(geom) AS geom_wkt, created_at::text
FROM locations
WHERE geom && ST_MakeEnvelope(-0.5, 51.3, 0.2, 51.6, 4326)
  AND id > 'a1b2c3d4-e5f6-7890-abcd-ef1234567890'::uuid
ORDER BY id ASC
LIMIT 20;

Look for these indicators in the output:

  • Index Scan using idx_locations_geom — GiST spatial pre-filter active
  • Index Cond: (geom && '...'::geometry) — bounding box pushed into the index scan
  • Filter: (id > '...'::uuid) — keyset predicate applied after GiST, before row projection
  • Rows Removed by Filter should be small relative to rows= in the index scan node

End-to-end smoke test with curl:

# First page (no cursor)
curl -s "http://localhost:8000/locations?bbox=-0.5,51.3,0.2,51.6&limit=5" | python3 -m json.tool

# Second page — paste next_cursor from the response above
curl -s "http://localhost:8000/locations?bbox=-0.5,51.3,0.2,51.6&limit=5&cursor=<next_cursor>" | python3 -m json.tool

A valid response on the second call must not repeat any id from the first page, and next_cursor must be absent when the final page contains fewer than limit items.

← Back to Spatial Pagination & Cursor Strategies