On May10, 2012, at 10:43 , Qi Huang wrote: > 2. use TIDSCAN to directly access tuples. The below way of using ctid > proposed by Kevin looks good. > > -One technique which might be suitably random without reading the > -whole table would be to figure out a maximum block number and tuple > -ID for the table, and generate a series of random ctid values to > -read. If the tuple doesn't exist or is not visible to the snapshot, > -you ignore it and continue, until you have read the requisite number > -of rows. You could try to generate them in advance and sort them by > -block number, but then you need to solve the problems of what to do > -if that set of ctids yields too many rows or too few rows, both of > -which have sticky issues.
> I think this technique could be considered as an implementation algo for > BERNOULLI method. It looks that it could still reduce a lot of cost compared > to just assign random number to every tuple and then retrieve. One problem I see with this approach is that its efficiency depends on the average tuple length, at least with a naive approach to random ctid generator. The simplest way to generate those randomly without introducing bias is to generate a random page index between 0 and the relation's size in pages, and then generate random tuple index between 0 and MaxHeapTuplesPerPage, which is 291 on x86-64 assuming the standard page size of 8k. The current toasting threshold (TOAST_TUPLE_THRESHOLD) is approximately 2k, so having tables with an average heap tuple size of a few hundred bytes doesn't seem unlikely. Now, assume the average tuple length is 128 bytes, i.e. on average you'll have ~ 8k/128 = 64 live tuples / page if the fill factor is 100% and all tuples are live. To account for lower fill factors and dead tuples, let's thus say there are 50 live tuples / page. Then, on average, only every 6th randomly generated ctid will point to a live tuple. But whether or not it does can only be decided after reading the page from disk, so you end up with a rate of 6 random-access reads per returned tuple. IIRC, the cutoff point where an index scan loses compared to a sequential scan is somewhere around 10% of the table read, i.e. if a predicate selects more than 10% of the available rows, a sequential scan is more efficient than an index scan. Scaling that with the 1/6-th success rate from above means that Kevin's approach would only beat a sequential scan if the sampling percentage isn't much larger than 1%, assuming an average row size of 128 bytes. The algorithm still seems like a good choice for very small sampling percentages, though. best regards, Florian Pflug -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
