Week 07 Lecture (39)

N-d Queries and Indexes (cont)

Implementing selection using one of several indices:

// Query: select * from R where a₁op₁C₁ and ... and a_nop_nC_n
// choose a_i with best selectivity
TupleIDs = IndexLookup(R,a_i,op_i,C_i)
// gives { tid₁, tid₂, ...} for tuples satisfying a_iop_iC_i
PageIDs = { }
foreach tid in TupleIDs
   { PageIDs = PageIDs ∪ {pageOf(tid)} }

// PageIDs = a set of b_{q_ix} page numbers
...

Cost = Cost_index + b_{q_ix} (some pages do not contain answers, b_{q_ix} > b_q)

DBMSs typically maintain statistics to assist with determining selectivity