apache / apache/lucene

Speed up prohibited clauses when they produce an oal.util.BitSet [LUCENE-6047]

Open
#7,109 0 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.