Predicate Migration: Optimizing Queries with Expensive Predicates

Summary: Predicate Migration builds a theory to move expensive predicates in plans, replacing zero-time restrictions with cost-aware optimization. Algorithm and PostgreSQL show orders-of-magnitude speedups over traditional optimizers, with modest extra cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf9076d8528d40613
Venue: SIGMOD
Year: 1993
Pagerank: 0.00030470848
Overall Rank: 125 | 99.17%
DOI: 10.1145/170035.170078

Incoming Non-self Citations Over Time

Authors

1. Joseph M. Hellerstein (University of California Berkeley; University of Wisconsin)
2. Michael Stonebraker (University of California Berkeley)

BibTeX Citation

@inproceedings{hellerstein_sigmod93,
        title = {{Predicate Migration: Optimizing Queries with Expensive Predicates}},
        author = {Hellerstein, Joseph M. and Stonebraker, Michael},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170078},
        url = {https://dl.acm.org/doi/10.1145/170035.170078},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 72 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,030	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	5.6173605e-05
7,316	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.5547672e-05
7,498	Exploring big volume sensor data with Vroom	2017	VLDB	5.5084042e-05
8,130	Client-Site Query Extensions	1999	SIGMOD	5.3937641e-05
8,153	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.3891786e-05
8,213	Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques	2023	VLDB	5.3770961e-05
8,269	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3648571e-05
8,317	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3559621e-05
8,599	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	5.3055205e-05
9,052	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.230408e-05
9,123	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.2254194e-05
9,418	MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources	2000	SIGMOD	5.1803485e-05
9,676	An IDEA: An Ingestion Framework for Data Enrichment in AsterixDB	2019	VLDB	5.1437328e-05
9,694	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1396592e-05
10,690	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	4.9793485e-05
10,858	Sema: A High-performance System for LLM-based Semantic Query Processing	2026	VLDB	4.9793485e-05
11,008	iPDB: SQL with ML and LLM Predicates (Towards a Database Engine for AI)	2026	VLDB	4.9793485e-05
13,018	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	4.9793485e-05
13,059	Data Densification in a Relational Database System	2004	SIGMOD	4.9793485e-05
13,238	Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions	1998	VLDB	4.9793485e-05
13,300	Processing Object-Oriented Queries with Invertible Late Bound Functions	1995	VLDB	4.9793485e-05
13,343	Using the Co-existence Approach to Achieve Combined Functionality of Object-Oriented and Relational Systems	1993	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
34	The Design Of Postgres	1986	SIGMOD	0.00049142315
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003276959
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
665	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014990574
1,075	Towards an Open Architecture for LDL	1989	VLDB	0.0001215903
1,843	A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures	1988	VLDB	9.5236698e-05
2,792	Managing Persistent Objects in a Multi-Level Store	1991	SIGMOD	8.0079179e-05
3,530	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.2276073e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,481	Filtering with Approximate Predicates	1998	VLDB
2	281	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
3	5,988	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
4	8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
5	1,859	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
6	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	9,123	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
8	1,119	Query Optimization by Predicate Move-Around	1994	VLDB
9	2,032	Practical Predicate Placement	1994	SIGMOD
10	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB