public inbox for [email protected]  

help / color / mirror / Atom feed
From: Xuneng Zhou <[email protected]>
To: cca5507 <[email protected]>
To: Andreas Karlsson <[email protected]>
Cc: John Naylor <[email protected]>
Cc: Sami Imseih <[email protected]>
Cc: Heikki Linnakangas <[email protected]>
Cc: pgsql-hackers <[email protected]>
Subject: Re: Support loser tree for k-way merge
Date: Mon, 25 May 2026 18:01:15 +0800
Message-ID: <CABPTF7WRcm=y-2dRs-vK3SLyCVyxLvUyTDQ-9+-OLoBYAwG+=Q@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<CAA5RZ0u=WDa-v+8Y_yE4WeRS8VtmcmQGuWVjZFCqZcXx-hEP3w@mail.gmail.com>
	<CANWCAZYKgc4xFbBXtePw_XY+a+Ao_-CxZ+Z8YWSrK2B1HqtdWg@mail.gmail.com>
	<[email protected]>
	<[email protected]>
	<CANWCAZZ6KpsL+oEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg@mail.gmail.com>
	<[email protected]>
	<[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.






reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
  Subject: Re: Support loser tree for k-way merge
  In-Reply-To: <CABPTF7WRcm=y-2dRs-vK3SLyCVyxLvUyTDQ-9+-OLoBYAwG+=Q@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox