[prev] 43 [next]

N-d Queries and Indexes (cont)

If using just one of several indexes, which one to use? 

select * from R
where  a1 op1 C1 and ... and an opn Cn

The one with best selectivity for ai opi Ci   (i.e. fewest matches)

Factors determining selectivity of ai opi Ci

  • assume uniform distribution of values in dom(ai)
  • equality test on primary key gives at most one match
  • equality test on larger dom(ai) ⇒ less matches
  • range test over large part of dom(ai) ⇒ many matches