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.00030398363
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,042	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	5.597835e-05
7,338	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.5338268e-05
7,522	Exploring big volume sensor data with Vroom	2017	VLDB	5.487591e-05
8,153	Client-Site Query Extensions	1999	SIGMOD	5.373387e-05
8,176	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.3688159e-05
8,231	Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques	2023	VLDB	5.3573407e-05
8,291	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3445863e-05
8,337	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3357365e-05
8,621	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	5.2863457e-05
9,079	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.2106452e-05
9,149	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.2061634e-05
9,437	MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources	2000	SIGMOD	5.1639026e-05
9,712	An IDEA: An Ingestion Framework for Data Enrichment in AsterixDB	2019	VLDB	5.1242974e-05
9,729	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1202393e-05
10,231	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	5.0432098e-05
10,928	Sema: A High-performance System for LLM-based Semantic Query Processing	2026	VLDB	4.9605343e-05
11,078	iPDB: SQL with ML and LLM Predicates (Towards a Database Engine for AI)	2026	VLDB	4.9605343e-05
13,066	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	4.9605343e-05
13,106	Data Densification in a Relational Database System	2004	SIGMOD	4.9605343e-05
13,285	Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions	1998	VLDB	4.9605343e-05
13,347	Processing Object-Oriented Queries with Invertible Late Bound Functions	1995	VLDB	4.9605343e-05
13,390	Using the Co-existence Approach to Achieve Combined Functionality of Object-Oriented and Relational Systems	1993	SIGMOD	4.9605343e-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.0023948467
34	The Design Of Postgres	1986	SIGMOD	0.00049063803
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
99	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034024478
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032702871
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00029092688
668	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014936842
1,076	Towards an Open Architecture for LDL	1989	VLDB	0.00012128405
1,853	A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures	1988	VLDB	9.4915966e-05
2,801	Managing Persistent Objects in a Multi-Level Store	1991	SIGMOD	7.9777181e-05
3,538	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.200842e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,495	Filtering with Approximate Predicates	1998	VLDB
2	278	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
3	5,999	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
4	8,188	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
5	1,866	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
6	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	9,149	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
8	1,122	Query Optimization by Predicate Move-Around	1994	VLDB
9	2,033	Practical Predicate Placement	1994	SIGMOD
10	2,521	Optimization of Queries with User-defined Predicates	1996	VLDB