December 09, 2025•Adrien Grand (Engineer), Morgan Gallant (Engineer)

FTS v2, the newest version of turbopuffer’s homegrown text search engine, is up to 20x faster than v1 thanks to (a) an improved storage layout and (b) a better search algorithm. This post is about the better search algorithm.

turbopuffer is often queried by agents, who tend to craft longer queries than humans. A key characteristic of the FTS v2 search algorithm is that it performs very well on such long queries (tens of terms). In particular, it is up to several times faster than block-max WAND, the most popular algorithm for lexical search.

Below are some representative benchmarks (full results) of FTS v1 versus FTS v2 on a 5M-document Wikipedia export sample dataset borrowed from Quickwit’s Search Benchmark Game. The results support the claim that FTS v2 works extremely well not only on simple queries, but also on harder queries with many terms or those with only stopwords.

turbopuffer FTS latency (k=100, dataset=English Wikipedia export @ ~5M documents)


san francisco  v1 ║░░░ 8ms
v2 ║▓ 3ms
║
║
the who  v1 ║░░░░░░░░░░░░░░░░░ 57ms
v2 ║▓▓ 7ms
║
║
united states  v1 ║░░░░░░ 20ms
constitution  v2 ║▓▓ 5ms
║
║
lord of the rings  v1 ║░░░░░░░░░░░░░░░░░░░░░░░ 75ms
v2 ║▓▓ 6ms
║
║
pop singer songwriter  v1 ║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 174ms
born 1989 won best  v2 ║▓▓▓▓▓▓ 20ms
country song time     ║
person of the year     ║

turbopuffer FTS latency (ms)

k=100,
English Wikipedia export
~5M documents

174ms
░░ v1                  ░░
░░
▓▓ v2                  ░░
░░
░░
░░
░░
░░
░░
░░
░░
░░
░░
░░
75ms  ░░
░░    ░░
░░    ░░
57ms        ░░    ░░
░░          ░░    ░░
░░          ░░    ░░
░░          ░░    ░░
░░    20ms  ░░    ░░20ms
░░    ░░    ░░    ░░▓▓
8ms   ░░7ms ░░    ░░6ms ░░▓▓
░░3ms ░░▓▓  ░░5ms ░░▓▓  ░░▓▓
░░▓▓  ░░▓▓  ░░▓▓  ░░▓▓  ░░▓▓
══════════════════════════════
q1    q2    q3    q4    q5
--------------------------------
q1 = san francisco

q2 = the who

q3 = united states
constitution

q4 = lord of the rings

q5 = pop singer songwriter
born 1989 won best
country song time
person of the year

Search algorithms: MAXSCORE vs WAND

Consider the query "new york" with a top-k of 10. It has two terms: "new" and "york", each contributing a max score of 2.0 and 5.0, respectively. "york" has a higher score because the word is less common than "new". The query score is the sum of the per-term scores, higher score is better.

We can deduce that any document may get scores up to the following values depending on what terms it contains:

Document	Max possible score
only "new"	2.0
only "york"	5.0
"new" and "york"	7.0

During evaluation, we may find ourselves in a scenario where the 10th best-scoring document so far has a score of 4.0. As k=10, any document containing only "new" can never enter the results! At this point, we can skip all documents that only contain "new". This simple optimization can lead to dramatic speedups.

There are two main algorithms that take advantage of this idea to speed up query evaluation without trading recall: MAXSCORE and WAND.

Let’s look at how they evaluate a query on terms "new", "york", and "population" which respectively contribute up to 2.0, 5.0, and 4.0 to the score (top_k=3 for brevity).

MAXSCORE: term-centric

The first family of search algorithms is MAXSCORE. It starts by sorting the query terms by their score contribution: [new(2.0), population(4.0), york(5.0)].

Then, it starts iterating through the documents that match each term, keeping track of the highest scoring documents in the top-k heap.

Let’s add a proverbial breakpoint a few iterations in:

