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:

Reply via email to