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: <a0aa7043-26cd-5473-a9d4-ef3bd035f132@2ndquadrant.com>
Date: Fri, 11 Jan 2019 22:18:32 +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:
> ...
>
> 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.
> 

I've been looking at this approach today, and I'm a bit puzzled. That
patch essentially uses SRE to compute mincount like this:

    mincount = n*(N-n) / (N-n+0.04*n*(N-1))

and then includes all items more common than this threshold. How could
that handle items significantly less common than the base frequency?

Or did you mean to use the SRE, but in some different way?

regards

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