[prev] 47 [next]

Hashing and pmr

For a pmr query like 

select * from R where a1 = C1 and ... and an = Cn

  • if one ai is the hash key, query is very efficient
  • if no ai is the hash key, need to use linear scan
Can be alleviated using multi-attribute hashing (mah)
  • form a composite hash value involving all attributes
  • at query time, some components of composite hash are known
    (allows us to limit the number of data pages which need to be checked)
MA.hashing works in conjunction with any dynamic hash scheme.