Combining KNN Ordering with Attribute Filters

Add a WHERE clause to a nearest-neighbour query and the index-assisted ordering can collapse. Three patterns that keep the KNN scan alive: partial indexes, expanding radius search, and LATERAL per-group.

← Back to K-Nearest Neighbor Routing Algorithms

This page covers what happens when “the ten nearest” becomes “the ten nearest that are available”, and the three ways to keep that query fast.

Context & When to Use

The <-> operator gives PostGIS a genuinely index-assisted nearest-neighbour scan: the GiST index is walked in distance order and the scan stops as soon as LIMIT is satisfied. Ten rows out of two million in about three milliseconds. It is one of the most elegant things in the database, and it is fragile in one specific way.

Add WHERE status = 'available' and the elegance leaks. The index cannot evaluate status, so the executor fetches each candidate in distance order, checks the attribute, and discards the misses. If one row in five hundred is available, returning ten means walking roughly five thousand index entries and doing five thousand heap fetches. The query still returns the right answer, and it now takes 400 ms instead of 3.

Three patterns fix it, and which one applies depends on the filter’s shape: few known values, a bounded search area, or a nearest-per-group requirement. All three preserve the property that makes KNN worth using — early termination — rather than falling back to computing distance for everything. The unfiltered baseline is covered in Optimizing KNN Queries with the PostGIS Distance Operator.

Runnable Implementation

-- Pattern 1 — PARTIAL INDEX: few known values, exact match
CREATE INDEX vehicles_geog_available_gix ON vehicles
    USING GIST ((geom::geography)) WHERE status = 'available';
CREATE INDEX vehicles_geog_busy_gix ON vehicles
    USING GIST ((geom::geography)) WHERE status = 'busy';

-- The planner picks the matching partial index; the scan is pure KNN again
SELECT id, ROUND(ST_Distance(geom::geography, $1::geography)::numeric, 1) AS m
FROM   vehicles
WHERE  status = 'available'
ORDER  BY geom::geography <-> $1::geography
LIMIT  10;

-- Pattern 2 — BOUNDED SEARCH: filter is arbitrary, area is not
SELECT id, ROUND(ST_Distance(geom::geography, $1::geography)::numeric, 1) AS m
FROM   vehicles
WHERE  ST_DWithin(geom::geography, $1::geography, 5000)   -- index narrows first
  AND  status = ANY($2::text[])                            -- then cheap filtering
ORDER  BY geom::geography <-> $1::geography
LIMIT  10;

-- Pattern 3 — LATERAL PER-GROUP: nearest of each category, one KNN scan each
SELECT c.code, n.id, ROUND(n.m::numeric, 1) AS m
FROM   categories c
CROSS  JOIN LATERAL (
    SELECT v.id, ST_Distance(v.geom::geography, $1::geography) AS m
    FROM   vehicles v
    WHERE  v.category = c.code
    ORDER  BY v.geom::geography <-> $1::geography
    LIMIT  1
) n;

Pattern 2 is the one to reach for first. It is a one-line change, needs no extra indexes, and converts an unbounded walk into a bounded one — the same ST_DWithin rewrite described in Avoiding Full Scans with ST_DWithin and Geography, used here to protect the ordering rather than the filter.

What the KNN scan walks in each caseTwo rows of index entries walked in distance order. In the unfiltered-index case, most entries are non-matching and are fetched then discarded; reaching ten matches requires walking about five thousand entries. In the partial-index case, every entry in the index already satisfies the filter, so ten entries are walked to return ten rows. The heap fetch count follows the same ratio, which is where the time actually goes.Walking the index in distance order, with and without a partial indexfull index + WHERE status = 'available'… ~5 000 entries walked, 4 990 discardedheap fetches:5 000· time:412 mspartial index WHERE status = 'available'scan stops here — every entry matchedheap fetches:10· time:3.1 msThe index still terminates early in both cases — the difference is how many candidates it has to reject first.

Key Parameters & Options

PatternBest whenCost
Partial index per value≤ ~20 known values, equality filterOne index per value; write overhead
ST_DWithin boundany filter, bounded area acceptableChanges semantics: no result beyond the radius
LATERAL per groupnearest-of-each-categoryOne KNN scan per group; needs a small groups table
Composite btree + GiSTfilter is highly selective on its ownLoses distance ordering; sort afterwards
Expanding radiusa result is mandatoryTwo or three queries in the worst case
No mitigationfilter matches > ~20 % of rowsAcceptable — the walk is short anyway

That last row matters. If the filter keeps most rows, the plain KNN scan discards very little and none of this is needed. The patterns are for selective filters, and measuring selectivity is the first step rather than the last.

A bounded search returns nothing when nothing is near, which is usually correct and occasionally unacceptable — a dispatcher must be given some vehicle. The answer is to try a small radius first and widen only on a miss, so the common case stays fast.

RADII_M = (2_000, 10_000, 50_000)     # try nearest first, widen on empty

async def nearest_available(conn, point_wkt: str, limit: int = 10):
    for radius in RADII_M:
        rows = await conn.fetch(NEAREST_BOUNDED_SQL, point_wkt, radius, limit)
        if len(rows) >= limit:
            return rows, radius
    # Final fallback: unbounded, and log it — a frequent fallback means the
    # radii are wrong for this data, not that the data is unusual
    return await conn.fetch(NEAREST_UNBOUNDED_SQL, point_wkt, limit), None
Expanding search: how often each step is reachedThree radius steps with the share of requests satisfied at each. The 2 kilometre step satisfies 87 percent of requests in 3 milliseconds. The 10 kilometre step handles a further 11 percent, costing 3 plus 9 milliseconds because the first attempt is wasted. The 50 kilometre step handles 2 percent at a cumulative 58 milliseconds. The weighted average is 5.4 milliseconds, close to the best case, which is the argument for trying the small radius first rather than starting wide.Expanding search over a real dispatch workload2 km — first attempt87 % · 3 ms10 km — second attempt11 %12 ms cumulative — the first try is wasted work50 km — third attempt2 %58 ms cumulativeWeighted average:5.4 ms· starting at 50 km instead:58 msfor every requestWasted first attempts cost far less than making the common case pay for the rare one. Track how often thefinal fallback is reached — a rising rate means the radii no longer match the data's density.

Choosing between the three patterns

Which pattern the filter's shape calls forA decision tree. The first question asks whether the filter has a small fixed set of values. If yes, a partial index per value is the answer. If no, the next question asks whether the query is nearest-per-group. If yes, a lateral join gives each group its own scan. If no, the final question asks whether a bounded search area is acceptable to the product. If yes, an ST_DWithin bound is the answer; if no, an expanding radius search is the fallback.Filter has few fixed values?yespartial index per valuepurest scan; costs write overheadnoNearest per group?yesLATERAL per groupone scan each; keep the group set smallnoBounded area acceptable?yesST_DWithin boundone line; try this firstnoexpanding radiustwo or three queries worst case

Gotchas & Failure Modes

  • A partial index the planner will not use. The index predicate must match the query predicate closely enough for PostgreSQL to prove implication. WHERE status = 'available' matches; WHERE status IN ('available') usually does too; WHERE status <> 'busy' does not.
  • Too many partial indexes. Each one is maintained on every write. Twenty partial GiST indexes on a high-write table can cost more than the queries save; measure the write path before adding the fifth.
  • LIMIT missing from the KNN query. Without it there is no early termination and the operator sorts the whole candidate set. The <-> operator is only fast in combination with a limit.
  • Ordering by ST_Distance instead of <->. Semantically identical, but only the operator form is index-assisted for ordering.
  • A LATERAL join over a large outer table. Pattern 3 runs one KNN scan per outer row. That is excellent for twelve categories and disastrous for 200 000 customers — for the latter, invert the problem and batch.
  • Filter selectivity changing over time. A partial index sized for “10 % available” behaves very differently when a fleet goes to 90 % idle overnight. Re-measure after any operational change.

Verification Snippet

-- Confirm the partial index is chosen, and that the scan terminates early
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM vehicles
WHERE status = 'available'
ORDER BY geom::geography <-> ST_SetSRID(ST_MakePoint(-0.1276, 51.5072), 4326)::geography
LIMIT 10;
-- Limit  (actual time=0.09..3.06 rows=10 loops=1)
--   ->  Index Scan using vehicles_geog_available_gix on vehicles
--         Order By: ((geom)::geography <-> '...'::geography)
--  (no "Rows Removed by Filter" line at all)

-- Selectivity check: is any of this necessary?
SELECT status, count(*), round(100.0 * count(*) / sum(count(*)) OVER (), 1) AS pct
FROM   vehicles GROUP BY status ORDER BY 2 DESC;
curl -s "localhost:8000/v1/nearest?lon=-0.1276&lat=51.5072&status=available&limit=10" \
  | jq '{count: (.results|length), radius_used: .radius_m, first: .results[0].distance_m}'
# {"count":10,"radius_used":2000,"first":184.6}

← Back to K-Nearest Neighbor Routing Algorithms