[Feature Request] Improve performance of range queries

[harshavamsi]

Is your feature request related to a problem? Please describe

I've been thinking of how we can improve the performance of certain types of range queries(non scoring to start with). Consider https://github.com/opensearch-project/opensearch-benchmark-workloads/blob/main/big5/operations/default.json#L32C1-L61C7. These are types of queries a user might have when they first load up a dashboard. Give me all the events that took place in the last 30 days, last 24 hours, etc.

Range queries on timestamps are common use cases for such dashboard events. Typically these are non-scoring queries -- queries that don't have another clause in them that force scoring of documents. For example, if this range queries was used in conjunction/disjunction with a text query, we would need to score all the documents in their order of relevance. Scoring + filtering on a range is a time consuming event and since the introduction of Lucene's IndexOrDocValuesQuery, have become much faster thanks to the use of doc_values in certain cases.

For the non-scoring cases, I feel we can do better. Today Lucene scores all documents in a segment but collects only 10. OpenSearch enforces that we collect 10,000 documents. By default, a search without the size attribute returns 10 hits but can be scrolled to get up-to 10,000 hits. What if we only score 10,000 hits instead of all the documents in the segment? This could significantly speed up these non-scoring queries.

Describe the solution you'd like

Similar to how we use other Lucene classes in OpenSearch, we could override the PointRangeQuery class. During search time, we use the searchContext to figure out the query shape and if it a simple range query. If it fits the description, we use the size attribute to determine the number of documents to collect. If size > 10,000, we collect size else we collect min(size, 10,000).

We override Lucene's intesectVisitor to stop intersecting after collecting the number of hits we want and then start collecting. Then we can override the range queries in the field mappers to point to this new query type.

Related component

Search:Performance

Describe alternatives you've considered

Alternative is to do nothing. But this could yield promising results.

Additional context

No response

[andrross]

[Triage - attendees 1 2 3 4] @harshavamsi Thanks for filing. Can you share any benchmark numbers if you have a rough prototype of this optimization?

[harshavamsi]

Ran some benchmarks on the range query on the big5 workload.

m5.12xlarge instance with 1 shard and 3 segments

before with default scoring and termination

|                                        50th percentile latency |  range |     243.858 |     ms |
|                                        90th percentile latency |  range |     251.206 |     ms |
|                                        99th percentile latency |  range |     252.733 |     ms |
|                                       100th percentile latency |  range |      257.93 |     ms |
|                                   50th percentile service time |  range |     242.703 |     ms |
|                                   90th percentile service time |  range |     249.837 |     ms |
|                                   99th percentile service time |  range |     251.789 |     ms |
|                                  100th percentile service time |  range |     256.552 |     ms |
|                                                     error rate |  range |           0 |      % |

After applying the optimization and terminating early after scoring 10,000 docs

|                                        50th percentile latency |  range |     66.1852 |     ms |
|                                        90th percentile latency |  range |     71.4432 |     ms |
|                                        99th percentile latency |  range |     75.3114 |     ms |
|                                       100th percentile latency |  range |     75.6549 |     ms |
|                                   50th percentile service time |  range |     64.9487 |     ms |
|                                   90th percentile service time |  range |     70.0652 |     ms |
|                                   99th percentile service time |  range |     73.6459 |     ms |
|                                  100th percentile service time |  range |     74.5425 |     ms |
|                                                     error rate |  range |           0 |      % |

[jainankitk]

By default, a search without the size attribute returns 10 hits but can be scrolled to get up-to 10,000 hits. What if we only score 10,000 hits instead of all the documents in the segment? This could significantly speed up these non-scoring queries.

Is the optimization applicable for queries without size parameter. If not, how many documents are you planning to score if the size is say 10k?

Also it might be okay to make this default behavior, should we have parameter for high precision use cases?

[harshavamsi]

Some updated numbers after more optimization

|                                        50th percentile latency |  range |     9.73964 |     ms |
|                                        90th percentile latency |  range |     10.3399 |     ms |
|                                        99th percentile latency |  range |     15.5541 |     ms |
|                                       100th percentile latency |  range |     18.8279 |     ms |
|                                   50th percentile service time |  range |     8.44937 |     ms |
|                                   90th percentile service time |  range |     8.85817 |     ms |
|                                   99th percentile service time |  range |     14.5879 |     ms |
|                                  100th percentile service time |  range |     17.0375 |     ms |

[jainankitk]

@harshavamsi - Thank you for sharing these numbers. Look amazing! Can you provide more details on further optimizations?

[harshavamsi]

@jainankitk I realized while writing the intersect function that I could do better by returning 0 here instead of returning pointValues.size(). This I believe causes us to terminate faster although I am still wrapping my head around why it is that much more faster.

[reta]

@harshavamsi I am moving it off to 2.16.0 since we well over the deadline for a release cut (please feel free to discuss that with release team / maintainers).