Join query optimization in parallel database systems

The authors present a new framework for studying query optimization. They first note that scheduling and optimization must go together in a parallel environment. They introduce the concept of response time envelopes which integrates scheduling and optimization. It is shown that it can be used effectively to develop parallel query optimization algorithms which have same order of complexity as the traditional sequential query optimization algorithms and produce provably optimal or near optimal join plans.