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>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <b423b2fe-8aff-d64c-152a-8c77cf45faa7@2ndquadrant.com>
Date: Wed, 28 Mar 2018 16:50:41 +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: 
 <CAEZATCUVD_f2CFWaVfGGTtzPXQo26m4u-C6iCTazE6PNpBSSNQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 03/28/2018 04:12 PM, Dean Rasheed wrote:
> On 28 March 2018 at 01:34, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>> Attached is a patch fixing this. In the end I've decided to keep both
>> branches - one handling boolean Vars and one for NOT clauses. I think
>> you're right we can only see (NOT var) cases, but I'm not sure about that.
>>
>> For example, what if an operator does not have a negator? Then we can't
>> transform NOT (a AND b) => (NOT a OR NOT b), I guess. So I kept this for
>> now, and we can remove this later.
>>
> 
> OK, but it's going to have to work harder to set "fullmatch"
> correctly. If you have a boolean Var clause, which is identical to
> "bool_var = true", it ought to add to "eqmatches" if true is found in
> the MCV list. Likewise a boolean Var under a NOT clause is identical
> to "bool_var = false", so it ought to add to "eqmatches" if false is
> found in the MCV list. Both those cases would be easy to handle, if
> general NOT support wasn't required, and you just special-cased "NOT
> bool_var".
> 
> If you're going to handle the general case of an arbitrary clause
> under a NOT, then the recursive call to mcv_update_match_bitmap()
> would seem to need to know that it's under a NOT (a new "is_not"
> parameter?), to invert the logic around adding to "eqmatches". That
> applies to other general OpExpr's too -- for example, "NOT (box_var =
> ?)" won't be rewritten because there is no box_ne operator, but when
> mcv_update_match_bitmap() is called recursively with the "box_var =
> ?", it shouldn't add to "eqmatches", despite this being an EQSEL
> operator.
> 
> As mentioned before, I think this whole thing only works if
> mcv_update_match_bitmap() returns the "eqmatches" list, so that if it
> is called recursively, it can be merged with the caller's list. What
> isn't immediately obvious to me is what happens to a NOT clause under
> another NOT clause, possibly with an AND or OR in-between. Would the
> "is_not" parameter just flip back to false again?
> 

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.


> There's also an interesting question around the NullTest clause. Since
> NULLs are being recorded in the MCV list, shouldn't "IS NULL" be
> treated as semantically like an equality clause, and cause that
> attribute to be added to "eqmatches" if NULL is found in the MCV list?
> 
> 
>> I've also realized that the "fullmatch" flag is somewhat confused,
>> because some places interpreted it as "there is equality on each
>> attribute" but in fact it also required an actual MCV match.
> 
> Yes, I was having similar thoughts. I think "eqmatches" / "fullmatch"
> probably just wants to track whether there was an exact comparison on
> all the attributes, not whether or not the value was in the MCV list,
> because the latter is already available in the "matches" bitmap.
> Knowing that complete, exact comparisons happened, and it wasn't in
> the MCV list, makes the "(1 - mcv_totalsel)) / otherdistinct" estimate
> reasonable.
> 

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).

> However, I don't think that tracking "eqmatches" or "fullmatch" is
> sufficient for the general case. For example, for other operators like
> "!=", "<", "<=", all (or maybe half) the "1 - mcv_totalsel" ought to
> count towards the selectivity, plus possibly part of the MCV list
> (e.g., for "<=", using the sum of the matching MCV frequencies plus
> half the sum of the non-MCV frequencies might be reasonable -- c.f.
> scalarineqsel()). For an OR clause, you might want to count the number
> of non-MCV matches, because logically each one adds another "(1 -
> mcv_totalsel)) / otherdistinct" to the total selectivity. It's not
> immediately obvious how that can be made to fit into the current code
> structure. Perhaps it could be made to work by tracking the overall
> selectivity as it goes along. Or perhaps it could track the
> count/proportion of non-MCV matches.
> 

Yes, ignoring the non-equality clauses in 0002 is wrong - that's pretty
much why it's WIP and not merged into 0001.

thanks for the feedback

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