Hi,
I summarized the number of comparisons needed for different 'k':
k = 2, heap: 1, loser tree: 1
k = 3, heap: 2, loser tree: [1, 2]
k = 4, heap: [2, 3], loser tree: 2
k = 5, heap: [2, 4], loser tree: [2, 3]
So if k < 5, the loser tree is never worse than the heap for any input data.
Thoughts
On Thu, Dec 4, 2025 at 1:14 AM Sami Imseih wrote:
> Can we drive the decision for what to do based on optimizer
> stats, i.e. n_distinct and row counts? Not sure what the calculation would
> be specifically, but something else to consider.
It's happened multiple times before that someone proposes
Hi,
Thank you for your reply.
> Can we drive the decision for what to do based on optimizer
> stats, i.e. n_distinct and row counts? Not sure what the calculation would
> be specifically, but something else to consider.
>
> We can still provide the GUC to override the optimizer decisions,
> but
Hi,
Thanks for raising this.
> 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.
I wa
> So on specific data, the heap may be better than the loser tree. But I think
> the possibility
> is very small.
For example, a column contains all the same values, so the heap can always
early return
when replacing top.
--
Regards,
ChangAo Chen
Hi Heikki,
> What is the worst case scenario for the loser tree, where the heap is
> faster? How big is the difference?
In tuplesort_heap_replace_top(), it has 2 comparisons each level, but it can
early return
if the parent less than both child.
In tuplesort_loser_tree_adjust(), it has 1 compa
On 03/12/2025 13:48, cca5507 wrote:
With the WIP patch(v1-0001), I got a 3% ~ 13%(different work_mem) speed up in
the following test case:
Nice speedup!
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 t
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
