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>
 <CANWCAZZ6KpsL+oEJFyQxqMMNv7FHRxPqUGafn9sqJzg_BmH5Qg@mail.gmail.com>
 <tencent_5A80D26E2054B9D0B4563C854CA61CAFEB05@qq.com>
 <69012ece-1907-4d70-ac1a-db7897bac865@proxel.se>
In-Reply-To: <69012ece-1907-4d70-ac1a-db7897bac865@proxel.se>
From: Xuneng Zhou <xunengzhou@gmail.com>
Date: Mon, 25 May 2026 18:01:15 +0800
Message-ID: 
 <CABPTF7WRcm=y-2dRs-vK3SLyCVyxLvUyTDQ-9+-OLoBYAwG+=Q@mail.gmail.com>
Subject: Re: Support loser tree for k-way merge
To: cca5507 <cca5507@qq.com>, Andreas Karlsson <andreas@proxel.se>
Cc: John Naylor <johncnaylorls@gmail.com>, 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/CABPTF7WRcm%3Dy-2dRs-vK3SLyCVyxLvUyTDQ-9%2B-OLoBYAwG%2B%3DQ%40mail.gmail.com>
Precedence: bulk

Hi ChangAo,

On Sat, Jan 3, 2026 at 11:46=E2=80=AFAM Andreas Karlsson <andreas@proxel.se=
> wrote:
>
> On 12/8/25 7:46 AM, cca5507 wrote:
> > For heap, it reduces one tuple comparison if the keys are same and incr=
ease 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 differen=
t, 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

--=20
Regards,
Xuneng Zhou
HighGo Software Co., Ltd.