Extent based Sampling

The solution to the above problem is to use Acceptance/Rejectance Sampling

• Allows the algorithm to pick a tuple from the page with a probability
  Pr = No. of tuples in page / Max No. of tuples in a page
• Therefore No. of I/Os required to fetch a random tuple is
  No. of I/Os is proportional to 1 / Fill Factor