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: Adrien Nayrat <adrien.nayrat@dalibo.com>
Cc: Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
Date: Sun, 15 Jul 2018 15:29:16 +0200
Message-ID: <adc47878-2927-2d96-3efc-71d283052a2d@2ndquadrant.com> (raw)
In-Reply-To: <CAEZATCUtvWzQ8BPgNcY8u6tnyAf6cvVoVC6RRdqbMuDNHfuS2g@mail.gmail.com>
References: <49348328-1a02-7e45-e50f-e1d4d0243c5c@2ndquadrant.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>
<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>
On 07/15/2018 11:36 AM, Dean Rasheed wrote:
> ...
>
> What I'm considering is an algorithm where we simultaneously compute 3 things:
>
> simple_sel - The result we would get without multivariate stats (*)
> mcv_sel - The multivariate MCV result
> hist_sel - The multivariate histogram result
>
> (*) except that at each stage where we add a new clause to the
> simple_sel value, we improve upon that estimate by factoring in a
> lower bound from the multivariate stats so far, so that even if the
> multivariate stats fail to generate anything at the end, we've managed
> to account for some of the non-independence of the columns.
>
> If the MCV matches represented all the matches, then at the end we
> would have simple_sel = mcv_sel, and hist_sel = 0, and we'd be done.
>
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 ...
> Otherwise, we'd have simple_sel >= mcv_sel, and a possibly non-zero
> hist_sel, but if we had managed to factor in both mcv_sel and hist_sel
> to simple_sel at each stage as we went along, then simple_sel is the
> best overall estimate we can return.
>
Hmm. I may not be understanding the algorithm yet, but I find it hard to
believe applying the stats incrementally is going to produce reliably
better estimates that looking at all clauses at once. I understand
deducing upper/lower boundaries is useful, but I wonder if we could do
that somehow with the current algorithm.
> Perhaps this is not so very different from what you're currently
> doing, except that with this approach we might also end up with
> mcv_sel = 0 and hist_sel = 0, but still have an improved simple_sel
> estimate that had accounted for some the multivariate stats available
> along the way.
>
I don't know, really. I'll have to try hacking on this a bit I guess.
But there's one obvious question - in what order should we add the
clauses? Does it matter at all, or what is the optimal order? We don't
need to worry about it now, because we simply consider all clauses at
once, but I guess the proposed algorithm is more sensitive to this.
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, adrien.nayrat@dalibo.com
Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
In-Reply-To: <adc47878-2927-2d96-3efc-71d283052a2d@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