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

On Wed, Jun 16, 2021 at 8:23 PM Tomas Vondra <tomas(dot)vondra(at)enterprisedb(dot)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.c, but I don't know if there
is something better out there:

* The following choice of minrows is based on the paper
* "Random sampling for histogram construction: how much is enough?"
* by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in

What is more troubling to me is that we set the number of MCVs to the
number of histograms. Since b5db1d93d2a6 we have a pretty good method of
finding the MCVs that are justified. When that first went in, I
experimented with removing the MCV limit and found it easy to create value
distributions that lead to thousands of MCVs. I guess the best
justification now for the limit is plan time, but if we have a sketch also,
we can choose one or the other based on a plan-time speed vs accuracy
tradeoff (another use for a planner effort guc). In that scenario, for
tables with many MCVs we would only use them for restriction clauses.

--
John Naylor
EDB: http://www.enterprisedb.com