When a query requires statistics on the result of a UNION or UNION ALL operation, create needed statistics uniformly on all UNION or UNION ALL inputs.  It is not sufficient to create statistics on a subset of the UNION or UNION ALL inputs, even when those inputs are dominant.  For example,

SELECT * FROM Lineitem l WHERE EXISTS

( SELECT * FROM Region1 r1 WHERE r1.C = l.C and r1.S = l.S

UNION SELECT * FROM Region2 r2 WHERE r2.C = l.C and r2.S = l.S )

In order for the EXISTS to be optimized accurately, it may be necessary to have a multi-column statistic on columns C and S in for Lineitem, Region1 and Region2.  If the multi-column statistic does not exist in either Region1 or Region2 then the remaining statistics cannot be used to optimize this query.