public inbox for [email protected]
help / color / mirror / Atom feedRe: Support loser tree for k-way merge
2+ messages / 2 participants
[nested] [flat]
* Re: Support loser tree for k-way merge
@ 2026-01-03 03:46 Andreas Karlsson <[email protected]>
2026-05-25 10:01 ` Re: Support loser tree for k-way merge Xuneng Zhou <[email protected]>
0 siblings, 1 reply; 2+ messages in thread
From: Andreas Karlsson @ 2026-01-03 03:46 UTC (permalink / raw)
To: cca5507 <[email protected]>; John Naylor <[email protected]>; +Cc: Sami Imseih <[email protected]>; Heikki Linnakangas <[email protected]>; pgsql-hackers <[email protected]>
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
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: Support loser tree for k-way merge
2026-01-03 03:46 Re: Support loser tree for k-way merge Andreas Karlsson <[email protected]>
@ 2026-05-25 10:01 ` Xuneng Zhou <[email protected]>
0 siblings, 0 replies; 2+ messages in thread
From: Xuneng Zhou @ 2026-05-25 10:01 UTC (permalink / raw)
To: cca5507 <[email protected]>; Andreas Karlsson <[email protected]>; +Cc: John Naylor <[email protected]>; Sami Imseih <[email protected]>; Heikki Linnakangas <[email protected]>; pgsql-hackers <[email protected]>
Hi ChangAo,
On Sat, Jan 3, 2026 at 11:46 AM Andreas Karlsson <[email protected]> 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.
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2026-05-25 10:01 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-01-03 03:46 Re: Support loser tree for k-way merge Andreas Karlsson <[email protected]>
2026-05-25 10:01 ` Xuneng Zhou <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox