apache / apache/lucene

BooleanFilter and ChainedFilter miss to fully optimize for OpenBitSets [LUCENE-2724]

Open
#3,798 1 comment 0 reactions 0 assignees View on GitHub
affects-version:3.0.2 legacy-jira-priority:Major type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

In line 65 of the BooleanFilter class there is an optimization for OpenBitSets, but i miss an optimization in line 62.

I would replace the existing line:

```Java
res = new OpenBitSetDISI(getDISI(shouldFilters, i, reader), reader.maxDoc());
```

with following code:

```Java
DocIdSet docIdSet = shouldFilters.get(i).getDocIdSet(reader);
if(docIdSet instanceof OpenBitSet) {
res = new OpenBitSetDISI(reader.maxDoc());
res.or((OpenBitSet) docIdSet);
} else {
res = new OpenBitSetDISI(docIdSet.iterator(), reader.maxDoc());
}
```

Same for line 78 and 95, adjusted for not and must filters.

That leads to an up to 5 times slower AND-combination in my test, where i had two filters to be AND-combined returning each a cached OpenBitSet, one with a cardinality of 15000 and the other with a cardinality of 13000. The result had a cardinality of 8300. Thats important if you do that 1000 times with a lot more documents.

The same must be also done for ChainedFilter in the method initialResult(..).

Also, the getDISI method in the BooleanFilter must be replaced by a getDocIdSet(..) method. This is useful because in line 87 the docIdSet is retrieved and in line 92 again when it is not of type OpenBitSet. This may also lead to a performance issue if the getDocIdSet method of a sub filter is not super fast.

---
Migrated from [LUCENE-2724](https://issues.apache.org/jira/browse/LUCENE-2724) by Fatih Uzdilli

Contributor guide

Open the contributing guide

Research direction

Read BooleanFilter around lines 62, 65, 78, 87, 92, and 95, then inspect ChainedFilter.initialResult(..). Verify the OpenBitSet optimization and single DocIdSet retrieval across the should, not, and must filter paths, with the reported AND-combination performance improvement as the completion criterion.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.