[ENH]: Fast O(1) Precomputed Array Lookup Table for `ExclusiveLongRangeCounter`

[rajat315315]

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:

// 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):

   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: perf/range_agg_bin_search
• 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.

[mikemccand]

This is a clever optimization! Nice example of time/space tradeoff.