Demo

Three pieces of the engine you can move with the mouse. A race between eight shards that share one score cutoff, the engine's own arithmetic for real queries, and a grid showing what happens to a search when you narrow it down.

flowchart LR
        s0["shard 0
scanning"] -->|"my tenth best"| f["coordinator
cutoff = highest published"]
        s1["shard 1
scanning"] -->|"my tenth best"| f
        s7["shard 7
scanning"] -->|"my tenth best"| f
        f -->|"raised cutoff to every shard"| s0
        f -->|"raised cutoff to every shard"| s1
        f -->|"raised cutoff to every shard"| s7

1. The race to a shared cutoff

Eight machines, one query. Each of them reads its own slice of the corpus and keeps a running list of the best answers it has found. As soon as one of those lists is full, its last entry is a useful piece of information for everybody: the best ten in the whole corpus are the best ten out of everything the machines hold together, so the corpus-wide tenth-best cannot be worse than any single machine's tenth-best. Each machine publishes that number, the coordinator takes the highest one and sends it back down, and every machine starts discarding anything below it. No real winner can be lost that way, because a document below the published cutoff already has ten documents beating it.

Press play. The lane bars are each machine's progress through its own slice. The counter is how many candidates had to be considered for the answer. Switch off the sharing to see what the same query costs when each machine can only use a cutoff it worked out for itself.

Both columns return the same documents, in the same order, with the same score bits. That equality is what makes the saving worth having. It is not a quality setting to be traded against speed; it is work that could not have changed the answer.

One detail the picture would otherwise hide. On the vector side a machine still reads every part of its slice. The shared cutoff decides what has to be considered, not when a machine can stop reading. A machine could stop early if it could show that everything in the part it has not read yet falls below the cutoff, and the vector scan cannot yet produce that assurance, so for now it reads on unless the query is cancelled. On the keyword side the equivalent assurance does exist. The word lists are stored in blocks, each block carrying the highest score any document in it could reach, so a block whose best case is below the cutoff is skipped without being read: worth up to about seventy times the speed on a word that appears in a large share of the corpus.

2. Real explain trees

Setting explain on a request hands each hit the arithmetic that produced its score. Every tree below came out of a real engine: a build of the current source, two shard nodes and a coordinator over localhost, native analysis, and twelve short documents written for this page. None of this is reformatted arithmetic; the values and the descriptions are what the engine returned.

A few things to look for. In the two-word keyword tree the root is the sum of one contribution per word, and each contribution is a field weight multiplied by two familiar quantities: how unusual the word is across the corpus, and how often it occurs in this document once the document's length is accounted for. The inputs are printed, so you can see that coffee is reduced to the stem coffe, appears in six of the twelve documents, and is therefore worth less than document, which appears in four. The fused tree shows the other way of combining two rankings: the root is a sum of terms of the form 1 / (60 + rank), one per ranking the document appeared in, with its raw score sitting underneath as the number that fixed its position rather than as something being added up. And in the boolean tree the condition appears under matched but never as a node of its own, because a condition decides membership and contributes no score at all. Two of the results come back with a score of zero, admitted by the condition alone.

The same query, folded

The last capture asks the same keyword query for a page of three results and, in the same request, folds up some arithmetic over the pool of candidates the page was drawn from: a count, a sum, and a mean of the year column, grouped by topic, plus a histogram of year in buckets of ten. This is the response the engine returned.

The histogram came back with two buckets: 5 documents from 2010 and 1 from 2020, with 0 values that could not be bucketed. The mean is an exact fraction of exact sums, not a float reduction in whatever order the shards happened to reply, and asking for page two of this query would report the same numbers to the bit, because naming an aggregation fixes the pool.

3. What narrowing a search does

Searches usually come with conditions attached: only this court, only after 1990, only within twenty-five kilometres of a point. Whether that is easy to honour depends on how the engine finds its candidates in the first place. Most vector search engines build a graph of neighbours and walk it, following links towards the query, which is fast and which chooses its candidates before it knows anything about your condition. Then the condition is applied, and whatever survives is what you get. An engine that reads every document instead can apply the condition first and score only what is left.

Here is a corpus of 10,000 documents, one square per 25 of them. Drag the slider to change how much of the corpus the condition allows through. The dark squares are the documents that survive it.

The two designs stay close together until the condition gets narrow, and then they part. The scan does the same amount of work at every position of the slider and returns the same exact answer. The filtered-afterwards pool, once the condition is down to a few percent, no longer holds enough surviving documents to fill a page of ten, and the ones it does hold were not chosen for being the best among the survivors, because the condition was not known when they were chosen. The usual repairs are to enlarge the pool until the query is slow, or to push the condition down into the graph walk and give up the assurances the walk was relying on.

In this engine the condition is compiled once on the coordinator into a typed tree of comparisons, resolved on each shard against that shard's own vocabulary, and turned into a list of which rows are still allowed. The vector scan takes that list as a mask, and the keyword side consults the same tree before a document can enter the answer, which is why a query that mixes both and carries a condition describes the set of documents it actually returned.

Related