Vespa adds fast-search map fields, promising 100x faster map queries

Vespa has introduced fast-search map fields, a feature meant to speed up queries on map fields in large product catalogs. According to the company, a simple idea built on its container architecture improved map search performance by a factor of one hundred and more.
- Vespa introduced fast-search map fields to speed up queries on map<k,v> fields.
- According to Vespa, a simple idea built on its container architecture improved map search performance by a factor of one hundred and more.
- Maps are stored as two arrays and queried with sameElement(), whose cost depends on documents matching the first sub-expression.
- Vespa says plain fast-search on a map's key or value does not remove this bottleneck.
- The feature targets large commerce catalogs with attributes that vary by product category.
Maps for catalogs with uneven attributes
Vespa describes the problem from the perspective of retailers and marketplaces. Shoppers filter products by attributes that differ widely between categories, from bicycle frame sizes to smartphone battery capacities. Vespa normally relies on schemas that define all documents, fields and data types, but real catalogs rarely fit neatly into them.
The company points to the map<k,v> data type as a way to add some schema-lessness. A bicycle might have a frame size and a wheel size, an electric vehicle a battery capacity, range and maximum speed. An e-bike has all of these, and a smartphone has a battery capacity but no range or top speed. Vespa says that building a complete taxonomy of everything that can be sold is like "tilting at windmills", and that maps offer a convenient way out.
Why map queries can become slow
Vespa says maps carry performance pitfalls. In its words, a map is "just two array fields wearing a trench coat". The back end does not know the map's internal structure. A map is syntactic sugar over an array of structs, where each struct holds a key and a value, and that array is stored as separate arrays for keys and values.
This is why maps are queried with the sameElement() operator, for example matching a key of 'country_of_origin' together with a value of 'Norway'. According to Vespa, the operator iterates over all documents that match its first sub-expression, checks whether the other sub-expressions also match, and then intersects the matching array positions within each document to confirm that key and value sit in the same element.
The consequence is that query time is dominated by the number of documents matching the first sub-expression. If only a few documents have a 'country_of_origin' key, the query is fast enough. If many documents have it, Vespa says the query can become "excruciatingly slow", and it shows a benchmark to illustrate this.
Enabling fast-search on the key or value struct-field does not fix this, according to the post. The benchmark was already run with it. Fast-search builds an index structure, by default a binary tree, which lets Vespa quickly find all documents with the key. It does not change how sameElement() is evaluated, so the engine still has to go through all those documents and compute the intersections.
From a do-it-yourself fix to a built-in feature
Vespa says the underlying issue is that the index structures do not directly yield the documents that match the sameElement() expression as a whole. The post then moves to a do-it-yourself approach that combines Vespa's flexible container architecture with what the company calls one "hilariously simple idea". The provided text breaks off before the details of that approach.
Vespa states that the idea worked so well that it turned it into a product feature called fast-search map fields. The company says any user can now easily benefit from the performance gains, and that the blog post links to a section on how to use the feature.
For teams running Vespa with heterogeneous product data, the news is relevant where map fields hold keys that appear in many documents, the case Vespa identifies as slow. The company's stated aim is to keep search responsive while supporting detailed product discovery across diverse catalogs.


