From: Ankur Jain (ankur@cs.washington.edu)
Date: Mon May 24 2004 - 10:19:06 PDT
An Overview of Query Optimization in Relational Systems - Surajit Chaudhuri
This paper discusses the various techniques used for query optimizing in the different components of the optimizer engine.
The author starts by discussing some of the more common transformations that are used for potentially optimizing costs
and the search space hence constructed. Over here, he discusses interesting transformations like those based on
commutativity, and the ones related to multi-block queries (I couldn't understand the example though that illustrates the
need to do LOJ in the bottom half of the left column of the 5th page).
In the section on statistics and cost estimation, I liked the idea of using histograms to decide class sizes to group
data in. Having the extensible optimizer paradigm as proposed in the section that followed was also nice as it
provides the flexibility to change the other components of the optimizer engine rather gracefully.
I found it very interesting to see that the overall structure of most query optimizers is still more or less
as it was proposed in System R. All of them use transformations to populate the search space and then use
logical( relation statistics) and physical(I/O and processor costs) properties to find the one which they think is the
least expensive. It would be interesting to know if there are some other techniques - inspired from the various
AI search strategies - that have been used in this context.
This archive was generated by hypermail 2.1.6 : Mon May 24 2004 - 10:19:06 PDT