Query Execution Techniques for Caching Expensive Methods

Object-Relational and Object-Oriented DBMSs allow users to invoke time-consuming ("expensive ") methods in their queries. When queries containing these expensive methods are run on data with duplicate values, the dominant part of query execution time is devoted to redundant computation, as methods are invoked repeatedly on the same value. This problem has been studied in the context of programming languages, where "memoization" is the standard solution. In the database literature, sorting has been proposed to deal with this problem. We compare these approaches along with a third solution, a variant of unary hybrid hashing which we call Hybrid Cache. We present a performance study of the three caching techniques in Illustra, which demonstrates that Hybrid Cache always dominates memoization, and significantly outperforms sorting in many instances. In particular, Hybrid Cache is always fastest for caching Boolean predicate methods, while other methods are most efficiently cached by one o..