From: Stavan Parikh (stavan@cs.washington.edu)
Date: Sun May 23 2004 - 18:57:43 PDT
Chaudari summarizes the major query optimization techniques in databases.
The author first identifies the three main issues an optimizer faces - including low-cost plans in the search space, using an accurate cost estimation technique, and efficiency of enumerating possible plans. Chaudari confirms that System R presented major techniques that are used in databases even today; mainly the idea of dynamic programming and use of 'interesting' ordering.
The majority of the article focuses on search space. First he discusses algebraic transformations like generalizing of join sequencing, reordering of normal and outer joins, and order of processing (group-by vs. join). Then he discusses handling of mult-block queries by flattening of queries. Then there is a brief look at cost estimation using statistics on the entire data set and statistics on data within an index. Finally the article look at a variety of advanced techniques like distributed databases and support for user defined functions. He also points out that using materialized views is still in its infancy.
I'm not sure what the takeaway of the paper was other than the fact that query optimization is a complex problem with many different components that all need to be handled well to get to an optimal solution. The article does a good job of discussing the search space issues, however for the rest of the discussion there is a lack of depth. It would have been more useful to just focus on 1 or 2 of the issues and provide a more detailed look at each.
This archive was generated by hypermail 2.1.6 : Sun May 23 2004 - 18:57:43 PDT