Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Bruce Momjian <bruce@momjian.us>,
 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>
References: <49348328-1a02-7e45-e50f-e1d4d0243c5c@2ndquadrant.com>
 <CAEZATCXYHJoocBq3yqEG_BNDgLuvDiCxcK9Tg-qbQXrs9pnnHg@mail.gmail.com>
 <4416a567-4452-c5fd-7117-5cc7827b5fad@2ndquadrant.com>
 <f52637bd-f761-f91b-c8ac-85e0c159807f@2ndquadrant.com>
 <CAEZATCVa-86yMzwVYVnrvfagO07YpXPR5X1uisvVasGHd3k-4A@mail.gmail.com>
 <d6e5e15d-3f53-239a-7064-bb99f037a0da@2ndquadrant.com>
 <CAEZATCUtvWzQ8BPgNcY8u6tnyAf6cvVoVC6RRdqbMuDNHfuS2g@mail.gmail.com>
 <f0625b09-bf50-5703-6241-51aea96a3f6a@2ndquadrant.com>
 <CAEZATCWORz=bXEPVJNxK49Ws9zeBHqsEdd3JsrrZWMvQ8oXuSA@mail.gmail.com>
 <80bc98b2-1c43-1fe8-b316-d447bb68cff2@2ndquadrant.com>
 <CAEZATCX04NOAqJm7+vb_jyrMxDo44Pzx8xd_z5rRH7snsLqxEA@mail.gmail.com>
 <c2614611-fd99-124f-c9aa-0fef3859c78f@2ndquadrant.com>
 <CAEZATCVqG5gBkn0RM8rSU1ZKz1boVYshz_XM-=s+TQovqX4kdw@mail.gmail.com>
 <341ca23f-144d-130d-1b45-ddddf581797e@2ndquadrant.com>
 <8ac8bd94-478d-215d-e6bd-339f1f20a74c@2ndquadrant.com>
 <CAEZATCUQSgWZSjN0G5kM8D+0zuAK6nkxLmRwSja3K1u1k_sM3Q@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <d17f081d-5cb8-3587-8fdc-30d216f7808e@2ndquadrant.com>
Date: Sun, 9 Sep 2018 23:49:59 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.5.2
MIME-Version: 1.0
In-Reply-To: 
 <CAEZATCUQSgWZSjN0G5kM8D+0zuAK6nkxLmRwSja3K1u1k_sM3Q@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

Hi,

On 09/04/2018 04:16 PM, Dean Rasheed wrote:
> On 3 September 2018 at 00:17, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>> Hi,
>>
>> Attached is an updated version of the patch series, adopting a couple of
>> improvements - both for MCV lists and histograms.
>>
>>
>> MCV
>> ---
>>
>> For the MCV list part, I've adopted the approach proposed by Dean, using
>> base selectivity and using it to correct the non-MCV part. I agree the
>> simplicity of the approach is a nice feature, and it seems to produce
>> better estimates. I'm not sure I understand the approach perfectly, but
>> I've tried to add comments explaining how it works etc.
>>
> 
> Cool. Looking at this afresh after some time away, it still looks like
> a reasonable approach, and the test results are encouraging.
> 
> In mcv_clauselist_selectivity(), you raise the following question:
> 
>     if (matches[i] != STATS_MATCH_NONE)
>     {
>         /* XXX Shouldn't the basesel be outside the if condition? */
>         *basesel += mcv->items[i]->base_frequency;
>         s += mcv->items[i]->frequency;
>     }
> 
> The reason it needs to be inside the "if" block is that what it's
> computing is the base (independent) selectivity of the clauses found
> to match the MCV stats, so that then in
> statext_clauselist_selectivity() it can be used in the following
> computation:
> 
>     /* Estimated selectivity of values not covered by MCV matches */
>     other_sel = simple_sel - mcv_basesel;
> 
> to give an estimate for the other clauses that aren't covered by the
> MCV stats. So I think the code is correct as it stands, but if you
> think it isn't clear enough, maybe a comment update is in order.
> 
> The assumption being made is that mcv_basesel will cancel out the part
> of simple_sel that is due to clauses matching the MCV stats, so that
> we can then just add on the MCV selectivity. Of course that's only an
> approximation, and it won't be exact -- partly due to the fact that
> simple_sel and mcv_basesel are potentially computed using different
> sample rows, and so will differ in the MCV region, and partly because
> of second-order effects arising from the way that selectivities are
> combined in clauselist_selectivity_simple(). Maybe that's something
> that can be improved upon, but it doesn't seem like a bad initial
> approximation.
> 

Thanks for the clarification. It's one of the comments I added while
reworking the patch, with still a very limited understanding of the
approach at that point in time. I'll replace it with a comment
explaining the reasoning in the next version.

> 
>> I've also changed how we build the MCV lists, particularly how we decide
>> how many / which items store in the MCV list. In the previous version
>> I've adopted the same algorithm we use for per-column MCV lists, but in
>> certain cases that turned out to be too restrictive.
>>
>> Consider for example a table with multiple perfectly correlated columns,
>> with very few combinations. That is, something like this:
>>
>>     CREATE TABLE t (a int, b int);
>>
>>     INSERT INTO t SELECT mod(i,50), mod(i,50)
>>       FROM generate_series(1,1e6) s(i);
>>
>>     CREATE STATISTICS s (mcv) ON a,b FROM t;
>>
>> Now, the data distribution is very simple - uniform, with 50 distinct
>> combinations, each representing 2% of data (and the random sample should
>> be pretty close to that).
>>
>> In these cases, analyze_mcv_list decides it does not need any MCV list,
>> because the frequency for each value is pretty much 1/ndistinct. For
>> single column that's reasonable, but for multiple correlated columns
>> it's rather problematic. We might use the same ndistinct approach
>> (assuming we have the ndistinct coefficients), but that still does not
>> allow us to decide which combinations are "valid" with respect to the
>> data. For example we can't decide (1,10) does not appear in the data.
>>
>> So I'm not entirely sure adopting the same algorithm analyze_mcv_list
>> algorithm both for single-column and multi-column stats. It may make
>> sense to keep more items in the multi-column case for reasons that are
>> not really valid for a single single-column.
>>
>> For now I've added a trivial condition to simply keep all the groups
>> when possible. This probably needs more thought.
>>
> 
> Ah, this is a good point. I think I see the problem here.
> 
> analyze_mcv_list() works by keeping those MCV entries that are
> statistically significantly more frequent than the selectivity that
> would have otherwise been assigned to the values, which is based on
> ndistinct and nullfrac. That's not really right for multivariate stats
> though, because the selectivity that would be assigned to a
> multi-column value if it weren't in the multivariate MCV list is
> actually calculated using the product of individual column
> selectivities. Fortunately we now calculate this (base_frequency), so
> actually I think what's needed is a custom version of
> analyze_mcv_list() that keeps MCV entries if the observed frequency is
> statistically significantly larger than the base frequency, not the
> ndistinct-based frequency.
> 

That's probably a good idea and should be an improvement in some cases.
But I think it kinda misses the second part, when a combination is much
less common than the simple product of selectivities (i.e. values that
are somehow "incompatible").

In the example above, there are only (a,b) combinations where (a == b),
so there's nothing like that. But in practice there will be some sort of
noise. So you may observe combinations where the actual frequency is
much lower than the base frequency.

I suppose "significantly larger than the base frequency" would not catch
that, so we need to also consider cases where it's significantly lower.

I also wonder if we could/should consider the multi-variate ndistinct
estimate, somehow. For the univariate case wen use the ndistinct to
estimate the average selectivity for non-MCV items. I think it'd be a
mistake not to leverage this knowledge (when ndistinct coefficients are
available), even if it only helps with simple equality clauses.

> It might also be worthwhile doing a little more work to make the
> base_frequency values more consistent with the way individual column
> selectivities are actually calculated -- currently the patch always
> uses the observed single-column frequencies to calculate the base
> frequencies, but actually the univariate stats would only do that for
> a subset of the single-column values, and the rest would get assigned
> a fixed share of the remaining selectivity-space. Factoring that into
> the base frequency calculation ought to give a better base frequency
> estimate (for use in mcv_clauselist_selectivity() and
> statext_clauselist_selectivity()), as well as give a more principled
> cutoff threshold for deciding which multivariate MCV values to keep.
> It may be possible to reuse some of the existing code for that.
> 

I agree, but I think we can leave this for later.

> The initial goal of the base frequency calculation was to replicate
> the univariate stats computations, so that it can be used to give the
> right correction to be applied to the simple_sel value. If it can also
> be used to determine how many MCV entries to keep, that's an added
> bonus.
> 

Yep.


regards

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