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.00012687016
Overall Rank: 982 | 93.42%
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
639	Answering Conjunctive Queries under Updates	2017	PODS	0.00015289346
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
1,242	Communication Steps for Parallel Query Processing	2013	PODS	0.00011372366
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
1,360	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010893993
1,547	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010268377
2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1064522e-05
2,350	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.5846492e-05
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
2,561	Minimal MapReduce Algorithms	2013	SIGMOD	8.2743492e-05
3,199	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5261206e-05
4,487	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5628751e-05
4,838	Association Rules with Graph Patterns	2015	VLDB	6.3753978e-05
5,610	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0498245e-05
6,545	Query Evaluation by Circuits	2022	PODS	5.7329641e-05
7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5428538e-05
7,628	On Scale Independence for Querying Big Data	2014	PODS	5.4649494e-05
8,075	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3786044e-05
8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2823858e-05
9,927	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.0974575e-05
11,538	Topology-aware Parallel Joins	2024	PODS	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,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9605343e-05
12,376	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9605343e-05
12,424	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9605343e-05
12,634	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9605343e-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.00050364918
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049707539
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043085722
655	Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience	2009	VLDB	0.00015076669
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	2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
2	4,912	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
3	2,308	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD
4	1,483	Skew in Parallel Query Processing	2014	PODS
5	4,357	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD
6	9,878	Implementation and Analysis of a Parallel Collection Query Language	1996	VLDB
7	12,376	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS
8	9,656	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
9	1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
10	8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS