public inbox for [email protected]  

help / color / mirror / Atom feed

From: John Naylor <[email protected]>
To: cca5507 <[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, 8 Dec 2025 10:20:27 +0700
Message-ID: <CANWCAZZ6KpsL+oEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg@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]>

On Thu, Dec 4, 2025 at 1:11 PM cca5507 <[email protected]> wrote:
> 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? If loser
tree can't early return, why is the number not always a constant?

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.

On Fri, Dec 5, 2025 at 11:11 PM cca5507 <[email protected]> wrote:
> Can we support loser tree first and set the default value of enable_loser_tree to off?

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)

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?

--
John Naylor
Amazon Web Services

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]
  Subject: Re: Support loser tree for k-way merge
  In-Reply-To: <CANWCAZZ6KpsL+oEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg@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