Optimizing Disjunctive Queries with Expensive Predicates

Summary: Proposes bypass processing to optimize disjunctive queries with expensive predicates, skipping costly terms when cheaper ones suffice. Extends a query optimizer and compares three bypass-plan generation algorithms to show viability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2800
Venue: SIGMOD
Year: 1994
Pagerank: 9.6721003e-05
Overall Rank: 1,826 | 87.48%
DOI: 10.1145/191839.191906

Incoming Non-self Citations Over Time

Authors

1. A. Kemper (University of Passau)
2. G. Moerkotte (University of Karlsruhe)
3. K. Peithner (University of Passau)
4. M. Steinbrunn (University of Karlsruhe)

BibTeX Citation

@inproceedings{kemper_sigmod94,
        title = {{Optimizing Disjunctive Queries with Expensive Predicates}},
        author = {Kemper, A. and Moerkotte, G. and Peithner, K. and Steinbrunn, M.},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191906},
        url = {https://dl.acm.org/doi/10.1145/191839.191906},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022238183
675	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00015080025
801	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013909408
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
1,024	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.0001258839
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
3,656	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.2224287e-05
5,861	Factorizing Complex Predicates in Queries to Exploit Indexes	2003	SIGMOD	6.0636778e-05
7,176	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.6816132e-05
8,147	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.4788421e-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,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.2273974e-05
12,728	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	5.093636e-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.0024089429
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
192	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00026028406
268	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022788687
583	Global Query Optimization	1986	SIGMOD	0.00016145442
615	A Rule-Based View of Query Optimization	1987	SIGMOD	0.00015720167
1,073	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.00012300294
1,341	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00011108876
1,462	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00010701465
2,286	Extending the Search Strategy in a Query Optimizer	1991	VLDB	8.8044994e-05
2,923	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.9578414e-05
4,413	A Blackboard Architecture for Query Optimization in Object Bases	1993	VLDB	6.7168289e-05
4,678	Control of an Extensible Query Optimizer: A Planning-Based Approach	1993	VLDB	6.5687429e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
2	1,154	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD
3	132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD
4	4,109	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB
5	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
6	8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
7	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
8	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB
9	3,656	Bypassing Joins in Disjunctive Queries	1995	VLDB
10	9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD