DuckDB Spatial Analytical SQL for GIS

Paginating Large Spatial Result Sets

LIMIT with OFFSET is the obvious way to page through a spatial result and the one that gets slower with every page, because the engine has to produce and discard everything before the offset. This walkthrough, part of the spatial range and nearest-neighbour search reference, covers keyset pagination over a spatial ordering, why the sort key has to be stable, and what to do when the ordering is a computed distance rather than a stored column.

Root-Cause Analysis: why offset pagination degrades

  • The offset is produced, not skipped. To return rows 10,000 to 10,050 the engine computes the first 10,050 and discards 10,000 of them. Page cost therefore grows linearly with page number, and the last page costs as much as the whole result.
  • The spatial predicate re-runs every page. Each request repeats the envelope test and the exact topology on the whole candidate set, so the expensive part of the query is paid once per page rather than once.
  • The ordering may not be stable. If the sort key has ties, two requests can order the tied rows differently, so a row can appear on two pages or on none. On a computed distance, ties are rarer but rounding makes them possible.
  • The result set can change between pages. Anything that mutates the underlying table shifts every row after the change point, which is a correctness problem rather than a performance one.
  • The client asked for a total. Producing a count of all matches requires evaluating every match, which defeats the point of paging in the first place.

The distinguishing question is whether the ordering key is stored or computed. A stored key supports keyset pagination directly; a computed one has to be materialised first, and that materialisation is the whole design.

Page cost by page number, offset versus keyset Offset pagination costs grow linearly with page number and quadratically in total; keyset pagination is flat. PAGE OFFSET PAGINATION KEYSET PAGINATION page 1 1 unit 1 unit page 100 ~100 units ~1 unit page 1,000 ~1,000 units ~1 unit whole result quadratic in pages linear in pages

The first row is why offset pagination survives review. The third is why it should not.

Deterministic Configuration 

INSTALL spatial; LOAD spatial;

SET memory_limit = '4GB';
SET threads = 8;

-- Pagination is only meaningful over a stable ordering, which means a unique
-- tiebreaker. Make sure one exists before designing the cursor.
CREATE INDEX idx_shops_geom ON shops USING RTREE (geom);

Optimized Execution Pattern

The pattern is keyset pagination: order by a stable key, return a cursor with the last row values, and seek past it on the next request rather than counting from the start.

-- ANTI-PATTERN: page 200 re-computes the spatial predicate for 10,000 rows
-- and throws away 9,950 of them.
SELECT shop_id, name, ST_Distance(geom, :origin) AS metres
FROM shops
WHERE ST_DWithin(geom, :origin, 5000)
ORDER BY metres
LIMIT 50 OFFSET 9950;
-- PATTERN: seek past the cursor. The predicate still runs, but the ordering
-- comparison eliminates everything before the cursor without materialising it.
SELECT shop_id, name, ST_Distance(geom, :origin) AS metres
FROM shops
WHERE ST_DWithin(geom, :origin, 5000)
  AND (ST_Distance(geom, :origin), shop_id) > (:last_metres, :last_shop_id)
ORDER BY ST_Distance(geom, :origin), shop_id
LIMIT 50;

The row-comparison syntax is what makes a compound cursor correct: comparing the tuple rather than the columns individually gives exactly “everything after this row in the ordering”, which a chain of AND/OR conditions on the two columns gets wrong in the tie case.

Four guarantees a pagination design needs A total ordering, a complete cursor, an unchanging predicate, and stable data for the duration. GUARANTEE WITHOUT IT FIX the ordering is total rows appear twice or never a unique tiebreaker the cursor is complete ties cannot be positioned encode every ordering column the predicate is identical the result changes shape pass it through the cursor the data is stable inserts shift later pages snapshot, or accept it

The first two are yours to fix. The second two are yours to decide about.

When the ordering is a computed distance

A distance is computed per row, so it is not a stored column and cannot be indexed. That does not prevent keyset pagination — the comparison in the WHERE clause still eliminates rows before the cursor — but it does mean the distance is recomputed for every candidate on every page.

Where the result set is browsed repeatedly, materialising the ranking once is usually the better design. A temporary table holding the matches with their distance and a dense rank turns every page into an indexed range scan on an integer, which is as cheap as pagination gets. The trade is that the ranking is a snapshot: it does not reflect changes to the underlying table until it is rebuilt.

-- Materialise the ranking once, then page on an integer. Every page is then
-- a range scan and the spatial work is paid exactly once.
CREATE OR REPLACE TEMP TABLE nearby AS
SELECT shop_id, name, ST_Distance(geom, :origin) AS metres,
       row_number() OVER (ORDER BY ST_Distance(geom, :origin), shop_id) AS rn
FROM shops
WHERE ST_DWithin(geom, :origin, 5000);

SELECT shop_id, name, metres FROM nearby WHERE rn BETWEEN 9951 AND 10000 ORDER BY rn;

Diagnostic Queries & Plan Validation

The signal that offset pagination is the problem is a page time that rises with the page number, and it is worth measuring rather than assuming.

-- The same query at three offsets. Under keyset pagination these are flat;
-- under offset pagination the third is roughly a hundred times the first.
EXPLAIN ANALYZE SELECT shop_id FROM shops
WHERE ST_DWithin(geom, :origin, 5000) ORDER BY ST_Distance(geom, :origin) LIMIT 50 OFFSET 0;
-- repeat with OFFSET 4950 and OFFSET 49950

Look at the row count the sort emits rather than the timing. Under offset pagination it is the offset plus the limit; under keyset pagination it is the limit. That number is the whole difference and it does not depend on the machine.

Three strategies and when each fits Offset for small bounded results, keyset for live large ones, and a materialised ranking for results browsed repeatedly. STRATEGY FITS COST LIMIT / OFFSET small, bounded results grows with page number keyset with a cursor live queries over large results flat per page a materialised ranking results browsed repeatedly one snapshot, then integer scans

Two of the three are cheap. The third is the one most APIs ship with.

Not returning a total

A page of results and a count of all matches are different queries, and the second is usually far more expensive than the first — it requires evaluating the predicate against everything, which is exactly what pagination exists to avoid. An interface that shows “page 3 of 812” has quietly committed to running the expensive query on every request.

The workable alternatives are to omit the total, to show an approximate one derived from a sample or from row-group statistics, or to compute it once when the search is created and reuse it for the life of the cursor. All three are honest; the one to avoid is computing it exactly on every page, which makes the paging free and the header expensive.

Geometry Validation & Fallback Routing

Where the client genuinely needs to jump to an arbitrary page, the fallback is a materialised ranking rather than an offset.

-- Random access by page number, on a materialised ranking. This is the only
-- shape that supports "jump to page 812" without paying for the first 811.
SELECT shop_id, name, metres
FROM nearby
WHERE rn > (:page - 1) * 50 AND rn <= :page * 50
ORDER BY rn;

Frequently Asked Questions

Why does OFFSET get slower on later pages?

Because the rows before the offset are produced and then discarded rather than skipped. Page 200 computes the spatial predicate for ten thousand rows to return fifty, so the cost grows linearly with the page number and walking the whole result is quadratic in the number of pages.

What does a keyset cursor need to contain?

Every column in the ordering, in order, so it names an exact position. A cursor holding only the first ordering column cannot position within its ties, which is how a row ends up on two pages. Compare the tuple rather than the columns individually — a hand-written chain of conditions gets the tie case wrong.

Can I paginate on a computed distance?

Yes — the cursor comparison works on any expression. What you do not get is an index on it, so the distance is recomputed for every candidate on every page. If the result is browsed repeatedly, materialising the ranking once is usually the better design.

Do I need a unique tiebreaker?

Yes. Without one the ordering is not total, so tied rows can be ordered differently between requests and a row can appear on two pages or on none. A primary key is the natural choice and it costs nothing.

How do I show a total result count?

Preferably not on every page. Computing it exactly requires evaluating the predicate against everything, which is the cost pagination exists to avoid. Compute it once when the search is created, approximate it, or omit it — all three are honest, and the alternative makes the paging free and the header expensive.

What if rows are inserted while the user is paging?

A row inserted before the cursor shifts everything after it, so a page can repeat or skip content. A materialised ranking avoids this by snapshotting the result; a live keyset query does not, and for most interactive searches that is an acceptable trade rather than a defect.

Up: Spatial Range and Nearest-Neighbor Search