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: 2709
Venue: SIGMOD
Year: 1993
Pagerank: 0.00030378624
Overall Rank: 132 | 99.10%
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 19 of 69 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,355	Exploring big volume sensor data with Vroom	2017	VLDB	5.6348348e-05
7,412	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.624223e-05
7,966	Client-Site Query Extensions	1999	SIGMOD	5.5173328e-05
8,115	Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques	2023	VLDB	5.4842672e-05
8,147	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.4788421e-05
8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	5.4252897e-05
8,465	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.4194578e-05
8,721	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3772617e-05
8,893	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.3504579e-05
8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD	5.3398545e-05
9,270	MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources	2000	SIGMOD	5.2946605e-05
9,508	An IDEA: An Ingestion Framework for Data Enrichment in AsterixDB	2019	VLDB	5.2581623e-05
9,917	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1955087e-05
10,504	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	5.093636e-05
12,728	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	5.093636e-05
12,769	Data Densification in a Relational Database System	2004	SIGMOD	5.093636e-05
12,948	Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions	1998	VLDB	5.093636e-05
13,010	Processing Object-Oriented Queries with Invertible Late Bound Functions	1995	VLDB	5.093636e-05
13,053	Using the Co-existence Approach to Achieve Combined Functionality of Object-Oriented and Relational Systems	1993	SIGMOD	5.093636e-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.0024089429
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
95	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034607909
110	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003309592
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
1,062	Towards an Open Architecture for LDL	1989	VLDB	0.000123618
1,816	A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures	1988	VLDB	9.6840978e-05
2,737	Managing Persistent Objects in a Multi-Level Store	1991	SIGMOD	8.1890257e-05
3,469	Extended User-Defined Indexing with Application to Textual Databases	1988	VLDB	7.3893582e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,435	Filtering with Approximate Predicates	1998	VLDB
2	295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
3	5,898	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
4	9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
5	1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
6	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
8	1,124	Query Optimization by Predicate Move-Around	1994	VLDB
9	2,005	Practical Predicate Placement	1994	SIGMOD
10	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB