Corruption read on term dictionaries in Lucene 9.9

[benwtrent]

Description

It seems that #12699 has inadvertantly broken reading term dictionaries created in Lucene 9.8<=.

To replicate a bug, one can index wikibigall with LuceneUtil & Lucene 9.8 & force-merge.

Then attempt to read the created index using a wildcard query:

    Path path = Paths.get("/data/local/lucene/indices/wikibigall.lucene-main.opt.Lucene90.dvfields.nd6.72652M/index");
    try (FSDirectory dir = FSDirectory.open(path);
        DirectoryReader reader = DirectoryReader.open(dir)) {
      IndexSearcher searcher = new IndexSearcher(reader); 
      searcher.count(new WildcardQuery(new Term("body", "*fo*")));
    }

This will result in a trace similar to below:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
	at org.apache.lucene.store.ByteArrayDataInput.readByte(ByteArrayDataInput.java:136)
	at org.apache.lucene.store.DataInput.readVInt(DataInput.java:110)
	at org.apache.lucene.store.ByteArrayDataInput.readVInt(ByteArrayDataInput.java:114)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.load(IntersectTermsEnumFrame.java:158)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.load(IntersectTermsEnumFrame.java:149)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.pushFrame(IntersectTermsEnum.java:203)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum._next(IntersectTermsEnum.java:531)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.next(IntersectTermsEnum.java:373)
	at org.apache.lucene.search.MultiTermQueryConstantScoreBlendedWrapper$1.rewriteInner(MultiTermQueryConstantScoreBlendedWrapper.java:111)
	at org.apache.lucene.search.AbstractMultiTermQueryConstantScoreWrapper$RewritingWeight.rewrite(AbstractMultiTermQueryConstantScoreWrapper.java:179)
	at org.apache.lucene.search.AbstractMultiTermQueryConstantScoreWrapper$RewritingWeight.bulkScorer(AbstractMultiTermQueryConstantScoreWrapper.java:220)
	at org.apache.lucene.search.LRUQueryCache$CachingWrapperWeight.bulkScorer(LRUQueryCache.java:930)
	at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:678)
	at org.apache.lucene.search.IndexSearcher.lambda$4(IndexSearcher.java:636)
	at org.apache.lucene.search.TaskExecutor$TaskGroup.lambda$0(TaskExecutor.java:118)
	at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:317)
	at org.apache.lucene.search.TaskExecutor$TaskGroup.invokeAll(TaskExecutor.java:153)
	at org.apache.lucene.search.TaskExecutor.invokeAll(TaskExecutor.java:76)
	at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:640)
	at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:607)
	at org.apache.lucene.search.IndexSearcher.count(IndexSearcher.java:423)
	at Corruption.main(Corruption.java:18)

We are currently not sure if this effects Lucene 9.9 created indices & reading via Lucene 9.9.

EDIT: This failure does NOT occur for indices created by 9.9 and read by 9.9.

NOTE: This also fails with just a prefix wildcard query. It seems to be all multi-term queries could be affected.

Will provide more example stack traces in issue comments.

Version and environment details

Lucene 9.9 reading Lucene 9.8 indices.

[benwtrent]

//cc @gf2121 && @mikemccand

[benwtrent]

Here are some exceptions ran into when trying to do multi-term queries with Lucene 9.9 against an index created in 9.8 or before:

Caused by: java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
	at org.apache.lucene.store.ByteArrayDataInput.readVInt(ByteArrayDataInput.java:112)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.load(IntersectTermsEnumFrame.java:158)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.load(IntersectTermsEnumFrame.java:149)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.pushFrame(IntersectTermsEnum.java:203)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum._next(IntersectTermsEnum.java:531)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.next(IntersectTermsEnum.java:373)
	at org.apache.lucene.index.FilterLeafReader$FilterTermsEnum.next(FilterLeafReader.java:201)

Caused by: org.apache.lucene.index.CorruptIndexException: Illegal code for a compression algorithm: 3 (resource=SearchIndexInput{[(clone of) _3e4i_Lucene90_0.tim], context=IOContext [context=READ, mergeInfo=null, flushInfo=null, readOnce=false], cacheFile=SharedCacheFile{cacheKey=FileCacheKey[shardId=[.ds-logs-endpoint.events.file-default-2023.11.22-000002][0], primaryTerm=3, fileName=stateless_commit_61353], length=3174808501}, length=308358826, offset=181596})
	at org.apache.lucene.core@9.9.0/org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.load(IntersectTermsEnumFrame.java:196)
	at org.apache.lucene.core@9.9.0/org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnumFrame.loadNextFloorBlock(IntersectTermsEnumFrame.java:119)
	at org.apache.lucene.core@9.9.0/org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.popPushNext(IntersectTermsEnum.java:339)
	at org.apache.lucene.core@9.9.0/org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum._next(IntersectTermsEnum.java:543)
	at org.apache.lucene.core@9.9.0/org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.next(IntersectTermsEnum.java:373)
	at org.apache.lucene.core@9.9.0/org.apache.lucene.index.FilterLeafReader$FilterTermsEnum.next(FilterLeafReader.java:201)

Caused by: java.lang.NullPointerException: Cannot invoke "org.apache.lucene.util.fst.FST$Arc.output()" because "arc" is null
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.pushFrame(IntersectTermsEnum.java:196)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum._next(IntersectTermsEnum.java:531)
	at org.apache.lucene.codecs.lucene90.blocktree.IntersectTermsEnum.next(IntersectTermsEnum.java:373)
	at org.apache.lucene.index.FilterLeafReader$FilterTermsEnum.next(FilterLeafReader.java:201)

Still digging into this to figure out why reading is now corrupted. #12699 has many subtle changes, including a very big one where we don't copy the byte arrays any longer.

[benwtrent]

Possibly related: #12631

NOTE: the read corruption doesn't occur when reading from an index created in 9.9.

[benwtrent]

Git bisect has confirmed the read corruption occurs with: #12699

[mikemccand]

Ugh -- I'll try to look at this later today. Disappointing that our back compat test specifically for reading 9.8 indices failed to catch this.

[mikemccand]

It's also curious that it's not happening w/ 9.9 created indices. #12699 is about optimizing how we accumulate the long output while traversing (reading) the FST block tree terms index.

[benwtrent]

@mikemccand I have to use at a minimum: wikibig1m for it to replicate.

Couple of weird things I noticed in that optimization PR:

• https://github.com/apache/lucene/pull/12699/files#diff-c30add12e4170e7905cdb0912fd869d447b5b1772d74c9fcaf0afe41cd58866aL200-R204 Now instead of giving a complete view of all appended arcs, there is this weird assumption that we only give one to floorDataReader
• https://github.com/apache/lucene/pull/12699/files#diff-c30add12e4170e7905cdb0912fd869d447b5b1772d74c9fcaf0afe41cd58866aR200-L202. The frame outputPrefix is then set as the accumulation of all the arc outputs. I am not sure if this is relevant as for it to be important getFrame would have to return a frame already seen before, I am not sure if that is valid or not.

This makes me think that each frame should have its own OutputAccumulator But all this code seems incredibly subtle and opaque to me. Been staring at it for hours now :)