Thread

Re: Support loser tree for k-way merge

Xuneng Zhou <xunengzhou@gmail.com> — 2026-05-25T10:01:15Z

Hi ChangAo,

On Sat, Jan 3, 2026 at 11:46 AM Andreas Karlsson <andreas@proxel.se> wrote:
>
> 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.

I came across a paper written by Goetz Graefe [1] which describes the
tree-of-losers priority queue model. I am not familiar with this
topic, but it looks promising. If some of the techniques described
there are desirable for Postgres, does it make sense to extract the
loser tree as a standalone module like generic heap does?

[1] https://dl.acm.org/doi/10.1145/3778176

-- 
Regards,
Xuneng Zhou
HighGo Software Co., Ltd.