Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Quoting Josh Berkus : > Mischa, > > > Okay, although given the track record of page-based sampling for > > n-distinct, it's a bit like looking for your keys under the > streetlight, > > rather than in the alley where you dropped them :-) > > Bad analogy, but funny. Bad analogy? Page-sampling effort versus row-sampling effort, c'est moot. It's not good enough for stats to produce good behaviour on the average. Straight random sampling, page or row, is going to cause enough untrustworthy engine behaviour,for any %ages small enough to allow sampling from scratch at any time. I'm curious what the problem is with relying on a start-up plus incremental method, when the method in the distinct-sampling paper doesn't degenerate: you can start when the table is still empty. Constructing an index requires an initial full scan plus incremental update; what's the diff? > Unless, of course, we use indexes for sampling, which seems like a > *really > good* idea to me "distinct-sampling" applies for indexes, too. I started tracking the discussion of this a bit late. Smart method for this is in VLDB'92: Gennady Antoshenkov, "Random Sampling from Pseudo-ranked B+-trees". I don't think this is online anywhere, except if you have a DBLP membership. Does nybod else know better? Antoshenkov was the brains behind some of the really cool stuff in DEC Rdb (what eventually became Oracle). Compressed bitmap indices, parallel competing query plans, and smart handling of keys with hyperbolic distributions. -- Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection. ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
John, > But doesn't an index only sample one column at a time, whereas with > page-based sampling, you can sample all of the columns at once. Hmmm. Yeah, we're not currently doing that though. Another good idea ... -- --Josh Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Josh Berkus wrote: Mischa, Okay, although given the track record of page-based sampling for n-distinct, it's a bit like looking for your keys under the streetlight, rather than in the alley where you dropped them :-) Bad analogy, but funny. The issue with page-based vs. pure random sampling is that to do, for example, 10% of rows purely randomly would actually mean loading 50% of pages. With 20% of rows, you might as well scan the whole table. Unless, of course, we use indexes for sampling, which seems like a *really good* idea to me But doesn't an index only sample one column at a time, whereas with page-based sampling, you can sample all of the columns at once. And not all columns would have indexes, though it could be assumed that if a column doesn't have an index, then it doesn't matter as much for calculations such as n_distinct. But if you had 5 indexed rows in your table, then doing it index wise means you would have to make 5 passes instead of just one. Though I agree that page-based sampling is important for performance reasons. John =:-> signature.asc Description: OpenPGP digital signature
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Mischa, > Okay, although given the track record of page-based sampling for > n-distinct, it's a bit like looking for your keys under the streetlight, > rather than in the alley where you dropped them :-) Bad analogy, but funny. The issue with page-based vs. pure random sampling is that to do, for example, 10% of rows purely randomly would actually mean loading 50% of pages. With 20% of rows, you might as well scan the whole table. Unless, of course, we use indexes for sampling, which seems like a *really good* idea to me -- --Josh Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Quoting Markus Schaber <[EMAIL PROTECTED]>: > Hi, Josh, > > Josh Berkus wrote: > > > Yes, actually. We need 3 different estimation methods: > > 1 for tables where we can sample a large % of pages (say, >= 0.1) > > 1 for tables where we sample a small % of pages but are "easily > estimated" > > 1 for tables which are not easily estimated by we can't afford to > sample a > > large % of pages. > > > > If we're doing sampling-based estimation, I really don't want > people to lose > > sight of the fact that page-based random sampling is much less > expensive than > > row-based random sampling. We should really be focusing on > methods which > > are page-based. Okay, although given the track record of page-based sampling for n-distinct, it's a bit like looking for your keys under the streetlight, rather than in the alley where you dropped them :-) How about applying the distinct-sampling filter on a small extra data stream to the stats collector? -- Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection. ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Hi, Josh, Josh Berkus wrote: > Yes, actually. We need 3 different estimation methods: > 1 for tables where we can sample a large % of pages (say, >= 0.1) > 1 for tables where we sample a small % of pages but are "easily estimated" > 1 for tables which are not easily estimated by we can't afford to sample a > large % of pages. > > If we're doing sampling-based estimation, I really don't want people to lose > sight of the fact that page-based random sampling is much less expensive than > row-based random sampling. We should really be focusing on methods which > are page-based. Would it make sense to have a sample method that scans indices? I think that, at least for tree based indices (btree, gist), rather good estimates could be derived. And the presence of a unique index should lead to 100% distinct values estimation without any scan at all. Markus ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Mischa Sandberg wrote: Perhaps I can save you some time (yes, I have a degree in Math). If I understand correctly, you're trying extrapolate from the correlation between a tiny sample and a larger sample. Introducing the tiny sample into any decision can only produce a less accurate result than just taking the larger sample on its own; GIGO. Whether they are consistent with one another has no relationship to whether the larger sample correlates with the whole population. You can think of the tiny sample like "anecdotal" evidence for wonderdrugs. Ok, good point. I'm with Tom though in being very wary of solutions that require even one-off whole table scans. Maybe we need an additional per-table statistics setting which could specify the sample size, either as an absolute number or as a percentage of the table. It certainly seems that where D/N ~ 0.3, the estimates on very large tables at least are way way out. Or maybe we need to support more than one estimation method. Or both ;-) cheers andrew ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
First I will comment my original idea. Second I will give another improved suggestion (an idea). I hope, that they will be useful for you. (I don't know, wether the first one was useful at all because it showed, that I and some others of us are not very good with statistics :( ) I haven't looked about the PostgreSQL code, so I don't know, that what is possible now, and what is not. I do know, that the full table scan and after that incremental statistics changes are a very big change, without looking at the code. I meant the following idea: - compare two equal sized samples. Then redo the same thing with double sized samples. So do lots of unnecessary work. Check out the correlation of the two samples to try to guess the distribution. So I tried to give you an idea, not to give you a full answer into the whole problem. I did read some parts of the attached PDFs. They did convince me, that it seems, that the heuristics for the hard cases would actually read almost the whole table in many cases. I did cover the "too little sample" problem by stating that the user should be able to give the minimum size of samples. This way you would avoid the too small sampling problem. My purpose was not to achieve at most 5% wrong estimates, but to decrease the 2000% wrong estimates, that are seen now sometimes. Conclusions: - No heuristics or similar thing of small samples will grant excellent results. - If you need excellent estimates, you need to process the whole table! - Some special cases, like primary keys and the unique indexes and special case column types do give easy ways to make estimates: For example, wether a boolean column has zero, one or two distinct values, it does not matter so much ??? Hashing seems the right choise for all of them. If I have understund correctly, the full table scans are out of questions for large tables at this time. The percentage idea of taking 10% samples seems good. So here is another suggestion: 1. Do a full percentage scan, starting at an arbitrary position. If the user's data is not homogenous, this hurts it, but this way it is faster. During that scan, try to figure out all those columns, that have at most 100 distinct values. Of course, with it you can't go into 100% accuracy, but if the full table scan is out of question now, it is better, if the accuracy is for example at most ten times wrong. You could also improve accuracy by instead of doing a 10% partial table scan, you could do 20 pieces of 0,5 percent partial table scans: This would improve accuracy a bit, but keep the speed almost the same as the partial table scan. Here are questions for the statisticians for distinct values calculation: If we want at most 1000% tolerance, how big percentage of table's one column must be processed? If we want at most 500% tolerance, how big percentage of table's one column must be processed? If we want at most 250% tolerance, how big percentage of table's one column must be processed? Better to assume, that there are at most 100 distinct values on a table, if it helps calculations. If we try to get as much with one discontinuous partial table scan (0,1-10% sample), here is the information, we can gather: 1. We could gather a histogram for max(100) distinct values for each column for every column. 2. We could measure variance and average, and the number of rows for these 100 distinct values. 3. We could count the number of rows, that didn't match with these 100 distinct values: they were left out from the histogram. 4. We could get a minimum and a maximum value for each column. => We could get exact information about the sample with one 0,1-10% pass for many columns. What you statisticans can gather about these values? My idea is programmatical combined with statistics: + Performance: scan for example 100 blocks each of size 100Mb, because disc I/O is much faster this way. + Enables larger table percentage. I hope it helps with the statistics formula. Required because of more robust statistics: take those blocks at random (not over each other) places to decrease the effect from hitting into statistically bad parts on the table. + Less table scan passes: scan all columns with limited hashing in the first pass. + All easy columns are found here with one pass. +- Harder columns need an own pass each, but we have some preliminary knoledge of them on the given sample after all (minimum and maximum values and the histogram of the 100 distinct values). Marko Ristola Greg Stark wrote: "Dave Held" <[EMAIL PROTECTED]> writes: Actually, it's more to characterize how large of a sample we need. For example, if we sample 0.005 of disk pages, and get an estimate, and then sample another 0.005 of disk pages and get an estimate which is not even close to the first estimate, then we have an idea that this is a table which defies analysis based on small samples. I buy that. Better yet is to use the entire sample you've gathered of .01
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Quoting Josh Berkus : > > >Perhaps I can save you some time (yes, I have a degree in Math). If I > > >understand correctly, you're trying extrapolate from the correlation > > >between a tiny sample and a larger sample. Introducing the tiny sample > > >into any decision can only produce a less accurate result than just > > >taking the larger sample on its own; GIGO. Whether they are consistent > > >with one another has no relationship to whether the larger sample > > >correlates with the whole population. You can think of the tiny sample > > >like "anecdotal" evidence for wonderdrugs. > > Actually, it's more to characterize how large of a sample we need. For > example, if we sample 0.005 of disk pages, and get an estimate, and then > sample another 0.005 of disk pages and get an estimate which is not even > close to the first estimate, then we have an idea that this is a table which > defies analysis based on small samples. Wheras if the two estimates are < > 1.0 stdev apart, we can have good confidence that the table is easily > estimated. Note that this doesn't require progressively larger samples; any > two samples would work. We're sort of wandering away from the area where words are a good way to describe the problem. Lacking a common scratchpad to work with, could I suggest you talk to someone you consider has a background in stats, and have them draw for you why this doesn't work? About all you can get out of it is, if the two samples are disjunct by a stddev, yes, you've demonstrated that the union of the two populations has a larger stddev than either of them; but your two stddevs are less info than the stddev of the whole. Breaking your sample into two (or three, or four, ...) arbitrary pieces and looking at their stddevs just doesn't tell you any more than what you start with. -- "Dreams come true, not free." -- S.Sondheim, ITW ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
"Dave Held" <[EMAIL PROTECTED]> writes: > > Actually, it's more to characterize how large of a sample > > we need. For example, if we sample 0.005 of disk pages, and > > get an estimate, and then sample another 0.005 of disk pages > > and get an estimate which is not even close to the first > > estimate, then we have an idea that this is a table which > > defies analysis based on small samples. > > I buy that. Better yet is to use the entire sample you've gathered of .01 and then perform analysis on that sample to see what the confidence interval is. Which is effectively the same as what you're proposing except looking at every possible partition. Unfortunately the reality according to the papers that were sent earlier is that you will always find the results disappointing. Until your sample is nearly the entire table your estimates for n_distinct will be extremely unreliable. -- greg ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
> -Original Message- > From: Josh Berkus [mailto:[EMAIL PROTECTED] > Sent: Wednesday, April 27, 2005 10:25 AM > To: Andrew Dunstan > Cc: Mischa Sandberg; pgsql-perform; pgsql-hackers@postgresql.org > Subject: Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks > suggested? > > [...] > Actually, it's more to characterize how large of a sample > we need. For example, if we sample 0.005 of disk pages, and > get an estimate, and then sample another 0.005 of disk pages > and get an estimate which is not even close to the first > estimate, then we have an idea that this is a table which > defies analysis based on small samples. I buy that. > Wheras if the two estimates are < 1.0 stdev apart, we can > have good confidence that the table is easily estimated. I don't buy that. A negative indication is nothing more than proof by contradiction. A positive indication is mathematical induction over the set, which in this type of context is logically unsound. There is no reason to believe that two small samples with a small difference imply that a table is easily estimated rather than that you got unlucky in your samples. > [...] > Yes, actually. We need 3 different estimation methods: > 1 for tables where we can sample a large % of pages > (say, >= 0.1) > 1 for tables where we sample a small % of pages but are > "easily estimated" > 1 for tables which are not easily estimated by we can't > afford to sample a large % of pages. I don't buy that the first and second need to be different estimation methods. I think you can use the same block sample estimator for both, and simply stop sampling at different points. If you set the default to be a fixed number of blocks, you could get a large % of pages on small tables and a small % of pages on large tables, which is exactly how you define the first two cases. However, I think such a default should also be overridable to a % of the table or a desired accuracy. Of course, I would recommend the distinct sample technique for the third case. > If we're doing sampling-based estimation, I really don't > want people to lose sight of the fact that page-based random > sampling is much less expensive than row-based random > sampling. We should really be focusing on methods which > are page-based. Of course, that savings comes at the expense of having to account for factors like clustering within blocks. So block sampling is more efficient, but can also be less accurate. Nonetheless, I agree that of the sampling estimators, block sampling is the better technique. __ David B. Held Software Engineer/Array Services Group 200 14th Ave. East, Sartell, MN 56377 320.534.3637 320.253.7800 800.752.8129 ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Mischa, > >Perhaps I can save you some time (yes, I have a degree in Math). If I > >understand correctly, you're trying extrapolate from the correlation > >between a tiny sample and a larger sample. Introducing the tiny sample > >into any decision can only produce a less accurate result than just > >taking the larger sample on its own; GIGO. Whether they are consistent > >with one another has no relationship to whether the larger sample > >correlates with the whole population. You can think of the tiny sample > >like "anecdotal" evidence for wonderdrugs. Actually, it's more to characterize how large of a sample we need. For example, if we sample 0.005 of disk pages, and get an estimate, and then sample another 0.005 of disk pages and get an estimate which is not even close to the first estimate, then we have an idea that this is a table which defies analysis based on small samples. Wheras if the two estimates are < 1.0 stdev apart, we can have good confidence that the table is easily estimated. Note that this doesn't require progressively larger samples; any two samples would work. > I'm with Tom though in being very wary of solutions that require even > one-off whole table scans. Maybe we need an additional per-table > statistics setting which could specify the sample size, either as an > absolute number or as a percentage of the table. It certainly seems that > where D/N ~ 0.3, the estimates on very large tables at least are way way > out. Oh, I think there are several other cases where estimates are way out. Basically the estimation method we have doesn't work for samples smaller than 0.10. > Or maybe we need to support more than one estimation method. Yes, actually. We need 3 different estimation methods: 1 for tables where we can sample a large % of pages (say, >= 0.1) 1 for tables where we sample a small % of pages but are "easily estimated" 1 for tables which are not easily estimated by we can't afford to sample a large % of pages. If we're doing sampling-based estimation, I really don't want people to lose sight of the fact that page-based random sampling is much less expensive than row-based random sampling. We should really be focusing on methods which are page-based. -- Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
On Tue, 2005-04-26 at 15:00 -0700, Gurmeet Manku wrote: > 2. In a single scan, it is possible to estimate n_distinct by using > a very simple algorithm: > > "Distinct sampling for highly-accurate answers to distinct value > queries and event reports" by Gibbons, VLDB 2001. > > http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf That looks like the one... ...though it looks like some more complex changes to the current algorithm to use it, and we want the other stats as well... > 3. In fact, Gibbon's basic idea has been extended to "sliding windows" > (this extension is useful in streaming systems like Aurora / Stream): > > "Distributed streams algorithms for sliding windows" > by Gibbons and Tirthapura, SPAA 2002. > > http://home.eng.iastate.edu/~snt/research/tocs.pdf > ...and this offers the possibility of calculating statistics at load time, as part of the COPY command Best Regards, Simon Riggs ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Quoting Andrew Dunstan <[EMAIL PROTECTED]>: > After some more experimentation, I'm wondering about some sort of > adaptive algorithm, a bit along the lines suggested by Marko Ristola, but limited to 2 rounds. > > The idea would be that we take a sample (either of fixed size, or > some small proportion of the table) , see how well it fits a larger sample > > (say a few times the size of the first sample), and then adjust the > formula accordingly to project from the larger sample the estimate for the full population. Math not worked out yet - I think we want to ensure that the result remains bounded by [d,N]. Perhaps I can save you some time (yes, I have a degree in Math). If I understand correctly, you're trying extrapolate from the correlation between a tiny sample and a larger sample. Introducing the tiny sample into any decision can only produce a less accurate result than just taking the larger sample on its own; GIGO. Whether they are consistent with one another has no relationship to whether the larger sample correlates with the whole population. You can think of the tiny sample like "anecdotal" evidence for wonderdrugs. -- "Dreams come true, not free." -- S.Sondheim, ITW ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
> -Original Message- > From: Gurmeet Manku [mailto:[EMAIL PROTECTED] > Sent: Tuesday, April 26, 2005 5:01 PM > To: Simon Riggs > Cc: Tom Lane; josh@agliodbs.com; Greg Stark; Marko Ristola; > pgsql-perform; pgsql-hackers@postgresql.org; Utkarsh Srivastava; > [EMAIL PROTECTED] > Subject: Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks > suggested? > > [...] > 2. In a single scan, it is possible to estimate n_distinct by using > a very simple algorithm: > > "Distinct sampling for highly-accurate answers to distinct value > queries and event reports" by Gibbons, VLDB 2001. > > http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf > > [...] This paper looks the most promising, and isn't too different from what I suggested about collecting stats over the whole table continuously. What Gibbons does is give a hard upper bound on the sample size by using a logarithmic technique for storing sample information. His technique appears to offer very good error bounds and confidence intervals as shown by tests on synthetic and real data. I think it deserves a hard look from people hacking the estimator. __ David B. Held Software Engineer/Array Services Group 200 14th Ave. East, Sartell, MN 56377 320.534.3637 320.253.7800 800.752.8129 ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Simon Riggs wrote: The comment * Every value in the sample appeared more than once. Assume * the column has just these values. doesn't seem to apply when using larger samples, as Josh is using. Looking at Josh's application it does seem likely that when taking a sample, all site visitors clicked more than once during their session, especially if they include home page, adverts, images etc for each page. Could it be that we have overlooked this simple explanation and that the Haas and Stokes equation is actually quite good, but just not being applied? No, it is being aplied. If every value in the sample appears more than once, then f1 in the formula is 0, and the result is then just d, the number of distinct values in the sample. cheers andrew ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Tom Lane wrote: Josh Berkus writes: Overall, our formula is inherently conservative of n_distinct. That is, I believe that it is actually computing the *smallest* number of distinct values which would reasonably produce the given sample, rather than the *median* one. This is contrary to the notes in analyze.c, which seem to think that we're *overestimating* n_distinct. Well, the notes are there because the early tests I ran on that formula did show it overestimating n_distinct more often than not. Greg is correct that this is inherently a hard problem :-( I have nothing against adopting a different formula, if you can find something with a comparable amount of math behind it ... but I fear it'd only shift the failure cases around. The math in the paper does not seem to look at very low levels of q (= sample to pop ratio). The formula has a range of [d,N]. It appears intuitively (i.e. I have not done any analysis) that at very low levels of q, as f1 moves down from n, the formula moves down from N towards d very rapidly. I did a test based on the l_comments field in a TPC lineitems table. The test set has N = 6001215, D = 2921877. In my random sample of 1000 I got d = 976 and f1 = 961, for a DUJ1 figure of 24923, which is too low by 2 orders of magnitude. I wonder if this paper has anything that might help: http://www.stat.washington.edu/www/research/reports/1999/tr355.ps - if I were more of a statistician I might be able to answer :-) cheers andrew ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Josh Berkus wrote: Simon, Tom: While it's not possible to get accurate estimates from a fixed size sample, I think it would be possible from a small but scalable sample: say, 0.1% of all data pages on large tables, up to the limit of maintenance_work_mem. Setting up these samples as a % of data pages, rather than a pure random sort, makes this more feasable; for example, a 70GB table would only need to sample about 9000 data pages (or 70MB). Of course, larger samples would lead to better accuracy, and this could be set through a revised GUC (i.e., maximum_sample_size, minimum_sample_size). I just need a little help doing the math ... please? After some more experimentation, I'm wondering about some sort of adaptive algorithm, a bit along the lines suggested by Marko Ristola, but limited to 2 rounds. The idea would be that we take a sample (either of fixed size, or some small proportion of the table) , see how well it fits a larger sample (say a few times the size of the first sample), and then adjust the formula accordingly to project from the larger sample the estimate for the full population. Math not worked out yet - I think we want to ensure that the result remains bounded by [d,N]. cheers andrew ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Hi everybody! Perhaps the following papers are relevant to the discussion here (their contact authors have been cc'd): 1. The following proposes effective algorithms for using block-level sampling for n_distinct estimation: "Effective use of block-level sampling in statistics estimation" by Chaudhuri, Das and Srivastava, SIGMOD 2004. http://www-db.stanford.edu/~usriv/papers/block-sampling.pdf 2. In a single scan, it is possible to estimate n_distinct by using a very simple algorithm: "Distinct sampling for highly-accurate answers to distinct value queries and event reports" by Gibbons, VLDB 2001. http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/dist_sampl.pdf 3. In fact, Gibbon's basic idea has been extended to "sliding windows" (this extension is useful in streaming systems like Aurora / Stream): "Distributed streams algorithms for sliding windows" by Gibbons and Tirthapura, SPAA 2002. http://home.eng.iastate.edu/~snt/research/tocs.pdf Thanks, Gurmeet Gurmeet Singh Manku Google Inc. http://www.cs.stanford.edu/~manku(650) 967 1890 ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
On Mon, 2005-04-25 at 17:10 -0400, Tom Lane wrote: > Simon Riggs <[EMAIL PROTECTED]> writes: > > On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote: > >> It's not just the scan --- you also have to sort, or something like > >> that, if you want to count distinct values. I doubt anyone is really > >> going to consider this a feasible answer for large tables. > > > Assuming you don't use the HashAgg plan, which seems very appropriate > > for the task? (...but I understand the plan otherwise). > > The context here is a case with a very large number of distinct > values... Yes, but is there another way of doing this other than sampling a larger proportion of the table? I don't like that answer either, for the reasons you give. The manual doesn't actually say this, but you can already alter the sample size by setting one of the statistics targets higher, but all of those samples are fixed sample sizes, not a proportion of the table itself. It seems reasonable to allow an option to scan a higher proportion of the table. (It would be even better if you could say "keep going until you run out of memory, then stop", to avoid needing to have an external sort mode added to ANALYZE). Oracle and DB2 allow a proportion of the table to be specified as a sample size during statistics collection. IBM seem to be ignoring their own research note on estimating ndistinct... > keep in mind also that we have to do this for *all* the > columns of the table. You can collect stats for individual columns. You need only use an option to increase sample size when required. Also, if you have a large table and the performance of ANALYZE worries you, set some fields to 0. Perhaps that should be the default setting for very long text columns, since analyzing those doesn't help much (usually) and takes ages. (I'm aware we already don't analyze var length column values > 1024 bytes). > A full-table scan for each column seems > right out to me. Some systems analyze multiple columns simultaneously. Best Regards, Simon Riggs ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Simon, > Could it be that we have overlooked this simple explanation and that the > Haas and Stokes equation is actually quite good, but just not being > applied? That's probably part of it, but I've tried Haas and Stokes on a pure random sample and it's still bad, or more specifically overly conservative. -- --Josh Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
On Sun, 2005-04-24 at 00:48 -0400, Tom Lane wrote:
> Josh Berkus writes:
> > Overall, our formula is inherently conservative of n_distinct. That is, I
> > believe that it is actually computing the *smallest* number of distinct
> > values which would reasonably produce the given sample, rather than the
> > *median* one. This is contrary to the notes in analyze.c, which seem to
> > think that we're *overestimating* n_distinct.
>
> Well, the notes are there because the early tests I ran on that formula
> did show it overestimating n_distinct more often than not. Greg is
> correct that this is inherently a hard problem :-(
>
> I have nothing against adopting a different formula, if you can find
> something with a comparable amount of math behind it ... but I fear
> it'd only shift the failure cases around.
>
Perhaps the formula is not actually being applied?
The code looks like this...
if (nmultiple == 0)
{
/* If we found no repeated values, assume it's a unique column */
stats->stadistinct = -1.0;
}
else if (toowide_cnt == 0 && nmultiple == ndistinct)
{
/*
* Every value in the sample appeared more than once. Assume
* the column has just these values.
*/
stats->stadistinct = ndistinct;
}
else
{
/*--
* Estimate the number of distinct values using the estimator
* proposed by Haas and Stokes in IBM Research Report RJ 10025:
The middle chunk of code looks to me like if we find a distribution
where values all occur at least twice, then we won't bother to apply the
Haas and Stokes equation. That type of frequency distribution would be
very common in a set of values with very high ndistinct, especially when
sampled.
The comment
* Every value in the sample appeared more than once. Assume
* the column has just these values.
doesn't seem to apply when using larger samples, as Josh is using.
Looking at Josh's application it does seem likely that when taking a
sample, all site visitors clicked more than once during their session,
especially if they include home page, adverts, images etc for each page.
Could it be that we have overlooked this simple explanation and that the
Haas and Stokes equation is actually quite good, but just not being
applied?
Best Regards, Simon Riggs
---(end of broadcast)---
TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
> -Original Message- > From: Andrew Dunstan [mailto:[EMAIL PROTECTED] > Sent: Monday, April 25, 2005 3:43 PM > To: josh@agliodbs.com > Cc: pgsql-perform; pgsql-hackers@postgresql.org > Subject: Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks > suggested? > > Josh Berkus wrote: > > >Simon, Tom: > > > >While it's not possible to get accurate estimates from a > >fixed size sample, I think it would be possible from a > >small but scalable sample: say, 0.1% of all data pages on > >large tables, up to the limit of maintenance_work_mem. Note that the results obtained in the cited paper were obtained from samples of 5 and 10%. It should also warrant caution that the authors don't offer any proofs of confidence bounds, even for the "average" case. > [...] > After some more experimentation, I'm wondering about some > sort of adaptive algorithm, a bit along the lines suggested > by Marko Ristola, but limited to 2 rounds. One path might be to use the published algorithm and simply recompute the statistics after every K blocks are sampled, where K is a reasonably small number. If it looks like the statistics are converging on a value, then take a few more samples, check against the trend value and quit. Otherwise continue until some artificial limit is reached. > The idea would be that we take a sample (either of fixed > size, or some small proportion of the table), see how well > it fits a larger sample (say a few times the size of the > first sample), and then adjust the formula accordingly to > project from the larger sample the estimate for the full > population. Math not worked out yet - I think we want to > ensure that the result remains bounded by [d,N]. The crudest algorithm could be something like the Newton- Ralphson method for finding roots. Just adjust the predicted value up or down until it comes within an error tolerance of the observed value for the current sample. No need to choose powers of 2, and I would argue that simply checking every so often on the way to a large sample that can be terminated early is more efficient than sampling and resampling. Of course, the crude algorithm would almost certainly be I/O bound, so if a more sophisticated algorithm would give a better prediction by spending a few more CPU cycles on each sample block gathered, then that seems like a worthwhile avenue to pursue. As far as configuration goes, the user is most likely to care about how long it takes to gather the statistics or how accurate they are. So it would probably be best to terminate the sampling process on a user-defined percentage of the table size and the minimum error tolerance of the algorithmic prediction value vs. the computed sample value. If someone wants a fast and dirty statistic, they set the row percent low and the error tolerance high, which will effectively make the blocks read the limiting factor. If they want an accurate statistic, they set the row percent as high as they feel they can afford, and the error tolerance as low as they need to in order to get the query plans they want. __ David B. Held Software Engineer/Array Services Group 200 14th Ave. East, Sartell, MN 56377 320.534.3637 320.253.7800 800.752.8129 ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Simon Riggs <[EMAIL PROTECTED]> writes: > On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote: >> It's not just the scan --- you also have to sort, or something like >> that, if you want to count distinct values. I doubt anyone is really >> going to consider this a feasible answer for large tables. > Assuming you don't use the HashAgg plan, which seems very appropriate > for the task? (...but I understand the plan otherwise). The context here is a case with a very large number of distinct values... keep in mind also that we have to do this for *all* the columns of the table. A full-table scan for each column seems right out to me. regards, tom lane ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
> -Original Message-
> From: Josh Berkus [mailto:[EMAIL PROTECTED]
> Sent: Sunday, April 24, 2005 2:08 PM
> To: Andrew Dunstan
> Cc: Tom Lane; Greg Stark; Marko Ristola; pgsql-perform;
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks
> suggested?
>
> [...]
> Actually, that paper looks *really* promising. Does anyone here have
> enough math to solve for D(sub)Md on page 6? I'd like to test it on
> samples of < 0.01%.
> [...]
D_Md = [1 - sqrt(f_1 / s)] D_b + sqrt(f_1 / s) D_B
s = block size
f~_1 = median frequency within blocks for distinct values occurring in
only one block
D_b = d + f_1^(b+1)
d = distinct classes in the sample
f_1^(b+1) = number of distinct values occurring in a single block in
a sample of b+1 blocks
D_B = d + [B / (b + 1)] f_1^(b+1)
b = sample size (in blocks)
B = total table size (in blocks)
f_k and f~_k are the only tricky functions here, but they are easy to
understand:
Suppose our column contains values from the set {a, b, c, ..., z}.
Suppose we have a sample of b = 10 blocks.
Suppose that the value 'c' occurs in exactly 3 blocks (we don't care
how often it occurs *within* those blocks).
Suppose that the value 'f' also occurs in exactly 3 blocks.
Suppose that the values 'h', 'p', and 'r' occur in exactly 3 blocks.
Suppose that no other value occurs in exactly 3 blocks.
f_3^b = 5
This is because there are 5 distinct values that occur in exactly
3 blocks. f_1^b is the number of distinct values that occur in
exactly 1 block, regardless of how often it occurs within that block.
Note that when you select a sample size of b blocks, you actually
need to sample b+1 blocks to compute f_1^(b+1). This is actually
pedantry since all occurrences of b in the formula are really b+1.
f~ is slightly trickier. First, we pick the distinct values that
occur in only one block. Then, we count how often each value
occurs within its block. To wit:
Suppose we have a set {d, q, y, z} of values that occur in only
one block.
Suppose that d occurs 3x, q occurs 1x, y occurs 8x, and z occurs 6x.
The function f- would take the mean of these counts to determine
the "cluster frequency". So f- here would be 4.5. This allows
one to compute D_MF.
The function f~ takes the median of this sample, which is 3 or 6
(or I suppose you could even take the mean of the two medians if
you wanted).
No tricky math involved. That should be enough to tell you how to
write the estimator.
__
David B. Held
Software Engineer/Array Services Group
200 14th Ave. East, Sartell, MN 56377
320.534.3637 320.253.7800 800.752.8129
---(end of broadcast)---
TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Guys, > While it's not possible to get accurate estimates from a fixed size sample, > I think it would be possible from a small but scalable sample: say, 0.1% of > all data pages on large tables, up to the limit of maintenance_work_mem. BTW, when I say "accurate estimates" here, I'm talking about "accurate enough for planner purposes" which in my experience is a range between 0.2x to 5x. -- --Josh Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Simon, Tom: While it's not possible to get accurate estimates from a fixed size sample, I think it would be possible from a small but scalable sample: say, 0.1% of all data pages on large tables, up to the limit of maintenance_work_mem. Setting up these samples as a % of data pages, rather than a pure random sort, makes this more feasable; for example, a 70GB table would only need to sample about 9000 data pages (or 70MB). Of course, larger samples would lead to better accuracy, and this could be set through a revised GUC (i.e., maximum_sample_size, minimum_sample_size). I just need a little help doing the math ... please? -- --Josh Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
On Mon, 2005-04-25 at 11:23 -0400, Tom Lane wrote: > Simon Riggs <[EMAIL PROTECTED]> writes: > > My suggested hack for PostgreSQL is to have an option to *not* sample, > > just to scan the whole table and find n_distinct accurately. > > ... > > What price a single scan of a table, however large, when incorrect > > statistics could force scans and sorts to occur when they aren't > > actually needed ? > > It's not just the scan --- you also have to sort, or something like > that, if you want to count distinct values. I doubt anyone is really > going to consider this a feasible answer for large tables. Assuming you don't use the HashAgg plan, which seems very appropriate for the task? (...but I understand the plan otherwise). If that was the issue, then why not keep scanning until you've used up maintenance_work_mem with hash buckets, then stop and report the result. The problem is if you don't do the sort once for statistics collection you might accidentally choose plans that force sorts on that table. I'd rather do it once... The other alternative is to allow an ALTER TABLE command to set statistics manually, but I think I can guess what you'll say to that! Best Regards, Simon Riggs ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Simon Riggs <[EMAIL PROTECTED]> writes: > My suggested hack for PostgreSQL is to have an option to *not* sample, > just to scan the whole table and find n_distinct accurately. > ... > What price a single scan of a table, however large, when incorrect > statistics could force scans and sorts to occur when they aren't > actually needed ? It's not just the scan --- you also have to sort, or something like that, if you want to count distinct values. I doubt anyone is really going to consider this a feasible answer for large tables. regards, tom lane ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Josh Berkus writes: > Tom, how does our heuristic sampling work? Is it pure random sampling, or > page sampling? Manfred probably remembers better than I do, but I think the idea is to approximate pure random sampling as best we can without actually examining every page of the table. regards, tom lane ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Folks, > I wonder if this paper has anything that might help: > http://www.stat.washington.edu/www/research/reports/1999/tr355.ps - if I > were more of a statistician I might be able to answer :-) Actually, that paper looks *really* promising. Does anyone here have enough math to solve for D(sub)Md on page 6? I'd like to test it on samples of < 0.01%. Tom, how does our heuristic sampling work? Is it pure random sampling, or page sampling? -- Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Andrew, > The math in the paper does not seem to look at very low levels of q (= > sample to pop ratio). Yes, I think that's the failing. Mind you, I did more testing and found out that for D/N ratios of 0.1 to 0.3, the formula only works within 5x accuracy (which I would consider acceptable) with a sample size of 25% or more (which is infeasable in any large table).The formula does work for populations where D/N is much lower, say 0.01. So overall it seems to only work for 1/4 of cases; those where n/N is large and D/N is low. And, annoyingly, that's probably the population where accurate estimation is least crucial, as it consists mostly of small tables. I've just developed (not original, probably, but original to *me*) a formula that works on populations where n/N is very small and D/N is moderate (i.e. 0.1 to 0.4): N * (d/n)^(sqrt(N/n)) However, I've tested it only on (n/N < 0.005 and D/N > 0.1 and D/N < 0.4) populations, and only 3 of them to boot. I'd appreciate other people trying it on their own data populations, particularly very different ones, like D/N > 0.7 or D/N < 0.01. Further, as Andrew points out we presumably do page sampling rather than purely random sampling so I should probably read the paper he referenced. Working on it now -- Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Here is my opinion. I hope this helps. Maybe there is no one good formula: On boolean type, there are at most 3 distinct values. There is an upper bound for fornames in one country. There is an upper bound for last names in one country. There is a fixed number of states and postal codes in one country. On the other hand, with timestamp, every value could be distinct. A primary key with only one column has only distinct values. If the integer column refers with a foreign key into another table's only primary key, we could take advantage of that knolege. A column with a unique index has only distinct values. First ones are for classifying and the second ones measure continuous or discrete time or something like the time. The upper bound for classifying might be 3 (boolean), or it might be one million. The properties of the distribution might be hard to guess. Here is one way: 1. Find out the number of distinct values for 500 rows. 2. Try to guess, how many distinct values are for 1000 rows. Find out the real number of distinct values for 1000 rows. 3. If the guess and the reality are 50% wrong, do the iteration for 2x1000 rows. Iterate using a power of two to increase the samples, until you trust the estimate enough. So, in the phase two, you could try to guess with two distinct formulas: One for the classifying target (boolean columns hit there). Another one for the timestamp and numerical values. If there are one million classifications on one column, how you can find it out, by other means than checking at least two million rows? This means, that the user should have a possibility to tell the lower bound for the number of rows for sampling. Regards, Marko Ristola Tom Lane wrote: Josh Berkus writes: Overall, our formula is inherently conservative of n_distinct. That is, I believe that it is actually computing the *smallest* number of distinct values which would reasonably produce the given sample, rather than the *median* one. This is contrary to the notes in analyze.c, which seem to think that we're *overestimating* n_distinct. Well, the notes are there because the early tests I ran on that formula did show it overestimating n_distinct more often than not. Greg is correct that this is inherently a hard problem :-( I have nothing against adopting a different formula, if you can find something with a comparable amount of math behind it ... but I fear it'd only shift the failure cases around. regards, tom lane ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Josh Berkus writes: > Overall, our formula is inherently conservative of n_distinct. That is, I > believe that it is actually computing the *smallest* number of distinct > values which would reasonably produce the given sample, rather than the > *median* one. This is contrary to the notes in analyze.c, which seem to > think that we're *overestimating* n_distinct. Well, the notes are there because the early tests I ran on that formula did show it overestimating n_distinct more often than not. Greg is correct that this is inherently a hard problem :-( I have nothing against adopting a different formula, if you can find something with a comparable amount of math behind it ... but I fear it'd only shift the failure cases around. regards, tom lane ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] [PERFORM] Bad n_distinct estimation; hacks suggested?
Josh Berkus said: > > > Well, unusual distributions are certainly tough. But I think the > problem exists even for relatively well-distributed populations. > Part of it is, I believe, the formula we are using: > > n*d / (n - f1 + f1*n/N) > [snip] > > This is so broken, in fact, that I'm wondering if we've read the paper > right? I've perused the paper on almaden, and the DUJ1 formula > appears considerably more complex than the formula we're using. > > Can someone whose math is more recent than calculus in 1989 take a look > at that paper, and look at the formula toward the bottom of page 10, > and see if we are correctly interpreting it?I'm particularly > confused as to what "q" and "d-sub-n" represent. Thanks! > Math not too recent ... I quickly read the paper and independently came up with the same formula you say above we are applying. The formula is on the page that is numbered 6, although it's the tenth page in the PDF. q = n/N = ratio of sample size to population size d_sub_n = d = number of distinct classes in sample cheers andrew ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
