In-memory indexing for parallel processing of single and multi-dimensional queries

Abstract

Database Systems are essential for modern applications, providing structured, efficient, and reliable ways to manage data in fields like banking, healthcare, and scientific research. They are designed to handle large amounts of data and answer queries quickly. A key factor in making queries fast is the use of indices. Efficient indexing can significantly improve the speed, credibility, and overall performance of a database. A good index supports fast searches and updates, while having low space requirements. With the advancements in hardware, we can redesign index structures to be faster and more efficient. For example, larger memory capacities allow us to move computations from disk storage to faster in-memory processing. Additionally, the latest processors offer significantly more cores, enhancing parallel computing by distributing tasks across multiple cores to improve performance. These modern hardware components are affordable and found in commodity computers, making them accessible for a wide range of applications. This dissertation examines how in-memory indexing combined with parallel processing techniques can enhance the performance of relational, temporal, and spatial databases. It addresses challenges like managing large-scale data and running complex queries on modern systems. Interval joins are crucial for temporal databases and are also useful in many applications. However, a major challenge in parallel implementations of interval joins is dividing the workload effectively across processor cores. A simple approach is to split the data domain into disjoint partitions and assign the data in each partition to a different core. However, this creates a new problem: when an interval spans multiple stripes, it must be processed by multiple cores, possibly generating duplicate join results. One way to handle duplicates is by using a data structure like a set to store unique results. However, this increases memory usage and slows down query performance because of the extra checks for duplicates. Domain-based partitioning approach divides the data into partitions that can be processed independently and in parallel, maximizing multi-core hardware capabilities. This study introduces three distinct strategies for parallel partitioning applicable to both hash-based and domain-based methods, significantly accelerating partitioning operations by reducing computational overhead and improving scalability. Indexing spatial data is challenging due to their shape and dimensionality. This complexity affects query performance, particularly for spatial intersection joins, which are the most resource-intensive. Like temporal databases, spatial databases also face duplication issues. For example, in a 2D grid, duplicates can occur when spatial objects overlap multiple grid tiles. The most common technique to avoid duplicates is the reference point approach, which reports a result in only one tile of the grid but requires additional computations. This dissertation primarily focuses on non-point data, where duplication issues arise. Our first study focuses on improving the Partition-Based Spatial Join (PBSM) algorithm for in-memory and parallel evaluation of spatial joins. We show how to choose the best partitioning settings based on data statistics to fine-tune the algorithm for specific join inputs. In our second study, we introduce a new secondary partitioning technique for space-oriented partitioning (SOP) indices, such as grids. This technique removes duplicate results during spatial queries by organizing objects within each partition and only accessing classes that do not produce duplicates. This innovation greatly improves the efficiency of grid-based spatial indices for range (disk and rectangle) and intersection joins. Finally, we propose a parallel method that boosts the performance of range queries. Relational databases also face challenges in creating efficient indices. This dissertation focuses only on tree-like indices. One of the most well-known and efficient indexing structures in this domain is the B+-tree, particularly suited for skewed workloads with dynamic data and for supporting range queries. With the rise of machine learning, many learned indices have been introduced. A learned index uses ML models to “learn” the data distribution and predict the location of the search key within a dataset aiming to reduce the space requirements and the memory accesses. The main difference between a traditional B+-tree and a learned index is that learned indices replace inner nodes with machine learning models. We believe that B+-tree are more efficient than learned indices because their query performance is stable and not affected by the data distribution. We also believe that advancements in hardware technology create new opportunities to further improve B-tree performance. Building on the foundational B+-tree structure, this research introduces BS-tree, a new indexing structure designed for main memory and modern hardware. The BS-tree leverages data parallelism and integrates innovative optimizations, offering significant advancements over both traditional B+-tree and emerging learned indices. Key features include a data-parallel branching mechanism implemented using SIMD instructions, a gap management strategy employing duplicate keys to delay splits and reduce data-shifting overhead, and a node compression scheme that minimizes memory usage while maintaining high throughput. In summary, this dissertation provides a comprehensive framework for enhancing the performance of relational, temporal, and spatial databases. Through the integration of in-memory indexing, parallel processing techniques and duplicate avoidance techniques, this dissertation delivers robust, scalable, and efficient solutions for the evolving needs of modern data-intensive applications.

Οι βάσεις δεδομένων είναι απαραίτητες για τις σύγχρονες εφαρμογές, προσφέροντας δομημένους, αποδοτικούς και αξιόπιστους τρόπους διαχείρισης δεδομένων σε τομείς όπως οι τραπεζικές συναλλαγές, η υγειονομική περίθαλψη και η επιστημονική έρευνα. Έχουν σχεδιαστεί για να διαχειρίζονται μεγάλους όγκους δεδομένων και να απαντούν αποδοτικά σε ερωτήματα. Βασικός παράγοντας που επηρεάζει την ταχύτητα των ερωτημάτων είναι η χρήση ευρετηρίων, τα οποία μπορούν να βελτιώσουν σημαντικά την ταχύτητα, την αξιοπιστία και τη συνολική απόδοση μιας βάσης δεδομένων. Ένα αποδοτικό ευρετήριο θα πρέπει να υποστηρίζει γρήγορες αναζητήσεις και ενημερώσεις, ενώ ταυτόχρονα θα πρέπει να διατηρεί χαμηλές απαιτήσεις σε αποθηκευτικό χώρο. Με τις τεχνολογικές εξελίξεις στο υλικό (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, μια στρατηγική διαχείρισης άδειων θέσεων που χρησιμοποιείδιπλότυπα κλειδιά για να καθυστερήσει τον διαχωρισμό κόμβων και να μειώσει το κόστος αναδιάταξης δεδομένων. Τέλος, προτείνουμε έναν αλγόριθμο συμπίεσης κόμβων που ελαχιστοποιεί τη χρήση μνήμης, ενώ διατηρεί υψηλή απόδοση. Συνοψίζοντας, η παρούσα διατριβή προσφέρει ένα ολοκληρωμένο πλαίσιο για τη βελτίωση της απόδοσης στις σχεσιακές, χρονικές και χωρικές βάσεις δεδομένων. Εστιάζει στη δημιουργία ευρετηρίων για την κύρια μνήμη, στη χρήση τεχνικών παράλληλης επεξεργασίας και στην αποφυγή διπλοτύπων, προσφέροντας αποδοτικές λύσεις για τις συνεχώς εξελισσόμενες ανάγκες των σύγχρονων εφαρμογών.