Πλαίσιο χρονοπρογραμματισμού εκτέλεσης σχεσιακών join επερωτήσεων σε συστήματα κατανεμημένων βάσεων δεδομένων πάνω απο αρχιτεκτονικές πλεγμάτων -grids

 
This item is provided by the institution :

Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2005 (EN)

A Framework for High-Performance Relational Join Queries Scheduling in Distributed Database Systems over Grid-aware Architectures
Πλαίσιο χρονοπρογραμματισμού εκτέλεσης σχεσιακών join επερωτήσεων σε συστήματα κατανεμημένων βάσεων δεδομένων πάνω απο αρχιτεκτονικές πλεγμάτων -grids

Μισαργόπουλος, Αντώνης (EL)
Misargopoulos, Antonis (EN)

Τα Grids (Πλέγματα) αποτελούν μια ραγδαίως εξελισσόμενη δικτυακή υποδομή για την αναζήτηση, προσπέλαση και χρήση κατανεμημένων υπολογιστικών πηγών. Λειτουργούν αφαιρετικά ανεξάρτητα από πρωτόκολλα και μηχανισμούς πιστοποίησης και ασφάλειας, προσπέλασης αρχείων, μεταφοράς δεδομένων, κλπ. και προσφέρουν δυνατότητα για δυναμική ανάπτυξη εφαρμογών σε ποικίλες hardware και software πλατφόρμες. Η δρομολόγηση της εκτέλεσης των υπολογισμών και η διαχείριση των πηγών για εφαρμογές πάνω από Grid αποτελεί πρόκληση, όσο οι πηγές του Grid είναι κατανεμημένες, ετερογενείς εν γένει, ανήκουν σε οργανισμούς με διαφορετική στρατηγική λειτουργίας, διαφορετικά μοντέλα πρόσβασης δεδομένων και υπολογισμού του αντίστοιχου κόστους. Ένας χρονοπρογραμματιστής υψηλών επιδόσεων στοχεύει στην βέλτιστη απόδοση εφαρμογών, βελτιώνοντας διάφορα κριτήρια επίδοσης, όπως ο χρόνος εκτέλεσης των εφαρμογών. Η ανάπτυξη μίας αποτελεσματικής στρατηγικής για τη βέλτιστη εκτέλεση επερωτήσεων και η a-priori διαχείριση – κατανομή των πηγών αποτελεί ένα δύσκολο ερευνητικό πρόβλημα. Είναι ιδιαίτερα σημαντικό για τους ερευνητές και τους σχεδιαστές κατανεμημένων βάσεων δεδομένων να γνωρίζουν εκ των προτέρων ποιες πηγές του Grid πρόκειται να συμμετέχουν στην εκτέλεση συγκεκριμένων επερωτήσεων. Το υπολογιστικό και το επικοινωνιακό κόστος είναι σημαντικοί παράγοντες για την επιλογή των εμπλεκόμενων πηγών για την εκτέλεση. Σε αυτή την εργασία ασχολούμαστε με ζητήματα υπολογισμού και κατανομής των πηγών του Grid για την εκτέλεση σχεσιακών join επερωτήσεων. Μελετάμε τις διάφορες πολιτικές replication των δεδομένων που παρατηρούνται σε συστήματα κατανεμημένων βάσεων δεδομένων. Εστιάζουμε στο πώς μπορούμε να βελτιστοποιήσουμε την τεχνολογία επεξεργασίας και εκτέλεσης των επερωτήσεων με την βοήθεια των Grids και πώς η κατανομή και η δέσμευση πηγών του Grid μπορεί να γίνει πιο αποδοτική και αποτελεσματική. Συγκεκριμένα, θεωρώντας την περίπτωση no replication των δεδομένων, σχεδιάσαμε και υλοποιήσαμε ένα χρονοπρογραμματιστή για την εκτέλεση join επερωτήσεων για κατανεμημένες βάσεις πάνω από Grid αρχιτεκτονικές. Μετατρέπουμε δεδομένες join επερωτήσεις σε κατευθυνόμενους άκυκλους γράφους που αναπαριστούν επαρκώς όλες τα πιθανά διαφορετικά πλάνα εκτέλεση της επερώτησης με την βοήθεια του αλγορίθμου Query Plan Graph Constructor (QuPGC ) που προτείνουμε. Όταν ο γράφος κατασκευαστεί, επιλέγουμε το βέλτιστο πλάνο εκτέλεσης της επερώτησης. Για το σκοπό αυτό, σχεδιάσαμε τον Heuristic Query Path Selector (HQuPaS) αλγόριθμο, ο οποίος χρησιμοποιεί δύο ευριστικές συναρτήσεις για τον υπολογισμό του υπολογιστικού και επικοινωνιακού κόστους κάθε εναλλακτικού πλάνου εκτέλεσης με βάσει τον γράφο. Το πλάνο εκτέλεσης με το μικρότερο συνολικό κόστος εκτιμάται ως το βέλτιστο για την εκτέλεση της επερώτηση με βάση τα χαρακτηριστικά (διαθέσιμη CPU, διαθέσιμο bandwidth) των πηγών του Grid και του μοντέλου υπολογισμού κόστους που χρησιμοποιούμε. (EL)
The Grid is an emerging infrastructure that supports the discovery, access and use of distributed computational resources. Grids abstract over platform or protocol-specific mechanisms for authentication, file access, data transfer, application invocation, etc. and allow dynamic deployment of applications on diverse hardware and software platforms. The scheduling of computations and the management of resources for Grid-aware applications is a challenging problem as resources are distributed, heterogeneous in nature, owned by different individuals or organizations with their own policies, have different access and cost models and dynamically varying loads and availability. A high-performance scheduler promotes the performance of individual applications by optimizing performance measurements such as minimal execution time. The strategy of efficient and optimized query execution is a challenging research problem. Besides that, the a-priori resource allocation and management is particularly hard, as well. It is important for the researchers and the distributed database designers to know in advance which and how many resources of the Grid architecture are involved in the execution of a given query. The selection of the proper query plan depends on factors such as, communication and computation costs. This work explores this aspect of service-based computing and resource management. We study the various data replication policies that could be followed in distributed database systems. In addition, we focus on how we can optimize query processing over computational Grids and how we can make resource allocation more efficient and effective. Especially, regarding the case in which no data replication takes place, we designed and implemented a high-performance application scheduler for relational join queries over a Grid-aware architecture. We transform given join expressions into directed acyclic graphs (DAGs) that contain all possible plans for the execution of the join. For that purpose, we developed the Query Plan Graph Constructor (QuPGC) algorithm. When the query plan graph is constructed, we select the execution plan that yields optimal performance. For that reason, we developed the Heuristic Query Path Selector (HQuPaS) algorithm, that uses two heuristic functions for the communication and the computation cost of each plan of the graph. The output will be a query execution plan that corresponds with optimal computation and communication cost. (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης


2005-04-01
2005-07-20


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)