EasyCompilers

Vocabulary for this course

The terms the chapters assume, in plain words. You can open this from any chapter.

approximate nearest neighbour (ANN)
A search that checks only part of the index, so it is fast but may miss some of the true closest matches.
collection
A named group of vectors that share one configuration and are searched together.
cosine similarity
The dot product of two unit-length arrows, from 1 when they point the same way to -1 when they oppose.
dot product
Multiply matching numbers in two lists and add the results; it grows with both length and agreement.
embedding
A list of numbers that places a piece of text in a space where similar meanings sit close together.
embedding model
The trained program that turns text into vectors, with one fixed output width.
hybrid search
Running a word-matching search and a meaning-based search together, then combining their ranked lists into one.
index
A structure built ahead of time so the database can find nearby items without comparing against every one.
magnitude
The length of a vector, found by squaring its numbers, adding them and taking the square root.
metadata filter
A rule that keeps only the items whose stored facts, such as date or owner, match before or during the search.
model card
A short document describing a trained system: its data, its scores and its known limits.
normalised vector
A vector divided by its own length, so it has length one and only direction remains.
quantisation
Storing each number with less precision, which shrinks memory and usually costs a little accuracy.
recall
The share of the truly closest items that a search actually returned.
reranking
Scoring a short list of results again with a slower, more careful method and putting the best first.
similarity function
A rule that scores two vectors and returns a number saying how alike they are.
top-k
The shortlist a search returns: its best few results, cut off at a number chosen in advance.
training loss
The average error an embedding model makes on the text pairs it is trained to match.
unit length
A vector whose magnitude is exactly 1, which makes a dot product read as pure agreement.
vector
An ordered list of numbers, where each position is one measured property.

Vector databases from the ground up

Flat versus approximate indexes

Flat search compares the query to everything and is exact. HNSW walks a graph and IVF probes a few partitions; both are faster and both can miss. The knob is real, and it can be measured.

Part 3 of 10

Intermediate16 min readBack to Courses

Flat is a loop, and that is fine

Flat search computes the distance from the query to every stored vector, sorts the results and takes the first k. It is exact by construction, it has no settings, and it is the ground truth every approximate index is measured against. If a query returns the wrong answer on a flat index, the index is not the problem: the embedding, the metric or the data is.

It is also linear: twice the vectors, twice the work. At ten thousand vectors that is nothing; at ten million it is the difference between a search box and a batch job. The crossover point depends on your hardware and your latency budget, not on a number from a vendor page. Measure it on the machine you will actually run, with the vectors you will actually store.

The same loop is also the simplest thing to test. A hundred vectors, a query, and a sorted list is a fixture you can read. Every later index in this chapter is judged against that fixture. So the flat version is worth writing even though a library will replace it in production. The fixture is the specification, and the index is an optimisation of it.

HNSW is a graph you walk

HNSW builds a hierarchy of neighbour graphs. The top layer is sparse and spans the space; each layer below is denser. A search enters at the top and greedily moves to the closest neighbour. It drops a layer and repeats, and finally explores a small candidate list at the bottom. The structure is a map you can walk, and the quality of the map depends on how it was built.

The knob is ef_search (how many candidates the bottom layer keeps). Raise it and recall (the share of the true nearest neighbours that were found) rises with latency. The graph is expensive to build and awkward to update, so deletes are usually tombstones (deleted markers) and a large rebuild is a planned event. Build settings such as M decide the graph’s shape once; the search setting can be tuned per query and per latency budget.

HNSW, with the knob exposed

import hnswlib

index = hnswlib.Index(space="cosine", dim=384)
index.init_index(max_elements=1_000_000, ef_construction=200, M=16)
index.add_items(vectors, ids)

index.set_ef(64)                 # recall and latency, per query
labels, distances = index.knn_query(query, k=5)

Probe more lists, find more neighbours

Run the recall table, then change the number of lists from 8 to 4 and to 16. Explain which change makes nprobe=1 better and which makes it worse.

Output
Click "Run" to execute your code

IVF is a partition you probe

IVF clusters the vectors into lists with k-means (a way to group points by nearness) and stores each list separately. At query time it compares the query to the centroids (the centre point of each list), picks the nprobe closest lists, and scans only those. It is cheaper to build than a graph and it degrades in a way that is easy to reason about. It is also easier to shard, because each list is already a self-contained partition.

The failure mode is at the boundary: a true neighbour that landed in an unprobed list is invisible. More probes means more recall and more scanning, and the curve is usually steep at the start and flat afterwards. That shape is the whole argument for measuring instead of guessing. The first few probes buy most of the quality, and the last ones buy almost none.

Measure recall against flat search on a sample of real queries before you tune anything. A recall number from a synthetic benchmark tells you the index works; a number from your own queries tells you the product works.

Choosing, and when not to

Start flat. Move to an approximate index when p95 latency (the slow end of the range) crosses the budget you set, not when a vendor says the corpus is large. The move is a setting change in most databases, and the measurement you built for flat search is what tells you the new index is good enough. A move without that measurement is a hope with a deployment date.

Once you move, keep the exact answer available for a sample of queries. An ANN index that has drifted, or whose settings were changed during an incident, is otherwise impossible to tell from a correct one. The sample does not need to serve users. It needs to answer the question “is the fast path still finding what the slow path would?”

The honest summary is that the index is a latency decision, not a quality decision. It does not make retrieval smarter; it makes it cheaper and slightly less complete. The quality work happens in the embedding, the chunking and the ranking, and no index setting can recover a passage that was never a good match. Keep those two conversations separate or you will tune the wrong layer.

A greedy walk on a neighbour graph

Run the walk and read its recall. Then rebuild the graph with four neighbours instead of eight and compare: fewer edges means fewer hops and more misses.

Output
Click "Run" to execute your code

Check what you learned

One question at a time. A wrong answer explains itself — take another go.

Part 1 of 5

What is true of flat search?