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-05T16:11:39Z

Lists: pgsql-hackers

Attachments

v2-0001-Support-tuplesort_heap_build-in-tuplesort.c.patch (application/octet-stream)
v2-0002-Support-loser-tree-for-k-way-merge.patch (application/octet-stream)

Hi,

Can we support loser tree first and set the default value of enable_loser_tree to off?

Anyway, I attach 2 patches. (pass check-world)

v2-0001: support tuplesort_heap_build() which can build a valid heap in O(n), better
than currently O(n log n). This also make beginmerge() more clear and simple when
supporting loser tree.

v2-0002: support the loser tree.

--
Regards,
ChangAo Chen