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

   

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 cname = ``Williams''.
   • Use the index on cname 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 cname to find pointers to records pertaining to Williams. 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 Williams records AND
   • Only a small number of records pertain to both Perryridge and Williams.
5. To speed up multiple search key queries special structures can be maintained.

• Grid Structure
• Partitioned Hash Function