ΠΑΡΑΛΛΗΛΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΚΑΙ ΕΚΤΕΛΕΣΗ ΕΡΩΤΗΣΕΩΝ ΠΡΟΣ ΣΧΕΣΙΑΚΟ ΣΥΣΤΗΜΑ ΔΙΑΧΕΙΡΙΣΗΣ ΒΑΣΗΣ ΔΕΔΟΜΕΝΩΝ ΣΕ ΠΕΡΙΒΑΛΛΟΝ ΠΑΡΑΛΛΗΛΗΣ ΚΑΙ ΣΩΛΗΝΩΤΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ

Abstract

A PARALLEL OPTIMIZATION MODEL IS PRESENTED, DESIGNED FOR QUERIES TOWARDS AN RDBMS OPERATING IN A LOW PARALLELISM ENVIRONMENT. THE OBJECTIVES OF THE MODEL ARETHE MINIMIZATION OF THE QUERY EXECUTION TIME AND THE MINIMIZATION OF THE QUERY OPTIMIZATION OVERHEAD, ESPECIALLY FOR QUERIES WITH A LARGE NUMBER OF OPERATORS. THE MODEL TRANSFORMS THE QUERY INTO A QUERY TREE, WHICH IS PARTITIONED INTO INDEPENDENTLY OPTIMIZABLE SUBTREES, WHICH ARE THEREAFTER OPTIMIZED IN PARALLEL. FOR THE CONSTRUCTION OF THE OPTIMAL EXECUTION PLAN, THE TECHNIQUES ADOPTED ARE ONE SCANNING THE SOLUTION SPACE ALMOST EXHAUSTIVELY AND ONE BASED ONE LOCAL SEARCH; THE SELECTION BETWEEN THEM IS BASED ON THE NUMBER OF JOINS IN THE QUERY TREE. THE PARALLELIZATION OF QUERY OPTIMIZATION AND THE USED TECHNIQUES ENSURE LOW OPTIMIZATION OVERHEAD, WHILE ALL OPTIMIZATION TECHNIQUES (SIMPLIFICATION, ALGORITHMS' SELECTION, TREE REORGANIZATION) ENSURE LOW EXECUTION TIME, BY EXPLOITING THE OFFERED PARALLELISM AND PIPELINE.

ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΠΑΡΟΥΣΙΑΖΕΤΑΙ ΕΝΑ ΠΑΡΑΛΛΗΛΟ ΜΟΝΤΕΛΟ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗΣ ΕΡΩΤΗΣΕΩΝΠΡΟΣ ΣΥΣΤΗΜΑ ΣΧΕΣΙΑΚΗΣ ΔΙΑΧΕΙΡΙΣΗΣ ΒΑΣΕΩΝ ΔΕΔΟΜΕΝΩΝ, ΤΟ ΟΠΟΙΟ ΛΕΙΤΟΥΡΓΕΙ ΣΕ ΠΕΡΙΒΑΛΛΟΝ ΧΑΜΗΛΗΣ ΠΑΡΑΛΛΗΛΙΑΣ. ΣΤΟΧΟΙ ΤΟΥ ΜΟΝΤΕΛΟΥ ΕΙΝΑΙ Η ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ ΚΑΙ Η ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΧΡΟΝΟΥ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗΣ ΜΙΑΣ ΕΡΩΤΗΣΗΣ, ΕΞΕΤΑΖΟΝΤΑΣ ΙΔΙΑΙΤΕΡΑ ΕΡΩΤΗΣΕΙΣ ΜΕ ΜΕΓΑΛΟ ΑΡΙΘΜΟ ΤΕΛΕΣΤΩΝ. ΤΟ ΜΟΝΤΕΛΟ ΜΕΤΑΣΧΗΜΑΤΙΖΕΙ ΤΗΝ ΕΡΩΤΗΣΗ ΣΕ ΔΕΝΔΡΟ ΤΕΛΕΣΤΩΝ, ΤΟ ΟΠΟΙΟ ΑΝΑΛΥΕΤΑΙ ΣΕ ΑΝΕΞΑΡΤΗΤΩΣ ΒΕΛΤΙΣΤΟΠΟΙΗΣΙΜΑ ΥΠΟΔΕΝΔΡΑ, ΤΑ ΟΠΟΙΑ ΒΕΛΤΙΣΤΟΠΟΙΟΥΝΤΑΙ ΠΑΡΑΛΛΗΛΑ. ΓΙΑ ΤΗΝ ΚΑΤΑΣΚΕΥΗ ΤΟΥ ΒΕΛΤΙΣΤΟΥ ΣΧΕΔΙΟΥ ΕΚΤΕΛΕΣΗΣ ΧΡΗΣΙΜΟΠΟΙΟΥΝΤΑΙ ΜΙΑ ΤΕΧΝΙΚΗ ΣΧΕΔΟΝ ΕΞΑΝΤΛΗΤΙΚΗΣ ΣΑΡΩΣΗΣ ΤΟΥ ΧΩΡΟΥ ΛΥΣΕΩΝ ΚΑΙ ΜΙΑ ΤΕΧΝΙΚΗ ΠΟΥ ΒΑΣΙΖΕΤΑΙ ΣΤΗΝ ΤΟΠΙΚΗ ΑΝΑΖΗΤΗΣΗ, ΑΝΑΛΟΓΑ ΜΕ ΤΟ ΠΛΗΘΟΣ ΤΩΝ ΤΕΛΕΣΤΩΝ ΣΥΝΔΕΣΗΣ ΤΟΥ ΔΕΝΔΡΟΥ ΕΡΩΤΗΣΗΣ. Η ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΤΗΣ ΒΕΛΤΙΣΤΟΠΟΙΗΤΙΚΗΣ ΔΙΑΔΙΚΑΣΙΑΣ ΚΑΙ ΟΙ ΥΙΟΘΕΤΟΥΜΕΝΕΣ ΤΕΧΝΙΚΕΣ ΕΞΑΣΦΑΛΙΖΟΥΝ ΧΑΜΗΛΗ ΧΡΟΝΙΚΗ ΕΠΙΒΑΡΥΝΣΗ ΚΑΤΑ ΤΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ, ΕΝΩ ΟΙ ΒΕΛΤΙΣΤΟΠΟΙΗΤΙΚΕΣ ΤΕΧΝΙΚΕΣ (ΑΠΛΟΠΟΙΗΣΗ, ΑΝΑΘΕΣΗ ΑΛΓΟΡΙΘΜΩΝ ΣΕ ΚΟΜΒΟΥΣ, ΑΝΑΔΙΟΡΓΑΝΩΣΗ ΔΕΝΔΡΟΥ) ΕΞΑΣΦΑΛΙΖΟΥΝ ΧΑΜΗΛΟ ΧΡΟΝΟ ΕΚΤΕΛΕΣΗΣ, ΜΕ ΕΚΜΕΤΑΛΛΕΥΣΗ ΤΗΣ ΠΡΟΣΦΕΡΟΜΕΝΗΣ ΠΑΡΑΛΛΗΛΙΑΣ ΚΑΙ ΤΩΝ ΔΥΝΑΤΟΤΗΤΩΝ ΣΩΛΗΝΩΤΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ.