Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Multi-dimensional resource scheduling for parallel queries

Garofalakis Minos, Ioannidis, Yannis, 1930-

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/4D14007E-1B71-4E9B-98A8-35CD5BB7D49F-
Αναγνωριστικόhttp://www.softnet.tuc.gr/~minos/Papers/sigmod96-cam.pdf-
Γλώσσαen-
Μέγεθος12 pagesen
ΤίτλοςMulti-dimensional resource scheduling for parallel queriesen
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςIoannidis, Yannis, 1930-en
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηScheduling query execution plans is an important component of query optimization in parallel database systems. The problem is particularly complex in a shared-nothing execution environment, where each system node represents a collection of time-shareable resources(e.g., CPU(s), disk(s), etc.) and communicates with other nodes only by message-passing. Significant research effort has concentrated on only a subset of the various forms of intra-query parallelism so that scheduling and synchronization is simplified. In addition, most previous work has focused its attention on one-dimensional models of parallel query scheduling, effectively ignoring 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 exploiting sharing of multi-dimensional resource nodes among concurrent plan operators. This allows scheduling a set of independent query tasks (i.e., operator pipelines) to be seen as an instance of the multidimensional bin-design problem. Using a novel quantification of coarse grain parallelism, we present a list scheduling heuristic algorithm that is provably near-optimal in the class of coarse grain parallel executions (with a worst-case performance ratio that depends on the number of resources per node and the granularity parameter). We then extend this algorithm to handle the operator precedence constraints in a bushy query plan by splitting the execution of the plan into synchronized phases. Preliminary performance results confirm the effectiveness of our scheduling algorithm compared both to previous approaches and the optimal solution. Finally, we present a technique that allows us to relax the coarse granularity restriction and obtain a list scheduling method that is provably near-optimal in the space of all possible parallel schedules.en
ΤύποςΔημοσίευση σε Συνέδριοel
ΤύποςConference Publicationen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-12-01-
Ημερομηνία Δημοσίευσης1996-
Θεματική ΚατηγορίαDatabasesen
Βιβλιογραφική ΑναφοράM. Garofalakis and Y. Ioannidis, "Multi-dimensional resource scheduling for parallel queries", in ACM SIGMOD International Conference on Management of Data, June 1996, pp. 365-376.en

Υπηρεσίες

Στατιστικά