Binary Search for Sparse IndexedDISI advanceWithinBlock & advanceExactWithinBlock [LUCENE-10624]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Problem Statement
We noticed DocValue read performance regression with the iterative API when upgrading from Lucene 5 to Lucene 9. Our latency is increased by 50%. The degradation is similar to what's described in https://issues.apache.org/jira/browse/SOLR-9599
By analyzing profiling data, we found method "advanceWithinBlock" and "advanceExactWithinBlock" for Sparse IndexedDISI is slow in Lucene 9 due to their O(N) doc lookup algorithm.
### Changes
Used binary search algorithm to replace current O(N) lookup algorithm in Sparse IndexedDISI "advanceWithinBlock" and "advanceExactWithinBlock" because docs are in ascending order.
### Test
```java
./gradlew tidy
./gradlew check
```
### Benchmark
06/30/2022 Update: The below benchmark data points are invalid. I started a new AWS EC2 instance and run the test. The performance of candidate and baseline are very close.
~~Ran sparseTaxis test cases from luceneutil. Attached the reports of baseline and candidates in attachments section.~~
~~1. Most cases have 5-10% search latency reduction.~~
~~2. Some highlights (>20%):~~
- ~~**T0 green_pickup_latitude:[40.75 TO 40.9] yellow_pickup_latitude:[40.75 TO 40.9] sort=null**~~
- ~~**Baseline:** 10973978+ hits hits in **726.81967 msec**~~
- ~~**Candidate:** 10973978+ hits hits in **484.544594 msec**~~
- ~~**T0 cab_color:y cab_color:g sort=null**~~
- ~~**Baseline:** 2300174+ hits hits in **95.698324 msec**~~
- ~~**Candidate:** 2300174+ hits hits in **78.336193 msec**~~
- ~~**T1 cab_color:y cab_color:g sort=null**~~
- ~~**Baseline:** 2300174+ hits hits in **391.565239 msec**~~
- ~~**Candidate:** 300174+ hits hits in **227.592885 msec**{**}{{**}}~~
- ~~**...**~~
---
Migrated from [LUCENE-10624](https://issues.apache.org/jira/browse/LUCENE-10624) by Weiming Wu (@wuwm), updated Jun 30 2022
Attachments: [baseline_sparseTaxis_searchsparse-sorted.0.log](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10624/baseline_sparseTaxis_searchsparse-sorted.0.log), [candiate-exponential-searchsparse-sorted.0.log](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10624/candiate-exponential-searchsparse-sorted.0.log), [candidate_sparseTaxis_searchsparse-sorted.0.log](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10624/candidate_sparseTaxis_searchsparse-sorted.0.log)
Pull requests: https://github.com/apache/lucene/pull/968
Contributor guide
Assessment
This issue has not been assessed yet.