Βελτιστοποίηση ερωτημάτων σε κατανεμημένα και δυναμικά περιβάλλοντα
Authors: Τσαμούρα Ευθυμία 
Published: August 2021

Σύμφωνα με την επίσημη έκθεση της IBM για το έτος 2012, ο όγκος των δεδομένων που παράγονται επί καθημερινής βάσης ξεπερνά τα 2.5 πεντάκις εκατομμύρια bytes δεδομένων. Οι πηγές αυτών των δεδομένων ποικίλουν από κοινωνικά δίκτυα και δικτυακούς τόπους διαμοιρασμού ψηφιακών αρχείων μέχρι δίκτυα αισθητήρων για τη συλλογή κλιματολογικών δεδομένων και κινητά τηλέφωνα. Τα ανωτέρω κατέστησαν επιτακτική την ανάπτυξη καινοτόμων υποδομών αποθήκευσης και επεξεργασίας δεδομένων, όπως αυτές της συστάδας, του πλέγματος και του νέφους. Προκειμένου να εκμεταλλευτούμε στο μέγιστο τις δυνατότητες π! ου προσφέρουν οι σύγχρονες υποδομές είναι αναγκαία η ανάπτυξη νέων τεχνικών βελτιστοποίησης και επεξεργασίας ερωτημάτων/εργασιών. Ο λόγος είναι ο εξής: οι αλγόριθμοι της βιβλιογραφίας δεν ελάμβαναν μέχρι στιγμής υπόψη πολλές από τις ιδιαιτερότητες αυτών των υποδομών με αποτέλεσμα τα πλάνα που παραγόταν να είναι λιγότερο αποδοτικά ή να μη συνάδουν με τις απαιτήσεις του εκάστοτε χρήστη. Στόχος της παρούσας διατριβής είναι η ανάπτυξη αλγορίθμων και τεχνικών για την αποδοτική και εναρμονισμένη με τις απαιτήσεις των χρηστών βελτιστοποίηση και εκτέλεση ερωτημάτων στις σύγχρονες υποδομές. Οι σημαντικότερες συνεισφορές της διατριβής συνοψίζονται στα εξής: (i) Αναπτύχθηκε ένας καινοτόμος βέλτιστος αλγόριθμος δημιουργίας πλάνων ερωτημάτων/ροών εργασιών όπου οι τελεστές SQL/εργασίες των χρηστών εκτελούνται μέσω κλήσεων σε απομακρυσμένες υπηρεσίες (services). Στόχος είναι η ελαχιστοποίηση του χρόνου ολοκλήρωσης του ερωτήματος/της ροής εργασίας του χρήστη. Οι παραδοχές που ελήφθησαν υπόψη και διαφοροποιούν τον προταθέντα αλγόριθμο από αυτούς της βιβλιογραφίας είναι, πρώτον, η υιοθέτηση παραλληλισμού σωλήνωσης και, δεύτερον, η απευθείας ανταλλαγή δεδομένων μεταξύ των υπηρεσιών μέσω ετερογενών συνδέσμων δικτύου. Κίνητρο για την ενασχόληση με το συγκεκριμένο πρόβλημα αποτέλεσε ο αυξανόμενος βαθμός χρήσης υπηρεσιών από τις σύγχρονες υποδομές. (ii) Αναπτύχθηκαν γενικεύσεις του ανωτέρω αλγορίθμου για τη δημιουργία πλάνων υπηρεσιών που περιλαμβάνουν υπηρεσίες σύνδεσης πολλαπλών εισόδων (multi-way join) και μελετήθηκαν θεωρητικά οι περιπτώσεις που οι προταθέντες αλγόριθμοι παράγουν πλάνα με τον ελάχιστο χρόνο ολοκλήρωσης. (iii) Εισήχθη μία νέα τεχνική για την προσαρμόσιμη εκτέλεση ερωτημάτων σε δυναμικά περιβάλλοντα. Όπως αποδεικνύεται και πειραματικά, η νέα τεχνική επιτυγχάνει να παράξει αποδοτικότερα πλάνα με μικρότερο φόρτο εκτέλεσης. Κίνητρα για την ανάπτυξη αυτής της τεχνικής υπήρξαν τόσο ο υψηλός βαθμός μεταβλητότητας όσο και η απρόβλεπτη φύση των σύγχρονων υποδομών και δεδομένων. (iv) Τέλος, έχοντας ως κίνητρο το γεγονός ότι οι πόροι των σύγχρονων υποδομών νέφους εκμισθώνονται, προτάθηκαν καινοτόμοι αλγόριθμοι χρονοδρομολόγησης ερωτημάτων/ροών εργασιών σε περιβάλλοντα πολλαπλών νεφών. Οι εν λόγω αλγόριθμοι αναλαμβάνουν να χρονοδρομολογήσουν τα ερωτήματα/ροές εργασιών εισόδου λαμβάνοντας υπόψη τόσο το χρόνο ολοκλήρωσης ενός τελεστή SQL/μίας υποεργασίας χρήστη όσο και το χρηματικό κόστος εκμίσθωσης των πόρων. Η ειδοποιός διαφορά των αλγορίθμων που προτάθηκαν από αυτούς της βιβλιογραφίας είναι η υπόθεση πως τα νέφη εκφράζουν τα χαρακτηριστικά χρόνου ολοκλήρωσης-χρηματικού κόστους εκμίσθωσης πόρων μέσω συνεχών συναρτήσεων.