next up previous
Next: Join Strategies Up: Query Processing Previous: Estimation of Query-Processing Cost

Estimation of Access Costs Using Indices

  1. So far, we haven't considered the effects of indices and hash functions on the cost of evaluating an expression.

  2. Detailed strategy for processing a query is called the access plan. This includes not only the relational operations to be performed, but also the indices to be used and the order in which tuples are to be accessed and the order in which operations are to be performed.
  3. The use of indices imposes some overhead (access to blocks containing the index.) We also must take this into account in computing cost of a strategy.
  4. We'll look at the query

     select account#

    from deposit

    where bname = ``Perryridge''

    and cname = ``Williams''

    and balance > 1000

  5. We assume the following statistical information is kept about the deposit relation:
  6. We also assume the following indices exist on deposit:
  7. We also still assume values are distributed uniformly.

    So the above strategy requires 12 block reads.
  8. Note: another way of calculating the number of levels in a tex2html_wrap_inline1046 -tree is to remember that the height is no greater than


    where there are K search key values in the relation, and n is the number of pointers in a node.

  9. You can use the change of base formula to calculate this value using a log function of base x with your calculator:


  10. If we use the index for cname, we estimate the number of block accesses as follows:
  11. If both indices were non-clustering, which one would we choose?
  12. Another interesting method is to look at pointers first:
  13. We didn't use the balance attribute as a starting point because there is no index for balance and also the predicate involves a ``greater than'' comparison (> 1000).
  14. Generally, equality predicates are more selective than ``greater than'' predicates, as they return fewer tuples.
  15. Estimation of access cost using indices allows us to estimate the complete cost, in terms of block accesses, of a plan. It is often worthwhile for a large number of strategies to be evaluated down to the access plan level before a choice is made.

next up previous
Next: Join Strategies Up: Query Processing Previous: Estimation of Query-Processing Cost

Osmar Zaiane
Sun Jul 26 17:45:14 PDT 1998