Horton

Re: Support loser tree for k-way merge

cca5507 <cca5507@qq.com>

View thread
From: cca5507 <cca5507@qq.com>
To: John Naylor <johncnaylorls@gmail.com>, Sami Imseih <samimseih@gmail.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Date: 2025-12-04T06:11:29Z
Lists: pgsql-hackers 
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?

--
Regards,
ChangAo Chen