Horton

Thread

Commits

  1. Improve UNION's output row count estimate

  1. Improve UNION's output rowcount estimate

    Richard Guo <guofenglinux@gmail.com> — 2026-06-20T02:21:10Z

    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

  2. Re: Improve UNION's output rowcount estimate

    David Rowley <dgrowleyml@gmail.com> — 2026-06-22T00:39:10Z

    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

  3. Re: Improve UNION's output rowcount estimate

    Richard Guo <guofenglinux@gmail.com> — 2026-06-22T02:59:30Z

    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

  4. Re: Improve UNION's output rowcount estimate

    David Rowley <dgrowleyml@gmail.com> — 2026-06-22T04:38:39Z

    On Mon, 22 Jun 2026 at 14:59, Richard Guo <guofenglinux@gmail.com> wrote:
> Patch updated.

Thanks. This one looks good.

David

  5. Re: Improve UNION's output rowcount estimate

    Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-06-25T03:12:13Z

    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

  6. Re: Improve UNION's output rowcount estimate

    Richard Guo <guofenglinux@gmail.com> — 2026-07-01T06:34:18Z

    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