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>
 <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>
 <11223173-bd90-4fa8-8cf1-49928b615405@2ndquadrant.com>
 <CAEZATCVEU=ZZ31yqQY=nUg+p7dBLxqJg6iDN-9MoE81uYs-8dw@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <e7d989e1-4a06-d2ab-8950-eb711a14df9c@2ndquadrant.com>
Date: Thu, 10 Jan 2019 16:45:23 +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: 
 <CAEZATCVEU=ZZ31yqQY=nUg+p7dBLxqJg6iDN-9MoE81uYs-8dw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 1/10/19 4:20 PM, Dean Rasheed wrote:
> On Wed, 9 Jan 2019 at 15:40, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>> On 1/8/19 3:18 PM, Dean Rasheed wrote:
>>> 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.
>>
> 
> I don't see how that would skew other_sel. Items close to the base
> frequency would also tend to be close to simple_sel, making other_sel
> approximately zero, so excluding them should have little effect.

Oh, I see. You're right those items should contribute very little to
other_sel, I should have realized that.

> However...
> 
> Re-reading the thread where we enhanced the per-column MCV stats last
> year [1], it was actually the case that an algorithm based on just
> looking at the relative standard error worked pretty well for a very
> wide range of data distributions.
> 
> The final algorithm chosen in analyze_mcv_list() was only a marginal
> improvement on that, and was directly based upon the fact that, in the
> univariate statistics case, all the values not included in the MCV
> list are assigned the same selectivity. However, that's not the case
> for multivariate stats, because each group not included in the
> multivariate MCV list gets assigned a different selectivity based on
> its per-column stats.
> 
> So perhaps what we should do for multivariate stats is simply use the
> relative standard error approach (i.e., reuse the patch in [2] with a
> 20% RSE cutoff). That had a lot of testing at the time, against a wide
> range of data distributions, and proved to be very good, not to
> mention being very simple.
> 
> That approach would encompass both groups more and less common than
> the base frequency, because it relies entirely on the group appearing
> enough times in the sample to infer that any errors on the resulting
> estimates will be reasonably well controlled. It wouldn't actually
> look at the base frequency at all in deciding which items to keep.
> 
> Moreover, if the group appears sufficiently often in the sample to
> justify being kept, each of the individual column values must also
> appear at least that often as well, which means that the errors on the
> base frequency estimate are also well controlled. That was one of my
> concerns about other algorithms such as "keep items significantly more
> or less common than the base frequency" -- in the less common case,
> there's no lower bound on the number of occurrences seen, and so no
> guarantee that the errors are kept under control.
> 

Yep, that looks like a great approach. Simple and tested. I'll try
tweaking the patch accordingly over the weekend.

Thanks!

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