Request a Demo
Home   >   mailing lists

Re: Support loser tree for k-way merge - Mailing list pgsql-hackers

From cca5507
Subject Re: Support loser tree for k-way merge
Date
Msg-id tencent_BCDD766860E1776D510A9F8C331EECC18306@qq.com
Whole thread Raw
In response to Re: Support loser tree for k-way merge  (John Naylor <johncnaylorls@gmail.com>)
Responses Re: Support loser tree for k-way merge
List pgsql-hackers
Tree view 
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

pgsql-hackers by date:

Previous
From: shveta malik
Date:
Subject: Re: Improve pg_sync_replication_slots() to wait for primary to advance
Next
From: Amit Kapila
Date:
Subject: Re: Simplify code building the LR conflict messages