Query Execution Techniques for Caching Expensive Methods

Summary: Evaluates caching of unary methods in OR/O-O queries with duplicates; compares memoization, sorting, and Hybrid Cache. Hybrid Cache dominates memoization and often beats sorting; adds unary-hash optimizations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h76a3002ab84e1700
Venue: SIGMOD
Year: 1996
Pagerank: 0.00013660347
Overall Rank: 821 | 94.49%
DOI: 10.1145/233269.233359

Incoming Non-self Citations Over Time

Authors

1. Joseph M. Hellerstein (University of California Berkeley; University of Wisconsin)
2. Jeffrey E. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{hellerstein_sigmod96,
        title = {{Query Execution Techniques for Caching Expensive Methods}},
        author = {Hellerstein, Joseph M. and Naughton, Jeffrey E.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233359},
        url = {https://dl.acm.org/doi/10.1145/233269.233359},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076195956
92	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034672523
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032459277
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013348278
1,130	WSQ/DSQ: A Practical Approach for Combined Querying of Databases and the Web*	2000	SIGMOD	0.00011902078
1,285	SQL/MapReduce: A practical approach to self-describing, polymorphic, and parallelizable user-defined functions	2009	VLDB	0.00011201377
1,378	Execution Strategies for SQL Subqueries	2007	SIGMOD	0.00010864448
1,703	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.8315219e-05
1,802	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.6081518e-05
2,114	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.0158191e-05
2,282	A Platform for Scalable One-Pass Analytics using MapReduce	2011	SIGMOD	8.6964781e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05
3,084	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	7.6630061e-05
3,984	Data Canopy: Accelerating Exploratory Statistical Analysis	2017	SIGMOD	6.8741188e-05
4,376	Optimization of Run-time Management of Data Intensive Web Sites	1999	VLDB	6.6286338e-05
4,726	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.4476785e-05
8,130	Client-Site Query Extensions	1999	SIGMOD	5.3937641e-05
8,317	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3559621e-05
9,694	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1396592e-05
12,909	XClean in Action: A Demonstration of Declarative XML Data Cleaning	2007	CIDR	4.9793485e-05
13,009	Action-Oriented Query Processing for Pervasive Computing	2005	CIDR	4.9793485e-05
13,018	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	4.9793485e-05
13,158	HyperQueries: Dynamic Distributed Query Processing on the Internet	2001	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
82	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036053776
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030470848
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013444911
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012401489
1,075	Towards an Open Architecture for LDL	1989	VLDB	0.0001215903
1,438	Magic is Relevant	1990	SIGMOD	0.00010648031
1,859	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.4898025e-05
2,032	Practical Predicate Placement	1994	SIGMOD	9.1561026e-05
3,530	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.2276073e-05
3,720	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.0715239e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,845	Query Processing in Tertiary Memory Databases	1995	VLDB
2	4,221	Efficiently Supporting Procedures In Relational Database Systems	1987	SIGMOD
3	4,832	ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data	2018	VLDB
4	1,041	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB
5	76	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB
6	3,059	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
7	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	7,918	Cache-Oblivious Query Processing	2007	CIDR
9	4,880	Loading a Cache with Query Results	1999	VLDB
10	2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD