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.00010500209
Overall Rank: 1,483 | 90.07%
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
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
1,253	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011316982
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1064522e-05
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
2,954	Distributed Data Deduplication	2016	VLDB	7.8045942e-05
3,144	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.5846375e-05
4,357	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6290396e-05
4,487	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5628751e-05
5,610	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0498245e-05
6,059	Topology Dependent Bounds For FAQs	2019	PODS	5.8832527e-05
6,539	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7351897e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-05
7,284	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5505534e-05
7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5428538e-05
7,942	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4055234e-05
8,459	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3148581e-05
8,550	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3030089e-05
8,576	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.2968015e-05
8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2823858e-05
9,078	Adaptive Quotient Filters	2024	SIGMOD	5.2107263e-05
9,445	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1630894e-05
9,695	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1258854e-05
11,289	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9605343e-05
11,538	Topology-aware Parallel Joins	2024	PODS	4.9605343e-05
11,551	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9605343e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
11,991	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9605343e-05
11,992	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9605343e-05
12,034	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9605343e-05
12,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9605343e-05
12,320	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.9605343e-05
12,376	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9605343e-05
12,380	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.9605343e-05
12,424	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9605343e-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.0010494385
436	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018274105
836	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013534835
1,242	Communication Steps for Parallel Query Processing	2013	PODS	0.00011372366
1,547	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010268377
1,675	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.8993233e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,633	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
2	8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
3	1,675	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
4	836	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB
5	982	Parallel Evaluation of Conjunctive Queries	2011	PODS
6	1,259	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
7	12,320	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
8	1,242	Communication Steps for Parallel Query Processing	2013	PODS
9	491	Practical Skew Handling in Parallel Joins	1992	VLDB
10	2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS