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: 8525
Venue: VLDB
Year: 1996
Pagerank: 8.5428786e-05
Overall Rank: 2,465 | 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
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
2,528	The Case for Enhanced Abstract Data Types	1997	VLDB	8.4620669e-05
3,036	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	7.8287552e-05
3,816	Optimizing Nested Queries with Parameter Sort Orders	2005	VLDB	7.1002641e-05
4,435	Filtering with Approximate Predicates	1998	VLDB	6.7078883e-05
4,645	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.5900051e-05
7,966	Client-Site Query Extensions	1999	SIGMOD	5.5173328e-05
8,147	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.4788421e-05
8,646	Supporting User-Defined Functions on Uncertain Data	2013	VLDB	5.3928856e-05
9,270	MOCHA: A Self-Extensible Database Middleware System for Distributed Data Sources	2000	SIGMOD	5.2946605e-05
9,917	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.1955087e-05
12,719	Action-Oriented Query Processing for Pervasive Computing	2005	CIDR	5.093636e-05
12,728	Predicate Result Range Caching for Continuous Queries	2005	SIGMOD	5.093636e-05
12,948	Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions	1998	VLDB	5.093636e-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.0024089429
71	Including Group-By in Query Optimization	1994	VLDB	0.00038021159
110	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003309592
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
677	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00015065909
1,062	Towards an Open Architecture for LDL	1989	VLDB	0.000123618
2,923	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.9578414e-05

Semantically Similar Papers

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