Multi-dimensional Resource

Scheduhng query executmrr plans 1s an mrportant component of query optimization in parallel datafmse systems. The prc}hlem M partmdarly cnmplex in a shared-nothing executmrr environment. where each system node represen~s a collection of tme-shareohle resources (e.g., CPU(S). disk(s), etc.) and commumcates with other nodes only hy message-passmg. Significant research effolt has concentrated on only a subset fIf the vmmtts forms of ’ mtra-query p.amllelism so that scheduling an~i synchromzatlon is smlphtied. In ackiitlon, most previous work has focused Its attention on (lne-ciimensional models of parrdlel query scheciuling, effectnwly Ignrmng the potential henefrts of resource sharing. In thu+ paper, we deveiop an approach that M more general in both directions, capturing all forms of mtra-query parallelism ami exploltmg sharing of multl-cfunensionzd resource nodes among conutrrentplan operators. ” This allows scheduhng a set of m~ieperr~ient query tasks (].e.. operator pipelines) to be seen as an instance of the muk-Limwnslonal bm-cieslgn problem. Using a novel quantificahon of C(mrse gram parallelism, we present a hst schwiulmg heurlstlc alg{mthm that M prnwthly near-optimal in the class {jt ’ coarse gram parallel executm ns (with a worst-case performance ratm that depends on the number of resources per nocie and the granularity parameter). We then extend this algorithm to handle the operator prectxience constrains m a bushy query plan by splitting the execution of the plan into synchronized phases. Prehmmaty performance results confirm the effectiveness of our scheduling algorithm compareci both to prevmus approaches and the optunal s[)lutl[)n. Finally, we present a technique that allows us to relax the coarse granulrmty restriction and obtain a list scheduhrrg methoci that N provably near-optimal m the space of ’ all posslhle parallel schedules.