apache / apache/lucene

Optimize `count()` for BooleanQuery disjunction

Open
#12,358 34 comments 0 reactions 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

Context: we (Amazon customer facing product search team, and also AWS) are attempting to understand the amazing performance Tantivy (Rust search engine) has over Lucene, iterating in [this GitHub repo](https://github.com/Tony-X/search-benchmark-game). That repo is sort of a merger of Lucene's benchmarking code ([luceneutil](https://github.com/mikemccand/luceneutil)), including its tasks and `enwiki` corpus, and the [open source Tantivy benchmark](https://github.com/quickwit-oss/search-benchmark-game). Tantivy is impressively fast :)

This issue is a spinoff from [this fascinating comment](https://github.com/Tony-X/search-benchmark-game/issues/30#issuecomment-1579761787) by @fulmicoton, creator and maintainer of [Tantivy](https://github.com/quickwit-oss/tantivy).

Tantivy optimizes `count()` for `BooleanQuery` disjunctions much like Lucene's `BooleanScorer`, by scoring in a windowed bitset of N docs at once, and then pop-counting the set bits in each window. This is not technically a sub-linear implementation: it is still linear, but I suspect with a smaller constant factor than the default `count()` fallback Lucene implements.

Perhaps, for all cases where `BooleanQuery` uses the windowed `BooleanScorer`, we could also implement this `count()` optimization.

From my read of Lucene's `BooleanWeight.count`, I don't think Lucene has this optimization? Maybe we should port over Tantivy's optimization? It should make disjunctive counting quite a bit faster?

Contributor guide

Open the contributing guide

Research direction

Start by reading Lucene's BooleanWeight.count and the BooleanScorer path to understand when windowed scoring is used for BooleanQuery disjunctions. Compare that behavior with Tantivy's windowed bitset and pop-count approach; done means disjunctive count operations use the optimization where applicable and demonstrate faster counting without changing results.

Written by the indexing model from the issue text.

Assessment

Tech stack
java, rust
Domain
backend, search
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.