On 12/8/25 7:46 AM, cca5507 wrote:
For heap, it reduces one tuple comparison if the keys are same and increase one if not. For loser tree, it reduces many tuple comparisons (maybe tree's height - 1?) if the keys are same and increase one if not. The bad case is all keys are different, so we still need to decide when to use the fast path, it's hard I think.
My suggestion is that you start with trying to find some cases where we get regressions and measure how big these regressions are and if there are any clear cutoffs where we can use a simple heuristic to select algorithm. One thought I have is that pre-sorted input could be slower with loser than with heap but since I am unfamiliar with loser trees I could be wrong.
Andreas
