In-memory indexing for parallel processing of single and multi-dimensional queries
Authors: Τσιτσίγκος Δημήτριος 
Published: February 2025

Οι βάσεις δεδομένων είναι απαραίτητες για τις σύγχρονες εφαρμογές, προσφέροντας δομημένους, αποδοτικούς και αξιόπιστους τρόπους διαχείρισης δεδομένων σε τομείς όπως οι τραπεζικές συναλλαγές, η υγειονομική περίθαλψη και η επιστημονική έρευνα. Έχουν σχεδιαστεί για να διαχειρίζονται μεγάλους όγκους δεδομένων και να απαντούν αποδοτικά σε ερωτήματα. Βασικός παράγοντας που επηρεάζει την ταχύτητα των ερωτημάτων είναι η χρήση ευρετηρίων, τα οποία μπορούν να βελτιώσουν σημαντικά την ταχύτητα, την αξιοπιστία και τη συνολική απόδοση μιας βάσης δεδομένων. Ένα αποδοτικό ευρετήριο θα πρέπει να υποστηρίζει γρήγορες αναζητήσεις και ενημερώσεις, ενώ ταυτόχρονα θα πρέπει να διατηρεί χαμηλές απαιτήσεις σε αποθηκευτικό χώρο. Με τις τεχνολογικές εξελίξεις στο υλικό (hardware) των υπολογιστών, μπορούμε να ανασχεδιάσουμε τις δομές των ευρετηρίων, ώστε να γίνουν ταχύτερα και πιο αποδοτικά. Για παράδειγμα, η αυξημένη χωρητικότητα της κύριας μνήμης επιτρέπει τη μεταφορά υπολογισμών από τον δίσκο, ένα αργό αποθηκευτικό μέσο, στη μνήμη, όπου οι υπολογισμοί μπορούν να εκτελούνται ταχύτερα. Παράλληλα, οι σύγχρονοι επεξεργαστές διαθέτουν περισσότερους πυρήνες, ενισχύοντας την παράλληλη εκτέλεση των εργασιών σε πολλαπλούς πυρήνες, βελτιώνοντας έτσι την απόδοση. Επιπλέον, αυτές οι σύγχρονες τεχνολογίες υλικού είναι πλέον οικονομικά προσιτές και διαθέσιμες ακόμα και σε συμβατικούς υπολογιστές, καθιστώντας τες ιδανικούς για πληθώρα εφαρμογών. Αυτή η διατριβή εξετάζει πώς οι τεχνικές παράλληλης δεικτοδότησης στη κύρια μνήμη μπορούν να βελτιώσουν την απόδοση των σχεσιακών, χρονικών και χωρικών βάσεων δεδομένων. Αντιμετωπίζει προκλήσεις όπως η διαχείριση δεδομένων μεγάλης κλίμακας και η εκτέλεση πολύπλοκων ερωτημάτων σε σύγχρονα συστήματα. Οι συνενώσεις διαστημάτων (interval joins) αποτελούν σημαντικό κομμάτι των χρονικών βάσεων δεδομένων και είναι χρήσιμες σε πολλές εφαρμογές. Ωστόσο, μια σημαντική πρόκληση στις παράλληλες υλοποιήσεις της συνένωσης διαστημάτων είναι η αποτελεσματική κατάτμηση του χώρου, με στόχο την καλύτερη κατανομή του φόρτου εργασίας στους πυρήνες του επεξεργαστή. Μια απλή προσέγγιση είναι η διαίρεση του χώρου δεδομένων σε μη επικαλυπτόμενες περιοχές και η ανάθεση των δεδομένων κάθε περιοχής σε διαφορετικό πυρήνα. Ωστόσο, αυτό δημιουργεί ένα νέο πρόβλημα: όταν ένα διάστημα εκτείνεται σε πολλές περιοχές, η επεξεργασία των διαστημάτων αυτών από διαφορετικούς πυρήνες, μπορεί να οδηγήσει σε διπλότυπα αποτελέσματα. Ένας τρόπος διαχείρισης των διπλοτύπων είναι η χρήση μιας δομής δεδομένων, όπως ένα σύνολο (set), για την αποθήκευση μοναδικών αποτελεσμάτων. Ωστόσο, αυτό αυξάνει τη χρήση μνήμης και επιβραδύνει την απόδοση των ερωτημάτων λόγω των επιπλέον ελέγχων για διπλότυπα. Μια αποδοτική τεχνική για τον διαχωρισμό των δεδομένων, που επιλύει τα παραπάνω προβλήματα, είναι η προσέγγιση κατανομής του χώρου δεδομένων (Domain-based partitioning). Αυτή η μέθοδος διαιρεί τα δεδομένα σε τμήματα που μπορούν να υποστούν επεξεργασία ανεξάρτητα και παράλληλα, αξιοποιώντας στο έπακρο τις δυνατότητες των πολυπύρηνων επεξεργαστών. Σε αυτή την διατριβή προτείνονται τρεις παράλληλες στρατηγικές, οι οποίες είναι εφαρμόσιμες τόσο σε μεθόδους βασισμένες σε κατακερματισμό (hash-based) όσο και σε κατανομές του χώρου δεδομένων (domain-based). Αυτές οι στρατηγικές επιταχύνουν σημαντικά τις λειτουργίες συνένωσης διαστημάτων, ελαχιστοποιώντας το υπολογιστικό κόστος και βελτιώνοντας την κλιμακωσιμότητα. Η ευρετηρίαση χωρικών δεδομένων είναι απαιτητική λόγω της πολυπλοκότητας του σχήματος και της πολυδιάστατης φύσης τους. Αυτή η πολυπλοκότητα επηρεάζει την απόδοση των ερωτημάτων, ιδιαίτερα των χωρικών συνενώσεων (spatial intersection joins), οι οποίες απαιτούν πολλούς υπολογιστικούς πόρους. Όπως και οι χρονικές βάσεις δεδομένων, οι χωρικές βάσεις δεδομένων αντιμετωπίζουν επίσης προβλήματα διπλότυπων. Για παράδειγμα, σε ένα δισδιάστατο πλέγμα (grid), διπλότυπα μπορεί να εμφανιστούν όταν χωρικά αντικείμενα επικαλύπτουν πολλαπλές διαμερίσεις του πλέγματος. Η πιο κοινή τεχνική για την αποφυγή διπλοτύπων είναι η προσέγγιση σημείου αναφοράς (reference point approach), η οποία αναφέρει ένααποτέλεσμα μόνο σε μία διαμέριση του πλέγματος, αλλά απαιτεί επιπλέον υπολογισμούς. Αυτή η διατριβή επικεντρώνεται κυρίως σε μη σημειακά δεδομένα, όπου προκύπτουν ζητήματα διπλοτύπων αποτελεσμάτων. Η πρώτη μας μελέτη εστιάζει στη βελτίωση του αλγορίθμου Partition-Based Spatial Join (PBSM) για την αξιολόγηση ερωτημάτων συνένωσης στην κύρια μνήμη με παραλληλοποίηση. Επίσης, προτείνουμε τρόπους για την επιλογή των παραμέτρων του αλγορίθμου, χρησιμοποιώντας στατιστικά δεδομένα του συνόλου δεδομένων. Στη δεύτερη μελέτη μας, εισάγουμε μια νέα τεχνική κατανομής για ευρετήρια κατανομής χώρου (space-oriented partitioning - SOP), όπως τα πλέγματα. Αυτή η τεχνική δημιουργεί μια καινούργια κατανομή πάνω από το πλέγμα και κατηγοριοποιεί τα αντικείμενα σε κλάσεις. Η αποφυγή των διπλοτύπων αποτελεσμάτων γίνεται κατά την εκτέλεση του χωρικού ερωτήματος, όπου ο αλγόριθμος μας προσπελαύνει μόνο τις κλάσεις που δεν παράγουν διπλότυπα. Αυτή η καινοτομία βελτιώνει σημαντικά την αποδοτικότητα των ευρετηρίων πλέγματος για ερωτήματα εύρους και συνενώσεων. Τέλος, προτείνουμε μια παράλληλη μέθοδο που ενισχύει την απόδοση των ερωτημάτων εύρους. Οι σχεσιακές βάσεις δεδομένων αντιμετωπίζουν επίσης προκλήσεις στη δημιουργία αποδοτικών ευρετηρίων. Αυτή η διατριβή επικεντρώνεται αποκλειστικά σε δενδρικές δομές ευρετηρίων. Μία από τις πιο γνωστές και αποδοτικές δομές ευρετηρίου σε αυτόν τον τομέα είναι το B+-δέντρο, το οποίο είναι ιδιαίτερα κατάλληλο για άνισα φορτία εργασίας με δυναμικά δεδομένα και για την υποστήριξη ερωτημάτων εύρους. Με την εξέλιξη της μηχανικής μάθησης (machine learning), έχουν προταθεί πολλά ευρετήρια (learned indices) που χρησιμοποιούν μοντέλα μηχανικής μάθησης για να κατανοήσουν την κατανομή των δεδομένων και να προβλέψουν τη θέση του κλειδιού αναζήτησης μέσα σε ένα σύνολο δεδομένων. Τα ευρετήρια αυτά στοχεύουν στη μείωση των απαιτήσεων χώρου και των προσβάσεων στη μνήμη. Η κύρια διαφορά μεταξύ ενός παραδοσιακού B+-δέντρου και ενός learned index είναι ότι τα learned indices αντικαθιστούν τους εσωτερικούς κόμβους με μοντέλα μηχανικής μάθησης. Πιστεύουμε ότι τα B+-δέντρα είναι πιο αποδοτικά από τα learned indices, επειδή η απόδοση των ερωτημάτων τους είναι σταθερή και δεν επηρεάζεται από την κατανομή των δεδομένων. Πιστεύουμε επίσης ότι οι σύγχρονες τεχνολογίες υλικού δημιουργούν νέες ευκαιρίες για περαιτέρω βελτίωση της απόδοσης του B+-δέντρου.Βασισμένη στη βασική δομή του B+-δέντρο, η έρευνά μας εισάγει το BS-δέντρο, ένα νέο ευρετήριο σχεδιασμένο για την κύρια μνήμη, το οποίο αξιοποιεί σύγχρονες τεχνολογίες. Το BS-δέντρο εκμεταλλεύεται την παραλληλία δεδομένων και ενσωματώνει καινοτόμες βελτιστοποιήσεις, προσφέροντας σημαντικές βελτιώσεις σε σχέση τόσο με τα παραδοσιακά B+-δέντρα όσο και με learned indices. Τα κύρια χαρακτηριστικά του, περιλαμβάνουν έναν παράλληλο μηχανισμό διακλάδωσης με χρήση εντολών SIMD, μια στρατηγική διαχείρισης άδειων θέσεων που χρησιμοποιείδιπλότυπα κλειδιά για να καθυστερήσει τον διαχωρισμό κόμβων και να μειώσει το κόστος αναδιάταξης δεδομένων. Τέλος, προτείνουμε έναν αλγόριθμο συμπίεσης κόμβων που ελαχιστοποιεί τη χρήση μνήμης, ενώ διατηρεί υψηλή απόδοση. Συνοψίζοντας, η παρούσα διατριβή προσφέρει ένα ολοκληρωμένο πλαίσιο για τη βελτίωση της απόδοσης στις σχεσιακές, χρονικές και χωρικές βάσεις δεδομένων. Εστιάζει στη δημιουργία ευρετηρίων για την κύρια μνήμη, στη χρήση τεχνικών παράλληλης επεξεργασίας και στην αποφυγή διπλοτύπων, προσφέροντας αποδοτικές λύσεις για τις συνεχώς εξελισσόμενες ανάγκες των σύγχρονων εφαρμογών.