Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26682
Titel: Closing the circle of algorithmic and system-centric database optimization : a comprehensive survey on adaptive indexing, data partitioning, and the rewiring of virtual memory
Alternativtitel: Über den Kreisschluss von algorithmischer und systembezogener Datenbankoptimierung : eine umfassende Untersuchung von adaptiver Indizierung, Datenpartitionierung und der Neuverdrahtung von virtuellem Speicher
VerfasserIn: Schuhknecht, Felix Martin
Sprache: Englisch
Erscheinungsjahr: 2016
Kontrollierte Schlagwörter: Informationssystem
Datenbank
Indizierung <Informatik>
Informatik
Sortieren
Speicherverwaltung
Betriebssystem
Optimierung
Freie Schlagwörter: Adaptivität
Datenpartitionierung
virtueller Speicher
adaptivity
database cracking
virtual memory
rewiring memory
data partitioning
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
Abstract: Over the decades, with the increase of computing resources, the amount of data to manage also increased tremendously. Besides of the sheer quantity of information, the quality of it highly varies today. Indexing all this data with equal effort is cumbersome and wasteful. Thus, adaptive indexing algorithms refine parts of interest more carefully. Unfortunately, the adaptivity also introduces a set of new problems. High variance in response times and low robustness against certain workloads are just two issues to mention. A vast amount of methods have been proposed to deal with these problems. Thus, in the first part of this thesis, we will reinvestigate, analyze, and enhance the class of adaptive indexing methods in a comprehensive evaluation on the algorithmic level. In total, we discuss 18 cracking methods, 6 sorting algorithms, and 3 full index structures, including our own proposed methods. Consequently, we identify data partitioning as the common component. Thus, in the second part, we analyze the surprising amount of optimizations possible to enhance partitioning. Interestingly, they mostly originate from a more sophisticated mapping of the method to the system properties, thus shifting our perspective to a system-centric view. Subsequently, in the third part, we dig down to the ground level by exploiting a core feature of any modern operating system, the virtual memory system. We investigate how virtual and physical memory can be separated in user space and how the mappings between the two memory types can be rewired freely at run-time. Using rewiring, we are able to significantly enhance core applications of data management systems. Finally, we apply the techniques identified in this thesis to the initial adaptive indexing algorithm to significantly improve it — and close the circle.
Im Laufe der Jahrzehnte kam es neben dem Anstieg der zur Verfüung stehenden Berechnungsressourcen auch zu einem heftigen Anstieg der zu verwaltenden Datenmengen. Abgesehen von der schieren Größe der Informationsmenge variiert heutzutage auch die Qualität dieser in großem Maße. Die Datenmenge mit gleichverteiltem Aufwand zu indizieren ist ein mühseliges und verschwenderisches Unterfangen. Daher investiert die Klasse der adaptiven Indizes mehr Indizierungsaufwand auf Bereiche von Interesse. Leider bringt adaptive Indizierung auch einige neue Probleme mit sich, die es zu handhaben gilt. Große Varianz in der Laufzeit und schwache Robustheit gegenüber gewissen Anfragemustern sind nur zwei der zu benennenden Schwierigkeiten. Um diesen Problemen entgegenzuwirken kam es in der Vergangenheit zur Entwicklung einer großen Anzahl verschiedenster Algorithmen. Im ersten Teil dieser Dissertation werden wir daher die Klasse der adaptiven Indizes in einer allumfassenden Evaluierung auf algorithmischer Ebene neu untersuchen, analysieren und erweitern. Insgesamt behandelt diese Auswertung 18 verschiedene Cracking-Methoden, 6 Sortieralgorithmen und 3 traditionelle Indexstrukturen, inklusive unserer eigenen Algorithmen. Auf Basis dieser Untersuchungen identifizieren wir Datenpartitionierung als gemeinsame Komponente. Daher analysieren wir im zweiten Teil dieser Dissertati- on die überraschend große Anzahl an möglichen Optimierungen zur Verbesserung der Partitionierungsphase. Interessanterweise entspringen diese hauptsächlich einer ausgeklügelteren Abbildung des Problems auf die Gegebenheiten des zu Grunde liegenden Systems. Daher verlagern wir unsere Perspektive auf eine system-zentrische Ebene. Darauffolgend gelangen wir im dritten Teil dieser Dissertation auf die unterste Ebene der Betrachtung, indem wir uns der Ausnutzung eines elementaren Bestandteiles eines jeden modernen Betriebssystems widmen, der virtuellen Speicherverwaltung. Wir untersuchen wie virtueller und physischer Speicher in der Benutzerumgebung voneinander getrennt werden können und wie die Abbildungen zwischen den beiden Speichertypen zur Laufzeit manipuliert und neu verdrahtet werden können. Mit Hilfe dieser Technik sind wir in der Lage, Kernapplikationen von Datenbanksystemen nachhaltig zu verbessern. Abschließend wenden wir die im Laufe dieser Arbeit identifizierten Methoden auf den initialen adaptiven Indizierungsalgorithmus an und verbessern diesen signifikant — um den Kreis zu schließen.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-67182
hdl:20.500.11880/26738
http://dx.doi.org/10.22028/D291-26682
Erstgutachter: Dittrich, Jens
Tag der mündlichen Prüfung: 8-Dez-2016
Datum des Eintrags: 19-Dez-2016
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
Diss_FelixMartinSchuhknecht.pdf8,28 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.