Query execution techniques for caching expensive methods
Joseph M. Hellerstein, Jeffrey F. Naughton · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1996
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, time is wasted redundantly computing methods 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 demonstrate that Hybrid Cache always dominates memoization, and significantly outperforms sorting in many instances. This provides new insights into the tradeoff between hashing and sorting for unary operations. Additionally, our Hybrid Cache algorithm includes some new optimization for unary hybrid hashing, which can be used for other applications such as grouping and duplicate elimination. We conclude with a discussion of techniques for caching multiple expensive methods in a single query, and raise some new optimization problems in choosing caching techniques.
Cited by 98 works. doi:10.1145/233269.233359
Authors
References
- Sorting and Searching
- Access path selection in a relational database management system
- Query evaluation techniques for large databases
- Implementation techniques for main memory database systems
- Multiple-query optimization
- Sampling-Based Estimation of the Number of Distinct Values of an Attribute
- “Memo” Functions and Machine Learning
- Hashing Methods and Relational Algebra Operations
- Statistical estimators for relational algebra expressions
- Predicate migration