Message-ID: <69012ece-1907-4d70-ac1a-db7897bac865@proxel.se>
Date: Sat, 3 Jan 2026 04:46:49 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Support loser tree for k-way merge
To: cca5507 <cca5507@qq.com>, John Naylor <johncnaylorls@gmail.com>
Cc: Sami Imseih <samimseih@gmail.com>, Heikki Linnakangas <hlinnaka@iki.fi>,
 pgsql-hackers <pgsql-hackers@lists.postgresql.org>
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>
From: Andreas Karlsson <andreas@proxel.se>
Content-Language: en-US
In-Reply-To: <tencent_5A80D26E2054B9D0B4563C854CA61CAFEB05@qq.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: <https://www.postgresql.org/message-id/69012ece-1907-4d70-ac1a-db7897bac865%40proxel.se>
Precedence: bulk

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