Re: Support loser tree for k-way merge

From: cca5507 <cca5507(at)qq(dot)com>
To: John Naylor <johncnaylorls(at)gmail(dot)com>, Sami Imseih <samimseih(at)gmail(dot)com>
Cc: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Re: Support loser tree for k-way merge
Date: 2025-12-04 06:11:29
Message-ID: tencent_BCDD766860E1776D510A9F8C331EECC18306@qq.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
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

In response to

Browse pgsql-hackers by date

  From Date Subject
Previous Message shveta malik 2025-12-04 06:03:50 Re: Improve pg_sync_replication_slots() to wait for primary to advance