Range Filter Conditions Reordering
TL;DR¶
As of Vespa 8.672.3, it is better to group range filters by the field:
(field_a >= X AND field_a <= Y) AND (field_b > X AND field_b < Y)Context¶
Filtering on high-cardinality[1] fields is expensive.
When tracing slow queries, you might see something like this:
looking into node doc[0]
┌────────────┬─────────────────────────────────────────────────────────────┐
│ timestamp │ event │
├────────────┼─────────────────────────────────────────────────────────────┤
│ 0.192 ms │ searching for 1 hits at offset 0 │
│ 0.235 ms │ Start query setup │
│ 0.240 ms │ Deserialize and build query tree │
│ 0.250 ms │ Build query execution plan │
│ 0.384 ms │ Optimize query execution plan │
│ 0.413 ms │ Perform dictionary lookups and posting lists initialization │
│ 364.680 ms │ Prepare shared state for multi-threaded rank executors │
│ 364.689 ms │ Complete query setup │
│ │ (query execution happens here, analyzed below) │
│ 986.970 ms │ returning 1 hits from total 6453248 │
└────────────┴─────────────────────────────────────────────────────────────┘
Note the Perform dictionary lookups and posting lists initialization entry which took about 364 ms.
When trace is turned off, the timing matches: most of the time was spent in preparations before matching.
Optimization¶
A natural trick is to reduce the granularity of the field. E.g., given a timestamp field with the second granularity, round it to hours. This reduces the cardinality of the field by a factor of 3600[2].
Not only the query overhead is large, but also the b-tree[3] on the attribute is massive.
E.g. ~25M docs in a content node with a field fast-search weights about 459MB, while the raw field is about 186 MB. The hourly field weights 200 MB.
The problem¶
However, by rounding we lose precision.
What if we could use the fast-search field to filter on the hour and then additionally filter on the second granularity field but without the fast-search?
This would eliminate dictionary lookups and posting lists initialization on the high-cardinality field.
While the lower cardinality field would do the heavy lifting of filtering.
The baseline query with range filters on both ends:
SELECT *
FROM sources *
WHERE
(timestamp_second >= 1776717390)
AND
(timestamp_second <= 1779717390)
The latency is ~190 ms.
match profiling for thread #0 (total time was 162.841 ms)
┌─────────┬──────────┬─────────┬──────┬───────────────────────────────────────────────────────┐
│ seeks │ total_ms │ self_ms │ step │ query tree │
├─────────┼──────────┼─────────┼──────┼───────────────────────────────────────────────────────┤
│ 3000002 │ 54.280 │ 54.280 │ S │ And[1] │
│ 3000002 │ 54.281 │ 54.281 │ S │ ├── Attribute{int32,fs}[2] timestamp_second:<range> │
│ 3000002 │ 54.280 │ 54.280 │ N │ └── WhiteList[3] │
└─────────┴──────────┴─────────┴──────┴───────────────────────────────────────────────────────┘
The initial query that used combined hour and second fields looked like this:
SELECT *
FROM sources *
WHERE
(
(timestamp_hour >= 1776715821)
AND
(timestamp_second_nofs > 1776715921)
)
AND
(
(timestamp_hour <= 1779715821)
AND
(timestamp_second_nofs < 1779715721)
)
And the latency without trace was 165 ms.
The matching breakdown:
match profiling for thread #0 (total time was 736.411 ms)
┌─────────┬──────────┬─────────┬──────┬────────────────────────────────────────────────────────────────┐
│ seeks │ total_ms │ self_ms │ step │ query tree │
├─────────┼──────────┼─────────┼──────┼────────────────────────────────────────────────────────────────┤
│ 2996922 │ 736.411 │ 481.056 │ S │ And[1] │
│ 2998801 │ 30.284 │ 30.284 │ S │ ├── Attribute{int32,fs}[2] timestamp_hour:<range> │
│ 2998801 │ 30.284 │ 30.283 │ N │ ├── Attribute{int32,fs}[3] timestamp_hour:<range> │
│ 2998800 │ 83.801 │ 83.801 │ N │ ├── Attribute{int32,lookup}[4] timestamp_second_nofs:<range> │
│ 2996921 │ 80.704 │ 80.704 │ N │ ├── Attribute{int32,lookup}[5] timestamp_second_nofs:<range> │
│ 2998801 │ 30.284 │ 30.283 │ N │ └── WhiteList[6] │
└─────────┴──────────┴─────────┴──────┴────────────────────────────────────────────────────────────────┘
Tracing for this query adds a lot of overhead, but the structure here is important. Anyway, this looked suspiciously slow.
When the query was rewritten to group range filters by field:
SELECT *
FROM sources *
WHERE
(
(timestamp_hour >= 1776716537)
AND
(timestamp_hour <= 1779716537)
)
AND
(
(timestamp_second_nofs > 1776716637)
AND
(timestamp_second_nofs < 1779716437)
)
The latency dropped to ~119 ms!
match profiling for thread #0 (total time was 555.878 ms)
┌─────────┬──────────┬─────────┬──────┬────────────────────────────────────────────────────────────────┐
│ seeks │ total_ms │ self_ms │ step │ query tree │
├─────────┼──────────┼─────────┼──────┼────────────────────────────────────────────────────────────────┤
│ 2997645 │ 555.878 │ 382.018 │ S │ And[1] │
│ 2998801 │ 45.348 │ 45.348 │ S │ ├── Attribute{int32,fs}[2] timestamp_hour:<range> │
│ 2998800 │ 83.165 │ 83.165 │ N │ ├── Attribute{int32,lookup}[3] timestamp_second_nofs:<range> │
│ 2998801 │ 45.348 │ 45.348 │ N │ └── WhiteList[4] │
└─────────┴──────────┴─────────┴──────┴────────────────────────────────────────────────────────────────┘
And most importantly, the matching breakdown now shows that instead of having four filters, now we have only two: for each field. Vespa managed to collapse the filters!
Summary¶
By reducing the field cardinality, using fast-search strategically, and rearranging range filters by field, we reduced the latency from ~187 ms down to ~119 ms (-36%)!
All while keeping the memory footprint at the same level.
But the query now is more complicated.
And such a rewrite might not be worth if/when Vespa optimizes range queries.
What other rewrites yield better latency with range filters?
P.S. Why simply dropping fast-search is not good enough?¶
If we simply drop the fast-search attribute, the query latency drops to ~ 73 ms!
Sounds great!
However, if used in combination with other retrievers such as ENN, a rage filter on a field that doesn’t have fast-search adds too much overhead.
E.g., a brute force ENN search over 10 M docs takes about ~60 ms.
If a filter that matches about 3 M docs is used, then latency jumps to ~80 ms.
If the selectivity is even lower, then latency grows even further.
When using the field with fast-search with 3 M selectivity, then latency is ~135 ms!
When filtering on the hour granularity field, the latency is 47 ms.
P.P.S. How about inverting filters?¶
Doesn’t help, posting lists initialization still takes a lot of time. Especially if the range is limited on both ends.
Let’s say that by high cardinality, we mean a field that on average the value has less than five documents. For such fields the posting list creation will take a lot of time if the range query that matches millions of documents. E.g., a query with a single filter that matches ~10M distinct values takes about 374 ms (without tracing enabled).
3600 seconds in an hour, 60 seconds * 60 minutes. It reduces the posting list fetch time in our example from 364 ms to 40 ms, ~89% decrease!
A b-tree is a data structure that is used to store data in a sorted order.