[prev] 13 [next]

Query Cost for SIMC

Cost to answer pmr query: Costpmr = bD + bq
  • read r descriptors on bD descriptor pages
  • then read bq data pages and check for matches
bD = ceil( r/cD )  and  cD = floor(B/ceil(m/8))

E.g. m=64,   B=8192,   r=104    ⇒    cD = 1024,   bD=10

bq includes pages with rq matching tuples and rF false matches

Expected false matches = rF  =  (r - rq).pF  ≅  r.pF   if rq ≪ r

E.g. Worst bq = rq+rF,   Best bq = 1,   Avg bq = ceil(b(rq+rF)/r)