Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>,
 Bruce Momjian <bruce@momjian.us>, Alvaro Herrera <alvherre@2ndquadrant.com>,
 Andres Freund <andres@anarazel.de>, 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>
 <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>
 <CAEepm=3nYxZ_WL6Ea_UqC_pq2ZzQW6ybB7tbABJu_LYp+zXL8g@mail.gmail.com>
 <c03d7a77-022f-3f4b-347a-232673c8cebf@2ndquadrant.com>
 <11b0d685-152d-8320-5f49-a7c6ac3ee90a@2ndquadrant.com>
 <3b8577ba-6a29-d1f0-b155-d3a50c1a8399@2ndquadrant.com>
 <CAEZATCW8=TDxAJUXnFT1p+4v+ReaabXxWJeGTn5EpEgGjQKBQw@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <11223173-bd90-4fa8-8cf1-49928b615405@2ndquadrant.com>
Date: Wed, 9 Jan 2019 16:39:57 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.3.1
MIME-Version: 1.0
In-Reply-To: 
 <CAEZATCW8=TDxAJUXnFT1p+4v+ReaabXxWJeGTn5EpEgGjQKBQw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


On 1/8/19 3:18 PM, Dean Rasheed wrote:
> On Mon, 7 Jan 2019 at 00:45, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>>
>> FWIW the main unsolved issue (at least on the MCV part) is how it
>> decides which items to keep in the list.
>>
>> As explained in [1], in the multivariate case we can't simply look at
>> the group frequency and compare it to the average frequency (of the
>> non-MCV items), which is what analyze_mcv_list() does in the
>> single-column case. In the multivariate case we also case about observed
>> vs. base frequency, i.e. we want the MCV list to include groups that are
>> present singificantly more/less than product of per-column stats.
>>
>> I've repeatedly tried to come up with a criteria that would address
>> that, but it seems rather difficult because we can't abandon the other
>> criteria either. So the MCV list should include groups that match both
>>
>> (a) items that are statistically more common than the non-MCV part (i.e.
>> the rule from per-column analyze_mcv_list)
>>
>> (b) items that are statistically more/less common than estimated from
>> per-column stats (i.e. the new rule)
> 
> Thinking about this some more, I think that it probably isn't
> appropriate to use analyze_mcv_list() directly because that's making
> specific assumptions about how items not in the list will be estimated
> that aren't actually true for groups of values in multivariate stats.
> If a group of values isn't in the MCV list, it gets estimated based on
> the product of the selectivities from the per-column stats (modulo the
> additional logic preventing the selectivity not exceeding the total
> non-MCV selectivity).
> 
> So actually, the estimate for a group of values will be either the MCV
> item's frequency (if the MCV item is kept), or (roughly) the MCV
> item's base_frequency (if the MCV item is not kept). That suggests
> that we should simply keep items that are significantly more or less
> common than the item's base frequency -- i.e., keep rule (b) and ditch
> rule (a).
> 

Hmmm, but won't that interfere with how we with how we extrapolate the
MCV estimate to the non-MCV part? Currently the patch does what you
proposed, i.e.

    other_sel = simple_sel - mcv_basesel;

I'm worried that if we only include the items that are significantly
more or less common than the base frequency, it may skew the other_sel
estimate.

>> Enforcing rule (a) seems reasonable because it ensures the MCV list
>> includes all items more frequent than the last one. Without it, it's
>> difficult to decide know whether the absent item is very common (but
>> close to base frequency) or very uncommon (so less frequent than the
>> last MCV item).
> 
> I'm not sure there's much we can do about that. Keeping the item will
> result in keeping a frequency that we know is close to the base
> frequency, and not keeping the item will result in per-column stats
> being used that we expect to also give an estimate close to the base
> frequency. So either way, the result is about the same, and it's
> probably better to discard it, leaving more room for other items about
> which we may have more information.
> 
> That said, there is a separate benefit to keeping items in the list
> even if their frequency is close to the base frequency -- the more
> items kept, the larger their total selectivity will be, giving a
> better cap on the non-MCV selectivities. So if, after keeping all
> items satisfying rule (b), there are free slots available, perhaps
> they should be used for the most common remaining values satisfying
> rule (a).
> 

Hmm, so essentially we'd use (b) first to bootstrap the MCV list, and
then we could do what analyze_mcv_list() does. That could work, I guess.

The question is how to define "significantly different from base freq"
though. Any ideas?

regards

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