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)
Incoming Non-self Citations Over Time
Authors
- 1. Chandra Chekuri
- 2. Waqar Hasan
- 3. Rajeev Motwani
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 977 | Pipelining in Multi-Query Optimization | 2001 | PODS | 0.000148774 |
| 1,229 | Toward a Progress Indicator for Database Queries | 2004 | SIGMOD | 0.00013153898 |
| 1,618 | Multiobjective Query Optimization | 2001 | PODS | 0.00011125239 |
| 2,329 | A Case for Staged Database Systems | 2003 | CIDR | 9.0237899e-05 |
| 2,458 | Multi-dimensional Resource Scheduling for Parallel Queries | 1996 | SIGMOD | 8.7601979e-05 |
| 5,397 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5277465e-05 |
| 6,336 | Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs | 2009 | SIGMOD | 5.1009488e-05 |
| 7,306 | Compliant Geo-distributed Query Processing | 2021 | SIGMOD | 4.7626702e-05 |
| 9,312 | Parallelizing Query Optimization on Shared-Nothing Architectures | 2016 | VLDB | 4.353536e-05 |
Previous
Page 1 / 1
Next
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.0040465394 |
| 439 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00023183237 |
| 1,826 | Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism | 1994 | VLDB | 0.00010392071 |
| 5,397 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5277465e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,358 | Managing Intra-operator Parallelism in Parallel Database Systems | 1995 | VLDB | 0.00012402333 |
| 2,051 | Optimization of Multi-Way Join Queries for Parallel Execution | 1991 | VLDB | 9.6871984e-05 |
| 5,687 | Efficient and Accurate Cost Models for Parallel Query Optimization | 1996 | PODS | 5.3711581e-05 |
| 5,397 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5277465e-05 |
| 439 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00023183237 |
| 806 | Exploiting Inter-Operation Parallelism in XPRS | 1992 | SIGMOD | 0.00016428214 |
| 977 | Pipelining in Multi-Query Optimization | 2001 | PODS | 0.000148774 |
| 2,458 | Multi-dimensional Resource Scheduling for Parallel Queries | 1996 | SIGMOD | 8.7601979e-05 |
| 3,129 | Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources | 1997 | VLDB | 7.5132501e-05 |
| 1,826 | Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism | 1994 | VLDB | 0.00010392071 |