Puneet Sharma created SOLR-18311:
------------------------------------
Summary: SpellCheckCollator/PossibilityIterator:
spellcheck.maxCollationEvaluations truncation produces incomplete/order-biased
top-N collations instead of true lowest-rank combinations
Key: SOLR-18311
URL: https://issues.apache.org/jira/browse/SOLR-18311
Project: Solr
Issue Type: Bug
Components: spellchecker
Affects Versions: 9.6.1
Reporter: Puneet Sharma
{{PossibilityIterator}} generates every candidate collation for a multi-word
misspelled query as the Cartesian product of each word's per-token suggestion
list, then keeps only the best {{N}} ({{{}maxCollationTries{}}}, or
{{maxCollations}} when tries is unset) ranked by "sum of chosen suggestion
indices" (lower = better), via a bounded max-heap ({{{}PriorityQueue{}}} in
{{{}PossibilityIterator(...){}}},
solr/core/src/java/org/apache/solr/spelling/PossibilityIterator.java:93-133).
The candidates are generated by a mixed-radix "odometer"
({{{}internalNextAdvance(){}}}, PossibilityIterator.java:187-238): the _last_
misspelled word's suggestion index increments fastest, carrying into earlier
words only on wraparound. This means combinations are visited in lexicographic
index order, *not* in increasing rank order — rank is provably non-monotonic
across the visitation sequence (see repro below).
Enumeration is capped by {{spellcheck.maxCollationEvaluations}} (default 10000;
consumed at
solr/core/src/java/org/apache/solr/handler/component/SpellCheckComponent.java:307,
and enforced by the {{numEvaluations < maxEvaluations}} loop condition at
PossibilityIterator.java:100).
Because the odometer is not rank-ordered, this cap has two effects, one a pure
inefficiency and one an actual correctness gap:
# *Wasted work when the full product fits under the cap.* All combinations get
scored even though only the top {{maxCollationTries}} (e.g. the commonly-used
value 10) are ever kept. E.g. a 6-misspelled-word query with 5 suggestions/word
already generates 5^6 = 15,625 combinations, of which only 10 survive — 15,615
evaluations (and, for {{verifyCandidateWithQuery=true}} cases downstream in
{{{}SpellCheckCollator.collate(){}}}, up to {{maxCollationTries}} {_}actual
re-queries against the index{_}) are pure overhead that a rank-ordered
generator would avoid entirely.
# *Incomplete / order-biased results once the product exceeds the cap.* Since
the outer (first) misspelled word's index only advances after its _entire_
inner block is exhausted, hitting {{maxCollationEvaluations}} mid-walk means
later index values of the first misspelled word are _never visited at all_ —
regardless of how low their rank would have been. The resulting "top N"
therefore silently depends on which word happens to be enumerated first (i.e.
token position order in the suggestions map), not on true rank quality. This
means {{spellcheck.collate}} can return worse suggestions — or fail to find a
valid collation at all — than the data actually supports, purely as an artifact
of enumeration order, with no way for a caller to detect that this happened (no
partial-results flag, no log line at INFO level).
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
