From sequential scan to vector index

A nearest-neighbor query with no index is honest work. Postgres computes the distance from your query vector to every row, sorts, and returns the top ten. It is exact, and at ten thousand rows it takes about the time you would spend blinking.

At two million rows it takes seconds, and your endpoint is broken.

The previous course, AI RAG architecture, treated the vector store as a box with a recall dial. This course opens the box. By the end you will be able to choose an index type, set its parameters from the shape of your data, measure what the choice cost you in recall, and explain why a filtered vector query behaved strangely.

Measure before you tune

Every tuning decision here is worthless without a number to compare against. Postgres gives you that for free:

EXPLAIN ANALYZE
SELECT id FROM rag_chunks
ORDER BY embedding <=> '[0.1, 0.2, ...]'
LIMIT 10;

Limit  (cost=..) (actual time=412.883..412.891 rows=10 loops=1)
  ->  Sort  (actual time=412.881..412.885 rows=10 loops=1)
        Sort Method: top-N heapsort  Memory: 27kB
        ->  Seq Scan on rag_chunks  (actual time=0.019..385.402
                                      rows=2000000 loops=1)
Planning Time: 0.104 ms
Execution Time: 412.951 ms

Three things in that output matter, and you will read them again after every change in this course. Seq Scan means no index was used. rows=2000000 is how many distance computations you paid for. Execution Time is the number your users feel.

Note also what a sequential scan is good at: it is exact. It is the ground truth you will measure every approximate index against in lesson 7, and that is a useful role for it long after you stop serving traffic with it.

What an index changes, and what it costs

An index over scalar values (a B-tree on created_at) is a shortcut to an answer that is still exact. Vector indexes are not like that.

There is no way to order high-dimensional points on a line such that near points stay near. That comes from the geometry of the space, and no implementation can get around it. So vector indexes give up exactness and organize the data such that most near neighbors can be found without visiting everything. The result is approximate nearest neighbor search, and the thing you gave up has a name and a number:

recall@10 = (how many of the true top 10 the index returned) / 10

A recall@10 of 0.95 means that on average, nine and a half of the ten rows you got back are among the ten closest, and the rest are near-misses: usually the eleventh and twelfth closest, not random rows.

flowchart LR
  S["Sequential scan"] --> S1["recall 1.00"]
  S --> S2["O(n) — seconds at 2M rows"]
  A["ANN index"] --> A1["recall 0.90-0.99, tunable"]
  A --> A2["sublinear — milliseconds"]

Recall is a dial, not a fixed property of the index. Every index type in this course exposes a query-time parameter that trades latency for recall. Building the index is the decision; turning that dial is the daily work.

Three costs, not one

Teams evaluate vector indexes on query speed and get surprised by the other two.

Query latency is the one you shopped for.

Build time is what you pay when the index is created and, more painfully, when it is rebuilt. An HNSW index over several million rows can take hours. If your deploy process rebuilds indexes, this is now a deploy problem.

Memory decides whether any of the above holds. Index performance falls off a cliff when the structure no longer fits in memory, because a graph traversal that was following pointers in RAM starts issuing random disk reads. A vector index is often larger than the table it indexes.

2,000,000 rows × 1024 dimensions × 4 bytes  =  8.2 GB of raw vectors
HNSW index on top of that                   =  roughly 2-4 GB more

Run those multiplications before you choose dimensions, not after. This is the arithmetic behind the quantization work in lesson 6.

What pgvector gives you

pgvector (0.8.6 at the time of writing) ships two index types and four vector types. The map for the rest of this course:

The "Needs existing data" row is an operational trap: an IVFFlat index built on an empty or tiny table produces bad clusters, and it does not fix itself as rows arrive. Lesson 3 covers what to do about it.

The course

1. From sequential scan to vector index: you are here.
2. Distance metrics and operator classes: getting the pairing right.
3. IVFFlat: lists, probes, and when clustering is enough.
4. HNSW: m, ef_construction, ef_search, and what the graph costs.
5. Filtering: where approximate search gets hard.
6. Quantization: halfvec, binary vectors, and rescoring.
7. Measuring recall and shipping it.

Next: the choice that silently disables your index if you get it wrong.