Re: [HACKERS] [GENERAL] Large DB
Manfred Koizar [EMAIL PROTECTED] writes: What I have in mind is a kind of Double Vitter algorithm. Whatever we do to get our sample of rows, in the end the sampled rows come from no more than sample_size different blocks. So my idea is to first create a random sample of sample_size block numbers, and then to sample the rows out of this pool of blocks. That assumption is faulty, though --- consider wholly-empty pages. A bigger problem is that this makes the sampling quite nonuniform, because rows that are on relatively low-density pages would be more likely to become part of the final sample than rows that are on pages with lots of tuples. Thus for example your sample would tend to favor rows with wide values of variable-width columns and exclude narrower values. (I am not certain that the existing algorithm completely avoids this trap, but at least it tries.) regards, tom lane ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html
Re: [HACKERS] [GENERAL] Large DB
On Fri, 02 Apr 2004 14:48:13 -0500, Tom Lane [EMAIL PROTECTED] wrote: Manfred Koizar [EMAIL PROTECTED] writes: What I have in mind is a kind of Double Vitter algorithm. [...] random sample of sample_size block numbers, and then to sample the rows out of this pool of blocks. That assumption is faulty, though --- consider wholly-empty pages. A bigger problem is that this makes the sampling quite nonuniform, because rows that are on relatively low-density pages would be more likely to become part of the final sample than rows that are on pages with lots of tuples. This sounds like you are assuming that I want to take exactly one tuple out of each block of the block sample. This is not the case. In the second round I plan to apply the same (or a better) Vitter method as it is done now. The main difference is that blocks will be adressed indirectly through the array of block numbers obtained in the first round. Thus for example your sample would tend to favor rows with wide values of variable-width columns and exclude narrower values. (I am not certain that the existing algorithm completely avoids this trap, but at least it tries.) I'm reading 7.4 source code and I fail to see how it does this. If the relation starts with an atypical distribution of wide/narrow or dead/alive tuples, a wrong value for tuplesperpage is used for the rest of the sampling. Tuples immediately following one or more dead tuples have a better chance of being selected. This may be called as random as anything else and not favouring a special property. OTOH after long runs of dead tuples consecutive tuples are likely to be selected. Your comment about nonuniformity above exactly describes the current algorithm: Once the initial sample is fetched and tuplesperpage is determined, targpos is computed without any further feedback. If targpos points to a sparsely populated area (with wide tuples or with many dead tuples) tuples in this area are more likely to get into the sample than tuples in densely populated areas (with many small active tuples). I think that cutting down the number of blocks to be looked at does not affect these problems. Servus Manfred ---(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] [GENERAL] Large DB
Manfred Koizar [EMAIL PROTECTED] writes: On Fri, 02 Apr 2004 14:48:13 -0500, Tom Lane [EMAIL PROTECTED] wrote: A bigger problem is that this makes the sampling quite nonuniform, because rows that are on relatively low-density pages would be more likely to become part of the final sample than rows that are on pages with lots of tuples. This sounds like you are assuming that I want to take exactly one tuple out of each block of the block sample. This is not the case. No, I understood that you wanted to resample, but [ ... thinks for awhile ... ] hmm, now I can't construct a failure case either. I must have done the math wrong before. There's still a risk of not being able to collect N rows out of N blocks, if you are unfortunate enough to select a lot of wholly-empty pages. But that seems like a low-probability scenario; besides such a table would be so desperately in need of VACUUM FULL that the possible low quality of the stats hardly matters. You should not need to use the Vitter algorithm for the block-level selection, since you can know the number of blocks in the table in advance. You can just use the traditional method of choosing each block or not with probability (k/K), where k = number of sample blocks still needed, K = number of blocks from here to the end. You'd run the Vitter algorithm separately to decide whether to keep or discard each live row you find in the blocks you read. I do like this, since it eliminates the current method's bias towards estimating the number of live rows from the density found near the start of the table only. At the end you'd know the total number of live rows on all the pages you read, and it's reasonable to extrapolate that total to the full table size. Question: if the table size is less than N blocks, are you going to read every block or try to reduce the number of blocks sampled? If you don't adjust the sample size then I think this would perform worse for intermediate-size tables than the current method does ... perhaps not so much at sample size = 3000, but at larger sizes it would hurt. A lot of people are setting the stats target to 100 which means a sample size of 3 --- how do the page-access counts look in that case? regards, tom lane ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] [GENERAL] Large DB
On Fri, 02 Apr 2004 18:06:12 -0500, Tom Lane [EMAIL PROTECTED] wrote: You should not need to use the Vitter algorithm for the block-level selection, since you can know the number of blocks in the table in advance. You can just use the traditional method of choosing each block or not with probability (k/K), where k = number of sample blocks still needed, K = number of blocks from here to the end. Sounds reasonable. I have to play around a bit more to get a feeling where the Vitter method gets more efficient. You'd run the Vitter algorithm separately to decide whether to keep or discard each live row you find in the blocks you read. You mean once a block is sampled we inspect it in any case? This was not the way I had planned to do it, but I'll keep this idea in mind. Question: if the table size is less than N blocks, are you going to read every block or try to reduce the number of blocks sampled? Don't know yet. people are setting the stats target to 100 which means a sample size of 3 --- how do the page-access counts look in that case? rel | page size | reads --+- 300 | 300 3000 | 3000 5000 | 4999 10K | 9.9K 30K | 25.8K 300K | 85K 1M | 120K 10M | 190K 100M | 260K 1G | 330K This is exactly the table I posted before (for sample size 3000) with every entry multiplied by 10. Well, not quite exactly, but the differences are far behind the decimal point. So for our purposes, for a given relation size the number of pages accessed is proportional to the sample size. Servus Manfred ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] [GENERAL] Large DB
Manfred Koizar [EMAIL PROTECTED] writes: You'd run the Vitter algorithm separately to decide whether to keep or discard each live row you find in the blocks you read. You mean once a block is sampled we inspect it in any case? This was not the way I had planned to do it, but I'll keep this idea in mind. Well, once we've gone to the trouble of reading in a block we definitely want to count the tuples in it, for the purposes of extrapolating the total number of tuples in the relation. Given that, I think the most painless route is simply to use the Vitter algorithm with the number-of-tuples-scanned as the count variable. You could dump the logic in acquire_sample_rows that tries to estimate where to read the N'th tuple from. If you like I can send you the Vitter paper off-list (I have a PDF of it). The comments in the code are not really intended to teach someone what it's good for ... regards, tom lane ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [HACKERS] [GENERAL] Large DB
On Fri, 02 Apr 2004 19:57:47 -0500, Tom Lane [EMAIL PROTECTED] wrote: If you like I can send you the Vitter paper off-list (I have a PDF of it). The comments in the code are not really intended to teach someone what it's good for ... Yes, please. [Would have sent this off-list. But I'm blacklisted.] Servus Manfred ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [HACKERS] [GENERAL] Large DB
[time to move this to -hackers] On Fri, 02 Apr 2004 11:16:21 -0500, Tom Lane [EMAIL PROTECTED] wrote: Manfred Koizar [EMAIL PROTECTED] writes: The first step, however, (acquire_sample_rows() in analyze.c) has to read more rows than finally end up in the sample. It visits less than O(nblocks) pages but certainly more than O(1). A vague feeling tries to tell me that the number of page reads is somehow related to the harmonic numbers 1 + 1/2 + 1/3 + ... + 1/n, which grow like O(ln(n)). Good guess. Vitter's paper says the expected time to sample n rows from a table of size N is O(n * (1 + log(N/n))). Well, for what I tried to find out my wild guess seems to be wrong. I don't doubt that Vitter's formula is correct, but it assumes that access to any tuple has the same cost. This does not apply to our problem, however. With 100 tuples per page, we access the first sample_size tuples at a cost of 0.01 sequential page reads per tuple. Later we use less and less tuples per page which results in higher per-tuple-cost. Near the end of a large relation we can expect to access only one tuple per page and more and more pages are skipped, so that prefetching doesn't help any more. Playing around with some real numbers (for 100 tuples/page and a sample size of 3000) I got: rel | page size | reads --+- 30 |30 300 | 300expectation is something like 299.9995 500 | 499 1K | 990 3K | 2.6K 30K |8K 100K | 12K 1M | 19K 10M | 26K 100M | 33K This growth rate is steeper than O(log(nblocks)). I have an idea how this could be done with O(1) page reads. What I have in mind is a kind of Double Vitter algorithm. Whatever we do to get our sample of rows, in the end the sampled rows come from no more than sample_size different blocks. So my idea is to first create a random sample of sample_size block numbers, and then to sample the rows out of this pool of blocks. I have to think harder though, what to do about those 400 pages that are not accessed when the sample size is 3000 ... The hard part is getting a genuinely random sample when we don't know N in advance. We do however know the table size in blocks, so if you're willing to make assumptions about constant tuple density you could do something different. (But the tuple density assumption is exactly the weak spot of what we've got, so I'm unconvinced that would be a big step forward.) Starting the scan at some random blocks should help against the common case of unusual distribution of dead tuples near the start of the relation. And I plan to factor information about dead tuple hits into an increasingly better estimation of dead/live tuple ratio. Servus Manfred ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