----------------------------------------------------------
| Term         | Max score | Postings (matching doc IDs) |
|--------------|-----------|-----------------------------|
| new          |       2.0 | 0, 1, 3, 5, 6, 7, 9, 10     |
|              |           |          ^                  |
| population   |       4.0 | 1, 2, 3, 8, 9               |
|              |           |          ^                  |
| york         |       5.0 | 2, 3, 7, 10                 |
|              |           |       ^                     |
----------------------------------------------------------

# (score, doc_id) -- bigger score is better
TOPK3_HEAP = [(6.0, 1), (9.0, 2), (11.0, 3)]

At this point, the minimum score in the heap is 6.0, so documents with “new” alone can no longer qualify, and “new” has become a non-essential term. We can simply ignore it when looking for the next document to evaluate, speeding up query performance.

In a few iterations, the minimum score will be 7.0, at which point “population” also becomes non-essential, speeding up the remainder of the query execution even further!

MAXSCORE: use essential terms to find candidates, use all terms to compute scores

WAND: document-centric

The second family of skipping algorithms is WAND ("weak and"). We consider it document-centric, because instead of continuously determining which terms no longer qualify, it attempts to find the next doc ID that could potentially qualify for the top-k heap.

Let’s breakpoint at the same moment as with MAXSCORE:

----------------------------------------------------------
| Term         | Max score | Postings (matching doc IDs) |
|--------------|-----------|-----------------------------|
| new          |       2.0 | 0, 1, 3, 5, 6, 7, 9, 10     |
|              |           |          ^                  |
| population   |       4.0 | 1, 2, 3, 8, 9               |
|              |           |          ^                  |
| york         |       5.0 | 2, 3, 7, 10                 |
|              |           |       ^                     |
----------------------------------------------------------

# (score, doc_id) -- bigger score is better
TOPK3_HEAP = [(6.0, 1), (9.0, 2), (11.0, 3)]

WAND sorts doc IDs in ascending order and calculates the score upper bound for each ID. A term contributes to the document score if its iterator has passed and confirmed the doc ID is present, or hasn’t yet reached the doc ID (WAND must assume it is in the posting list).

For example:

# (doc ID, score upper bound)
[
(5, 2.0),   # matches "new", will not match "york" or "population"
(7, 7.0),   # matches "york", might match "new"
(8, 11.0)   # matches "population", might match "new" and "york"
]

Then, WAND finds the first document whose best possible score exceeds the minimum heap score (6.0). Here, that’s doc ID 7, so WAND evaluates it next. If the minimum heap score were greater than 7.0, WAND would skip directly to 8.

WAND: use all terms, continuously skipping doc IDs that cannot possibly qualify.

Block-max MAXSCORE/WAND

In their basic forms, these algorithms use global max scores: each term has a single max score (like 2.0 for "new") that applies to its entire posting list containing all doc IDs. With a global max score, we must evaluate each document individually to determine if it can qualify for the heap. But what if we could skip entire groups of documents at once?

This is what the block-max variants of MAXSCORE and WAND achieve. Block-max divides each posting list into fixed-size blocks containing a subset of doc IDs, storing a local max score for each block (the maximum score any document in that block can get from that term). Documents within a block can have different scores because term frequency (TF) varies per document, even though inverse document frequency (IDF) is constant for the term. If a block’s local max score doesn’t exceed the minimum heap score, the algorithm can skip the entire block of documents. Block-max MAXSCORE and block-max WAND are currently considered the state of the art for lexical search.

There are really no disadvantages to block-max MAXSCORE/WAND versus MAXSCORE/WAND. For brevity, I’ll be using "MAXSCORE" and "WAND" to describe the algorithms for the remainder of this post, but know I’m referring to their block-max counterparts.

Comparison

WAND is currently the dominant algorithm for query evaluation, as it takes more information into account (the current positions of the postings list iterators) and can thus skip more documents than MAXSCORE.

However, skipping more documents doesn’t necessarily mean faster. In order to skip more documents, WAND must spend more cycles computing the next doc ID that can qualify for the top-k heap. This introduces more work per evaluated document, giving WAND a lower throughput than MAXSCORE. When WAND’s skipping power is outweighed by low throughput, MAXSCORE becomes more performant.

