Remove Fields Order Checks from CheckIndex? [LUCENE-8924]

[asfimport]

CheckIndex checks the order of fields read from the FieldsEnum for the posting reader. Since we do not explicitly sort or use a sorted data structure to represent keys (atleast explicitly), and no FieldsEnum depends on the order apart from MultiFieldsEnum, which no longer exists.

 

Should we remove the check?

---

Migrated from LUCENE-8924 by Atri Sharma (@atris)

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

We rely on the order for merging, see "MultiFields".

[asfimport]

Atri Sharma (@atris) (migrated from JIRA)

I see. Should we make this more explicit and robust then? For E.g., since we do not explicitly maintain a sort order but rely on the key set to do the right thing, a change from Collections.unModifiableSet to Set.copyOf breaks this assertion in checkIndex (since Ser.copyOf explicitly calls out that there is no guarantee in the order of traversal)

[serhiy-bzhezytskyy]

The check cannot be removed — @jpountz's 2019 answer still holds. MultiFields is still there, still merging these iterators with MergedIterator, and PerFieldPostingsFormat#merge does the same.

But the follow-up question here was never answered:

Should we make this more explicit and robust then? For E.g., since we do not explicitly maintain a sort order but rely on the key set to do the right thing, a change from Collections.unModifiableSet to Set.copyOf breaks this assertion in checkIndex

#16475 is an attempt at it. Three things I found while looking:

The requirement is stated nowhere. Fields#iterator() documents only "Returns an iterator that will step through all fields names". FieldsConsumer#write has a Notes list of what an implementation must do and may assume, and does not mention order, although Lucene103BlockTreeTermsWriter relies on it and AssertingFieldsConsumer has asserted it since 2013. FieldsProducer says nothing either.

Nothing but CheckIndex detects a violation. MergedIterator documents "the behavior is undefined if the iterators are not actually sorted" rather than checking it, and the concrete effect is that deduplication stops working:

input	result
[a,b] + [a,c] — sorted	[a, b, c]
[b,a,c] + [a,z] — one unsorted	[a, b, a, c, z] — a twice, from two different sub-iterators

The comment on the check points at a class that was deleted. CheckIndex says // MultiFieldsEnum relies upon this order...; MultiFieldsEnum was removed in 80811d02f5b. The check is justified by MultiFields, but anyone auditing it is sent to a class that is not there — which is plausibly how this issue came to be filed.

On the Set.copyOf concern specifically: all thirteen Fields implementations in the repository honour the order today, but by four different means — a TreeMap in four of them, an explicit sort on the way out in two, and in FreqProxFields a LinkedHashMap with a comment relying on the caller having sorted first. None of those is protected by anything, so the concern is real; the PR adds the assertion to the asserting codec so any codec the test suite exercises fails at the violation rather than in CheckIndex afterwards.

This issue can be closed as "won't remove" whenever that suits — the documentation and the assertion stand on their own either way.