zhoulii opened a new issue, #9302: URL: https://github.com/apache/paimon/issues/9302
### Search before asking - [x] I searched in the [issues](https://github.com/apache/paimon/issues) and found nothing similar. ### Motivation BinaryExternalSortBuffer merges spilled files incrementally during write() and re-adds the merged output back into the spill list (spillChannelIDs.addAll(merged)). Since the merged (large) files are then re-merged together with subsequently spilled files in the next round, already-merged data gets rewritten repeatedly. This cascading re-merge degrades merge IO from the intended O(N·log N) to O(N^2). ### Solution Move the merge out of write() and perform it once in spilledIterator(), before opening any readers. After spilling is finished, merge the sorted runs down to the fan-in limit: while (spillChannelIDs.size() > maxNumFileHandles) { List<ChannelWithMeta> merged = merger.mergeChannelList(spillChannelIDs); spillChannelIDs.clear(); spillChannelIDs.addAll(merged); } This mirrors Flink's SpillingThread#mergeOnDisk (while (channels > maxFanIn) channels = mergeChannelList(channels)) — the final-merge pattern used by Flink/Stratosphere since 2010, now restored without introducing any new algorithm. Because merging runs strictly after writing, each mergeChannelList only reduces the file count, so no data is merged more than once. Total merge IO returns to O(N·log N), while the peak number of open file handles stays bounded by maxNumFileHandles (each merge round opens at most maxFanIn readers, freed in finally). Note: a while (not a one-shot if) is required here. A single mergeChannelList call brings N files down to <= F only when N <= F^2; once N > F^2 one call leaves F^2 files still exceeding the limit, and a one-shot if would let getMergingIterator open far more than F handles (Too many open files). A regression test, testNoCascadingMergeAtFinalIterator, asserts both that no merge happens during write() (spill count stays above F^2) and that the final fan-in is capped at F. ### Anything else? _No response_ ### Are you willing to submit a PR? - [x] I'm willing to submit a PR! -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
