Re: proposal : cross-column stats

Dne 12.12.2010 17:33, Florian Pflug napsal(a):
> On Dec12, 2010, at 15:43 , Heikki Linnakangas wrote:
>> The way I think of that problem is that once you know the postcode, knowing the city name doesn't add any information. The postcode implies the city name. So the selectivity for "postcode = ? AND city = ?" should be the selectivity of "postcode = ?" alone. The measurement we need is "implicativeness": How strongly does column A imply a certain value for column B. Perhaps that could be measured by counting the number of distinct values of column B for each value of column A, or something like that. I don't know what the statisticians call that property, or if there's some existing theory on how to measure that from a sample.
>
> The statistical term for this is "conditional probability", written P(A|B), meaning the probability of A under the assumption or knowledge of B. The basic tool for working with conditional probabilities is bayes' theorem which states that
>
> P(A|B) = P(A and B) / P(B).
>
> Currently, we assume that P(A|B) = P(A), meaning the probability (or selectivity as we call it) of an event (like a=3) does not change under additional assumptions like b=4. Bayes' theorem thus becomes
>
> P(A) = P(A and B) / P(B) <=>
> P(A and B) = P(A)*P(B)
>
> which is how we currently compute the selectivity of a clause such as "WHERE a=3 AND b=4".
>
> I believe that measuring this by counting the number of distinct values of column B for each A is basically the right idea. Maybe we could count the number of distinct values of "b" for every one of the most common values of "a", and compare that to the overall number of distinct values of "b"...

Good point!

Well, I was thinking about this too - generally this means creating a
contingency table with the MCV as bins. Then you can compute these
interesting probabilities P(A and B). (OK, now I definitely look like
some contingency table weirdo, who tries to solve everything with a
contingency table. OMG!)

The question is - what are we going to do when the values in the query
are not in the MCV list? Is there some heuristics to estimate the
probability from MCV, or something like that? Could we use some
"average" probability or what?

Tomas