Multi-version indexing for large datasets with high-rate continuous insertions

Abstract

Trends in modern database workload properties are guided by business application needs with the characteristics of exponential growth of data, high-rate continuous insertions and analytical processing, aiming for knowledge gains and leading edges over competitors. Cheap Flash-based secondary storage devices provide an economic way to deal with massive amounts of modifiable data whenever their characteristics are efficiently leveraged. Thereby, it turned out that maintenance of physical materialized tuple version records in base tables not only scale with the number of concurrent transactions, but also provides beneficial access patterns to secondary storage devices, whereby asset and operational costs become manageable. However, beneficial characteristics are hardly valid for common version-oblivious additional access paths. Their actual profit is limited by excessive maintenance as well as additional search and visibility check costs. By means of empirical methods, i.e. literature studies and controlled experiments, characteristics of modern workloads, Flash-based storage hardware as well as state-of-the-art data management techniques in academia and industry are gathered in order to identify existing problems, research opportunities and challenges in mutual interactions. Based on derived findings, novel as well as matured techniques are considered to design a new kind of version-aware and hardware leveraging storage and index management structure, which is prototypically implemented and integrated in well-known systems and experimentally evaluated by system performance benchmarks. This thesis gives significant contributions in modern data management with Multi-Version Partitioned BTrees (MV-PBT) - i.e. append-based multi-versioned tuple maintenance, high-rate continuous insertion workloads with analytical processing on a common dataset instance, which comprises massive amounts of data on secondary storage devices. First, the approach massively improves selectivity of additional access paths by introduced index-only visibility checks, yielding 2× increased analytical and 14% transactional throughput in mixed workloads. Second, strict append-based and out-of-place replacement update schemes facilitate improved benefit by maintained indexes, by 47% improved throughput. Third, due to its near-optimal write characteristics and cost-efficient searches, the applied approach is highly qualified as storage management structure, with 2× increased throughput compared to widely used LSM-Tree. Fourth, logical linkage of version records facilitate independent partition, reorganization and maintenance techniques as well as robust performance characteristics for various workload properties, scaling up to orders of magnitude. Last, bloomRF, as a novel low-cost point-range filter technique, enables robust performance characteristics for search and maintenance operations in MV-PBT. Contributions of this work unambiguously elaborate benefits of high-performant version-aware index management for recent developments in modern workload properties. Moreover, extendable design concepts on base of the ubiquitous B+ -Tree combine modern in-memory techniques, massive amounts of data and form a basis for recent trends in decentralized processing and storage hardware technologies. MV-PBT exhibits a broad range of applicability and facilitates a full substitution of matured storage and index management structures.

Die Eigenschaften moderner Arbeitslasten gegenüber Datenbanken orientieren sich an den Anforderungen von Geschäftsanwendungen, die auf Wissensgewinne und einen technologischen Vorsprung ausgerichtet sind. Diese Arbeitslasten zeichnen sich durch ein exponentielles Datenwachstum, einen hohen Anteil an kontinuierlichen Einfügungen und analytische Verarbeitung aus. Flash Sekundärspeicher sind eine wirtschaftliche Möglichkeit, mit großen Mengen modifizierbarer Daten umzugehen, wenn ihre Eigenschaften effizient genutzt werden. In diesem Kontext führt die Verwaltung von physisch materialisierten Tupel-Versionen in Basistabellen durch vorteilhafte Zugriffsmuster auf Sekundärspeichermedien zu einem kostengünstigen und skalierbaren transaktionalen Durchsatz. Vorteilhafte Eigenschaften gelten jedoch kaum für gängige unversionierte sekundäre Zugriffspfade. Ihr tatsächlicher Nutzen wird durch Wartung sowie zusätzliche Kosten für Suche und Sichtbarkeitsprüfung begrenzt. Mittels empirischer Methoden, also Literaturstudien und kontrollierter Experimente, werden spezifische Eigenschaften von modernen Arbeitslasten, Flash-basierten Speichertechnologien und modernster Datenverwaltungstechniken in Wissenschaft und Industrie gesammelt, um existierende Probleme, Forschungsmöglichkeiten und Herausforderungen in deren Interaktion zu identifizieren. Auf Basis der daraus abgeleiteten Erkenntnisse werden sowohl neue als auch ausgereifte Techniken betrachtet, mit dem Ziel eine neue multi-versionierte Speicher- und Indexverwaltungsstruktur für die Eigenschaften moderner Speichertechnologien zu entwickeln. Durch standardisierten Arbeitslasten wird eine prototypische Implementierung in bekannten Systemen experimentell evaluiert. Diese Arbeit leistet einen wichtigen Beitrag zur modernen Datenverwaltung mit Multi-Version Partitioned BTrees (MV-PBT). Ferner beinhaltet dies eine anfüge-basierte Tupel-Versions-Verwaltung für Arbeitslasten mit gleichbleibend hohen Dateneinspeisungsraten und analytischer Verarbeitung einer gemeinsamen Datenbasis, welche sich hauptsächlich auf einem Sekundärspeicher befindet. Erstens, der Ansatz verbessert die Selektivität sekundärer Zugriffspfade durch die Einführung von internen Sichtbarkeitsprüfungen. Dies führt bei gemischten Arbeitslasten zu einer Verdopplung des analytischen und zu einer Erhöhung von 14% des transaktionalen Durchsatzes. Zweitens, das Tupel-Aktualisierungsverfahren verbessert die Verwaltungskosten von Indizes durch das Hinzufügen logisch verketteter Versionen, womit ein um 47% erhöhter Durchsatz erzielt wird. Drittens, MV-PBT eignet sich aufgrund seiner Schreibeigenschaften und kosteneffizienten Suchvorgängen als Speicherverwaltungsstruktur, welche den Durchsatz im Vergleich zu den verbreiteten LSM-Bäumen verdoppelt. Viertens, die logische Verknüpfung von Versionsdaten erleichtert unabhängige Partitionierungs-, Reorganisations- und Wartungstechniken, was einen gleichbleibenden und um ein Vielfaches erhöhten Durchsatz für verschiedene Arbeitslasten ermöglicht. Letztens, bloomRF ermöglicht als neuartige, kostengünstige Punkt- und Intervall-Filtertechnik gleichbleibende Leistung für Such- und Wartungsoperationen in MV-PBT. In dieser Arbeit werden die Vorteile einer multi-versionierten Hochleistungsindexverwaltung für die Eigenschaften moderner Arbeitslasten erläutert. Darüber hinaus kombinieren erweiterbare Designkonzepte auf Basis des B+ -Baums moderne Hauptspeichertechniken mit enormen Datenmengen und bilden die Grundlage für die Einbindung dezentraler Verarbeitungs- und Speichertechnologien. MV-PBT ist für ein breites Anwendungsspektrum geeignet und bildet einen ganzheitlichen Ersatz für bestehende Speicher- und Indexverwaltungsstrukturen.