Support loser tree for k-way merge

From: cca5507 <cca5507(at)qq(dot)com>
To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Support loser tree for k-way merge
Date: 2025-12-03 11:48:10
Message-ID: tencent_901D6A0152786410F0E00E72EC38432D0A09@qq.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi hackers,

Background
==========
Now we use 'heap' during the k-way merge, it's O(n log k). The 'loser tree' is also O(n log k), but
it's usually has fewer comparisons than the 'heap'. When the tuple comparator is complex, the
'loser tree' can significantly speed up the k-way merge.

Test
====
With the WIP patch(v1-0001), I got a 3% ~ 13%(different work_mem) speed up in the following test case:

SET max_parallel_workers_per_gather = 0;
CREATE UNLOGGED TABLE t AS SELECT generate_series(1, 20000000) AS a, md5(random()::text) AS b;
create extension if not exists pg_prewarm;
select pg_prewarm('t');

SET enable_loser_tree = OFF;
# SET work_mem = '4MB'; ('8MB' '16MB' '32MB' '64MB' ...)
explain analyze select * from t order by b;

SET enable_loser_tree = ON;
# SET work_mem = '4MB'; ('8MB' '16MB' '32MB' '64MB' ...)
explain analyze select * from t order by b;

Open questions
==============
1) Now I add a GUC 'enable_loser_tree' to control the use of loser tree, maybe we should
decide whether to use the 'loser tree' based on the value of 'k', the complexity of tuple
comparators or just always use the 'loser tree'?

Looking forward to your reply and comment.

--
Regards,
ChangAo Chen

Attachment Content-Type Size
v1-0001-Support-loser-tree-for-k-way-merge.patch application/octet-stream 7.8 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message VASUKI M 2025-12-03 11:59:33 Re: BUG #19095: Test if function exit() is used fail when linked static
Previous Message Ashutosh Bapat 2025-12-03 11:30:49 Re: [PATCH] Add enable_copy_program GUC to control COPY PROGRAM