[LUCENE-8867] Optimise BKD tree for low cardinality leaves

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 8.2
• Lucene Fields: New
• Assignee: Ignacio Vera
• Reporter: Ignacio Vera
• Created: 18/Jun/19 08:17
• Updated: 28/Aug/22 15:47
• Resolved: 04/Jan/20 08:58

Description

Currently if a leaf on the BKD tree contains only few values, then the leaf is treated the same way as it all values are different. It many cases it can be much more efficient to store the distinct values with the cardinality.

In addition, in this case the method IntersectVisitor#visit(docId, byte[]) is called n times with the same byte array but different docID. This issue proposes to add a new method to the interface that accepts an array of docs so it can be override by implementors and gain search performance.

Issue Links

• links to: GitHub Pull Request #728