Optimization and execution techniques for queries with expensive methods
Joseph M. Hellerstein · Minds at UW (University of Wisconsin) · 1996
This dissertation describes techniques for optimizing and executing queries that can commonly arise in extensible database management systems. These systems allow knowledgeable users to define new types, as well as new methods (operators) for the types. This flexibility produces an attendant complexity, which must be handled in new ways for an extensible database management system to be efficient. The focus of the dissertation is on optimizing and efficiently executing queries that contain time-consuming methods. In query optimization, the traditional focus has been on the choice of join methods and orders. Selections have been handled by pushdown rules, which apply selections in an arbitrary order before as many joins as possible. This works under the assumption that selection takes no time. However, users of extensible systems can embed complex methods in selections. Thus selections may take significant amounts of time, and the query optimization model must be enhanced. Query execution techniques also require enhancement to handle expensive methods, which should not be evaluated twice on the same inputs. Avoiding this redundancy efficiently requires new perspectives on well-known techniques for related--but subtly different--problems. The dissertation first addresses optimization issues from a theoretical perspective. We develop an algorithm called Predicate Migration, and prove that it produces optimal plans for queries with expensive methods. We then describe our implementation of Predicate Migration in the commercial extensible database management system Illustra, and discuss practical issues that affect our earlier assumptions. We compare Predicate Migration to a variety of simpler optimization techniques, and demonstrate that Predicate Migration is the best general solution to date. We continue with techniques to avoid redundant computation of expensive methods. We develop a form of hybrid hashing called Hybrid Cache, which proves particularly effective for queries with expensive predicates. We isolate new tradeoffs between hashing and sorting, and demonstrate that sorting out-performs Hybrid Cache for expensive methods with large outputs. We conclude with an overview of results and directions for future work, focussing on research perspectives and our experience bringing research into practice in an industrial-strength system.