Skew in Parallel Query Processing

Summary: Tight one-round communication bounds for computing conjunctive queries on p servers characterized by fractional edge packings when only relation cardinalities are known (skew-free), matching up to polylog p. For skewed data with known heavy hitters/frequencies, matching upper/lower bounds via packings of residual queries obtained by fixing heavy hitters, with information-theoretic bit lower bounds even under unbounded local computation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: he352158b7063636d
Venue: PODS
Year: 2014
Pagerank: 0.00010539119
Overall Rank: 1,481 | 90.05%
DOI: 10.1145/2594538.2594558

Incoming Non-self Citations Over Time

Authors

1. Paul Beame (University of Washington)
2. Paraschos Koutris (University of Washington)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{beame_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{Skew in Parallel Query Processing}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594558},
        doi = {10.1145/2594538.2594558},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Beame, Paul and Koutris, Paraschos and Suciu, Dan},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
1,249	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011340141
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
2,948	Distributed Data Deduplication	2016	VLDB	7.8230494e-05
3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6046928e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6541797e-05
4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5877664e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
6,044	Topology Dependent Bounds For FAQs	2019	PODS	5.9055665e-05
6,525	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.756805e-05
6,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-05
7,259	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5716049e-05
7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5638766e-05
7,923	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4260253e-05
8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3350162e-05
8,524	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3231221e-05
8,550	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.3168829e-05
8,614	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.3024208e-05
9,051	Adaptive Quotient Filters	2024	SIGMOD	5.2304894e-05
9,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
9,659	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1453267e-05
11,225	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9793485e-05
11,480	Topology-aware Parallel Joins	2024	PODS	4.9793485e-05
11,493	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-05
11,941	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9793485e-05
11,942	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9793485e-05
11,984	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9793485e-05
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-05
12,271	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.9793485e-05
12,327	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9793485e-05
12,331	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.9793485e-05
12,375	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.001052036
432	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018339357
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013583955
1,231	Communication Steps for Parallel Query Processing	2013	PODS	0.00011410373
1,545	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010302384
1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9318041e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
2	8,614	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
3	1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
4	833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB
5	977	Parallel Evaluation of Conjunctive Queries	2011	PODS
6	1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
7	12,271	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
8	1,231	Communication Steps for Parallel Query Processing	2013	PODS
9	489	Practical Skew Handling in Parallel Joins	1992	VLDB
10	2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS