Filtered KNN When the Index Cannot Help

Problem Statement

“The five nearest charging stations that are currently available” is a nearest-neighbour query with a filter, and the filter changes everything. A plain KNN query stops after five index pops; the same query filtered to a 2% subset walks two hundred and fifty. This page covers the three strategies that recover the performance, and how to choose between them from the selectivity of the filter.

Why the Naive Approach Fails

sql
SELECT id, name FROM stations
WHERE status = 'available'
ORDER BY geom <-> ST_SetSRID(ST_MakePoint($1, $2), 4326)
LIMIT 5;

The plan is still an index scan, and the plan is still correct. What it does not show is how many entries it had to consume: the ordered scan emits candidates nearest-first, the filter rejects the unavailable ones, and the executor keeps going until five survive.

How far the scan has to walk Four selectivity levels. With no filter, five index entries produce five rows. At fifty percent selectivity it takes about ten. At ten percent, fifty. At two percent, two hundred and fifty — and the latency grows with it. Index entries consumed to return 5 rows no filter 5 entries · 1.1 ms 50% match ~10 entries · 1.4 ms 10% match ~50 entries · 4.8 ms 2% match ~250 · 31 ms Every one of these is an "Index Scan" in EXPLAIN. The plan shape does not change; only the work does, which is why this regression is invisible to anyone reading plans without row counts.

Production-Ready Implementation

Strategy one: a partial index per filter value. When the filter has few distinct values and one of them is hot, give it its own tree:

sql
CREATE INDEX CONCURRENTLY stations_geom_available_idx
    ON stations USING gist (geom)
    WHERE status = 'available';

The ordered scan then runs against an index containing only available stations, and five pops produce five rows again. The constraint is that the query’s WHERE clause must match the index predicate exactly — a parameterised status = $1 cannot use it, which is the partial index rule in a different costume.

Strategy two: an expanding radius. For arbitrary filters, bound the search spatially and widen only if needed:

python
from sqlalchemy import select, func

START_METRES = 800          # tuned from the data's density
MAX_METRES = 25_000


def nearest_available(session, point, k: int = 5) -> list:
    """Nearest k rows matching a filter, using the smallest radius that works."""
    radius = START_METRES
    while radius <= MAX_METRES:
        stmt = (
            select(Station)
            .where(func.ST_DWithin(Station.geog, point, radius))
            .where(Station.status == "available")
            .order_by(Station.geog.distance_centroid(point))
            .limit(k)
        )
        rows = session.scalars(stmt).all()
        if len(rows) == k:
            return rows
        radius *= 3
    return rows          # fewer than k exist within the maximum radius

The ST_DWithin bound is what makes each iteration cheap: it is an ordinary index-driven radius query over a small area, and the ordering happens on the handful of rows that survive. Most calls answer on the first iteration; the loop exists for the sparse regions where they do not.

Strategy three: a lateral over candidate cells. When the filter is highly selective and the geography is dense, precomputing a grid cell per row and joining laterally through it lets the planner use an ordinary composite index — trading exactness of ordering for a bounded candidate set. It is more machinery than most applications need, and it is the right answer for the ones that do.

Choosing the strategy A two-way split. A filter with few distinct values and stable predicates suits partial indexes. An arbitrary or parameterised filter suits the expanding radius. A very selective filter over dense data suits the grid-cell lateral. Each is annotated with its main cost. Three strategies, chosen by the filter's shape partial index few distinct values literal predicate in the query fastest by far cost: one index per value, and write amplification expanding radius arbitrary or parameterised filters works everywhere cost: occasional second round trip in sparse areas grid-cell lateral very selective filter, dense data bounded candidates cost: a derived column, and approximate ordering Start with the expanding radius: it needs no schema change and covers every case adequately. Latency by strategy at 2% selectivity Latency of the four approaches at two percent filter selectivity: unfiltered baseline 1.1 milliseconds, partial index 1.3, expanding radius 2.4 including one retry, and the plain filtered ordered scan 31. The same filtered query, four ways no filter (baseline) 1.1 ms partial index 1.3 ms — as good as unfiltered expanding radius 2.4 ms including one widen plain ORDER BY + filter 31 ms — walks 250 index entries The expanding radius costs a little more than a partial index and works for filters you cannot index.

Configuration and Tuning Knobs

The starting radius should come from the data, not from a guess. A reasonable derivation is the radius that contains k rows at the median local density — computable once with a sample query and hard-coded thereafter, or recomputed nightly if the density changes.

The growth factor trades round trips against overshoot. Tripling is a good default: it reaches a 25 km cap in three iterations from 800 metres, and each iteration that fails is cheap because it found almost nothing.

The maximum radius is a product decision and a denial-of-service guard. Without it, a request in the middle of an ocean walks the entire index.

work_mem matters slightly for the sort in the bounded query, but with a LIMIT of five over a few dozen candidates the sort is trivial — if it is not, the radius is too large.

Verification Steps

sql
-- how many entries did the unfiltered ordered scan actually consume?
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM stations
WHERE status = 'available'
ORDER BY geom <-> ST_SetSRID(ST_MakePoint(10.75, 59.91), 4326)
LIMIT 5;
-- look at "Rows Removed by Filter" on the index scan node

-- and with the partial index in place, the same query
-- should report Rows Removed by Filter: 0

Rows Removed by Filter on the index scan node is the number this page is about. Zero means the index is doing the filtering; anything large means the scan is walking past rejects.

Gotchas Checklist

  • A partial index is only used when the query predicate implies the index predicate. Parameterised status values do not qualify, which defeats the strategy in exactly the applications most likely to reach for it.
  • The expanding loop must have a maximum. An unbounded loop over an empty region is a slow query with no natural end.
  • Return fewer than k rather than searching forever. “The three nearest available stations within 25 km” is a better product answer than a thirty-second wait for five.
  • Distance ordering inside the bounded query still needs the index. Ordering by ST_Distance rather than the operator turns each iteration into a sort over the candidates — correct, and slower than it needs to be.
  • Watch for filter columns that change constantly. A status flag updated every few seconds makes partial indexes churn, which trades query time for write time and vacuum pressure.

Reading the Plan for a Filtered Nearest-Neighbour Query

The plan tells you within about ten seconds whether the index is being used in distance order or merely being used.

A working index-ordered scan looks like a Limit node directly above an Index Scan using idx_stations_geom on stations, with Order By: (geom <-> '...'::geometry) on the index scan itself. That Order By line — as opposed to a separate Sort node — is the whole game. It means PostgreSQL is walking the GiST index in increasing distance and can stop as soon as the limit is satisfied, so rows on the Limit node will be exactly the requested count and the index scan above it will report a number only slightly larger.

The failure mode is a plan with a Sort node between the Limit and the scan, and Sort Method: top-N heapsort in the detail line. That means every candidate row was fetched, its distance computed, and the whole set ordered before the limit applied. The give-away number is Rows Removed by Filter on the scan below: if it is in the tens of thousands while the query asked for five rows, the ordering operator never engaged.

There is a third shape worth recognising. When the filter is selective and a btree index exists on the filtered column, the planner may choose that index instead and sort by distance afterwards. That plan is not wrong — for a filter matching forty rows it is the fastest thing available — but it does not scale with the table, and it will silently become the slow plan when the filter stops being selective. The actual rows on the btree scan is the number to watch over time; when it drifts from tens into thousands, the plan needs revisiting.

Always read these plans from EXPLAIN (ANALYZE, BUFFERS) output rather than plain EXPLAIN, because the buffer counts distinguish an index scan that touched forty pages from one that touched forty thousand.