[prev] 64 [next]

Query Cost for MA.Hashing (cont)

Consider a query of type Q with m attributes unspecified.

Each unspecified Ai contributes di *'s.

Total number of *'s is   s  =  ∑i ∉ Q di.

Number of pages to read is   2s  =  ∏i ∉ Q 2di.

Ignoring overflows, Cost(Q) = 2s    (where s is determined by Q)

Including overflows, Cost(Q) = 2s(1+Ov)