[Feature Request] Approximation Framework for queries with search_after #18546
Description
Is your feature request related to a problem? Please describe
Today we see great improvement for queries that use Approximation Framework with custom BKD walk. But for the same queries with search_after the framework is skipped and fallback to default Lucene PointRangeQuery traversal.
Even today in big5 workloads we track queries like asc_sort_timestamp, desc_sort_timestamp and for same query type we have desc_sort_with_after_timestamp and asc_sort_with_after_timestamp. We saw great improvement for asc/desc sorts and range queries. We should extend this framework for the same query types when search_after is included.
Useful links:
- Approximation Framework Enhancement: Update the BKD traversal logic to improve the performance on skewed data #18439 (comment)
- Approximation Framework Enhancement: Update the BKD traversal logic to improve the performance on skewed data #18439 (comment)
- Approximation Framework Enhancement: Update the BKD traversal logic to improve the performance on skewed data #18439 (comment)
- Fix performance regression in
ApproximatePointRangeQuerywith Lucene 10.2.1 change #18358
Describe the solution you'd like
The solution is to convert the search_after to a proper range query so they can continue to go over the ApproximatePointRangeQuery. For asc sorts the search_after will be the lowerBound and vice versa for desc sorts.
Example for timestamps with desc and search_after we want documents that are older than search_after and for asc and search_after we want documents that are newer than search_after.
I was able to do a POC locally and seen great performance improvement for desc_sort_with_after_timestamp and asc_sort_with_after_timestamp
asc_sort_with_after_timestamp without approximation
| Heap used for stored fields | | 0 | MB |
| Segment count | | 13 | |
| Min Throughput | asc_sort_with_after_timestamp | 2 | ops/s |
| Mean Throughput | asc_sort_with_after_timestamp | 2 | ops/s |
| Median Throughput | asc_sort_with_after_timestamp | 2 | ops/s |
| Max Throughput | asc_sort_with_after_timestamp | 2.01 | ops/s |
| 50th percentile latency | asc_sort_with_after_timestamp | 181.354 | ms |
| 90th percentile latency | asc_sort_with_after_timestamp | 194.828 | ms |
| 99th percentile latency | asc_sort_with_after_timestamp | 211.491 | ms |
| 100th percentile latency | asc_sort_with_after_timestamp | 214.763 | ms |
| 50th percentile service time | asc_sort_with_after_timestamp | 180.138 | ms |
| 90th percentile service time | asc_sort_with_after_timestamp | 193.795 | ms |
| 99th percentile service time | asc_sort_with_after_timestamp | 210.368 | ms |
| 100th percentile service time | asc_sort_with_after_timestamp | 213.727 | ms |
| error rate | asc_sort_with_after_timestamp | 0 | % |
asc_sort_with_after_timestamp with approximation
| Heap used for points | | 0 | MB |
| Heap used for stored fields | | 0 | MB |
| Segment count | | 13 | |
| Min Throughput | asc_sort_with_after_timestamp | 2.01 | ops/s |
| Mean Throughput | asc_sort_with_after_timestamp | 2.01 | ops/s |
| Median Throughput | asc_sort_with_after_timestamp | 2.01 | ops/s |
| Max Throughput | asc_sort_with_after_timestamp | 2.01 | ops/s |
| 50th percentile latency | asc_sort_with_after_timestamp | 7.47536 | ms |
| 90th percentile latency | asc_sort_with_after_timestamp | 8.459 | ms |
| 99th percentile latency | asc_sort_with_after_timestamp | 10.5862 | ms |
| 100th percentile latency | asc_sort_with_after_timestamp | 21.4123 | ms |
| 50th percentile service time | asc_sort_with_after_timestamp | 6.21366 | ms |
| 90th percentile service time | asc_sort_with_after_timestamp | 6.76854 | ms |
| 99th percentile service time | asc_sort_with_after_timestamp | 8.95205 | ms |
| 100th percentile service time | asc_sort_with_after_timestamp | 19.9641 | ms |
| error rate | asc_sort_with_after_timestamp | 0 | % |
desc_sort_with_after_timestamp without approximation
| Heap used for terms | | 0 | MB |
| Heap used for norms | | 0 | MB |
| Heap used for points | | 0 | MB |
| Heap used for stored fields | | 0 | MB |
| Segment count | | 13 | |
| Min Throughput | desc_sort_with_after_timestamp | 2 | ops/s |
| Mean Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| Median Throughput | desc_sort_with_after_timestamp | 2 | ops/s |
| Max Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| 50th percentile latency | desc_sort_with_after_timestamp | 185.023 | ms |
| 90th percentile latency | desc_sort_with_after_timestamp | 188.037 | ms |
| 99th percentile latency | desc_sort_with_after_timestamp | 199.995 | ms |
| 100th percentile latency | desc_sort_with_after_timestamp | 200.207 | ms |
| 50th percentile service time | desc_sort_with_after_timestamp | 183.844 | ms |
| 90th percentile service time | desc_sort_with_after_timestamp | 186.679 | ms |
| 99th percentile service time | desc_sort_with_after_timestamp | 198.518 | ms |
| 100th percentile service time | desc_sort_with_after_timestamp | 198.771 | ms |
| error rate | desc_sort_with_after_timestamp | 0 | % |
desc_sort_with_after_timestamp with approximation
| Heap used for points | | 0 | MB |
| Heap used for stored fields | | 0 | MB |
| Segment count | | 13 | |
| Min Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| Mean Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| Median Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| Max Throughput | desc_sort_with_after_timestamp | 2.01 | ops/s |
| 50th percentile latency | desc_sort_with_after_timestamp | 6.59544 | ms |
| 90th percentile latency | desc_sort_with_after_timestamp | 7.09016 | ms |
| 99th percentile latency | desc_sort_with_after_timestamp | 11.1221 | ms |
| 100th percentile latency | desc_sort_with_after_timestamp | 21.6603 | ms |
| 50th percentile service time | desc_sort_with_after_timestamp | 5.14168 | ms |
| 90th percentile service time | desc_sort_with_after_timestamp | 5.99644 | ms |
| 99th percentile service time | desc_sort_with_after_timestamp | 9.83968 | ms |
| 100th percentile service time | desc_sort_with_after_timestamp | 20.1508 | ms |
| error rate | desc_sort_with_after_timestamp | 0 | % |
Important Considerations
- We should also battle test and consider when
search_afterhas 2 values, coming from above sorts.
{
"query": {"match_all": {}},
"sort": [
{"status": "asc"},
{"@timestamp": "desc"}
],
"search_after": ["active", "2023-06-15T12:00:00.000Z"]
}
- In my above testing I have seen great improvement with
match_allhavingsearch_afterqueries. We should also battle testrangewithsearch_after.
Related component
Search:Performance