Motivation

In Paimon's SortMergeReader, the multiple RecordReader will be used and the same key will be merged using MergeFunction. Essentially, this process is to perform multi-way merging on the value of RecordReader, which is implemented by default in Paimon using heapsort, and the number of comparisons for each adjustment of the heap is 2logN. LoserTree is also mainly used for multi-way merging. Compared with heap sorting, each comparison only needs to be compared with the parent node, while the heapsort needs to be compared with the two child nodes. The number of comparisons of LoserTree(logN) is less than that of heapsort, so LoserTree can be considered for optimization.

...