Re: proposal : cross-column stats

Dne 12.12.2010 15:43, Heikki Linnakangas napsal(a):
> On 12.12.2010 15:17, Martijn van Oosterhout wrote:
>> On Sun, Dec 12, 2010 at 03:58:49AM +0100, Tomas Vondra wrote:
>> Very cool that you're working on this.
>
> +1
>
>>> Lets talk about one special case - I'll explain how the proposed
>>> solution works, and then I'll explain how to make it more general, what
>>> improvements are possible, what issues are there. Anyway this is by no
>>> means a perfect or complete solution - it's just a starting point.
>>
>> It looks like you handled most of the issues. Just a few points:
>>
>> - This is obviously applicable to more than just integers, probably
>>    anything with a b-tree operator class. What you've coded seems rely
>>    on calculations on the values. Have you thought about how it could
>>    work for, for example, strings?
>>
>> The classic failure case has always been: postcodes and city names.
>> Strongly correlated, but in a way that the computer can't easily see.
>
> Yeah, and that's actually analogous to the example I used in my
> presentation.
>
> 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.
>
> That's assuming the combination has any matches. It's possible that the
> user chooses a postcode and city combination that doesn't exist, but
> that's no different from a user doing "city = 'fsdfsdfsd'" on a single
> column, returning no matches. We should assume that the combination
> makes sense.

Well, I've read several papers this week, in an attempt to find out what
possibilities are there when implementing cross-column statistics. One
of the papers seems like a reasonable solution to this particular
problem - discrete data + equality queries.

The article is "A Bayesian Approach to Estimating The Selectivity of
Conjuctive Predicates" (written by Heimel, Markl and Murthy). It's
freely available as a PDF

http:://subs.emis.de/LNI/Proceedings/Proceedings144/52.pdf

I do have a PDF with my own notes in it (as annotations), let me know if
you're interested ...

The basic principle is that instead of 'attribute value independence'
(which is the problem with correlated columns) they assume 'uniform
correlation' which is a much weaker assumption.

In the end, all they need to compute an estimate is number of distinct
values for each of the columns (we already have that in pg_stats) and a
number of distinct values for the group of columns in a query. They
really don't need any multidimensional histogram or something like that.

The funny thing is I've implemented most of the PoC before reading the
article - the only difference was the way to combine the estimates (

------------------------ pros and cons --------------------------

So let's see the pros:

* it's reasonably simple, the overhead should be minimal I guess (we're
  already estimating distinct values for the columns, so I guess we can
  do that for multiple columns with reasonable impact)

* there are no 'advanced data structures' as multi-dimensional
   histograms that are expensive to build and maintain

* it consistently produces better estimates than the current estimator
  based on attribute value independence assumption, and it's reasonably
  accurate (I've been playing with it for some time, so we'll need
  more tests of course)

* it's easily extensible to more columns

* I guess we could improve the estimated by our own heuristicts, to
  catch the special case when one column is perfectly implied by
  another one (e.g. when state is implied by ZIP code) - we can catch
  that by 'distinct for combination = distinct for column' and use just
  the estimate for one of the column

but there are some cons too:

* this really is not designed to work with real-valued data, it's a
  very nice solution for discrete data (namely 'labels' as for example
  city/state names, ZIP codes etc.)

* you need to know the list of columns in advance (there's nothing like
  'let's build' the stats for columns (a,b,c) and then query just (a,b))
  as you need to know the count of distinct values for the queried
  columns (well, maybe it's possible - I guess we could 'integrate'
  over all possible values of the omited column)

* it's built for 'equality' qeuries, although maybe we could modify it
  for inequalities too (but it won't be as elegant), but I guess the
  equality queries are much more common in case of discrete data (OK,
  you can run something like

    WHERE (zip_code BETWEEN '49389' AND '54980') AND state = '48'

  but I guess that's not very frequent. And I think we could still use
  the solution described in the paper.

------------------------ proof of concept --------------------------

I've prepared another 'proof of concept' example - see the attachment.
It works with data from

  http://www.census.gov/geo/www/tiger/zip1999.zip

which is a list of US ZIP codes from 1999, along with info on GPS,
state, county etc. Basically a perfect example of the fail case
described above. It's in a DBF format, so use http:://pgdbf.sf.net (or
something like that) to extract the data.

Then use the script to create a table zip_codes_usa (with appropriate
data types), table 'cross_stats' to store the stats (number of distinct
values) and plpgsql functions collect_stats, get_estimate and
get_frequency.

Run the 'collect_stats' with two columns as parameters, i.e.

  SELECT collect_stats('zip_code', 'state');

and then you can run the 'get_estimate' with values for the columns,
i.e. something like this

  SELECT get_estimate('07034', '34');

which prints some debug notices and returns three integers - estimate
for the colums separately, and then the combined result. So what really
matters is the third number ...

Some basic tests, compared with the current estimator:

a) queries involving 'zip_code' - I've put there the heuristics
   described above, so it actually returns the best estimate (unless
   the combination with state does not make sense, of course)

     ZIP  | state | actual | current estimate | get_estimate
   =========================================================
    07034 | 34    | 32     | 1                | 32
    07034 | 32    | 0      | 1                | 32

   There are 32 rows with this combination as I've copied the data
   multiple times to make the table bigger.

   The 'better performance' of the current estimator in the second case
   is actually just a lucky coincidence, a side-effect of the
   independence assumption. And as Heikki already pointed out, we should
   assume the combination makes sense, so this actually is not an
   advantage of the current estimator.

b) queries involving 'post_name' and 'state' - this can't use the
   heuristics as in (a), as there are 18.940 different post names,
   59 states and 30113 combinations. On the other side, post name
   implies state.

    post name | state | actual | current estimate | get_estimate
   =========================================================
    ESSEX     | 09    | 32     | 1                | 75
    ELMSFORD  | 36    | 32     | 4                | 188

   Hm, in this case the estimate is not as good as in the first case,
   but I guess it's still a bit better than the current estimate. In
   the first case it's about 2.5x overestimated (compared to 32x
   underestimate of the current estimate), and about 5x overestimated
   in the second case (compared to 8x underestimate of the current one).

   Again, with the invalid combination (e.g. ESSEX/36) the current
   estimator would perform better.

regards
Tomas