Pushing Data-Induced Predicates Through Joins in Big-Data Clusters

Summary: Introduces data-induced predicates that propagate filters across joins, enabling optimizer-only data skipping without execution overhead. Using existing zone maps—and modestly richer statistics—substantially reduces input and roughly doubles median production-cluster query speed. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: he9c9b372d221fd91
Venue: VLDB
Year: 2020
Pagerank: 7.6742518e-05
Overall Rank: 3,075 | 79.34%
DOI: 10.14778/3368289.3368292
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Srikanth Kandula (Microsoft)
2. Laurel Orr (University of Washington)
3. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@article{kandula_vldb20,
        title = {{Pushing Data-Induced Predicates Through Joins in Big-Data Clusters}},
        author = {Kandula, Srikanth and Orr, Laurel and Chaudhuri, Surajit},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {3},
        pages = {252--265},
        doi = {10.14778/3368289.3368292},
        url = {https://doi.org/10.14778/3368289.3368292},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,949	Quantifying TPC-H Choke Points and Their Optimizations	2020	VLDB	9.3172855e-05
2,661	End-to-end Optimization of Machine Learning Prediction Queries	2022	SIGMOD	8.1568473e-05
2,765	Instance-Optimized Data Layouts for Cloud Analytics Workloads	2021	SIGMOD	8.0401855e-05
4,371	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6284915e-05
5,451	Crystal: A Unified Cache Storage System for Analytical Databases	2021	VLDB	6.1238308e-05
5,842	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.971167e-05
6,149	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	5.8683464e-05
6,248	The Cosmos Big Data Platform at Microsoft: Over a Decade of Progress and a Decade to Look Forward	2021	VLDB	5.8345657e-05
6,395	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD	5.7981019e-05
6,714	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.6993812e-05
7,247	Pruning in Snowflake: Working Smarter, Not Harder	2025	SIGMOD	5.5734736e-05
7,927	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4234567e-05
8,159	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.3866275e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
8,275	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3623175e-05
8,587	Conditional Cuckoo Filters	2021	SIGMOD	5.3075325e-05
9,098	Hyperspace: The Indexing Subsystem of Azure Synapse	2021	VLDB	5.2258409e-05
10,157	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0691578e-05
10,853	I-Rex: An Interactive Debugger for SQL	2026	VLDB	4.9769913e-05
11,135	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9769913e-05
11,517	PLAQUE: Automated Predicate Learning at Query Time	2024	SIGMOD	4.9769913e-05
11,733	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 41 of 41 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
6	Pig Latin: A Not-So-Foreign Language for Data Processing	2008	SIGMOD	0.0010515896
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058997063
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055384955
30	SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets	2008	VLDB	0.00050475202
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049821554
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035340164
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027827605
178	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026620521
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
252	Database Cracking	2007	CIDR	0.00023101361
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017955913
456	Mergeable Summaries	2012	PODS	0.00017904764
492	Database Tuning Advisor for Microsoft SQL Server 2005	2004	VLDB	0.00017406029
617	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015548752
745	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.0001430357
889	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013243846
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012396854
1,036	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012372946
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011946162
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011147959
1,302	Apache Hadoop Goes Realtime at Facebook	2011	SIGMOD	0.00011106173
1,378	Execution Strategies for SQL Subqueries	2007	SIGMOD	0.00010859556
1,663	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.942673e-05
2,139	Quickstep: A Data Platform Based on the Scaling-Up Approach	2018	VLDB	8.9735524e-05
2,157	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9425625e-05
2,326	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.628257e-05
2,384	The Uncracked Pieces in Database Cracking	2014	VLDB	8.5401256e-05
2,688	CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop	2011	VLDB	8.1262948e-05
2,741	Efficient View Maintenance at Data Warehouses	1997	SIGMOD	8.0650842e-05
2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8119682e-05
3,083	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	7.6620866e-05
3,241	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD	7.4972383e-05
3,445	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2911896e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
3,707	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.0789307e-05
4,534	AdaptDB: Adaptive Partitioning for Distributed Joins	2017	VLDB	6.5535468e-05
7,000	Statisticum: Data Statistics Management in SAP HANA	2017	VLDB	5.6226404e-05
8,028	Optimizing Iceberg Queries with Complex Joins	2017	SIGMOD	5.4028948e-05
9,163	High Performance Stream Query Processing With Correlation-Aware Partitioning	2014	VLDB	5.2152138e-05
10,128	Amoeba: A Shape changing Storage System for Big Data	2016	VLDB	5.0729194e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,069	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
2	3,637	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB
3	6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
4	9,939	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD
5	3,154	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
6	5,429	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
7	883	Dynamic Programming Strikes Back	2008	SIGMOD
8	138	Join Synopses for Approximate Query Answering	1999	SIGMOD
9	4,371	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR
10	8,275	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD