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
v1-0001-Support-loser-tree-for-k-way-merge.patch
Description: Binary data
