Improve UNION's output rowcount estimate
I noticed that UNION's output rowcount estimate can be very wrong, as
the planner ignores the duplicate removal and just uses the total
input size. Here is an example:
create table t (x int);
insert into t select g % 50 from generate_series(1, 100000) g;
create table big (id int primary key, payload text);
insert into big select g, repeat('p', 20) from generate_series(1, 2000000) g;
analyze t, big;
set max_parallel_workers_per_gather = 0;
explain (analyze)
select b.id from big b
join (select x from t union select x from t) s
on s.x = b.id;
On master, the UNION is estimated at 200000 rows, while it actually
only has 50 rows. As a result, the planner chooses hash-join and
seqscan all of big.
-- master
-> HashAggregate (cost=4386.00..6386.00 rows=200000 width=4)
(actual time=62.052..62.526 rows=50.00 loops=1)
explain (costs off)
select b.id from big b
join (select x from t union select x from t) s
on s.x = b.id;
QUERY PLAN
-------------------------------------------
Hash Join
Hash Cond: (b.id = t.x)
-> Seq Scan on big b
-> Hash
-> HashAggregate
Group Key: t.x
-> Append
-> Seq Scan on t
-> Seq Scan on t t_1
(9 rows)
We can improve this rowcount by estimating the output as the sum of
the per-child distinct-group counts, which build_setop_child_paths()
already computes for us. Since
distinct(A union B) <= distinct(A) + distinct(B)
this is a safe upper bound, and it never exceeds the old estimate, so
it only tightens the previous over-estimate.
On patched, the UNION is estimated at 100 rows; still over-estimate,
but much better than the old estimate. And the planner ends up with
an index nested loop.
-- patched
-> HashAggregate (cost=4386.00..4387.00 rows=100 width=4)
(actual time=63.593..63.601 rows=50.00 loops=1)
explain (costs off)
select b.id from big b
join (select x from t union select x from t) s
on s.x = b.id;
QUERY PLAN
-----------------------------------------------
Nested Loop
-> HashAggregate
Group Key: t.x
-> Append
-> Seq Scan on t
-> Seq Scan on t t_1
-> Index Only Scan using big_pkey on big b
Index Cond: (id = t.x)
(8 rows)
Running this two plans, and here are what I got:
-- on master
Planning Time: 0.554 ms
Execution Time: 357.520 ms
-- on patched
Planning Time: 0.521 ms
Execution Time: 42.313 ms
This is about 8x faster.
Thoughts?
- Richard
Attachments:
v1-0001-Improve-UNION-s-output-row-count-estimate.patchapplication/octet-stream; name=v1-0001-Improve-UNION-s-output-row-count-estimate.patchDownload+54-12
On Sat, 20 Jun 2026 at 14:21, Richard Guo <guofenglinux@gmail.com> wrote:
I noticed that UNION's output rowcount estimate can be very wrong, as
the planner ignores the duplicate removal and just uses the total
input size.
I believe this should make the following code redundant, so shouldn't
the patch remove it too?
/*
* Estimate the number of UNION output rows. In the case when only a
* single UNION child remains, we can use estimate_num_groups() on
* that child. We must be careful not to do this when that child is
* the result of some other set operation as the targetlist will
* contain Vars with varno==0, which estimate_num_groups() wouldn't
* like.
*/
if (list_length(cheapest.subpaths) == 1 &&
first_path->parent->reloptkind != RELOPT_UPPER_REL)
{
dNumGroups = estimate_num_groups(root,
first_path->pathtarget->exprs,
first_path->rows,
NULL,
NULL);
}
Then you may as well pass dNumChildGroups directly to the path
creation functions and get rid of your new "With multiple children,"
comment.
Aside from that, I don't see any issues.
David
On Mon, Jun 22, 2026 at 9:39 AM David Rowley <dgrowleyml@gmail.com> wrote:
I believe this should make the following code redundant, so shouldn't
the patch remove it too?/*
* Estimate the number of UNION output rows. In the case when only a
* single UNION child remains, we can use estimate_num_groups() on
* that child. We must be careful not to do this when that child is
* the result of some other set operation as the targetlist will
* contain Vars with varno==0, which estimate_num_groups() wouldn't
* like.
*/
if (list_length(cheapest.subpaths) == 1 &&
first_path->parent->reloptkind != RELOPT_UPPER_REL)
{
dNumGroups = estimate_num_groups(root,
first_path->pathtarget->exprs,
first_path->rows,
NULL,
NULL);
}Then you may as well pass dNumChildGroups directly to the path
creation functions and get rid of your new "With multiple children,"
comment.Aside from that, I don't see any issues.
Thanks for looking. You're right. build_setop_child_paths() already
computes each child's distinct estimate, so for a single surviving
child dNumChildGroups is exactly what that branch recomputed.
(And removing it can be a slight improvement, as the old branch ran
estimate_num_groups on the subquery-scan Vars, while
build_setop_child_paths uses the child's own rowcount when it has
GROUP BY/DISTINCT/aggs.)
Patch updated.
- Richard
Attachments:
v2-0001-Improve-UNION-s-output-row-count-estimate.patchapplication/octet-stream; name=v2-0001-Improve-UNION-s-output-row-count-estimate.patchDownload+53-39
On Mon, 22 Jun 2026 at 14:59, Richard Guo <guofenglinux@gmail.com> wrote:
Patch updated.
Thanks. This one looks good.
David
Hi,
On Jun 22, 2026, at 10:59, Richard Guo <guofenglinux@gmail.com> wrote:
On Mon, Jun 22, 2026 at 9:39 AM David Rowley <dgrowleyml@gmail.com> wrote:
I believe this should make the following code redundant, so shouldn't
the patch remove it too?/*
* Estimate the number of UNION output rows. In the case when only a
* single UNION child remains, we can use estimate_num_groups() on
* that child. We must be careful not to do this when that child is
* the result of some other set operation as the targetlist will
* contain Vars with varno==0, which estimate_num_groups() wouldn't
* like.
*/
if (list_length(cheapest.subpaths) == 1 &&
first_path->parent->reloptkind != RELOPT_UPPER_REL)
{
dNumGroups = estimate_num_groups(root,
first_path->pathtarget->exprs,
first_path->rows,
NULL,
NULL);
}Then you may as well pass dNumChildGroups directly to the path
creation functions and get rid of your new "With multiple children,"
comment.Aside from that, I don't see any issues.
Thanks for looking. You're right. build_setop_child_paths() already
computes each child's distinct estimate, so for a single surviving
child dNumChildGroups is exactly what that branch recomputed.(And removing it can be a slight improvement, as the old branch ran
estimate_num_groups on the subquery-scan Vars, while
build_setop_child_paths uses the child's own rowcount when it has
GROUP BY/DISTINCT/aggs.)Patch updated.
- Richard
<v2-0001-Improve-UNION-s-output-row-count-estimate.patch>
Thanks for working on this. I agree this is a real problem, and
estimating UNION’s row count from the per-child distinct estimates looks
like the right direction to me.
I reviewed the v2 patch and it looks good. I also ran the regression
tests locally on my Apple Silicon machine, and they all passed.
The added regression test looks reasonable to me, since it checks the
plan change that motivated the patch. One small question: would it be
worth adding a direct row-estimate check, perhaps with a helper like
planner_est.sql’s explain_mask_costs() so that rows= stays visible while
cost/width are masked? The existing plan-shape test may already be
sufficient, though.
--
Best regards,
Chengpeng Yan
On Thu, Jun 25, 2026 at 12:12 PM Chengpeng Yan
<chengpeng_yan@outlook.com> wrote:
The added regression test looks reasonable to me, since it checks the
plan change that motivated the patch. One small question: would it be
worth adding a direct row-estimate check, perhaps with a helper like
planner_est.sql’s explain_mask_costs() so that rows= stays visible while
cost/width are masked? The existing plan-shape test may already be
sufficient, though.
I think the plan-shape test is sufficient here. I've committed this
patch to master. Thanks for all the reviews.
- Richard