Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
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>
References: <20180310171906.gd6vyz6hnou2n3h7@alvherre.pgsql>
 <850c3b6b-2641-496c-4efc-500c720f7260@2ndquadrant.com>
 <ec49a434-b814-2cfa-f602-02a0cc9e518c@2ndquadrant.com>
 <CAEZATCW9AXzf+1T44B0=rBd8a0AD+pWO_PpkhApqLBE9JS1Cyg@mail.gmail.com>
 <66ba9c45-3b07-e5b6-fd11-15e75f6ee8e1@2ndquadrant.com>
 <CAEZATCUC8h6Osegq2Lw75Hc1NG=72JgNiiTQSSp9CpDCkQgakw@mail.gmail.com>
 <49348328-1a02-7e45-e50f-e1d4d0243c5c@2ndquadrant.com>
 <CAEZATCUk5rfLxm60W0VYT8zF2trFRRBonJKTwF46s+hjr28Fyw@mail.gmail.com>
 <CAEZATCUOyMMpyrUKFV15_Eaaxgxg3oxSL_ChA9EVm0MaA_eXcw@mail.gmail.com>
 <1aaa338a-fa70-1b92-988e-498eb996ce57@2ndquadrant.com>
 <681c6a78-2aef-769e-bd0f-290ac650e71d@2ndquadrant.com>
 <CAEZATCUVD_f2CFWaVfGGTtzPXQo26m4u-C6iCTazE6PNpBSSNQ@mail.gmail.com>
 <b423b2fe-8aff-d64c-152a-8c77cf45faa7@2ndquadrant.com>
 <CAEZATCW=081sEDERoty8knpjwjnCQP+zCh-bFSb8xVxT8KKwHQ@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <7d12b5d1-ac77-67e3-c67e-7fcbd3753e9c@2ndquadrant.com>
Date: Thu, 29 Mar 2018 15:36:09 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.4.0
MIME-Version: 1.0
In-Reply-To: 
 <CAEZATCW=081sEDERoty8knpjwjnCQP+zCh-bFSb8xVxT8KKwHQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 03/29/2018 02:27 AM, Dean Rasheed wrote:
> On 28 March 2018 at 15:50, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>> After thinking about this a bit more, I'm not sure if updating the info
>> based on recursive calls makes sense. The fullmatch flag was supposed to
>> answer a simple question - can there be just a single matching item?
>>
>> If there are equality conditions on all columns, there can be just a
>> single matching item - if we have found it in the MCV (i.e. s1 > 0.0),
>> then we don't need to inspect the non-MCV part.
>>
>> But handling this in recursive manner breaks this entirely, because with
>> something like
>>
>>    (a=1) AND (b=1 OR b=2)
>>
>> you suddenly can have multiple matching items. Which makes the fullmatch
>> flag somewhat useless.
>>
>> So I think we should be looking at top-level equality clauses only, just
>> like number_of_groups() does.
>>
> 
> I'm not quite sure what you mean by that, but it sounds a bit limiting
> in terms of the kinds of user queries that would be supported.
> 

Let me explain. The question is "Can there be just a single combination
of values matching the conditions?" which (if true) allows us to produce
better estimates. If we found a match in the MCV, we don't need to look
at the non-MCV part. If not found in the MCV, we can compute an average
selectivity as 1/ndistinct (possibly using the ndistinct coefficients).

If we can't deduce the existence of a single possible match, we have to
compute an estimate in a more generic way.

With (a=1 AND b=1) and stats on (a,b) there's just a single possible
match (1,1), so that's fine. But it does not work once we start looking
for equalities nested deeper - for example (a=1 AND (b=1 OR b=2)) can be
translated as ((a=1 AND b=1) OR (a=1 AND b=2)) so technically there's an
equality on each column, but there are two possible matches (1,1) and
(1,2). So the optimization does not work.

Does that clarify what I meant?

Although, perhaps we could improve this by deducing number of possible
matches and then track matching items in the MCV list. But that seems
quite a bit harder.

(Of course, we need to consider the non-equality clauses in both cases,
the WIP patch does not do that yet.)

> 
>> I think we can remove the fullmatch flag from mcv_update_bitmap
>> entirely. All we need to know is the presence of equality clauses and
>> whether there was a match in MCV (which we know from s1 > 0.0).
>>
> 
> I agree with removing the fullmatch flag, but I don't think we
> actually need to know about the presence of equality clauses:
> 
> The way that mcv_update_bitmap() recursively computes the set of
> matching MCVs seems to be correct. That gives us a value (call it
> mcv_matchsel) for the proportion of the table's rows that are in the
> MCV list and satisfy the clauses in stat_clauses.
> 

Sure, but the extra bit of information allows us to (a) ignore the
non-MCV part and (b) apply the 1/ndistinct estimate.

> We can also estimate that there are (1-mcv_totalsel)*N rows that are
> not in the MCV list, for which the MCV stats therefore tell us
> nothing. The best way to estimate those rows would seem to be to use
> the logic from the guts of clauselist_selectivity(), without
> consulting any extended MCV stats (but still consulting other extended
> stats, I think). Doing that would return a selectivity value (call it
> nonmcv_sel) for those remaining rows. Then a reasonable estimate for
> the overall selectivity would seem to be
> 
>   mcv_matchsel + (1-mcv_totalsel) * nonmcv_sel
> 
> and there would be no need for mcv_update_bitmap() to track eqmatches
> or return fullmatch, and it wouldn't actually matter whether or not we
> had equality clauses or if all the MCV columns were used.
> 

Right, although I'm not sure about fallback to clauselist_selectivity()
which kinda throws away the statistical dependency.

That's why I think we should use 1/ndistinct for equality clauses, and
then perhaps leverage the MCV for non-equality clauses somehow.

It just occurred we can apply the 1/ndistinct estimate for equalities
even when we it's not a 'fullmatch'.

So what I propose is roughly this

1) compute selectivity "mcv_sel" using MCV

2) see if there can be just a single match, and (mcv_sel > 0) - if yes,
we're done and we don't need to look at non-MCV part

3) split the clauses into top-level equality clauses and the rest

4) estimate "equal_sel" for equality clauses using 1/ndistinct

5) estimate the "inequal_sel" for remaining clauses using MCV (assumes
the selectivity will be the same on non-MCV part)

6) total selectivity is

    mcv_sel + (1 - mcv_totalsel) * equal_sel * inequal_sel


We may need to fall back to clauselist_selectivity() in some cases, of
course, but I think we should leverage the MCV as much as possible.

Another thing is that some of this will change once the histograms are
considered, which helps with estimating the non-MCV part.


regards

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