The Apache Lucene project initially started with WAND. While it worked well for most queries, users reported certain query types where it was slower than even exhaustive evaluation due to poor skipping decisions compounded by poor throughput. This led Lucene to switch to MAXSCORE and optimize it for throughput by improving memory locality, reducing unpredictable branches, and taking advantage of SIMD instructions.

Algorithm	Skipping	Evaluation throughput
Exhaustive	None	Very good
WAND	Very good	Average
MAXSCORE	Good	Good
Lucene’s vectorized MAXSCORE	Good	Very good

Lucene’s vectorized MAXSCORE throughput is so good that it’s also extremely competitive with WAND on simple queries where WAND is expected to shine, as confirmed by the Tantivy vs. Lucene benchmarks (Tantivy implements WAND). And because throughput is very good, it doesn’t become slower than exhaustive search in cases when skipping is hard.

This good throughput is especially important on long queries (tens of terms) where skipping is harder, especially for WAND-based algorithms whose overhead scales with the number of terms. Our evaluations confirmed those made by Apache Lucene; this algorithm often performs several times faster than WAND on long queries.

Side note: the WAND vs. MAXSCORE trade-off has similarities with HNSW vs. SPFresh, the system turbopuffer uses for ANN search. WAND and HNSW optimize for skipping first, and throughput second, whereas Lucene’s MAXSCORE and SPFresh optimize for throughput first, and skipping second.

turbopuffer’s MAXSCORE variant

While building on the same skipping logic as MAXSCORE, we borrow from Lucene’s vectorized implementation, differing significantly from the textbook description in order to improve throughput.

The main novelty is that postings iterators are no longer advanced in an alternating fashion. In traditional MAXSCORE implementations, iterators advance alternately: if iterator A is at doc ID 5 and iterator B is at doc ID 3, the algorithm advances B to catch up, perhaps advancing B beyond A, causing A to then catch up, and so on.

Our implementation works differently. After computing the next range of doc IDs to evaluate based on local max scores, it processes all matching doc IDs and scores needed from each postings iterator in one batch before moving to the next iterator. This means the same iterator advances many times in a row (often tens of times or more) before switching to another iterator.

This batching approach achieves specific CPU-level throughput optimizations:

• Better memory locality: Accessing consecutive memory locations from the same iterator enables the CPU’s cache prefetcher to predict and load upcoming data before it’s needed, achieving higher cache hit rates.
• Branch prediction: When the same iterator advances many times in a row, the CPU’s branch predictor achieves higher accuracy by learning a consistent pattern, keeping the instruction pipeline full more often.
• SIMD vectorization: Modern CPUs take advantage of SIMD instructions to process multiple data elements in parallel, but they require sequential data. Processing many consecutive elements from the same iterator enables SIMD optimizations that wouldn’t be possible with frequently alternating iterators.

Conclusion

Designing fast search engines is a subtle optimization problem. On the one hand, CPUs reach peak efficiency on serial workloads with predictable branches. On the other hand, the smartest algorithms often have a random access pattern and lots of conditionals. So it takes some effort to select the right algorithm and then tune it to get the best out of the CPU.

Plus, context keeps changing. AVX-512 has now been widely available on server-side CPUs for several years, further moving the cursor in the direction of serial, branchless workloads. "Serial and dumb" can often beat "smart and random" on modern CPUs. Furthermore, agents write longer queries than humans, so it’s becoming increasingly important for text search to scale well with the number of terms.

These factors force us to periodically revisit our choices of algorithms and their implementations. For text search, this means that the cursor has shifted more and more from WAND to MAXSCORE, which scales better with the number of terms and can be tuned to be more CPU-friendly.

Thanks for reading through this blog. I hope you enjoyed the deep dive, as well as the performance that you’re now getting on text search with turbopuffer thanks to FTS v2.

Appendix: turbopuffer FTS v2 benchmark results

Below you’ll find results of turbopuffer’s nightly benchmarks, comparing FTS v1 vs. FTS v2. It is reusing infrastructure from Search Benchmark, the Game: a 5M export of English Wikipedia, plus a mix of some AOL queries and handcrafted queries that exhibit similar characteristics to those we see in production.

