Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Multi-dimensional resource scheduling for parallel queries

Garofalakis Minos, Ioannidis, Yannis, 1930-

Full record

---

Summary

Scheduling query execution plans is an important component ofquery optimization in parallel database systems. The problem isparticularly complex in a shared-nothing execution environment,where each system node represents a collection of time-shareableresources(e.g., CPU(s), disk(s), etc.) and communicates with othernodes only by message-passing. Significant research effort hasconcentrated on only a subset of the various forms of intra-queryparallelism so that scheduling and synchronization is simplified.In addition, most previous work has focused its attention onone-dimensional models of parallel query scheduling, effectivelyignoring the potential benefits of resource sharing. In this paper,we develop an approach that is more general in both directions,capturing all forms of intra-query parallelism and exploitingsharing of multi-dimensional resource nodes among concurrent planoperators. This allows scheduling a set of independent query tasks(i.e., operator pipelines) to be seen as an instance of the multidimensionalbin-design problem. Using a novel quantification ofcoarse grain parallelism, we present a list scheduling heuristicalgorithm that is provably near-optimal in the class of coarsegrain parallel executions (with a worst-case performance ratio thatdepends on the number of resources per node and the granularityparameter). We then extend this algorithm to handle the operatorprecedence constraints in a bushy query plan by splitting theexecution of the plan into synchronized phases. Preliminaryperformance results confirm the effectiveness of our schedulingalgorithm compared both to previous approaches and the optimalsolution. Finally, we present a technique that allows us to relax thecoarse granularity restriction and obtain a list scheduling methodthat is provably near-optimal in the space of all possible parallelschedules.

Services