Re: Support loser tree for k-way merge

> 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?

The "k" is "k-way merge", and the "comparisons" are the number of tuple comparisons
during one heap's sift down or loser tree's adjustment.

> If loser tree can't early return, why is the number not always a constant?

Because the leaf nodes are in the bottom two levels of the loser tree, and different levels
have different number of comparisons.

> 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.

Yeah, the loser tree at most reduce one tuple comparison in each adjustment if k < 5.

> 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)

Yeah, users may have no ideas about the characteristics of their data, so it's hard for them
to choose the setting.

> 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?

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.

--
Regards,
ChangAo Chen