MIME-Version: 1.0
References: <tencent_901D6A0152786410F0E00E72EC38432D0A09@qq.com>
 <28f47336-84e2-445e-8216-d1ce7d3ddc3e@iki.fi>
 <tencent_DCD98184361486D41AA430C8B0E0691D740A@qq.com>
 <tencent_E80D0FFA80C2AE21D4ABB0A7163EC54B0605@qq.com>
 <CAA5RZ0u=WDa-v+8Y_yE4WeRS8VtmcmQGuWVjZFCqZcXx-hEP3w@mail.gmail.com>
 <CANWCAZYKgc4xFbBXtePw_XY+a+Ao_-CxZ+Z8YWSrK2B1HqtdWg@mail.gmail.com>
 <tencent_BCDD766860E1776D510A9F8C331EECC18306@qq.com>
 <tencent_A7644AF1100E34EC9E428D0A976A6F524609@qq.com>
In-Reply-To: <tencent_A7644AF1100E34EC9E428D0A976A6F524609@qq.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Mon, 8 Dec 2025 10:20:27 +0700
Message-ID: 
 <CANWCAZZ6KpsL+oEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg@mail.gmail.com>
Subject: Re: Support loser tree for k-way merge
To: cca5507 <cca5507@qq.com>
Cc: Sami Imseih <samimseih@gmail.com>, Heikki Linnakangas <hlinnaka@iki.fi>,
	pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CANWCAZZ6KpsL%2BoEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg%40mail.gmail.com>
Precedence: bulk

On Thu, Dec 4, 2025 at 1:11=E2=80=AFPM cca5507 <cca5507@qq.com> wrote:
> I summarized the number of comparisons needed for different 'k':
>
> k =3D 2, heap: 1, loser tree: 1
> k =3D 3, heap: 2, loser tree: [1, 2]
> k =3D 4, heap: [2, 3], loser tree: 2
> k =3D 5, heap: [2, 4], loser tree: [2, 3]
>
> So if k < 5, the loser tree is never worse than the heap for any input da=
ta.

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=E2=80=AFPM cca5507 <cca5507@qq.com> 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