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.00010534147
Overall Rank: 1,482 | 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.00021236408
1,252	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011334813
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011147959
2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1363731e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4221003e-05
2,949	Distributed Data Deduplication	2016	VLDB	7.8193962e-05
3,140	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6012971e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6510297e-05
4,466	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.584648e-05
5,596	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0698953e-05
6,046	Topology Dependent Bounds For FAQs	2019	PODS	5.9027709e-05
6,528	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7540798e-05
6,725	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6954425e-05
7,266	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5689674e-05
7,295	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5612427e-05
7,927	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4234567e-05
8,443	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3324907e-05
8,531	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3206021e-05
8,557	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.314366e-05
8,623	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2999107e-05
9,059	Adaptive Quotient Filters	2024	SIGMOD	5.2280134e-05
9,420	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1802184e-05
9,666	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.142891e-05
11,233	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9769913e-05
11,486	Topology-aware Parallel Joins	2024	PODS	4.9769913e-05
11,499	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9769913e-05
11,542	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9769913e-05
11,947	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9769913e-05
11,948	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9769913e-05
11,990	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9769913e-05
12,200	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9769913e-05
12,277	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.9769913e-05
12,333	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9769913e-05
12,337	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.9769913e-05
12,381	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9769913e-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.0010515896
432	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018331051
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013577649
1,233	Communication Steps for Parallel Query Processing	2013	PODS	0.00011404978
1,546	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.0001029751
1,671	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9271979e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,666	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD
2	8,623	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
3	1,671	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	978	Parallel Evaluation of Conjunctive Queries	2011	PODS
6	1,256	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
7	12,277	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
8	1,233	Communication Steps for Parallel Query Processing	2013	PODS
9	490	Practical Skew Handling in Parallel Joins	1992	VLDB
10	2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS