rajat315315 opened a new issue, #16436:
URL: https://github.com/apache/lucene/issues/16436
### Description
### 1. Motivation & Problem Statement
Currently, Lucene's range faceting implementation (`LongRangeFacetCounts` /
`ExclusiveLongRangeCounter`) evaluates document numeric values against $R$
requested range intervals by executing a binary search over a range segment
tree.
For every document evaluated, this costs $O(\log R)$ comparisons per value:
```java
// Current ExclusiveLongRangeCounter binary search
int lo = 0, hi = numRanges - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (v < min[mid]) {
hi = mid - 1;
} else if (v > max[mid]) {
lo = mid + 1;
} else {
countBuffer[mid]++;
break;
}
}
```
However, many real-world numeric range faceting use cases operate over
bounded numeric domains where the domain span (`globalMax - globalMin + 1`) is
relatively small. Common examples include:
- **`dayOfYear`**: Domain $[1, 366]$ (Span $\approx 366$)
- **`month`**: Domain $[1, 12]$ (Span $= 12$)
- **`age`**: Domain $[0, 120]$ (Span $= 121$)
- **`HTTP status code`**: Domain $[100, 599]$ (Span $= 500$)
- **`percentile / score buckets`**: Domain $[0, 100]$ (Span $= 101$)
In these scenarios, executing an $O(\log R)$ binary search per document
introduces unnecessary CPU branch mispredictions and memory comparison overhead
when a simple precomputed array lookup can resolve the value to its range index
in **$O(1)$ time (1 CPU instruction)**.
---
### 2. Proposed Solution: Precomputed Array Lookup Table (Option B)
We propose adding a fast $O(1)$ precomputed array lookup path to
`ExclusiveLongRangeCounter` for bounded range domains:
1. **Domain Span Calculation**:
During `ExclusiveLongRangeCounter` constructor initialization, compute
global domain boundaries:
$$\text{span} = \text{globalMax} - \text{globalMin} + 1$$
2. **Precomputed Array Initialization**:
If $\text{span} \le 65,536$ (64 KB array size limit for optimal L1/L2
cache locality):
- Allocate `int[] fastRangeMap = new int[(int) span]`.
- Populate `fastRangeMap` with range bucket indices, or `-1` for unmapped
values.
3. **$O(1)$ Single-Instruction Value Lookup**:
In `addSingleValued(long v)`:
```java
if (useFastTable && v >= fastMinVal && v <= fastMaxVal) {
int bucket = fastRangeMap[(int) (v - fastMinVal)];
if (bucket != -1) {
countBuffer[bucket]++;
}
} else {
// Fallback to existing O(log R) binary search for out-of-bounds or
wide domains
addSingleValuedBinarySearch(v);
}
```
4. **Zero Overhead Fallback**:
If the domain span exceeds $65,536$, `useFastTable` is set to `false`,
incurring zero extra memory or runtime overhead and falling back to standard
binary search.
---
### 3. Benchmark Results (`luceneutil`)
We benchmarked the implementation using `luceneutil` (`runFacets.py`) on the
`wikimedium10k` dataset, evaluating 39 fine-grained range buckets over the
`dayOfYear` field ($[0, 390]$):
- **Correctness**: Count outputs were verified to be **100% identical**
across all test runs.
- **Pure Scalar**: Implemented in 100% pure Java without any external
framework or Vector API / SIMD dependencies.
| Query Category | `post_collection_facets` (QPS) |
`during_collection_facets` (QPS) | QPS Difference |
| :--- | :---: | :---: | :---: |
| **`range` Facets** | **1,605.31** | **1,548.19** | Baseline Validated |
| **`MedTerm`** | 1,795.97 | **2,471.15** | **+37.6%** |
| **`HighPhrase`** | 89.80 | **130.96** | **+45.8%** |
| **`OrHighHigh`** | 39.68 | **59.57** | **+50.1%** |
| **`MedIntervalsOrdered`** | 37.97 | **65.70** | **+73.0%** |
| **`ConstMSM2`** | 261.04 | **340.77** | **+30.5%** |
---
### 4. Code Location & Branch
- **Feature Branch**: `feature/range-agg-log-r-lookup`
- **Modified Classes**:
- `org.apache.lucene.facet.range.ExclusiveLongRangeCounter`
- `org.apache.lucene.facet.range.LongRangeFacetCounts`
Feedback and suggestions from maintainers (@gsmiller, @mikemccand, @rmuir)
are welcome!
---
> [!IMPORTANT]
> **Active Development Notice**: I am actively working on the implementation
and benchmarking for this optimization and will be opening a Pull Request
shortly. Please ping me before starting redundant work on this issue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
