Subject: Re: [HACKERS] PATCH: multivariate histograms and MCV lists
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Bruce Momjian <bruce@momjian.us>,
 Alvaro Herrera <alvherre@2ndquadrant.com>, Andres Freund
 <andres@anarazel.de>, Thomas Munro <thomas.munro@enterprisedb.com>,
 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>
 <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>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <adc47878-2927-2d96-3efc-71d283052a2d@2ndquadrant.com>
Date: Sun, 15 Jul 2018 15:29:16 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.5.2
MIME-Version: 1.0
In-Reply-To: 
 <CAEZATCUtvWzQ8BPgNcY8u6tnyAf6cvVoVC6RRdqbMuDNHfuS2g@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


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