DBScholar

Back to papers

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

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 50 of 72 citing papers.

Rank Citing Paper Year Venue Pagerank
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
259 Answering Queries using Humans, Algorithms and Databases 2011 CIDR 0.00022923243
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022509573
281 Accelerating Machine Learning Inference with Probabilistic Predicates 2018 SIGMOD 0.00022295232
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
689 Query Optimization in the Presence of Foreign Functions 1993 VLDB 0.00014752546
761 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014143602
796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD 0.00013938011
821 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013660347
838 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00013550235
869 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00013348278
898 Orthogonal Security With Cipherbase 2013 CIDR 0.00013189879
900 Query Optimization In Compressed Database Systems 2001 SIGMOD 0.00013186558
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,119 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011950395
1,285 SQL/MapReduce: A practical approach to self-describing, polymorphic, and parallelizable user-defined functions 2009 VLDB 0.00011201377
1,714 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 9.80996e-05
1,859 Optimizing Disjunctive Queries with Expensive Predicates 1994 SIGMOD 9.4898025e-05
2,032 Practical Predicate Placement 1994 SIGMOD 9.1561026e-05
2,286 Join Queries with External Text Sources: Execution and Optimization Techniques 1995 SIGMOD 8.6942645e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,480 REX: Recursive, Delta-Based Data-Centric Computation 2012 VLDB 8.4035081e-05
2,516 Optimization of Queries with User-defined Predicates 1996 VLDB 8.3610198e-05
2,616 Query Optimization over Web Services 2006 VLDB 8.2253465e-05
2,776 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0309448e-05
2,787 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 8.0158999e-05
3,084 On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS 1998 SIGMOD 7.6630061e-05
3,139 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.6046928e-05
3,410 Scalable Pattern Sharing on Event Streams 2016 SIGMOD 7.3258817e-05
3,592 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.1835842e-05
3,630 VISTA: Optimized System for Declarative Feature Transfer from Deep CNNs at Scale 2020 SIGMOD 7.1496182e-05
3,720 Bypassing Joins in Disjunctive Queries 1995 VLDB 7.0715239e-05
3,724 Coalescing in Temporal Databases 1996 VLDB 7.0702677e-05
3,849 EROC: A Toolkit for Building NEATO Query Optimizers 1996 VLDB 6.9810881e-05
3,933 Operator Placement for In-Network Stream Query Processing 2005 PODS 6.9176947e-05
3,969 Optimizing Machine Learning Inference Queries with Correlative Proxy Models 2022 VLDB 6.8899861e-05
3,988 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.871854e-05
4,293 A Method for Optimizing Opaque Filter Queries 2020 SIGMOD 6.6819917e-05
4,369 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6315141e-05
4,481 Filtering with Approximate Predicates 1998 VLDB 6.5807146e-05
4,486 Optimization of Continuous Queries with Shared Expensive Filters 2007 PODS 6.5788984e-05
4,726 User-Defined Table Operators: Enhancing Extensibility for ORDBMS 1999 VLDB 6.4476785e-05
4,773 Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System 1999 VLDB 6.4212044e-05
4,793 Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling 2021 VLDB 6.4127583e-05
5,969 Factorizing Complex Predicates in Queries to Exploit Indexes 2003 SIGMOD 5.9317876e-05
6,106 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8859291e-05
6,444 RTScan: Efficient Scan with Ray Tracing Cores 2024 VLDB 5.7825648e-05
6,886 Multi-Objective Agentic Rewrites for Unstructured Data Processing 2026 VLDB 5.6551172e-05
7,027 Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems 2008 SIGMOD 5.6179837e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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