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.00012731794
Overall Rank: 977 | 93.44%
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.00015341557
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
1,231	Communication Steps for Parallel Query Processing	2013	PODS	0.00011410373
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,351	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010934347
1,545	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010302384
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,338	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.6124366e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2821647e-05
3,187	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5546613e-05
4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5877664e-05
4,858	Association Rules with Graph Patterns	2015	VLDB	6.3793644e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
6,531	Query Evaluation by Circuits	2022	PODS	5.754708e-05
7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5638766e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
8,052	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3990042e-05
8,614	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.3024208e-05
9,886	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.1166963e-05
11,480	Topology-aware Parallel Joins	2024	PODS	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
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-05
12,327	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9793485e-05
12,375	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9793485e-05
12,585	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9793485e-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.00050495102
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049839909
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
651	Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience	2009	VLDB	0.00015130782
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	2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
2	4,888	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
3	2,293	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD
4	1,481	Skew in Parallel Query Processing	2014	PODS
5	4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD
6	9,835	Implementation and Analysis of a Parallel Collection Query Language	1996	VLDB
7	12,327	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS
8	9,621	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,614	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS