Re: POC: GROUP BY optimization

On Wed, Jun 6, 2018 at 8:06 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> >>> Comparison cost can be approximated probabilistically as:
> >>>
> >>> cost_comp = sum(cost_op_n * (1.0 / ndistinct(col_1_to_n)))
> >>>
> >>> Where cost_op_n is the cost of the comparison function for column N,
> >>> and ndistinct(col_1_to_n) is an estimation of the number of distinct
> >>> values for columns prior to N in the sort order.
> >>>
> >>> You can approximate ndistinct as the product of ndistinct of previous
> >>> columns, or use extended statistics when available.
> >>>
> >>
> >> Sure. The trouble is this also assumes uniform distribution, which is
> >> not always the case.
> >
> > Well, (1.0 / ndistinct) = p(left == right).
> >
> > If you can compute a better p(left == right) with an MCV, you can get
> > a better estimate. If you have an MCV. But that'd be a bit expensive,
> > and I'm not sure it's all that relevant.
> >
> > To what degree does improving this produce better plans? As long as
> > average expected cost is relatively well estimated (as in, one sort
> > order relative to another sort order), it won't affect the decision.
> >
>
> I'd bet I can construct corner-case examples with vastly different
> behavior depending on column data distributions, so it's not entirely
> insignificant. How important is it in practice I don't know.

I guess that can only be answered by building that solution and
testing it against the corner cases.