Re: PoC: Using Count-Min Sketch for join cardinality estimation - Mailing list pgsql-hackers

From Tomas Vondra
Subject Re: PoC: Using Count-Min Sketch for join cardinality estimation
Date
Msg-id bf65f065-1eb9-b8ef-5623-32539139b1d8@enterprisedb.com
Whole thread Raw
In response to Re: PoC: Using Count-Min Sketch for join cardinality estimation  (John Naylor <john.naylor@enterprisedb.com>)
List pgsql-hackers
On 6/18/21 9:54 PM, John Naylor wrote:
> 
> On Fri, Jun 18, 2021 at 3:43 PM Tomas Vondra 
> <tomas.vondra@enterprisedb.com <mailto:tomas.vondra@enterprisedb.com>> 
> wrote:
> 
>  > Sorry, I'm not sure what you mean by "we set the number of MCVs to the
>  > number of histograms" :-(
>  >
>  > When you say "MCV limit" you mean that we limit the number of items to
>  > statistics target, right? I agree plan time is one concern - but it's
>  > also about analyze, as we need larger sample to build a larger MCV or
>  > histogram (as the paper you referenced shows).
> 
> Ah, I didn't realize the theoretical limit applied to the MCVs too, but 
> that makes sense since they're basically singleton histogram buckets.
> 

Something like that, yes. Looking at MCV items as singleton histogram 
buckets is interesting, although I'm not sure that was the reasoning 
when calculating the MCV size. AFAIK it was kinda the other way around, 
i.e. the sample size is derived from the histogram paper, and when 
building the MCV we ask what's sufficiently different from the average 
frequency, based on the sample size etc.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company



pgsql-hackers by date:

Previous
From: Jeff Davis
Date:
Subject: Re: A few nuances about specifying the timeline with START_REPLICATION
Next
From: Tomas Vondra
Date:
Subject: Re: pg_stats and range statistics