A hierarchical approach to parallel multiquery scheduling

There has been a good deal of progress made recently toward the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper the authors devise and experimentally evaluate a number of scheduling algorithms designed to handle multiple parallel queries. (Scheduling in this context implies the determination of both processor allotments and temporal processor assignments to individual queries and query phases.) One of these algorithms perfroms the best in the present experiments. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the firstj phase are used to create an overall schedule of the full set of queries. This component is based on previously publshed work on nonprecedence-based malleable scheduling. Even through the problem the authors are considering is NP-hard in the strong sense, the multiple query schedules generated by the present hierarchical algorithm are seen experimentally to achieve high quality results.