Many applications require storage and indexing of new kinds of data in main-memory, e.g. color histograms, textures, shape features, gene sequences, sensor readings, or financial time series. Even though, many domain index structures were developed, very a few of them are implemented in any database management system (DBMS), usually only B-trees and hash indexes. A major reason is that the manual effort to include a new index implementation in a regular DBMS is very costly and time-consuming because it requires integration with all components of the DBMS kernel. To alleviate this, there are some extensible indexing frameworks. However, they all require re-engineering the index implementations, which is a problem when the index has third-party ownership, when only binary code is available, or simply when the index implementation is complex to re-engineer. Therefore, the DBMS should allow including new index implementations without code changes and performance degradation. Furthermore, for high performance the query processor needs knowledge of how to process queries to utilize plugged-in index. Moreover, it is important that all functionalities of a plugged-in index implementation are correct. The extensible main memory database system (MMDB) Mexima (Main-memory External Index Manager) addresses these challenges. It enables transparent plugging in main-memory index implementations without code changes. Index specific rewrite rules transform complex queries to utilize the indexes. Automatic test procedures validate the correctness of them based on user provided index meta-data. Moreover, the same optimization framework can also optimize complex queries sent to a back-end DBMS by exposing hidden indexes for its query optimizer. Altogether, Mexima is a complete and extensible platform for transparently index integration, utilization, and evaluation.

Über die letzten Jahrzehnte haben sich Datenbanken von festplatten-basierten zu hauptspeicher-basierten Datenbanksystemen entwickelt. Um diese Herausforderungen anzugehen und das volle Potenzial moderner Prozessoren zu erschließen, stellt diese Dissertation vier Ansätze vor um den Einfluss der „Memory Wall“ zu reduzieren. Der erste Ansatz zeigt auf, wie spezielle Prozessorinstruktionen (sogenannte SIMD Instruktionen) die Ausnutzung von Caches erhöhen und gleichzeitig die Anzahl der Instruktionen verringern. In dieser Arbeit werden dazu vorhandene Baumstrukturen so angepasst, dass diese SIMD Instruktionen verwendet werden können und somit die benötigte Hauptspeicherbandbreite verringert wird. Der zweite Ansatz dieser Arbeit führt ein Model ein, welches es ermöglicht die Anfrageausführung in verschiedenen Datenbanksystemen zu vereinheitlichen und dadurch vergleichbar zu machen. Durch diese Vereinheitlichung wird es möglich, die Hardwareausnutzung durch Hinzunahme von Wissen über die auszuführende Hardware zu optimieren. Der dritte Ansatz analysiert verschiedene Datenbankoperatoren bezüglich ihres Verhaltens auf verschiedenen Hardwareumgebungen. Diese Analyse ermöglicht es, Datenbankoperatoren besser zu verstehen und Kostenmodelle für ihr Verhalten zu entwickeln. Der vierte Ansatz dieser Arbeit baut auf der Analyse der Operatoren auf und führt einen progressiven Optimierungsalgorithmus ein, der die Ausführung von Anfragen zur Laufzeit auf die jeweiligen Bedingungen wie z.B. Daten- oder Hardwareeigenschaften anpasst. Dazu werden zur Laufzeit prozessorinterne Zähler verwendet, die das Verhalten des Operators auf der jeweiligen Hardware widerspiegeln. / Over the last decades, database systems have been migrated from disk to memory architectures such as RAM, Flash, or NVRAM. Research has shown that this migration fundamentally shifts the performance bottleneck upwards in the memory hierarchy. Whereas disk-based database systems were largely dominated by disk bandwidth and latency, in-memory database systems mainly depend on the efficiency of faster memory components, e.g., RAM, caches, and registers. To encounter these challenges and enable the full potential of the available processing power of modern CPUs for database systems, this thesis proposes four approaches to reduce the impact of the Memory Wall. First, SIMD instructions increase the cache line utilization and decrease the number of executed instructions if they operate on an appropriate data layout. Thus, we adapt tree structures for processing with SIMD instructions to reduce demands on the memory bus and processing units are decreased. Second, by modeling and executing queries following a unified model, we are able to achieve high resource utilization. Therefore, we propose a unified model that enables us to utilize knowledge about the query plan and the underlying hardware to optimize query execution. Third, we need a fundamental knowledge about the individual database operators and their behavior and requirements to optimally distribute the resources among available computing units. We conduct an in-depth analysis of different workloads using performance counters create these insights. Fourth, we propose a non-invasive progressive optimization approach based on in-depth knowledge of individual operators that is able to optimize query execution during run-time. In sum, using additional run-time statistics gathered by performance counters, a unified model, and SIMD instructions, this thesis improves query execution on modern CPUs.

abstract: The availability of a wide range of general purpose as well as accelerator cores on modern smartphones means that a significant number of applications can be executed on a smartphone simultaneously, resulting in an ever increasing demand on the memory subsystem. While the increased computation capability is intended for improving user experience, memory requests from each concurrent application exhibit unique memory access patterns as well as specific timing constraints. If not considered, this could lead to significant memory contention and result in lowered user experience. This work first analyzes the impact of memory degradation caused by the interference at the memory system for a broad range of commonly-used smartphone applications. The real system characterization results show that smartphone applications, such as web browsing and media playback, suffer significant performance degradation. This is caused by shared resource contention at the application processor’s last-level cache, the communication fabric, and the main memory. Based on the detailed characterization results, rest of this thesis focuses on the design of an effective memory interference mitigation technique. Since web browsing, being one of the most commonly-used smartphone applications and represents many html-based smartphone applications, my thesis focuses on meeting the performance requirement of a web browser on a smartphone in the presence of background processes and co-scheduled applications. My thesis proposes a light-weight user space frequency governor to mitigate the degradation caused by interfering applications, by predicting the performance and power consumption of web browsing. The governor selects an optimal energy-efficient frequency setting periodically by using the statically-trained performance and power models with dynamically-varying architecture and system conditions, such as the memory access intensity of background processes and/or coscheduled applications, and temperature of cores. The governor has been extensively evaluated on a Nexus 5 smartphone over a diverse range of mobile workloads. By operating at the most energy-efficient frequency setting in the presence of interference, energy efficiency is improved by as much as 35% and with an average of 18% compared to the existing interactive governor, while maintaining the satisfactory performance of web page loading under 3 seconds. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2016

The expansion of the internet over recent years has resulted in an increase in digital attacks on computers. Most attacks, including the more dangerous ones, directly target program vulnerabilities. The increase in attacks has prompted a need to develop new ways to classify, detect, and avoid vulnerabilities. The effectiveness of these goals relies on the development of new methods and tools that facilitate the process of detecting vulnerabilities and exploits. This thesis presents the development of a tool that provides a visual representation of main memory for the purpose of security analysis. The tool provides new insight into memory utilization by software; users are able to see memory utilization as execution time progression, visually distinguish between memory behaviors (allocations, writes, etc), and visually observe special relationships between memory locations. The insight enables users to search for visual evidence that software is vulnerable, violated, or utilizing memory incorrectly. The development process for our visual tool has three stages: (1) identifying the memory utilization policies of the Windows 32-bit operating system; (2) identifying the data required for visual representations of memory and then implementing one possible method to capture the data; and (3) enumerating and implementing requirements for a memory tool that generates visual representations of memory for the purpose of vulnerability and exploit analysis. / Master of Science

This thesis proposes a new methodology to extend the software performance engineering process. Common performance measurement and tuning principles mainly target to improve the software function itself. Hereby, the application source code is studied and improved independently of the overall system performance behavior. Moreover, the optimization of the software function has to be done without an estimation of the expected optimization gain. This often leads to an under- or overoptimization, and hence, does not utilize the system sufficiently. The proposed performance improvement methodology and framework, called dynamic performance stubs, improves the before mentioned insufficiencies by evaluating the overall system performance improvement. This is achieved by simulating the performance behavior of the original software functionality depending on an adjustable optimization level prior to the real optimization. So, it enables the software performance analyst to determine the systems’ overall performance behavior considering possible outcomes of different improvement approaches. Moreover, by using the dynamic performance stubs methodology, a cost-benefit analysis of different optimizations regarding the performance behavior can be done. The approach of the dynamic performance stubs is to replace the software bottleneck by a stub. This stub combines the simulation of the software functionality with the possibility to adjust the performance behavior depending on one or more different performance aspects of the replaced software function. A general methodology for using dynamic performance stubs as well as several methodologies for simulating different performance aspects is discussed. Finally, several case studies to show the application and usability of the dynamic performance stubs approach are presented.

This thesis explores memory performance for smartphone workloads. We design a Video Conference Workload (VCW) to model typical smartphone usage. We describe a trace-based methodology which uses a software implementation to mimic the behaviour of specialised hardware accelerators. Our methodology stores dataflow information from the original application to maintain the relationships between requests. We first study seven address mapping schemes with our VCW, using a first-ready, first-come-first-served (FR-FCFS) memory scheduler. Our results show the best performing scheme is up to 82% faster than the worst. The VCW is memory intensive, with up to 86.8% bandwidth utilisation using the best performing scheme. We also test a Web Browsing and a set of computer vision workloads. Most are not memory intensive, with utilisation under 15%. Finally, we compare four schedulers and find that the FR-FCFS scheduler using the Write Drain mode [8] performed the best, outperforming the worst scheduler by 6.3%.

This thesis explores memory performance for smartphone workloads. We design a Video Conference Workload (VCW) to model typical smartphone usage. We describe a trace-based methodology which uses a software implementation to mimic the behaviour of specialised hardware accelerators. Our methodology stores dataflow information from the original application to maintain the relationships between requests. We first study seven address mapping schemes with our VCW, using a first-ready, first-come-first-served (FR-FCFS) memory scheduler. Our results show the best performing scheme is up to 82% faster than the worst. The VCW is memory intensive, with up to 86.8% bandwidth utilisation using the best performing scheme. We also test a Web Browsing and a set of computer vision workloads. Most are not memory intensive, with utilisation under 15%. Finally, we compare four schedulers and find that the FR-FCFS scheduler using the Write Drain mode [8] performed the best, outperforming the worst scheduler by 6.3%.

There has been a surge of new databases in recent years. Applications today create a higher demand on database performance than ever before. Main-memory databases have come into the market quite recently and they are just now catching a lot of interest from many different directions. Main-memory databases are a type of database that stores all of its data in the primary memory. They provide a big increase in performance to a lot of different applications. This work evaluates the difference in performance between two chosen candidates. To represent main memory databases we chose VoltDB and to represent traditional databases we chose MySQL. We have performed several tests on those two databases. We point out differences in functionality, performance and design choices. We want to create a reference where anyone that considers changing from a traditional database to a main memory database, can find support for their decision. What are the advantages and what are the disadvantages of using a main-memory database, and when should we switch from our old database to a newer technology.

