Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-18 Thread Tomas Vondra
On 6/18/21 9:54 PM, John Naylor wrote: On Fri, Jun 18, 2021 at 3:43 PM Tomas Vondra mailto:tomas.von...@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 n

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-18 Thread John Naylor
On Fri, Jun 18, 2021 at 3:43 PM Tomas Vondra 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

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-18 Thread Tomas Vondra
On 6/18/21 7:03 PM, John Naylor wrote: On Wed, Jun 16, 2021 at 8:23 PM Tomas Vondra mailto:tomas.von...@enterprisedb.com>> wrote: > Not really, but to be fair even for the histograms it's only really > supported by "seems to work in practice" :-( Hmm, we cite a theoretical result in analyze

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-18 Thread John Naylor
On Wed, Jun 16, 2021 at 8:23 PM Tomas Vondra wrote: > Not really, but to be fair even for the histograms it's only really > supported by "seems to work in practice" :-( Hmm, we cite a theoretical result in analyze.c, but I don't know if there is something better out there: * The following choi

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-17 Thread Tomas Vondra
On 6/17/21 2:23 AM, Tomas Vondra wrote: > On 6/17/21 1:31 AM, John Naylor wrote: >> On Wed, Jun 16, 2021 at 12:23 PM Tomas Vondra >> mailto:tomas.von...@enterprisedb.com>> >> wrote: >> >> ... >> >> + * depth 8 and width 128 is sufficient for relative error ~1.5% with a >> + * probability of appr

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-16 Thread Tomas Vondra
On 6/17/21 1:31 AM, John Naylor wrote: > On Wed, Jun 16, 2021 at 12:23 PM Tomas Vondra > mailto:tomas.von...@enterprisedb.com>> > wrote: > > > The attached patch is a very simple (and perhaps naive) implementation > > adding count-min sketch to pg_statistic for all attributes with a hash > >

Re: PoC: Using Count-Min Sketch for join cardinality estimation

2021-06-16 Thread John Naylor
On Wed, Jun 16, 2021 at 12:23 PM Tomas Vondra wrote: > The attached patch is a very simple (and perhaps naive) implementation > adding count-min sketch to pg_statistic for all attributes with a hash > function (as a new statistics slot kind), and considering it in > equijoinsel_inner. There's a G