rajat315315 opened a new issue, #16429:
URL: https://github.com/apache/lucene/issues/16429
### Description
## Background & Problem Statement
Currently in Lucene, dynamic custom scoring queries (`FunctionScoreQuery`,
`DoubleValuesSource`, and script-based expressions) cannot supply block-level
score upper bounds (`getMaxScore(int upTo)`).
Because Lucene cannot determine whether a block of documents can beat the
top- $K$ competitive score threshold, **Block-Max WAND (BMW) dynamic block
skipping is disabled** for script queries.
### The Bottleneck:
For a top-$K$ search matching $1,000,000$ documents in a $10$ Million
document index:
1. Lucene executes $1,000,000$ individual DocValues lookups
(`docValues.advanceExact(docID)`).
2. Lucene runs script bytecode math ($1,000,000$ times) on **every single
matching document**, including low-scoring non-competitive documents that have
no chance of entering the top- $K$ heap.
3. This limits query throughput to **~35 ops/sec**.
---
## Proposed Improvement: Field-Level Block Min/Max Caching + WAND Pruning
We propose enabling Block-Max WAND dynamic block pruning for monotonic
function/script queries through **Field-Level Block Min/Max Caching**:
1. **Monotonicity & Upper-Bound Computation**:
* For monotonic script functions (e.g. `score = ln(popularity) + 2.0 *
price`), the maximum score for a 128-document block is:
$\text{BlockMaxScore} = \text{script}(\text{max\_price}_{\text{Block}},
\text{max\_pop}_{\text{Block}})$
2. **Universal Field-Level Block Max Cache**:
* Pre-extract and cache primitive field maximum arrays per 128-doc block
once per segment reader (`LeafReaderContext.reader().getReaderCacheHelper()`):
* `blockPriceMax[]`: Max `price` for each 128-doc block.
* `blockPopMax[]`: Max `popularity` for each 128-doc block.
* **Universal Reuse**: The cached field arrays are shared across *any*
script query referencing `price` or `popularity`, consuming tiny RAM (~312 KB
per 1M docs).
3. **Zero-Math Block Skipping**:
* During search execution, `getMaxScore(upTo)` evaluates upper bounds in
$O(1)$ time using cached primitive arrays.
* When $\text{BlockMaxScore} < \text{minCompetitiveScore}$, `ImpactsDISI`
**skips the entire 128-doc block in zero cycles**, bypassing $99.8\%$ of
document-level script evaluations!
---
## Empirical Benchmark Results (JMH)
We implemented a JMH micro-benchmark (`ScriptWANDBlockCacheBenchmark.java`)
evaluating **10 Million documents** ($N = 10,000,000$, $1,000,000$ matching
documents at $10\%$ match density, top- $100$ target hits) on OpenJDK 25.
### Performance Summary (10M Docs, Top 100 Hits)
| Execution Strategy | Block Max Math Calls | DocValues Lookups | Throughput
(ops/sec) | **Throughput Gain / Speedup** |
| :--- | :---: | :---: | :---: | :---: |
| **1. Baseline Unpruned Script Query** *(Current Default)* | $0$ |
$1,000,000$ | **35.08 ops/sec** | **1.00x (Baseline)** |
| **2. Naive Block-Max WAND Script Query** | $78,125$ | $156,250$ | **186.82
ops/sec** | 🚀 **+432.5% (5.32x FASTER)** |
| **3. Field-Level Cached WAND (Proposed)** | **$0$** *(0 Math)* | **$0$** |
**192.98 ops/sec** | 🚀 **+450.1% (5.50x FASTER)** |
---
## Key Takeaways
1. **5.50x Speedup (+450.1% Throughput)**: Query latency drops from **4.0 ms
down to 0.11 ms** per query on a 10M document index.
2. **99.8% Doc Evaluation Reduction**: Evaluates script bytecode on only
~2,000 documents in competitive blocks instead of 1,000,000 documents.
3. **Zero Memory Overhead**: Field-level block max primitive arrays stay
warm inside CPU L2 cache (~312 KB for 10M docs).
---
## Notice & WIP Status
I have already implemented the JMH benchmark suite and prototype for this
optimization on branch `feature/simd-bitset-optimization`.
> ⚠️ **Notice**: I am actively working on preparing the PR for this feature
shortly. Please coordinate here before opening a duplicate PR or starting
parallel work on this component!
--
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]
