MIME-Version: 1.0
References: <tencent_901D6A0152786410F0E00E72EC38432D0A09@qq.com>
 <28f47336-84e2-445e-8216-d1ce7d3ddc3e@iki.fi>
 <tencent_DCD98184361486D41AA430C8B0E0691D740A@qq.com>
 <tencent_E80D0FFA80C2AE21D4ABB0A7163EC54B0605@qq.com>
In-Reply-To: <tencent_E80D0FFA80C2AE21D4ABB0A7163EC54B0605@qq.com>
From: Sami Imseih <samimseih@gmail.com>
Date: Wed, 3 Dec 2025 12:14:25 -0600
Message-ID: 
 <CAA5RZ0u=WDa-v+8Y_yE4WeRS8VtmcmQGuWVjZFCqZcXx-hEP3w@mail.gmail.com>
Subject: Re: Support loser tree for k-way merge
To: cca5507 <cca5507@qq.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>,
 pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: 
 <https://www.postgresql.org/message-id/CAA5RZ0u%3DWDa-v%2B8Y_yE4WeRS8VtmcmQGuWVjZFCqZcXx-hEP3w%40mail.gmail.com>
Precedence: bulk

Hi,

Thanks for raising this.

> Now we use 'heap' during the k-way merge, it's O(n log k). The 'loser tree' is also O(n log k), but
> it's usually has fewer comparisons than the 'heap'. When the tuple comparator is complex, the
> 'loser tree' can significantly speed up the k-way merge.

I was playing around with this and I do also see the performance
benefits that you
mention with loser tree.

```
DROP TABLE IF EXISTS t;
CREATE TABLE t (
    col1 INT,
    col2 INT
);


INSERT INTO t (col1, col2)
SELECT
    (i % 10000000),
    (i % 100)
FROM generate_series(1, 10000000) AS s(i);
```

Using something like the above, testing an "external merge" on the
high cardinality
column there is a bit of an improvement with loser tree, but there is
a bit of a loss on
low-cardinality.

In general though, I see a bit of an issue with allowing a GUC to
change strategies. What happens if there are multiple "external merge"
nodes and they can each benefit from different strategies? Maybe that's
not an issue since all the other enable_ GUCs have that problem, but
it is something to consider.

Can we drive the decision for what to do based on optimizer
stats, i.e. n_distinct and row counts? Not sure what the calculation would
be specifically, but something else to consider.

We can still provide the GUC to  override the optimizer decisions,
but at least the optimizer, given up-to-date stats, may get it right most
of the time.

--
Sami Imseih
Amazon Web Services (AWS)