Parallel Evaluation of Conjunctive Queries

Summary: Propose a simple synchronous parallel model measuring global synchronization rounds to analyze conjunctive-query evaluation on massive clusters. Characterize one-round computable queries as "tall-flat" (strict subset of hierarchical), give a one-round algorithm and matching impossibility for others, with extensions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3e90bdaf75eaa1d8
Venue: PODS
Year: 2011
Pagerank: 0.00012725823
Overall Rank: 978 | 93.43%
DOI: 10.1145/1989284.1989310

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{koutris_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Parallel Evaluation of Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989310},
        doi = {10.1145/1989284.1989310},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koutris, Paraschos and Suciu, Dan},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015334386
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
1,233	Communication Steps for Parallel Query Processing	2013	PODS	0.00011404978
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011147959
1,351	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010929229
1,546	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.0001029751
2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1363731e-05
2,340	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.6083649e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4221003e-05
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2782871e-05
3,188	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5510881e-05
4,466	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.584648e-05
4,860	Association Rules with Graph Patterns	2015	VLDB	6.3763445e-05
5,596	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0698953e-05
6,533	Query Evaluation by Circuits	2022	PODS	5.7519838e-05
7,295	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5612427e-05
7,612	On Scale Independence for Querying Big Data	2014	PODS	5.4829143e-05
8,058	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3964484e-05
8,623	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2999107e-05
9,893	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.1142741e-05
11,486	Topology-aware Parallel Joins	2024	PODS	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
12,200	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9769913e-05
12,333	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9769913e-05
12,381	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9769913e-05
12,591	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004314366
651	Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience	2009	VLDB	0.00015123701
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	2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
2	4,889	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
3	2,297	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD
4	1,482	Skew in Parallel Query Processing	2014	PODS
5	4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD
6	9,842	Implementation and Analysis of a Parallel Collection Query Language	1996	VLDB
7	12,333	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS
8	9,628	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
9	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
10	8,623	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS