salvatorecampagna opened a new issue, #16887:
URL: https://github.com/apache/lucene/issues/16887
### Description
`TopFieldCollector` can return the wrong top hits on segments with document
blocks when the search sort is a prefix of the index sort and child documents
match.
In that case the collector stops as soon as a document is not competitive
against the bottom of the queue (`canEarlyTerminate`, `thresholdCheck`),
because it assumes the documents come in sort order. With a parent field only
the blocks are sorted, by the key of their parent. A child either has no value
(it sorts as the missing value) or an unrelated one, so a later document can
still be better.
Ascending sort on `ts`, two blocks `[child, parent]` with parent values 1
and 2, no value on the children, `MatchAllDocsQuery`, top 2. The values by
docID are `[missing, 1, missing, 2]`. The collector returns `[1, missing]`
instead of `[1, 2]`. With the value 9 on the children, `[9, 1, 9, 2]`, it
returns `[1, 9]`. Sorting by `ts` and then docID, which does not terminate
early, returns `[1, 2]`. Using a `TopFieldCollectorManager` with
`totalHitsThreshold` set to `Integer.MAX_VALUE` does not fix the results: the
hit count is exact but the top documents are still wrong.
Results are correct without blocks, and when only the parent documents match
(300 random indexes per sort direction).
Early termination is only safe when the matching documents follow the search
sort order. With document blocks this holds for the parents but not for the
children. I could not find anything that requires a query to match only
parents, and the collector cannot know up front whether a query matches
children.
Suggested fix: do not use the index sort prefix optimization
(`canEarlyTerminateOnPrefix`) on segments with `hasBlocks()`. Sorting by docID
is not affected. This also turns early termination off for queries that only
match parents, which may cost performance (not measured).
Related: #16886 and #16885 make the same assumption, that index sort order
implies document-level docID order, in range queries.
#### Reproduction
Save as `EarlyTerminationRepro.java` and run `java -cp <lucene-core jar>
EarlyTerminationRepro.java`. Each case checks the top 2 values against the
expected ones, against a search sorted by the same field and then by docID, and
against a search with `totalHitsThreshold` set to `Integer.MAX_VALUE`, which
must also report the exact hit count of 4. It throws an `AssertionError` on the
versions below.
```java
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.SortedNumericDocValuesField;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.search.FieldDoc;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.MatchAllDocsQuery;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.Sort;
import org.apache.lucene.search.SortField;
import org.apache.lucene.search.SortedNumericSelector;
import org.apache.lucene.search.SortedNumericSortField;
import org.apache.lucene.search.TopFieldCollectorManager;
import org.apache.lucene.search.TopFieldDocs;
import org.apache.lucene.search.TotalHits;
import org.apache.lucene.store.ByteBuffersDirectory;
import org.apache.lucene.store.Directory;
public class EarlyTerminationRepro {
static final long NO_VALUE = -1;
static final SortField SORT_FIELD =
new SortedNumericSortField(
"ts", SortField.Type.LONG, false, SortedNumericSelector.Type.MIN,
Long.MAX_VALUE);
public static void main(String[] args) throws Exception {
List<String> failures = new ArrayList<>();
long[][] childrenWithoutValues = {{NO_VALUE, 1}, {NO_VALUE, 2}};
long[][] childrenWithValues = {{9, 1}, {9, 2}};
failures.add(check("children without values", childrenWithoutValues,
List.of(1L, 2L)));
failures.add(check("children with values", childrenWithValues,
List.of(1L, 2L)));
failures.removeIf(Objects::isNull);
if (failures.isEmpty() == false) {
throw new AssertionError(failures);
}
}
static String check(String name, long[][] blocks, List<Long> expected)
throws IOException {
try (Directory dir = new ByteBuffersDirectory();
IndexWriter writer = new IndexWriter(dir, indexWriterConfig())) {
for (long[] block : blocks) {
writer.addDocuments(List.of(document(block[0]), document(block[1])));
}
try (DirectoryReader reader = DirectoryReader.open(writer)) {
IndexSearcher searcher = new IndexSearcher(reader);
int k = expected.size();
Sort indexSort = new Sort(SORT_FIELD);
Sort referenceSort = new Sort(SORT_FIELD, SortField.FIELD_DOC);
TopFieldDocs reference = searcher.search(MatchAllDocsQuery.INSTANCE,
k, referenceSort);
TopFieldDocs actual = searcher.search(MatchAllDocsQuery.INSTANCE, k,
indexSort);
TopFieldDocs exact =
searcher.search(
MatchAllDocsQuery.INSTANCE,
new TopFieldCollectorManager(indexSort, k, null,
Integer.MAX_VALUE));
TotalHits allDocs = new TotalHits(2L * blocks.length,
TotalHits.Relation.EQUAL_TO);
if (expected.equals(values(reference))
&& expected.equals(values(actual))
&& expected.equals(values(exact))
&& allDocs.equals(exact.totalHits)) {
return null;
}
return name + ": expected " + expected + " but got " + values(actual)
+ " (reference " + values(reference)
+ ", exact hit count " + exact.totalHits.value() + " with " +
values(exact) + ")";
}
}
}
static List<Long> values(TopFieldDocs docs) {
List<Long> values = new ArrayList<>();
for (ScoreDoc hit : docs.scoreDocs) {
values.add((Long) ((FieldDoc) hit).fields[0]);
}
return values;
}
static IndexWriterConfig indexWriterConfig() {
return new IndexWriterConfig().setIndexSort(new
Sort(SORT_FIELD)).setParentField("parent");
}
static Document document(long value) {
Document document = new Document();
if (value != NO_VALUE) {
document.add(new SortedNumericDocValuesField("ts", value));
}
return document;
}
}
```
### Version and environment details
Lucene 10.4.0, 10.5.2, a 10.6.0 snapshot and `main` at `bc0d7097dc`. Java 25.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
