Optimization of Queries with User-defined Predicates

Summary: Optimizes queries with expensive user-defined predicates, where eager evaluation is unsound. Extends System R optimization to guarantee optimal plans without exhaustive join-order enumeration, with polynomial complexity in predicate count, plus a near-optimal local heuristic. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h596dbc1879c8176a
Venue: VLDB
Year: 1996
Pagerank: 8.3610198e-05
Overall Rank: 2,516 | 83.09%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Kyuseok Shim (AT&T; IBM)

BibTeX Citation

@article{chaudhuri_vldb96,
        title = {{Optimization of Queries with User-defined Predicates}},
        author = {Chaudhuri, Surajit and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '96},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001282305
2,571	The Case for Enhanced Abstract Data Types	1997	VLDB	8.2840962e-05
3,084	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	7.6630061e-05
3,865	Optimizing Nested Queries with Parameter Sort Orders	2005	VLDB	6.962283e-05
4,481	Filtering with Approximate Predicates	1998	VLDB	6.5807146e-05
4,726	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.4476785e-05
8,130	Client-Site Query Extensions	1999	SIGMOD	5.3937641e-05
8,317	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3559621e-05
8,808	Supporting User-Defined Functions on Uncertain Data	2013	VLDB	5.2725914e-05
9,418	MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources	2000	SIGMOD	5.1803485e-05
9,694	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1396592e-05
13,009	Action-Oriented Query Processing for Pervasive Computing	2005	CIDR	4.9793485e-05
13,018	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	4.9793485e-05
13,238	Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions	1998	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
73	Including Group-By in Query Optimization	1994	VLDB	0.00037522101
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003276959
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030470848
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
446	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018174972
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
689	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00014752546
1,075	Towards an Open Architecture for LDL	1989	VLDB	0.0001215903
2,983	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.7839431e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
2	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
3	73	Including Group-By in Query Optimization	1994	VLDB
4	689	Query Optimization in the Presence of Foreign Functions	1993	VLDB
5	9,123	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
6	143	Optimization of Nonrecursive Queries	1986	VLDB
7	125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD
8	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
9	272	An Overview of Query Optimization in Relational Systems	1998	PODS
10	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB