Βελτιστοποίηση Ερωτημάτων Με Eddies Και Ενισχυτική Μάθηση

Abstract

Η βελτιστοποίηση ερωτημάτων σε Βάσεις Δεδομένων είναι ένα πολύπλοκο πρόβλημα συνδυαστικής βελτιστοποίησης που καθιστά μη θεμιτή την εξαντλητική αναζήτηση όταν το μέγεθος του ερωτήματος είναι μεγάλο. Ταυτόχρονα, δυναμικά περιβάλλοντα εκτέλεσης καθώς και η πολυπλοκότητα των ίδιων των δεδομένων καθιστούν τις υποθέσεις που γίνονται κατά το χρόνο βελτιστοποίησης μη ρεαλιστικές κατά το χρόνο εκτέλεσης. Τα eddies παρέχουν ένα μηχανισμό εκτέλεσης ερωτημάτων κατά τον οποίο το πλάνο εκτέλεσης προσαρμόζεται ανά πλειάδα, αντιμετωπίζοντας την εκτέλεση του ερωτήματος ως μια διαδικασία δρομολόγησης των πλειάδων στους τελεστές. Στη διπλωματική αυτή εργασία μοντελοποιούμε τη διαδικασία βελτιστοποίησης ερωτημάτων που εκτελούνται με τη βοήθεια του μηχανισμού των eddies και των αρχιτεκτονικών εκτέλεσης συνδέσμων που τον περιβάλλουν (SteMs, STAIRs) ως πρόβλημα Ενισχυτικής Μάθησης. Αναπαριστούμε την πολιτική δρομολόγησης των πλειάδων σαν μια απεικόνιση από ένα χώρο καταστάσεων σε ένα χώρο δράσεων ενσωματώνοντας στο μοντέλο τους σημασιολογικούς περιορισμούς καθώς και τους περιορισμούς δρομολόγησης. Το πρόβλημα της βελτιστοποίησης μετατρέπεται έτσι σε ένα πρόβλημα μη επιβλεπόμενης μάθησης από ποσοτικές ενισχύσεις. Μέσω της μοντελοποίησης αυτής προτείνουμε αλγόριθμους μάθησης μιας βέλτιστης πολιτικής δρομολόγησης διατηρώντας την προσαρμοστικότητα σε επίπεδο πλειάδας.Database query optimization is a complex combinatorial optimization problem which makes exhaustive search inapplicable as query size grows. Moreover, dynamic execution environments as well as data complexities result that assumptions made at optimization time do not hold at execution time. Eddies provide an execution mechanism in which the query plan can be adapted in a per - tuple fashion by treating query execution as a tuple routing process. This thesis models the execution of a query using an eddy and the corresponding join mechanisms (SteMs, STAIRs) as a Reinforcement Learning problem. The tuple - routing policy is treated as a mapping from a state space to an action space and the semantics as well as the routing constraints get embedded into the model. Thus, the optimization problem is transformed to an unsupervised learning problem by quantitative rewards. Through this process, we propose algorithms that can learn an optimal routing policy without sacrificing the desired per - tuple adaptivity.