Vector Indexes and Store Selection: HNSW vs. Inverted File, Quantization to Save Memory, Filtered Queries and Multi-Tenant Isolation

HNSW: a layered map of acquaintances

The first catalog is the hierarchical navigable small world graph, universally abbreviated HNSW. An intimidating name holding only two ideas.

The first idea is a small world graph: connect each vector to several nearby neighbors and the store becomes a network. Finding a nearest neighbor needs no full scan — start anywhere and move each step to the neighbor closer to the target, like following a chain of acquaintances, and a few dozen steps reach the target's vicinity.

The second idea is layering. With only one network, walking from one end of the store to the other takes a long time. So stack several sparser networks above it: the top layer has few points connected far apart, like intercity rail; lower layers have denser points connected closer, like city buses. A query enters at the top, takes the express to roughly the right area, and descends layer by layer for a precise search. That is the same trick as a skip list.

pgvector turns it into two build parameters and one query parameter:

-- Building: m is how many neighbors each point connects to per layer (default 16),
-- ef_construction is how large each point's candidate neighbor list is while building (default 64)
CREATE INDEX ON chunk_embeddings
USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
 
-- Querying: ef_search is the size of the dynamic candidate list during search (default 40)
SET hnsw.ef_search = 100;

Three parameters govern three things, so do not confuse them: m decides how dense the graph is, with denser meaning higher recall but a larger index and slower builds; ef_construction decides how thoroughly neighbors are sought while building and affects only that one build; and ef_search is the only one adjustable per query. Changing the first two means rebuilding the index; the last takes effect immediately.

What does the trade-off curve look like? In the twenty-thousand-row lab, taking ef_search from 10 to 400 raises recall from 69.0% to 98.0% and median latency from 0.6 to 2.4 milliseconds (graph building is randomized, so your own run will differ by a point or two; read the trend, not the decimals). Note the shape: the first half is a bargain and the second half is not — going from 10 to 100 buys 26 percentage points for 0.5 milliseconds, and going from 200 to 400 buys 1 point for 0.8 milliseconds. Tuning here comes down to one sentence: find the knee.

IVFFlat: partition first, then search within a partition

The second catalog is the inverted file index (IVFFlat), whose approach is entirely different and easier to grasp.

At build time it runs k-means over all the vectors into lists clusters, each remembering its centroid. At query time it compares the question vector against every centroid, picks the nearest probes clusters, and scans only those. Rather as a library first divides into subject collections, and you first judge which collections to visit and then leaf through within them.

-- A starting point for lists: rows / 1000 up to a million rows, sqrt(rows) beyond
CREATE INDEX ON chunk_embeddings
USING ivfflat (embedding vector_cosine_ops) WITH (lists = 20);
 
-- A starting point for probes: sqrt(lists). The default is 1 and is almost certainly not enough
SET ivfflat.probes = 10;

The division is clean: lists decides how finely it partitions and is fixed at build time; probes decides how many clusters a query looks at and can change any time. Raise probes to equal lists and it degenerates into a full scan — and the lab produces exactly that: from 1 to 20, recall runs from 60.0% to 100.0% and latency from 0.5 to 5.3 milliseconds, with a full scan itself at 5.3 milliseconds.

Here is a pothole every beginner hits: probes defaults to 1. Build the index, tune nothing, and a query looks at one cluster with recall possibly barely over half. After building an IVFFlat index, setting probes is not an optimization but what makes it usable.

How to choose? Measured build costs are 1.5 seconds and 38.8 MB for HNSW against 0.3 seconds and 31.3 MB for IVFFlat: IVFFlat builds faster and takes less space, with higher latency at equal recall. There is a more consequential difference: IVFFlat's clusters are determined by the data at build time, so continued writes distort the clustering and require periodic rebuilds, whereas HNSW is a graph built by incremental insertion with no such problem. So static data with tight memory takes IVFFlat, and frequent writes with query quality first takes HNSW.

Quantization: swapping books for microfilm

An index saves time and quantization saves space. A 384-dimensional single-precision vector occupies 4 × dimensions + 8 bytes in pgvector, measured at 1,540 bytes per row, so twenty thousand rows make a 36.5 MB table with a 38.8 MB HNSW index — the index being larger than the table is normal in vector search. At tens of millions of rows, memory is the bulk of the bill.

The first tier is half precision (halfvec): 2 bytes per dimension instead of 4. Measured at 776 bytes per row, the index drops from 38.8 MB to 22.2 MB, and at the same ef_search = 40 recall is 90.5% against 92.0% — a difference inside the noise of a rerun, so effectively no loss. It also resolves a hard limit: vector indexes cap at 2,000 dimensions, halfvec at 4,000, and bit at 64,000 — anyone on a 3,072-dimensional model has only this road.

-- Half precision: an expression index, with no change to the column's type
CREATE INDEX ON chunk_embeddings
USING hnsw ((embedding::halfvec(384)) halfvec_cosine_ops);
 
