Hi ChangAo, On Sat, Jan 3, 2026 at 11:46 AM Andreas Karlsson <[email protected]> wrote: > > 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.
I came across a paper written by Goetz Graefe [1] which describes the tree-of-losers priority queue model. I am not familiar with this topic, but it looks promising. If some of the techniques described there are desirable for Postgres, does it make sense to extract the loser tree as a standalone module like generic heap does? [1] https://dl.acm.org/doi/10.1145/3778176 -- Regards, Xuneng Zhou HighGo Software Co., Ltd.
