| 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 |
| 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 |