SELECT chunk_id FROM chunk_embeddings
ORDER BY embedding::halfvec(384) <=> $1::halfvec(384) LIMIT 10;

The second tier is binary quantization: keep only each dimension's sign, positive as 1 and the rest as 0, compressing 384 dimensions into 384 bits, measured at 56 bytes per row with the index down to 6.6 MB, nearly six times smaller. The cost is correspondingly large, so the standard usage is never taking its results directly but coarse-filtering a large batch with it and re-ranking that small batch with the original vectors:

SELECT chunk_id FROM (
  SELECT chunk_id, embedding FROM chunk_embeddings
  ORDER BY binary_quantize(embedding)::bit(384) <~> binary_quantize($1)::bit(384)
  LIMIT 500
) coarse
ORDER BY embedding <=> $1 LIMIT 10;

Add one WHERE and the results shrink

Everything so far was a warm-up; this section is where production most easily breaks.

Consider an utterly ordinary requirement: search only documents in a given department, tenant, or time range. Add a condition to the SQL. And you find something strange — the store clearly holds hundreds of matching rows and the query returns one or two.

The reason is stated plainly in pgvector's documentation: filtering on an approximate index happens after the index scan. The index first fetches ef_search candidates by distance (40 by default) and only then applies the WHERE to those 40. When matching rows are 1% of the table, on average 0.4 of those 40 survive.

We constructed that scene for real: of twenty thousand rows, one tenant has 200 (exactly 1%), and retrieval carries the tenant condition. Under the default configuration it returns 0.5 rows on average at 5.0% recall. Not a broken database and not missing data — turn the index off for a full scan and a complete ten come back immediately.

Since 0.8.0, pgvector has offered a switch called iterative scanning: when too many candidates are filtered out, it returns to the index and scans more until enough are gathered.

-- Strict order: results strictly ordered by distance, with slightly lower recall
SET hnsw.iterative_scan = strict_order;
 
-- Relaxed order: allows slight deviation in distance ordering in exchange for higher recall
SET hnsw.iterative_scan = relaxed_order;

On the same batch of queries, relaxed_order brings recall from 5.0% back to 89.5% and strict_order to 77.5%, at the cost of median latency rising from 0.7 to around 6 milliseconds. That is the course's recurring three bills: the metric up 84 percentage points, latency up roughly ninefold, money unchanged. Whether it is worth it depends on how selective your filter is.

On the application side, both switches go into a transaction with SET LOCAL rather than being set globally, or unfiltered ordinary queries slow down too:

// Effective only within this transaction; unfiltered queries should not be slowed
export async function searchInTenant(sql, queryVector, tenantId, k = 10) {
  return sql.begin(async (tx) => {
    await tx.unsafe('set local hnsw.ef_search = 40')
    await tx.unsafe('set local hnsw.iterative_scan = relaxed_order')
    return tx`
      select chunk_id, embedding <=> ${queryVector}::vector as distance
      from chunk_embeddings
      where tenant_id = ${tenantId}
      order by distance
      limit ${k}
    `
  })
}

async def search_in_tenant(conn, query_vector, tenant_id: str, k: int = 10):
    """Effective only within this transaction; unfiltered queries should not be slowed"""
    async with conn.transaction():
        await conn.execute("SET LOCAL hnsw.ef_search = 40")
        await conn.execute("SET LOCAL hnsw.iterative_scan = relaxed_order")
        return await conn.fetch(
            """
            SELECT chunk_id, embedding <=> $1 AS distance
            FROM chunk_embeddings
            WHERE tenant_id = $2
            ORDER BY distance
            LIMIT $3
            """,
            query_vector,
            tenant_id,
            k,
        )

Multi-tenancy: three isolations, three bills

The most common form of filtered retrieval is multi-tenancy: one system serving many customers, each able to search only their own material. Three approaches with entirely different cost structures.

The first is a filter field, the previous section's setup. It is the smallest change, and beyond under-recall it has a subtler problem: every tenant shares one graph, so tenant A loading a million rows genuinely degrades tenant B's retrieval quality and speed — B's candidate slots were taken by A. pgvector's documentation warns about this specifically.

The second is a partial index for high-traffic tenants: an index containing only that tenant's rows. The lab builds one for that 1% tenant, at only 408 KB and 0.1 seconds to build, giving 100% recall without iterative scanning and 0.4 milliseconds median latency, winning on all three metrics. The cost is elsewhere: an index predicate cannot use a bind parameter, so each tenant needs its own DDL, and a thousand tenants means a thousand indexes.

-- A partial index: the condition must be a constant, so one DDL per tenant
CREATE INDEX ON chunk_embeddings
USING hnsw (embedding vector_cosine_ops) WHERE (tenant_id = 't07');

The third is list partitioning: split the table into partitions by tenant, each with its own index. That is pgvector's documented recommendation for multi-tenant isolation, giving the cleanest isolation with dropping a tenant becoming dropping a partition, at the cost of moving the complexity into DDL and operations.

The criterion is simple: few and stable tenants take partial indexes; many tenants each with modest data take a filter field plus iterative scanning; and a large customer crowding out small ones takes partitions. The three do not conflict, and many systems mix them — the largest customers in their own partitions and the long tail sharing one table.

One boundary: today covers making filtered retrieval not under-recall, and whether a given user is permitted to see a given row is a different matter, involving where permissions come from, invalidation, and incremental sync, handled on day 13.

When to move vectors out of PostgreSQL

The conclusion first: most teams' first version should stay on PostgreSQL, not because its vector search is outstanding but because of everything it saves you — transactions, backups, point-in-time recovery, permissions, joins against business tables, and the operational tooling you already know, all off the shelf. One more database means one more sync, one more consistency problem, and one more chance of being woken at night.

When a move genuinely deserves consideration, watch four lines, any one of which clearly crossed warrants a reassessment:

1. Data volume. Once one table's vectors reach tens of millions and must stay resident in memory, dedicated stores' optimizations in memory layout and paging start to show a gap. The criterion is not how many rows I have but whether the index still fits in memory.
2. Write frequency. Frequent inserts, updates, and deletes distort IVFFlat's clustering and continually inflate HNSW's graph. A minute-by-minute stream needs a dedicated store's incremental maintenance more than a daily batch import does.
3. Filter complexity. The most practical line: when the filter is not one tenant field but an arbitrary combination of a dozen attributes, partial indexes and partitions cannot cover the combinatorics, while stores like Qdrant build filtering into the index structure itself and are inherently better suited.
4. The team's operational capacity. The line in the other direction: if nobody is willing to look after a second database long term, do not move even if the first three hold.

There is one more often-overlooked road: not moving does not mean only one kind of retrieval. A keyword index, a vector index, and day 9's reranking should coexist anyway, and many "vector search is not good enough" problems have their real fix on day 9 rather than in a new store. Which embedding model and how many dimensions was settled on day two; revisit D2.

Source Reading

Hands-On Lab

Before starting, run docker compose up -d in the lab directory to bring up the database. There is no in-memory fallback today — what is being measured is the database index itself, so substituting a fake implementation measures nothing, and the script tells you how to start the database and exits if it cannot connect. MOCK=1 replaces only the one external dependency, embedding, and needs neither network nor key.

starter/ has four exercise points cut out in a considered order: get recall computed correctly first, then make the ground truth genuinely use a full scan, and only then tune and fix under-recall. Skip the first two and the latter two's numbers are all fictional — which is itself today's central methodology.

1. Start the database, load twenty thousand rows, and look first at the brute-force full comparison's latency, remembering that number — it is the denominator of every later comparison.
2. Complete the recall calculation and the ground truth query, rerun, and watch HNSW's recall go from "always 100%" to a real curve rising with ef_search.
3. Change IVFFlat's lists from a hard-coded 1 to a row-derived value, sweep probes again, and compare the two indexes' latency at equal recall.
4. Run the tenant-filtered set, first seeing the scene where under one row is returned on average, then turning iterative scanning on to fix it and recording how many times latency rose.
5. Copy the space, speed, and recall columns for half precision and binary quantization into the closing selection memo, writing after each conclusion how many rows it holds for.

Interview Questions

Today's 4 questions are in the question bank below, weighted toward how approximate nearest neighbor indexes work and are tuned, under-recall in filtered queries, and vector store selection. Expand each one and read the analysis before the key points — practicing the derivation beats memorizing bullets. The high-frequency labels for the domestic and overseas markets are there so you can pick by target market.

Checklist and Tomorrow

• Explain how Hierarchical Navigable Small World graphs and inverted files are each built, and what each of their tunable parameters affects
• Explain why filtered vector queries can under-recall, and state when iterative scanning versus pre-filtering each applies
• Give selection criteria for what scale and what constraints should stay on PostgreSQL, and when to move to a dedicated vector store
• Distinguish too-few-rows under-recall from enough-rows-wrong-order under-recall, and say which wrench each needs
• All 5 acceptance criteria of the lab pass, with every conclusion in the selection memo labeled with its data scale
• Answer at least 3 of the 4 interview questions without looking at the key points

Tomorrow (D6) moves the battlefield to the generation side: once material is fetched, how the context is ordered, how citations are labeled, when refusal is mandatory, and how to stream a response. Why that order? Because after today, fetching what should be fetched has a quantifiable guarantee, and only then is it fair to pursue fetched-and-answered-wrongly. A retrieval-side problem cannot be patched by generation-side means, nor the reverse — dividing the two sides' responsibilities first is what lets day 8's evaluation know which side each metric belongs to.