MIT Department of Electrical Engineering & Computer Science

DATE: THURSDAY, MARCH 2, 1995

TIME: TALK AT 2:15
Refreshments at 2:00

PLACE NE43-518

Optimization and Execution
of Queries with Expensive Methods

Joseph Hellerstein
University of Wisconsin

Abstract

The traditional focus of database query processing research has been on the efficient evaluation of joins. In today's Object-Relational and Object-Oriented database systems, however, joins are not the only time-consuming operations. Users may define arbitrary expensive methods for their data objects, and invoke these methods in declarative queries. My dissertation explores algorithms for optimizing and executing queries that invoke expensive methods.

This talk focuses on an optimization algorithm called Predicate Migration, which I developed and implemented in the commercial Object-Relational system Illustra. Predicate Migration works in concert with a standard relational query optimizer, to produce efficient plans for queries with expensive predicates. I demonstrate the theoretical optimality of these plans, and describe practical issues that influence the effectiveness of Predicate Migration. I also present results of a performance study comparing Predicate Migration with alternative heuristic solutions in Illustra. Although Predicate Migration is the only algorithm that produces good plans for all queries, the study isolates workloads for which the heuristics form acceptable solutions. This provides a range of solutions of varying implementation complexity, efficiency, and effectiveness.

HOST: Prof. Liskov