Thread: Re: [pgsql-hackers] Group-count estimation statistics

Re: [pgsql-hackers] Group-count estimation statistics

From
Josh Berkus
Date:
Tom,

> The only real solution, of course, is to acquire cross-column
> statistics, but I don't see that happening in the near future.

Y'know, that's been on the todo list for a while.   Surely someone is inspired
for 8.1/8.2?   At least for columns which are indexed together?

> As a short-term hack, I am thinking that the "clamp to size of table"
> part of the rule is overly pessimistic, and that we should consider
> something like "clamp to size of table / 10" instead.  The justification
> for this is the thought that you aren't going to bother grouping unless
> it actually reduces the data volume.  We have used similar rules in the
> past --- for example, before the logic for trying to estimate actual
> group counts was put in, the estimate for the number of output rows
> from an Agg or Group node was just the number of input rows over 10.

Why 10?   I'd think we could come up with a slightly less arbitrary number,
based on "At what point does the median possible cost of estmating too low
equal the median possible cost of estimating too high?"  This seems
calculable based on the other information available ...

... although perhaps not without a math PhD.  Surely there's one in the house?

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco


Re: [pgsql-hackers] Group-count estimation statistics

From
Tom Lane
Date:
Josh Berkus <josh@agliodbs.com> writes:
> Why 10?   I'd think we could come up with a slightly less arbitrary number, 

Well, it's probably within an order of magnitude of the right thing ;-).
We know we don't want 1, but 100 seems awfully optimistic.

If someone can come up with a more defensible number then I'm all for
it.  Greg Stark's thought about a power correction seemed interesting
too, though again far too optimistic to trust without some good math
to back it up.
        regards, tom lane


Re: Group-count estimation statistics

From
Greg Stark
Date:
Tom Lane <tgl@sss.pgh.pa.us> writes:

> Greg Stark's thought about a power correction seemed interesting too, though
> again far too optimistic to trust without some good math to back it up.

Fwiw, I'm pretty sure good math is not going to back up my off-the-cuff
algorithm. But I did like the answer it gave in this instance.

I'm told an actual solution to the problem is hard and probably not even
solvable in closed form. I'm still looking around but I suspect we would need
some pretty severe simplifying assumptions to make it work.

-- 
greg