Query Interpretation

Posted By on December 12, 2014

Download PDF
Measures of query cost

Query Interpretation

  1. Why do we need to optimize?
    • A high-level relational query is generally non-procedural in nature.
    • It says “what”, rather than “how” to find it.
    • When a query is presented to the system, it is useful to find an efficient method of finding the answer, using the existing database structure.
    • Usually worthwhile for the system to spend some time on strategy selection.
    • Typically can be done using information in main memory, with little or no disk access.
    • Execution of the query will require disk accesses.
    • Transfer of data from disk is slow, relative to the speed of main memory and the CPU
    • It is advantageous to spend a considerable amount of processing to save disk accesses.
  2. Do we really optimize?
    • Optimizing means finding the best of all possible methods.
    • The term “optimization” is a bit of a misnomer here.
    • Usually the system does not calculate the cost of all possible strategies.
    • Perhaps “query improvement” is a better term.
  3. Two main approaches:
    1. Rewriting the query in a more effective manner.
    2. Estimating the cost of various execution strategies for the query.

    Usually both strategies are combined.

    • The difference in execution time between a good strategy and a bad one may be huge.
    • Thus this is an important issue in any DB system.
    • In network and hierarchical systems, optimization is left for the most part to the application programmer.
    • Since the DML language statements are embedded in the host language, it is not easy to transform a hierarchical or network query to another one, unless one has knowledge about the entire application program.
    • As a relational query can be expressed entirely in a relational query language without the use of a host language, it is possible to optimize queries automatically.
    • SQL is suitable for human use, but internally a query should be represented in a more useful form, like the relational algebra.
  4. So, first the system must translate the query into its internal form. Then optimization begins:
    • Find an equivalent expression that is more efficient to execute.
    • Select a detailed strategy for processing the query. (Choose specific indices to use, and order in which tuples are to be processed, etc.)
  5. Final choice of a strategy is based primarily on the number of disk accesses required.


Measures of query cost

Download PDF

Posted by