From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Bruce Momjian <bruce@momjian.us>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Mark Dilger <hornschnorter@gmail.com>
Cc: Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
Date: Mon, 16 Jul 2018 14:17:49 +0200
Message-ID: <0a2de724-ef48-b0b6-d2dd-7a6bde31f970@2ndquadrant.com> (raw)
In-Reply-To: <5721b874-35f7-89aa-6c17-4f9a0e8063d0@2ndquadrant.com>
References: <49348328-1a02-7e45-e50f-e1d4d0243c5c@2ndquadrant.com>
<CAEZATCUVD_f2CFWaVfGGTtzPXQo26m4u-C6iCTazE6PNpBSSNQ@mail.gmail.com>
<b423b2fe-8aff-d64c-152a-8c77cf45faa7@2ndquadrant.com>
<CAEZATCW=081sEDERoty8knpjwjnCQP+zCh-bFSb8xVxT8KKwHQ@mail.gmail.com>
<7d12b5d1-ac77-67e3-c67e-7fcbd3753e9c@2ndquadrant.com>
<abfb7b66-af22-ac32-a74d-3fcf9bdb5c5c@2ndquadrant.com>
<20180407141201.GA10394@momjian.us>
<CAEZATCXYHJoocBq3yqEG_BNDgLuvDiCxcK9Tg-qbQXrs9pnnHg@mail.gmail.com>
<4416a567-4452-c5fd-7117-5cc7827b5fad@2ndquadrant.com>
<f52637bd-f761-f91b-c8ac-85e0c159807f@2ndquadrant.com>
<CAEZATCVa-86yMzwVYVnrvfagO07YpXPR5X1uisvVasGHd3k-4A@mail.gmail.com>
<d6e5e15d-3f53-239a-7064-bb99f037a0da@2ndquadrant.com>
<CAEZATCUtvWzQ8BPgNcY8u6tnyAf6cvVoVC6RRdqbMuDNHfuS2g@mail.gmail.com>
<adc47878-2927-2d96-3efc-71d283052a2d@2ndquadrant.com>
<CAEZATCXwTYmw5dBhuShh-1kmDV3UYSbf0=+qweXH5Y3=_m1WiA@mail.gmail.com>
<5721b874-35f7-89aa-6c17-4f9a0e8063d0@2ndquadrant.com>
On 07/16/2018 12:16 AM, Tomas Vondra wrote:
>
> On 07/15/2018 04:43 PM, Dean Rasheed wrote:
>> On 15 July 2018 at 14:29, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>>> It's quite unclear to me how this algorithm could reliably end up with
>>> hist_sel=0 (in cases where we already don't end up with that). I mean,
>>> if a bucket matches the conditions, then the only way to eliminate is by
>>> deducing that MCV already contains all the matches - and that's rather
>>> difficult for complex clauses ...
>>
>> Ah, I didn't realise that you were using histograms for equality
>> clauses as well. I had assumed that they would only use the MCV stats,
>> as in the univariate case. Using histograms for equality seems
>> problematic -- if bucket_contains_value() returns STATS_MATCH_PARTIAL,
>> as things stand that would end up with an estimate of half the
>> bucket's frequency, which seems excessive.
>
> Yeah, I think you're right - this is likely to produce over-estimates
> and needs rethinking. With top-level equality clauses it should be
> fairly trivial to use approach similar to the univariate case, i.e.
> computing ndistinct and using
>
> (1 - mcv_totalsel) / ndistinct
>
> If there are ndistinct coefficients this might be pretty good estimate
> of the non-MCV part, I think. But it only works for top-level
> equalities, not for complex clauses as in your examples.
>
On further thought, it's a bit more complicated, actually. Firstly, we
already do that when there's no histogram (as in your example), and
clearly it does not help. I initially thought it's a mistake to use the
histogram in this case, but I can think of cases where it helps a lot.
1) when the equality clauses match nothing
In this case we may not find any buckets possibly matching the
combination of values, producing selectivity estimate 0.0. While by
using 1/ndistinct would give us something else.
2) when there are equality and inequality clauses
Similarly to the previous case, the equality clauses are useful in
eliminating some of the buckets.
Now, I agree estimating equality clauses using histogram is tricky, so
perhaps what we should do is using them as "conditions" to eliminate
histogram buckets, but use ndistinct to estimate the selectivity. That
is something like this:
P(a=1 & b=1 & c<10 & d>=100)
= P(a=1 & b=1) * P(c<10 & d>=100 | a=1 & b=1)
= 1/ndistinct(a,b) * P(c<10 & d>=100 | a=1 & b=1)
where the second part is estimated using the histogram.
Of course, this still only works for the top-level equality clauses :-(
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, dean.a.rasheed@gmail.com, bruce@momjian.us, alvherre@2ndquadrant.com, andres@anarazel.de, thomas.munro@enterprisedb.com, hornschnorter@gmail.com
Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
In-Reply-To: <0a2de724-ef48-b0b6-d2dd-7a6bde31f970@2ndquadrant.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox