Review

I consider this survey paper to be a perfect followup to the classic Selinger "Access Path Selection" paper [2] for anyone who wants to learn the detailed fundamentals of query processing and optimization. The Graefe paper is long and can be tedious to read and understand completely, but it includes a quite modern treatment of query processing issues and almost entirely complements the material in the Selinger paper. Things I like about the paper include its nice explanation of iterators, its formalization of sorting and hashing techniques, the way it develops shared building blocks and uses them to explain execution techniques for different operations, and its attention to "esoteric" but important operations such as universal quantification. Not being a connoisseur of parallel databases, I tend to skim Sections 9 and 10 of the paper (as well as the less mainstream Sections 11 and 12), but I expect that these sections also provide an excellent foundation for folks who want to learn the areas addressed.

Jeff Ullman will chastise me if he sees this review, because much of the material in the Graefe paper has found its way into our recent textbook on database system implementation [3] (with Hector Garcia-Molina). Jeff would contend that the textbook is the place to learn the basics. However, the Graefe paper does go at least one step beyond the textbook in terms of details and breadth, evidenced by the fact that the paper remains on the reading list for our Ph.D. qualifying exam in databases at Stanford, and I use it in my advanced database system implementation course.

The paper also provides an excellent bibliography for publications in the area of query processing and optimization, albeit only up to 1993.