Techniques and systems for online and distributed database processing

Abstract

Modern information processing is moving into a realm where we often need to process large amounts of data on daily basis, as a result of increasing monitoring of environmental parameters, market transactions, web activity, and other sources of valuable information. The availability of this data establishes new business and application scenarios with increasing performance requirements. Current database engines are expected to analyze the data while providing a high query throughput. In order to accommodate user needs, it is necessary to reconsider the role of several database components in a new light. In particular, advances of the state of the art need to be introduced in the query processing, transaction processing and index management areas. Advances in the query processing module of the database engine are triggered by the need to accommodate new scenarios. While traditional query processing is designed with the assumption that data is always available, modern database systems should be ready to process various types of incoming, streamed data, often arriving at uncontrollable rates or experiencing variable delays. New query processing algorithms, and in particular join algorithms, need to be designed in order to retrieve valuable information from this type of input as soon as incoming data is available. This thesis addresses two common operations: the join of two (or more) data inputs streamed in by autonomous sources and the join of a data stream with a disk-resident relation. The transaction processing system is nowadays faced with new challenges as a result of data replication. Data replication introduces the potential for higher availability and better performance compared to the traditional centralized management, by sharing the database load between several engines. However, maintaining consistency amongst the replicas in the presence of updates is far from trivial. Transaction processing needs to be governed by novel concurrency control mechanisms suitable for data replication. This thesis shows how to provide transactional properties, atomicity, consistency, isolation and durability, in a replicated database in an efficient and scalable manner. Selecting indices that are appropriate for the workload is an important task for the database, since indices directly impact the performance of query processing. It is also an interesting optimization problem, as indices may help some parts of the workload, while requiring maintenance overhead when the data is updated. As database applications become increasingly complex, index tuning becomes more and more challenging for database administrators. This thesis introduces an online technique that captures the relevant changes in the workload and manages the indexes in parallel with query processing.

Η επεξεργασία πληροφοριών στις μέρες μας απαιτεί συχνά την καθημερινή επεξεργασία μεγάλων όγκων δεδομένων, όπως αυτά προκύπτουν από τη συνεχώς αυξανόμενη παρακολούθηση περιβαλλοντικών παραμέτρων, επιχειρηματικών συναλλαγών, δραστηριοτήτων στο διαδίκτυο, καθώς και άλλων σημαντικών πληροφοριών που προέρχονται από διάφορες πηγές. Το κρίσιμο ζήτημα της διαθεσιμότητας των δεδομένων αυτών οδηγεί σε νέες εφαρμογές που χαρακτηρίζονται από ιδιαίτερα υψηλές απαιτήσεις στην απόδοση. Οι σύγχρονες βάσεις δεδομένων καλούνται να πραγματοποιούν την ανάλυση των δεδομένων αυτών, ενώ την ίδια στιγμή πρέπει να είναι σε θέση να εξυπηρετούν μεγάλο όγκο επερωτήσεων χωρίς καθυστερήσεις. Για να ικανοποιηθούν οι ανάγκες των χρηστών, πολλά επιμέρους στοιχεία των βάσεων δεδομένων πρέπει να μελετηθούν εκ νέου και υπό το νέο πρίσμα των σύγχρονων αναγκών. Πιο συγκεκριμένα, απαιτούνται νέες προσεγγίσεις στις επιμέρους περιοχές της επεξεργασίας επερωτήσεων, της επεξεργασίας συναλλαγών και της διαχείρισης ευρετηρίων. Στην περιοχή της επεξεργασίας επερωτήσεων, οι παραδοσιακές βάσεις δεδομένων έχουν σχεδιαστεί θεωρώντας ότι τα δεδομένα είναι πάντα διαθέσιμα. Τα σύγχρονα συστήματα βάσεων δεδομένων, όμως, πρέπει να είναι σε θέση να επεξεργαστούν διάφορους τύπους εισερχομένων δεδομένων, ροών δεδομένων, που συχνά εισέρχονται στο σύστημα με απρόβλεπτο ρυθμό ή/και εμφανίζοντας μεγάλες καθυστερήσεις στην άφιξή τους. Για το λόγο αυτό καθίσταται αναγκαία η ανάπτυξη νέων αλγορίθμων σύζευξης για την ανάκτηση σημαντικής πληροφορίας από τέτοιου είδους δεδομένα και μάλιστα από την πρώτη στιγμή που ξεκινά η εισαγωγή τους στο σύστημα. Στην παρούσα διατριβή αντιμετωπίζονται αρχικά δύο βασικές λειτουργίες, η σύζευξη δύο ή περισσοτέρων ροών δεδομένων προερχόμενες από αυτόνομες πηγές, καθώς και η σύζευξη μίας ροής δεδομένων με μία συσχέτιση που βρίσκεται στο δίσκο του συστήματος. Παράλληλα, η δημιουργία αντιγράφων δεδομένων εισάγει νέες προκλήσεις στη διαχείριση των συναλλαγών. Η ύπαρξη των αντιγράφων των δεδομένων οδηγεί σε μεγαλύτερη διαθεσιμότητα και σε καλύτερες αποδόσεις στα σύγχρονα συστήματα συγκρινόμενα με τις παραδοσιακές βάσεις δεδομένων μέσω του διαμοιρασμού του φόρτου της βάσης σε διαφορετικές μηχανές. Ένα σημαντικό ζήτημα που τίθεται όμως στις περιπτώσεις αυτές είναι η διατήρηση της συνέπειας ανάμεσα στα αντίγραφα αυτά, καθώς τα δεδομένα ανανεώνονται συνεχώς. Κρίνεται λοιπόν απαραίτητη η δημιουργία νέων μεθόδων ελέγχου του συγχρονισμού των αντιγράφων αυτών. Υιοθετώντας την προσέγγιση των βάσεων δεδομένων που χρησιμοποιούν αντίγραφα, αναπτύξαμε στην παρούσα διατριβή αποδοτικούς μηχανισμούς για τη διατήρηση των απαραίτητων ιδιοτήτων των αντιγράφων: ατομικότητα, συνέπεια, απομόνωση, ανθεκτικότητα. Τέλος, η επιλογή των κατάλληλων ευρετηρίων αποτελεί σημαντικό ζήτημα στη διαχείριση των βάσεων δεδομένων, λόγω της μεγάλης εξάρτησης που παρουσιάζει η απόδοση της επεξεργασίας επερωτήσεων από τη χρήση ευρετηρίων. Η επιλογή των ευρετηρίων αποτελεί ένα ιδιαίτερα ενδιαφέρον πρόβλημα βελτιστοποίησης, καθώς αυτά μπορούν να εξυπηρετούν ένα μέρος του φόρτου επερωτήσεων απαιτώντας όμως ταυτόχρονα επιπλέον διαχειριστικό κόστος κάθε φορά που τα δεδομένα ανανεώνονται. Στις σύγχρονες βάσεις δεδομένων που εμφανίζουν μεγάλη πολυπλοκότητα, η επιτυχής διαχείριση των ευρετηρίων αποτελεί σημαντική πρόκληση για τους διαχειριστές των συστημάτων αυτών. Στην παρούσα διατριβή παρουσιάζουμε μια συνεχή τεχνική που αντιλαμβάνεται τις αλλαγές στα δεδομένα που σχετίζονται με το φόρτο του συστήματος και διαχειρίζεται αποδοτικά τα ευρετήρια, ενώ παράλληλα επιτρέπει την αδιάλειπτη επεξεργασία των επερωτήσεων.