You Cannot Compare the Question Against Everything
Last timeExact Words and Rough Meaning
Comparing a question against every piece is simple, correct and impossible at scale. The structures that avoid it have build times, memory costs and rules about changing them.
A question has become a list of numbers. There are ten million pieces in the
index, each with its own list. The obvious thing to do is compare the question
against all ten million and keep the best ten.
This works. It is also the only method that is exactly correct, and for a
collection of fifty thousand pieces it is the right choice: a few lines of code
with no index to build, no parameters and no failure modes.
At ten million it costs a few billion multiplications per question. That is a
substantial fraction of a second of a machine's full attention, on every single
question, before anything else has happened.
- pieces in the collection
- partitions the collection was divided into in advance
- partitions actually opened for this question
- comparisons done: the members of the opened partitions, plus one per representative to decide which to open
Two ways to avoid it
Notice what has been given up. The exact method returns the true nearest pieces
by construction. A partition index returns the nearest pieces among those it
happened to look at, and there is no way to know from the result whether
something better was sitting in an unopened partition. The answer is no longer
correct, only usually correct, and the word usually is now a parameter you set.
The second family does not divide the space at all. It joins each piece to a few
dozen of its neighbours, forming a graph, and searches by walking.
| step | hops taken so far | distance from the question | neighbours checked so far | what happened |
|---|---|---|---|---|
| 1 | 0 | 1.42 | 0 | Start at an arbitrary entry point. The distance is roughly what you would expect between two unrelated pieces. |
| 2 | 3 | 0.81 | 96 | Three hops in, already in a broadly relevant region of the space. |
| 3 | 7 | 0.44 | 224 | Seven hops. Close now, and the improvements per hop are getting small. |
| 4 | 11 | 0.39 | 352 | No neighbour of the current piece is nearer than the current piece. The walk stops here, having compared against three hundred and fifty two pieces rather than ten million. |
Memory, not time
Having fixed the time problem, a second one becomes visible, and on real
deployments it binds first.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents