pgsql: Improve UNION's output row count estimate

Improve UNION's output row count estimate

A UNION (not UNION ALL) removes duplicates, so its output has no more
rows than its input. The planner did not account for this: it set the
set-op relation's row count to the total size of the appended input,
as though dedup removed nothing. That inflated estimate then
propagated to every node above the UNION, leading to poor plan choices
such as a hash join with a full table scan where an index nested loop
would have been cheaper.

This patch estimates the number of distinct output rows as the sum of
the per-child distinct-group estimates instead. This relies on the
fact that:

distinct(A union B) <= distinct(A) + distinct(B)

that is, the union cannot have more distinct rows than its children do
in total. And because each child's distinct-group estimate never
exceeds that child's row-count estimate, this sum is never larger than
the old estimate, so it only tightens the previous over-estimate.

Author: Richard Guo <guofenglinux(at)gmail(dot)com>
Reviewed-by: David Rowley <dgrowleyml(at)gmail(dot)com>
Reviewed-by: Chengpeng Yan <chengpeng_yan(at)outlook(dot)com>
Discussion: https://postgr.es/m/CAMbWs48Fu1nhGXPa60oc+adj7ge4dn0nHhqngqKvOVVQP61duA@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/be69a5ff1fd96cdbfe917ac4739142e52aab126e

Modified Files
--------------
src/backend/optimizer/prep/prepunion.c | 68 +++++++++++++++-------------------
src/test/regress/expected/union.out | 17 +++++++++
src/test/regress/sql/union.sql | 6 +++
3 files changed, 53 insertions(+), 38 deletions(-)