Speed up prohibited clauses when they produce an oal.util.BitSet [LUCENE-6047]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
When we have a query that has a required clause A and an prohibited clause B (A AND_NOT B), we typically use A's iterator to drive the iteration and then check B's iterator to see if it also has the document.
Yet we have a couple of queries (eg. MultiTermQuery with filter rewrite) and filters (eg. TermsFilter) that fill an oal.util.BitSet in order to return an iterator, and this BitSet could return its inverse iterator quite efficiently by using `nextClearBit` instead of `nextSetBit` to locate the next document.
This would potentially make queries that have prohibited clauses faster by performing a leap-frog instead of running the positive clauses first and then checking the negative clauses afterwards?
This could also be a way for BooleanQuery to be faster when the cost of the optional/required clauses is high by loading the DocIdSetIterators of the prohibited clauses into a BitSet and turning the inverse of the BitSet (using nextClearBit instead of nextSetBit) into a required clause? This would typically be used by Solr when running pure negative queries (see QueryUtils.fixNegativeQuery) which are made of a required clause on a MatchAllDocsQuery and a prohibited clause.
---
Migrated from [LUCENE-6047](https://issues.apache.org/jira/browse/LUCENE-6047) by Adrien Grand (@jpountz)
Contributor guide
Research direction
Start by reading BooleanQuery, MultiTermQuery filter rewrite, TermsFilter, and QueryUtils.fixNegativeQuery, focusing on how DocIdSetIterators and oal.util.BitSet are used. The issue proposes using nextClearBit for prohibited-clause iteration, but it names no tests or concrete acceptance criteria, so establish performance and correctness checks before implementation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100