Make segment merging parallel in SegmentMerger [LUCENE-8580]

[asfimport]

A placeholder issue stemming from the discussion on the mailing list [1]. Not of any high priority.

At the moment any merging from N segments into one will happen sequentially for each data structure involved in a segment (postings, norms, points, etc.). If the input segments are large, the CPU (and I/O) are mostly unused and the process takes a long time.

Merging of these data structures is mostly independent of each other, so it'd be interesting to see if we can speed things up by allowing them to run concurrently. I investigated this on a 40GB index with 22 segments, force-merging this into 1 segment (of similar size). Quick and dirty patch attached.

I see some improvement, although it's not by much; the largest component dominates everything else.

Results from an 8-core CPU.
Before:

SM 0 [2018-11-30T09:21:11.662Z; main]: 347237 msec to merge stored fields [41922110 docs]
SM 0 [2018-11-30T09:21:18.236Z; main]: 6562 msec to merge norms [41922110 docs]
SM 0 [2018-11-30T09:33:53.746Z; main]: 755507 msec to merge postings [41922110 docs]
SM 0 [2018-11-30T09:33:53.746Z; main]: 0 msec to merge doc values [41922110 docs]
SM 0 [2018-11-30T09:33:53.746Z; main]: 0 msec to merge points [41922110 docs]
SM 0 [2018-11-30T09:33:53.746Z; main]: 7 msec to write field infos [41922110 docs]

IW 0 [2018-11-30T09:33:56.124Z; main]: merge time 1112238 msec for 41922110 docs

After:

SM 0 [2018-11-30T10:16:42.179Z; ForkJoinPool.commonPool-worker-1]: 8189 msec to merge norms
SM 0 [2018-11-30T10:16:42.195Z; ForkJoinPool.commonPool-worker-3]: 0 msec to merge doc values
SM 0 [2018-11-30T10:16:42.195Z; ForkJoinPool.commonPool-worker-3]: 0 msec to merge points
SM 0 [2018-11-30T10:16:42.211Z; ForkJoinPool.commonPool-worker-1]: merge store matchedCount=22 vs 22
SM 0 [2018-11-30T10:23:24.574Z; ForkJoinPool.commonPool-worker-1]: 402381 msec to merge stored fields [41922110 docs]
SM 0 [2018-11-30T10:32:20.862Z; ForkJoinPool.commonPool-worker-2]: 938668 msec to merge postings

IW 0 [2018-11-30T10:32:23.513Z; main]: merge time  950249 msec for 41922110 docs

Ideally, one would need to push forkjoin into individual subroutines so that, for example, postings utilize concurrency when merging (pulling blocks of terms concurrently from the input, calculating statistics, etc. and then pushing in an ordered fashion to the codec).

[1] https://markmail.org/thread/dtejwq42qagykeac

---

Migrated from LUCENE-8580 by Dawid Weiss (@dweiss), updated Apr 26 2022
Attachments: LUCENE-8580.patch

[asfimport]

Dawid Weiss (@dweiss) (migrated from JIRA)

About time, eh?

[asfimport]

Vigya Sharma (@vigyasharma) (migrated from JIRA)

I started looking into this, and had some early questions... What would be the right benchmark to look at, for measuring any improvements here? Would it be the Indexing Throughput benchmark?

Should we add some benchmark specifically for merge related performance, like triggering a force merge? I suppose it wont be a measure of qps, but rather, the time to complete a merge on a given index? Do we have such benchmarks already?

Apologies if these are obvious things, I've only recently started looking at benchmarks. Will update here if I'm able to figure something out about these myself..

[asfimport]

Vigya Sharma (@vigyasharma) (migrated from JIRA)

I'm thinking of tackling this one data structure at a time, starting with postings.

Extending on the @dweiss's  patch, I was wondering if we could merge each field in parallel, in a separate fork-join task. I feel merging terms in parallel is tricky as we want to retain their sorted order, but going one level deeper, we could parallelize merging the postings within a term. Every ReaderSlice maps to a separate chunk of docIds in the target segment, so we could write postings for a term from each subreader in parallel.

For the fields part first, would it work to just spawn off multiple FieldsConsumer.write(...) calls in parallel, with different subsets of fields (maybe 1 field per task)?

TermsIndex has an FST per field and I see we go field by field while writing terms and merging their postings, which makes it look viable. I'm not yet clear on whether this will require writing to multiple (tim/tip/tmd/others?) files, and if that is a problem (whether we need to stitch them together which drains away all our concurrency gains, or if we can explore ways to work with multiple files).

I'll explore more on how the files get written. Want to check with the community for any pointers, if I'm on the right track here, and if there are some obvious wrinkles I should look at. 

[asfimport]

Michael Sokolov (@msokolov) (migrated from JIRA)

It seems we have generally stuck with one or a handful of files per format. Presumably we don't want to fragment into many small files in order to enable the OS to handle I/O more optimally? I think the key is not to impact search performance. But maybe start by writing many files in parallel just to see what is the best we can achieve for parallel merging with this approach and worry about connecting them together later? It shouldn't be hard to do the stitching, just block copies + rewriting the metadata?