Extent based Sampling

• Doesn't require index on any key
• Assumes pages are allocated in contiguous units called extents
• Information about where a page of the file is stored by linking together extents in a small memory resident structure.
• Random pages are selected by choosing a random number r between 1 and the number of pages in the relation and walking down the (linked) extent list.
• Random tuples in a page are selected by choosing one of the tuples in the page.
  
  
  
• PROBLEM - This method would choose a random page unbiasedly only if the pages in the relation have an identical number of tuples each.