Multiple-Key Access

1. For some queries, it is advantageous to use multiple indices if they exist.
2. If there are two indices on deposit, one on bname and one on cname, then suppose we have a query like

    aaaaaaaaaaaa¯select balance
   
   		 from deposit
   
   		 where bname = ``Perryridge'' and balance = 1000
   
   

3. There are 3 possible strategies to process this query:
   • Use the index on bname to find all records pertaining to Perryridge branch. Examine them to see if balance = 1000
   • Use the index on balance to find all records pertaining to Williams. Examine them to see if bname = ``Perryridge''.
   • Use index on bname to find pointers to records pertaining to Perryridge branch. Use index on balance to find pointers to records pertaining to 1000. Take the intersection of these two sets of pointers.
4. The third strategy takes advantage of the existence of multiple indices. This may still not work well if
   • There are a large number of Perryridge records AND
   • There are a large number of 1000 records AND
   • Only a small number of records pertain to both Perryridge and 1000.
5. To speed up multiple search key queries special structures can be maintained.

• Grid File
• Partitioned Hashing