Datenbanksysteme verwenden Indexstrukturen, um Suchanfragen zu beschleunigen. Im Laufe der letzten Jahre haben Forscher verschiedene Ansätze zur Indexierung von Datenbanktabellen im Hauptspeicher entworfen. Hauptspeicherindexstrukturen versuchen möglichst häufig Daten zu verwenden, die bereits im Zwischenspeicher der CPU vorrätig sind, anstatt, wie bei traditionellen Datenbanksystemen, die Zugriffe auf den externen Speicher zu optimieren. Die meisten vorgeschlagenen Indexstrukturen für den Hauptspeicher beschränken sich jedoch auf Punktabfragen und vernachlässigen die ebenso wichtigen Bereichsabfragen, die in zahlreichen Anwendungen, wie in der Analyse von Genomdaten, Sensornetzwerken, oder analytischen Datenbanksystemen, zum Einsatz kommen. Diese Dissertation verfolgt als Hauptziel die Fähigkeiten von modernen Hauptspeicherdatenbanksystemen im Ausführen von Bereichsabfragen zu verbessern. Dazu schlagen wir zunächst die Cache-Sensitive Skip List, eine neue aktualisierbare Hauptspeicherindexstruktur, vor, die für die Zwischenspeicher moderner Prozessoren optimiert ist und das Ausführen von Bereichsabfragen auf einzelnen Datenbankspalten ermöglicht. Im zweiten Abschnitt analysieren wir die Performanz von multidimensionalen Bereichsabfragen auf modernen Serverarchitekturen, bei denen Daten im Hauptspeicher hinterlegt sind und Prozessoren über SIMD-Instruktionen und Multithreading verfügen. Um die Relevanz unserer Experimente für praktische Anwendungen zu erhöhen, schlagen wir zudem einen realistischen Benchmark für multidimensionale Bereichsabfragen vor, der auf echten Genomdaten ausgeführt wird. Im letzten Abschnitt der Dissertation präsentieren wir den BB-Tree als neue, hochperformante und speichereffziente Hauptspeicherindexstruktur. Der BB-Tree ermöglicht das Ausführen von multidimensionalen Bereichs- und Punktabfragen und verfügt über einen parallelen Suchoperator, der mehrere Threads verwenden kann, um die Performanz von Suchanfragen zu erhöhen. / Database systems employ index structures as means to accelerate search queries. Over the last years, the research community has proposed many different in-memory approaches that optimize cache misses instead of disk I/O, as opposed to disk-based systems, and make use of the grown parallel capabilities of modern CPUs. However, these techniques mainly focus on single-key lookups, but neglect equally important range queries. Range queries are an ubiquitous operator in data management commonly used in numerous domains, such as genomic analysis, sensor networks, or online analytical processing. The main goal of this dissertation is thus to improve the capabilities of main-memory database systems with regard to executing range queries. To this end, we first propose a cache-optimized, updateable main-memory index structure, the cache-sensitive skip list, which targets the execution of range queries on single database columns. Second, we study the performance of multidimensional range queries on modern hardware, where data are stored in main memory and processors support SIMD instructions and multi-threading. We re-evaluate a previous rule of thumb suggesting that, on disk-based systems, scans outperform index structures for selectivities of approximately 15-20% or more. To increase the practical relevance of our analysis, we also contribute a novel benchmark consisting of several realistic multidimensional range queries applied to real- world genomic data. Third, based on the outcomes of our experimental analysis, we devise a novel, fast and space-effcient, main-memory based index structure, the BB- Tree, which supports multidimensional range and point queries and provides a parallel search operator that leverages the multi-threading capabilities of modern CPUs.

In-Memory-Datenbanken halten den gesamten Datenbestand permanent im Hauptspeicher vor. Somit können lesende Zugriffe weitaus schneller erfolgen als bei traditionellen Datenbanksystemen, da keine I/O-Zugriffe auf die Festplatte erfolgen müssen. Für schreibende Zugriffe wurden Mechanismen entwickelt, die Persistenz und somit Transaktionssicherheit gewährleisten. In-Memory-Datenbanken werden seit geraumer Zeit entwickelt und haben sich in speziellen Anwendungen bewährt. Mit zunehmender Speicherdichte von DRAM-Bausteinen sind Hardwaresysteme wirtschaftlich erschwinglich, deren Hauptspeicher einen kompletten betrieblichen Datenbestand aufnehmen können. Somit stellt sich die Frage, ob In-Memory-Datenbanken auch in betrieblichen Anwendungssystemen eingesetzt werden können. Hasso Plattner, der mit HANA eine In-Memory-Datenbank entwickelt hat, ist ein Protagonist dieses Ansatzes. Er sieht erhebliche Potenziale für neue Konzepte in der Entwicklung betrieblicher Informationssysteme. So könne beispielsweise eine transaktionale und eine analytische Anwendung auf dem gleichen Datenbestand laufen, d. h. eine Trennung in operative Datenbanken einerseits und Data-Warehouse-Systeme andererseits ist in der betrieblichen Informationsverarbeitung nicht mehr notwendig (Plattner und Zeier 2011). Doch nicht alle Datenbank-Vertreter stimmen darin überein. Larry Ellison hat die Idee des betrieblichen In-Memory-Einsatzes, eher medienwirksam als seriös argumentativ, als „wacko“ bezeichnet (Bube 2010). Stonebraker (2011) sieht zwar eine Zukunft für In-Memory-Datenbanken in betrieblichen Anwendungen, hält aber weiterhin eine Trennung von OLTP- und OLAP-Anwendungen für sinnvoll. [Aus: Einleitung]