| From: | Andreas Karlsson <andreas(at)proxel(dot)se> |
|---|---|
| To: | cca5507 <cca5507(at)qq(dot)com>, John Naylor <johncnaylorls(at)gmail(dot)com> |
| Cc: | Sami Imseih <samimseih(at)gmail(dot)com>, 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: | 2026-01-03 03:46:49 |
| Message-ID: | 69012ece-1907-4d70-ac1a-db7897bac865@proxel.se |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On 12/8/25 7:46 AM, cca5507 wrote:
> For heap, it reduces one tuple comparison if the keys are same and increase one if not.
> For loser tree, it reduces many tuple comparisons (maybe tree's height - 1?) if the keys
> are same and increase one if not. The bad case is all keys are different, so we still need
> to decide when to use the fast path, it's hard I think.
My suggestion is that you start with trying to find some cases where we
get regressions and measure how big these regressions are and if there
are any clear cutoffs where we can use a simple heuristic to select
algorithm. One thought I have is that pre-sorted input could be slower
with loser than with heap but since I am unfamiliar with loser trees I
could be wrong.
Andreas
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Tristan Partin | 2026-01-03 04:35:27 | Re: [PATCH] meson: Update meson to enable building postgres as a subproject |
| Previous Message | Andreas Karlsson | 2026-01-03 03:12:39 | Re: Speed up ICU case conversion by using ucasemap_utf8To*() |