turbopuffer v3

On 9/19, we saw p90 latency for hot and cold FTS queries on tpuf v3 drop by up to 80%. Building on our past work that batched reads of postings, we now retain these batches through query execution. Previously, we converted these batches into individual rows for simplicity and correctness in our initial implementation. In this change, we operate on and score batches of postings directly, in a very similar manner to how our current FTS v2 query engine vectorizes scoring.

Cold full-text search queries saw a compounding improvement because we also eliminated an object storage round trip on cold FTS reads. To understand how we improved cold latency for FTS queries, we must understand our data dependencies. At a high level, to score documents for a BM25 query, we must load text postings for the query terms, any attribute data needed for filtering, and BM25 statistics for the corpus (e.g. document frequencies) from object storage. Previously, tpuf v3 made these requests serially, loading corpus statistics during planning and postings/attributes for filtering at execution time. A large part of optimizing tpuf cold workloads comes from reducing serial round trips to object storage. Here, we've pushed loading corpus statistics down to be fetched concurrently with the remainder of our postings and attribute data, just before scoring documents. By combining these into a single round trip, we shave hundreds of milliseconds off cold FTS query latency.

On 09/19, we saw a 95% reduction in the runtime for unfiltered order-by queries. Order-by queries have two halves: scanning over documents and accumulating the top-k set. Depending on the specific query, either or both can be the slow part. When working with unfiltered order-by queries, the bottleneck typically falls on the top-k selection, since we must consider each row for inclusion.

To make queries an order of magnitude faster, it isn't enough to micro-optimize our top-k operation, we must also fundamentally reduce the number of rows we consider for inclusion. We achieve this by adding a dynamic filter to queries to rapidly exclude rows that could never enter our result set, leveraging our vectorized filter evaluation for fast processing.

Consider SELECT _ ORDER BY age asc LIMIT 2 run over the table [1, 10, 4, 8, 5, 15, 7]. We add a < DYN filter to our query. This dynamic filter is initially inactive, but once we've scanned the first two rows, we have a candidate result set: [1, 10]. From this we know any new candidate must have age < 10 to make the result set, so we can skip the 6th row (age = 15). After the third row, the result set is [1, 4] and we can skip evaluating all other rows. By updating the dynamic filter after each row, we progressively skip more and more rows in bulk, making the query much faster. This skipping mechanism is quite similar to how our MAXSCORE algorithm executes full-text queries, but applied on order-by queries.

We designed the tpuf v3 query engine to benefit from vectorization everywhere. Our last two devlogs described how we batched reads from storage, but vectorization also extends beyond storage and into the query engine. The first part of the engine to benefit from this is our filter evaluation logic.

As we scan over the documents in a namespace to execute a query, we must check that each candidate row satisfies all filters. We do this by building a bitmap, which is an intersect (AND) or union (OR) of the bitmaps representing which documents match each filter. Previously we filled this bitmap one document at a time, now we build it a page at a time.

Vectorization in tpuf v3 is more than just asking the storage to read and return a range of rows, then operating over them in batches. We also perform "compute pushdown": instead of asking the query engine to evaluate the filter on each row, we ask the underlying storage to answer questions like "are all these rows = 8?". By structuring things this way, we can leverage the specific physical encodings of the data to answer questions in bulk and maximize throughput. Compute pushdown is fundamental to the performance of v3, and a big part of the reason v3 filtering is now faster than current production (v2). We'll talk in more detail about pushdown in the upcoming blog post on our columnar storage layout.

After the large speedup we observed implementing batched reads for FTS, we applied a similar change to our order_by query plans, allowing them to take advantage of our new columnar storage layout, and avoiding the overhead of materializing each individual row during read. The majority of optimizations coming to our query engine — spanning filter execution, order_by, full-text search, and aggregation queries — will have roughly of this shape, e.g. taking advantage of the new physical layouts to find opportunities for batched execution and vectorization.

We're working on a deeper blog post discussing our new columnar layouts and the impact it will have on our query plans. We expect to publish it in a couple of weeks.

Also of note, we simplified how we execute filters for full-text queries, temporarily causing the performance regression you observe in the benchmark chart. The naive implementation evalutes the filter on every row prior to scoring, which is inefficient, but the codepath sets the foundation for significant optimizations on filtered full-text search queries. In particular, we will be able to incorporate filter execution directly into our vectorized full-text query engine, like we do today in production, and skip filtering unnecessary rows.

On 09/08, we implemented batched reads in the v3 full-text engine, leading to a ~9x performance improvement. Sometimes, optimization is not about being clever, but simply avoiding mistakes. Postings are stored as columns, and we were reading them a row at a time. The fix here was obvious, we batched reads from storage. Notably, we're not even batching execution during scoring yet, that will come soon.

Modern CPUs are happiest when their pipelines are full, and batching helps keep them full. Full-text search on tpuf v2 took advantage of this with a bespoke storage system and query engine to enable batching all the way through the pipeline, from reads to scoring.

Unlike v2, v3 unifies every index that uses posting lists on the same internal storage format, so this fix benefits all of them, not just full-text.

We're working on a deeper technical post about this, and we'll share it in the next few weeks.