Query	top_k	FTS v1 latency (ms)	FTS v2 latency (ms)	Speedup (Multiplier)
the	10	26.0	3.9	6.7x
the	100	25.9	5.2	5.0x
the	1000	28.8	12.8	2.2x
search	10	3.1	1.4	2.2x
search	100	3.5	2.0	1.8x
search	1000	5.9	4.6	1.3x
new york	10	17.5	4.0	4.4x
new york	100	17.7	6.0	2.9x
new york	1000	20.2	9.7	2.1x
san francisco	10	7.1	2.2	3.2x
san francisco	100	7.5	2.8	2.7x
san francisco	1000	9.9	5.7	1.7x
the who	10	57.4	4.8	12.0x
the who	100	57.3	6.7	8.6x
the who	1000	60.1	16.4	3.7x
the incredibles	10	37.4	3.3	11.3x
the incredibles	100	37.4	5.2	7.2x
the incredibles	1000	40.9	13.7	3.0x
new york population	10	31.0	6.5	4.8x
new york population	100	31.3	8.3	3.8x
new york population	1000	33.8	14.0	2.4x
world bank president	10	20.9	4.6	4.5x
world bank president	100	21.1	6.2	3.4x
world bank president	1000	23.9	10.4	2.3x
united states constitution	10	19.8	3.8	5.2x
united states constitution	100	19.8	5.1	3.9x
united states constitution	1000	23.0	9.4	2.4x
law school rankings	10	14.9	2.7	5.5x
law school rankings	100	15.3	4.3	3.6x
law school rankings	1000	18.0	9.9	1.8x
lord of the rings	10	74.5	4.2	17.7x
lord of the rings	100	75.4	6.3	12.0x
lord of the rings	1000	79.8	15.6	5.1x
story of a girl	10	84.2	5.0	16.8x
story of a girl	100	84.3	7.1	11.9x
story of a girl	1000	86.5	16.4	5.3x
to be or not to be	10	99.7	18.4	5.4x
to be or not to be	100	100.6	22.3	4.5x
to be or not to be	1000	103.8	31.1	3.3x
arsenal player 1998 forward goal non flying dutch	10	32.7	7.2	4.5x
arsenal player 1998 forward goal non flying dutch	100	33.1	8.6	3.8x
arsenal player 1998 forward goal non flying dutch	1000	36.2	13.6	2.7x
france president world war resistance london appeal	10	53.7	10.6	5.1x
france president world war resistance london appeal	100	54.4	12.0	4.5x
france president world war resistance london appeal	1000	57.6	18.9	3.0x
pop singer songwriter born 1989 won best country song time person of year	10	172.9	15.9	10.9x
pop singer songwriter born 1989 won best country song time person of year	100	174.4	20.1	8.7x
pop singer songwriter born 1989 won best country song time person of year	1000	178.0	32.4	5.5x
kenyan world marathon record olympic champion bbc world sport star of the year	10	143.5	12.0	12.0x
kenyan world marathon record olympic champion bbc world sport star of the year	100	143.2	17.2	8.3x
kenyan world marathon record olympic champion bbc world sport star of the year	1000	147.3	30.4	4.8x
a search engine is an information retrieval software system designed to help find information stored on one or more computer systems	10	350.2	18.3	19.1x
a search engine is an information retrieval software system designed to help find information stored on one or more computer systems	100	350.0	26.7	13.1x
a search engine is an information retrieval software system designed to help find information stored on one or more computer systems	1000	357.7	47.7	7.5x
a database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure indexes are used to quickly locate data without having to search every row in a database table every time said table is accessed	10	570.9	30.5	18.7x
a database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure indexes are used to quickly locate data without having to search every row in a database table every time said table is accessed	100	575.1	43.3	13.3x
a database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure indexes are used to quickly locate data without having to search every row in a database table every time said table is accessed	1000	577.7	80.7	7.2x

---

turbopuffer

We host 1T+ documents, handle writes at 10M+ writes/s, and serve 10k+ queries/s. We are ready for far more. We hope you’ll trust us with your queries.

Get started