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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
