public inbox for [email protected]  

help / color / mirror / Atom feed

From: Andreas Karlsson <[email protected]>
To: cca5507 <[email protected]>
To: 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: Sat, 3 Jan 2026 04:46:49 +0100
Message-ID: <[email protected]> (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]>

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

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]
  Subject: Re: Support loser tree for k-way merge
  In-Reply-To: <[email protected]>

* 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