Re: Support loser tree for k-way merge

On Thu, Dec 4, 2025 at 1:11 PM cca5507 <cca5507(at)qq(dot)com> wrote:
> I summarized the number of comparisons needed for different 'k':
>
> k = 2, heap: 1, loser tree: 1
> k = 3, heap: 2, loser tree: [1, 2]
> k = 4, heap: [2, 3], loser tree: 2
> k = 5, heap: [2, 4], loser tree: [2, 3]
>
> So if k < 5, the loser tree is never worse than the heap for any input data.

Please explain your notation. For starters, does "comparison" refer to
sortkey comparison or does it include checking for sentinel? If loser
tree can't early return, why is the number not always a constant?

If "k" is very small, I'm guessing the merge step is small compared to
sorting the individual runs, in which case it matters less which one
to use. That's just a guess, though -- we need structured testing.

On Fri, Dec 5, 2025 at 11:11 PM cca5507 <cca5507(at)qq(dot)com> wrote:
> Can we support loser tree first and set the default value of enable_loser_tree to off?

If you, the patch author, cannot demonstrate how to choose this
setting, what makes you think our users can? (That said, a temporary
GUC is useful for testing)

Here's a half-baked idea: If the regressions are mostly in
low-cardinality inputs, is it possible to add a fast path that just
checks if the current key is the same as the last one?

--
John Naylor
Amazon Web Services