I've just started using extended stats cause the planner was giving me terrible estimates for a certain table. MCV extended stats solved my problem when values are in the extended MCV list, but estimates are still terrible when they are not in the MCV list. Limited as my knowledge of database internals is, I dug into the source code and found an important difference on how these not-MCV values are handled in the single-column and multi-column cases.
For single columns, the estimate is calculated as follows:
selectivity = (1 - sum(MCV_frequencies)) / (distinct_values - count(MCV))
Which seems to assume a uniform distribution of non-MCV values and looks like a sensible guess, at least to my amateur eyes.
For multi-column statistics it seems to me that the estimate is calculated instead as:
selectivity = 1 - sum(MCV_frequencies)
Which instead seems to assume that the value could potentially be present in all the rows not covered by the MCV. This seems like an adequate upper bound, but is also quite conservative compared to the single-column estimate. In my specific case this yields a selectivity even higher than some of the least frequent MCV values, which is a condition that is actually checked for and compensated in the single-column estimate as an additional check. I have MCV and distinct extended stats, so I know the distinct_values stats is available.
So I hope my question is clear from the above. How come the estimates are calculated with such different approaches? I insist I have no experience with database/query planner development, so excuse me if I am overlooking some obvious conceptual difference between single-column and multi-column stats. The single-column estimate is actually described in the documentation, but the multi-column estimate is not. If there is indeed a good reason for this difference, I think it should be documented.
Thanks,
Pedro