Scheduling Problems in Parallel Query Optimization

Summary: Studies multiprocessor scheduling of pipelined operator trees exploiting inter-/intra-operator parallelism; node weights model operator cost and edge weights model communication charged only when connected operators reside on different processors. Proves NP-hard and gives two approximation algorithms (fast: 3.56 ratio; slow: 2.87 ratio). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h227bf9798a790165
Venue: PODS
Year: 1995
Pagerank: 9.0414685e-05
Overall Rank: 2,103 | 85.87%
DOI: 10.1145/212433.212471

Incoming Non-self Citations Over Time

Authors

1. Chandra Chekuri (Stanford University)
2. Waqar Hasan (Hewlett Packard Enterprise; Stanford University)
3. Rajeev Motwani (Stanford University)

BibTeX Citation

@inproceedings{chekuri_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Scheduling Problems in Parallel Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/212433.212471},
        doi = {10.1145/212433.212471},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chekuri, Chandra and Hasan, Waqar and Motwani, Rajeev},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
831	Pipelining in Multi-Query Optimization	2001	PODS	0.00013589597
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011771949
1,806	Multiobjective Query Optimization	2001	PODS	9.5976083e-05
2,305	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.669801e-05
2,440	A Case for Staged Database Systems	2003	CIDR	8.46509e-05
5,583	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.0764905e-05
6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.9047797e-05
7,404	Compliant Geo-distributed Query Processing	2021	SIGMOD	5.5357067e-05
9,621	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	5.1497631e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
446	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018174972
2,168	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	8.9275427e-05
5,583	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.0764905e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,271	Managing Intra-operator Parallelism in Parallel Database Systems	1995	VLDB
2	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
3	5,735	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
4	5,583	Coloring Away Communication in Parallel Query Optimization	1995	VLDB
5	446	Query Optimization for Parallel Execution	1992	SIGMOD
6	844	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD
7	831	Pipelining in Multi-Query Optimization	2001	PODS
8	2,305	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
9	3,091	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB
10	2,168	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB