Indexing Spatial Embeddings with HNSW and Metadata Filters

A graph index answers nearest-neighbour questions by walking edges toward the query. Add a filter that excludes most nodes and the walk can strand itself in a region of the graph where nothing is eligible, returning three results when it was asked for twenty. This guide builds the index and the queries so that does not happen, for the workload described in spatial vector store selection.

When to Use This Approach

Use a graph index when the corpus is large enough that exact search is too slow, and the filters are selective. For small corpora, exact search under a filter is simpler, has perfect recall, and is often fast enough — a fact worth confirming before adding an approximate index and its parameters.

The last row is the one people miss. If a bounding box reduces two million chunks to eight hundred, an exact scan of those eight hundred is microseconds of work and the graph index contributes nothing but risk.

Implementation

The index definition carries three decisions: the distance operator, the graph connectivity, and the build-time search width. The filter columns need their own indexes, because the planner has to be able to narrow before or during the graph walk.

-- Vector column plus the metadata the filters use.
ALTER TABLE spatial_chunks
    ADD COLUMN IF NOT EXISTS embedding vector(768);

-- Graph index over cosine distance. m controls connectivity; ef_construction
-- controls how hard the builder searches while wiring each node in.
CREATE INDEX IF NOT EXISTS spatial_chunks_embedding_idx
    ON spatial_chunks USING hnsw (embedding vector_cosine_ops)
    WITH (m = 24, ef_construction = 128);

-- The filters need indexes of their own or the pre-filter is a scan.
CREATE INDEX IF NOT EXISTS spatial_chunks_geom_idx   ON spatial_chunks USING gist (geom);
CREATE INDEX IF NOT EXISTS spatial_chunks_period_idx ON spatial_chunks (captured_at);

-- Query-time search width: higher means better recall and more work.
SET hnsw.ef_search = 120;

SELECT chunk_id
FROM   spatial_chunks
WHERE  geom && :bbox
  AND  ST_Intersects(geom, :region)
  AND  captured_at >= :since
ORDER  BY embedding <=> :qvec
LIMIT  20;

The build parameters are chosen higher than the defaults on purpose. Filtered search spends part of its budget walking through ineligible nodes, so a graph with more edges per node and a wider build search gives the traversal more routes into eligible territory. The cost is memory and build time, both of which are covered in sizing HNSW parameters for spatial recall.

The application layer’s job is to raise the search width when the filter is tight, since a single global value cannot serve both loose and selective queries.

import logging
import math

log = logging.getLogger("hnsw_index")

BASE_EF = 60
MAX_EF = 500


def ef_for_selectivity(selectivity: float, k: int = 20) -> int:
    """Widen the search when the filter removes most of the corpus.

    selectivity is the estimated share of the corpus passing the filter, in (0, 1].
    """
    if not (0.0 < selectivity <= 1.0) or math.isnan(selectivity):
        log.warning("implausible selectivity %r — using the base width", selectivity)
        return BASE_EF                              # deterministic fallback
    # Roughly: to see k eligible nodes, the walk must visit k / selectivity nodes.
    needed = int(k / max(selectivity, 1e-4))
    return max(BASE_EF, min(MAX_EF, needed))


def search(conn, qvec, region, since, k: int = 20, selectivity: float = 1.0):
    ef = ef_for_selectivity(selectivity, k)
    with conn.cursor() as cur:
        try:
            cur.execute("SET LOCAL hnsw.ef_search = %s", (ef,))
        except Exception as exc:                    # older server, or a store without the knob
            log.info("could not set search width (%s) — proceeding with the default", exc)
        cur.execute(FILTERED_QUERY, {"qvec": qvec, "region": region,
                                     "since": since, "k": k})
        rows = cur.fetchall()
    if len(rows) < k:
        log.info("filtered search returned %d of %d at ef=%d", len(rows), k, ef)
    return rows

The estimate of selectivity does not need to be accurate, only roughly right in order of magnitude. Deriving it from the region’s area relative to the corpus extent, cached per region size band, is enough to distinguish a town-sized query from a national one, which is the distinction that matters.

Validation & Testing

def test_recall_holds_at_high_selectivity(conn):
    truth = brute_force_topk(conn, QVEC, TIGHT_REGION, k=20)
    got = {r[0] for r in search(conn, QVEC, TIGHT_REGION, SINCE, k=20, selectivity=0.005)}
    assert len(truth & got) / len(truth) >= 0.9


def test_full_result_count_under_a_tight_filter(conn):
    rows = search(conn, QVEC, TIGHT_REGION, SINCE, k=20, selectivity=0.005)
    assert len(rows) == 20, f"stranded walk: only {len(rows)} results"


def test_search_width_scales_with_selectivity():
    assert ef_for_selectivity(1.0) == 60
    assert ef_for_selectivity(0.01) > ef_for_selectivity(0.5)
    assert ef_for_selectivity(0.0) == 60          # implausible input falls back, not crashes


def test_filter_indexes_are_used(conn):
    plan = explain(conn, FILTERED_QUERY)
    assert "Seq Scan on spatial_chunks" not in plan

The second test is the one that catches stranding directly, and it is easy to omit because a short result set looks like “the corpus has little about this place”. Assert the count, not just the overlap.

Gotchas & Edge Cases

Filters on unindexed columns. A metadata predicate with no index forces a scan of whatever the graph returns, which caps throughput and, worse, changes the plan under load. Index every column a filter touches, including the ones added later for a single feature.

Insert-heavy workloads degrading connectivity. Nodes added after the graph is built are wired into the graph as it exists, which over time produces a less well-connected structure than a full rebuild would. Track recall over time and rebuild on a schedule rather than waiting for complaints.

Quantization applied before measuring. Compressing vectors before establishing a recall baseline makes it impossible to attribute a later recall problem to compression or to the filter. Measure uncompressed first, then compress and measure again.

A search width set globally and forgotten. A width tuned during a demonstration with loose filters will underserve every selective query in production. Set it per query from selectivity, as above, and log when a search returns fewer results than requested.

Deleted records left in the graph. Soft deletes that remain as graph nodes consume search budget and can strand a walk exactly like a filter does. Ensure deletions are reflected in the index, and treat a rising deleted-node fraction as a reason to rebuild.

Frequently Asked Questions

A final note on ordering the work: establish the recall baseline before touching any parameter. Every knob in this guide trades recall against memory or latency, and without a baseline you cannot tell whether a change helped, hurt, or merely moved the cost somewhere you were not measuring. The baseline should be recorded with the corpus size and the filter selectivity it was measured at, because both change what the number means.

Related

• Up to the parent topic: Spatial Vector Store Selection
• Sizing HNSW Parameters for Spatial Recall
• pgvector vs Qdrant vs Milvus for Spatial Embeddings
• Technique: Filtering Retrieval by Bounding Box Before Vector Search