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.0001488881 |
| 1,228 | Toward a Progress Indicator for Database Queries | 2004 | SIGMOD | 0.00013164884 |
| 1,614 | Multiobjective Query Optimization | 2001 | PODS | 0.00011135193 |
| 2,328 | A Case for Staged Database Systems | 2003 | CIDR | 9.0225171e-05 |
| 2,459 | Multi-dimensional Resource Scheduling for Parallel Queries | 1996 | SIGMOD | 8.7676516e-05 |
| 5,392 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5329138e-05 |
| 6,334 | Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs | 2009 | SIGMOD | 5.1058462e-05 |
| 7,324 | Compliant Geo-distributed Query Processing | 2021 | SIGMOD | 4.762032e-05 |
| 9,305 | Parallelizing Query Optimization on Shared-Nothing Architectures | 2016 | VLDB | 4.3577129e-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.0040449103 |
| 438 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00023199245 |
| 1,825 | Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism | 1994 | VLDB | 0.00010401739 |
| 5,392 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5329138e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,354 | Managing Intra-operator Parallelism in Parallel Database Systems | 1995 | VLDB | 0.00012408166 |
| 2,044 | Optimization of Multi-Way Join Queries for Parallel Execution | 1991 | VLDB | 9.6953608e-05 |
| 5,676 | Efficient and Accurate Cost Models for Parallel Query Optimization | 1996 | PODS | 5.376109e-05 |
| 5,392 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5329138e-05 |
| 438 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00023199245 |
| 807 | Exploiting Inter-Operation Parallelism in XPRS | 1992 | SIGMOD | 0.00016434207 |
| 977 | Pipelining in Multi-Query Optimization | 2001 | PODS | 0.0001488881 |
| 2,459 | Multi-dimensional Resource Scheduling for Parallel Queries | 1996 | SIGMOD | 8.7676516e-05 |
| 3,124 | Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources | 1997 | VLDB | 7.5201555e-05 |
| 1,825 | Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism | 1994 | VLDB | 0.00010401739 |