On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
On 10/02/2014 02:30 AM, Peter Geoghegan wrote: > On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs <simon@2ndquadrant.com> wrote: >> Having read papers on it, I believe the problem is intractable. Coding >> is not the issue. To anyone: please prove me wrong, in detail, with >> references so it can be coded. > > I think it might be close to intractable if you're determined to use a > sampling model. HyperLogLog looks very interesting for n_distinct > estimation, though. My abbreviated key patch estimates the cardinality > of abbreviated keys (and original strings that are to be sorted) with > high precision and fixed overhead. Maybe we can figure out a way to > do opportunistic streaming of HLL. Believe it or not, the way I use > HLL for estimating cardinality is virtually free. Hashing is really > cheap when the CPU is bottlenecked on memory bandwidth.
Yes, it's only intractable if you're wedded to the idea of a tiny, fixed-size sample. If we're allowed to sample, say, 1% of the table, we can get a MUCH more accurate n_distinct estimate using multiple algorithms, of which HLL is one. While n_distinct will still have some variance, it'll be over a much smaller range.
In my hands, the problems with poor n_distinct were not due to the insufficient size of the sample, but the insufficient randomness of it. Increasing default_statistics_target did help but not because it increases the number of rows sampled, but rather because it increases the number of blocks sampled. Once substantially all of the blocks are part of the block sampling, the bias is eliminated even though it was still sampling a small fraction of the rows (roughly one per block).
So one idea would be go get rid of the 2-stage sampling algorithm (sample blocks, sample rows from the chosen blocks) and just read the whole table and sample rows from it unbiased, at least under some conditions. Some low level benchmarking on my favorite server showed that reading 1% of a system's blocks (in block number order within each file) was no faster than reading all of them from an IO perspective. But that is a virtualized server that wasn't really speced out to be an IO intensive database server in the first place. It would be interesting to see what people get on real hardware that they actually designed for the task.
A problem right now is that we only have one knob. I want to compute more accurate n_distinct and most_common_freqs, but I don't want to store huge numbers entries for most_common_vals and histogram_bounds.
