apache / apache/lucene

Binary Search for Sparse IndexedDISI advanceWithinBlock & advanceExactWithinBlock [LUCENE-10624]

Open
#11,660 8 comments 0 reactions 0 assignees View on GitHub
affects-version:9.0 affects-version:9.1 affects-version:9.2 legacy-jira-priority:Major module:core/codecs type:enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.