DocIdsetBuilder implementation is inconsistent with DocIdSetBuilder#grow contract [LUCENE-10429]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
Currently the contract of DocIdSetBulder#grow says:
```
/**
* Reserve space and return a \{`@link` BulkAdder} object that can be used to add up to \{`@code` * numDocs}documents.
*/
public BulkAdder grow(int numDocs)
```
I would expect that from the PointValues API I could call this method by using the following:
```
DocIdSetBulder#grow((int) Math.min(docCount, node.size()));
```
But it seems it is not true as the implementation expects that the method is grow for all the call to growAdder, counting duplicated documents. Therefore we have this other implementation of addAll instead, to make happy the implementation:
```
public void addAll(PointValues.IntersectVisitor visitor, boolean grown) throws IOException {
if (grown == false) {
final long size = size();
if (size <= Integer.MAX_VALUE) {
visitor.grow((int) size);
grown = true;
}
}
if (isLeafNode()) {
// Leaf node
leafNodes.seek(getLeafBlockFP());
// How many points are stored in this leaf cell:
int count = leafNodes.readVInt();
// No need to call grow(), it has been called up-front
docIdsWriter.readInts(leafNodes, count, visitor);
} else {
pushLeft();
addAll(visitor, grown);
pop();
pushRight();
addAll(visitor, grown);
pop();
}
}
```
Therefore we have three options here:
1) Modify the grow API to reflect that it can be called more than Integer#MAX_VALUE, and therefore change the input parameter from int to long. Note that this method is exposed due to the points API so we have tried this implementation in #11347 by creating a specific implementation of DocIdSetBuilder for points. This has so far been rejected.
2) Modify the implementation of DocIdSetBuilder. Currently the issue is that we have a counter inside the implementation that it is used to compute the cost for the dense case of the final iterator. Therefore we need to change the way we compute the cost.
The proposal here is to change the way we compute cost from:
```
final long cost = Math.round(counter / numValuesPerDoc);
```
Which might underestimate the cost of the iterator to the following that overestimate the cost:
```
final long cost = Math.min(counter, docCount))
```
I lack of intuition of how this might affect performance down the line. One thing I notice is that for the Terms API (that is when we add docs using a DocIdSetIterator via DocIdSetBuilder#add), we ignore the counter in the dense case, so we are already providing a totally wrong cost on that case!
3) If none of this proposals is successful we should at least update the java docs to reflect reality.
---
Migrated from [LUCENE-10429](https://issues.apache.org/jira/browse/LUCENE-10429) by Ignacio Vera (@iverase), updated Mar 16 2022
Pull requests: https://github.com/apache/lucene/pull/698
Contributor guide
Research direction
Start with the DocIdSetBuilder#grow contract and implementation, then trace PointValues and the addAll method shown in the issue. Compare the documented behavior with duplicate-document counting and the dense-iterator cost calculation. Done means choosing and implementing a consistent API or implementation behavior, or updating the JavaDoc if the behavior is intentional, with the relevant Lucene tests and performance implications addressed.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100