[prev] 14 [next]

Exercise 1: SIMC Query Cost

Consider a SIMC-indexed database with the following properties
  • all pages are B = 8192 bytes
  • tuple descriptors have m = 64 bits ( = 8 bytes)
  • total records r = 102,400,   records/page c = 100
  • false match probability pF = 1/1000
  • answer set has 1000 tuples from 100 pages
  • 90% of false matches occur on data pages with true match
  • 10% of false matches are distributed 1 per page
Calculate the total number of pages read in answering the query.