Horton

Re: [HACKERS] PATCH: multivariate histograms and MCV lists

Tomas Vondra <tomas.vondra@2ndquadrant.com>

View thread View on postgr.es
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>, Andres Freund <andres@anarazel.de>, Thomas Munro <thomas.munro@enterprisedb.com>, Mark Dilger <hornschnorter@gmail.com>, Adrien Nayrat <adrien.nayrat@dalibo.com>, Pg Hackers <pgsql-hackers@postgresql.org>
Date: 2018-04-01T16:07:55Z
Lists: pgsql-hackers

Attachments

Hi,

The attached patch version modifies how the non-MCV selectivity is
computed, along the lines explained in the previous message.

The comments in statext_clauselist_selectivity() explain it in far more
detail, but we this:

1) Compute selectivity using the MCV (s1).

2) To compute the non-MCV selectivity (s2) we do this:

2a) See how many top-level equalities are there (and compute ndistinct
estimate for those attributes).

2b) If there is an equality on each column, we know there can only be a
single matching item. If we found it in the MCV (i.e. s1 > 0) we're
done, and 's1' is the answer.

2c) If only some columns have equalities, we estimate the selectivity
for equalities as

    s2 = ((1 - mcv_total_sel) / ndistinct)

If there are no remaining conditions, we're done.

2d) To estimate the non-equality clauses (on non-MCV part only), we
either repeat the whole process by calling clauselist_selectivity() or
approximating s1 to the non-MCV part. This needs a bit of care to
prevent infinite loops.


Of course, with 0002 this changes slightly, because we may try using a
histogram to estimate the non-MCV part. But that's just an extra step
right before (2a).

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Commits

  1. Convert pre-existing stats_ext tests to new style

  2. Add support for multivariate MCV lists

  3. Improve ANALYZE's strategy for finding MCVs.

  4. Clone extended stats in CREATE TABLE (LIKE INCLUDING ALL)

  5. Try again to fix accumulation of parallel worker instrumentation.

  6. Adjust psql \d query to avoid use of @> operator.

  7. Message style fixes

  8. Add security checks to selectivity estimation functions