Exploiting Correlations for Expensive Predicate Evaluation

Summary: Proposes cost-aware techniques for evaluating selection queries with UDF predicates by exploiting correlations and prior probabilities to meet user-specified precision/recall constraints. The methods handle known, noisy, or unknown probabilities, generalize to complex queries, and deliver up to 80% UDF savings with modest accuracy loss on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd0cee266066cfd64
Venue: SIGMOD
Year: 2015
Pagerank: 6.8489751e-05
Overall Rank: 4,000 | 73.19%
DOI: 10.1145/2723372.2723715

Incoming Non-self Citations Over Time

Authors

1. Manas Joglekar (Stanford University)
2. Hector Garcia-Molina (Stanford University)
3. Aditya Parameswaran (University of Illinois Urbana-Champaign)
4. Christopher Re (Stanford University)

BibTeX Citation

@inproceedings{joglekar_sigmod15,
        title = {{Exploiting Correlations for Expensive Predicate Evaluation}},
        author = {Joglekar, Manas and Garcia-Molina, Hector and Parameswaran, Aditya and Re, Christopher},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723715},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723715},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
278	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022277737
6,155	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	5.8540214e-05
7,175	Learning to Sample: Counting with Complex Queries	2020	VLDB	5.5779755e-05
7,338	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.5338268e-05
9,415	JENNER: Just-in-time Enrichment in Query Processing	2022	VLDB	5.1672232e-05
9,867	AMNES: Accelerating the computation of data correlation using FPGAs	2023	VLDB	5.1056602e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076079812
92	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034613457
105	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033605348
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030398363
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027775994
247	Overview of SciDB: Large Scale Array Storage, Processing and Analysis	2010	SIGMOD	0.00023119762
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
311	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021315058
337	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020593498
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020486383
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
450	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.0001806593
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016251304
691	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00014701803
852	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013447072
935	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00012968914
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,670	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9124313e-05
2,033	Practical Predicate Placement	1994	SIGMOD	9.1389597e-05
2,337	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.6002736e-05
2,439	Deco: A System for Declarative Crowdsourcing	2012	VLDB	8.4510942e-05
3,509	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.2279142e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,018	Demonstration of Accelerating Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB
2	4,088	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
3	3,212	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
4	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
5	9,149	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
6	1,866	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
7	9,729	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB
8	278	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
9	2,521	Optimization of Queries with User-defined Predicates	1996	VLDB
10	8,002	Efficient Execution of User-Defined Functions in SQL Queries	2023	VLDB