Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Bereichsnavigation

Hauptinhalt

Efficient Scans on Modern Hardware (Benjamin Kramer)

Title

Efficient Scans on Modern Hardware

Type

Master's Thesis

Author

Benjamin Kramer

Abstract

In recent years, hardware characteristics, software systems, and application patterns have all changed in a way that emphasizes the importance of scan tasks in modern main-memory database systems. Main memory is available cheaply and can hold significant amounts of data nowadays. In-memory computing has matured and has resulted in key business platforms such as SAP HANA. Expectations for ad-hoc querying defeat the use of pre-built index structures and mandate scans instead.

At the same time, it is still unclear how the latest advances on the hardware side can best be leveraged to support efficient scans. Growing SIMD widths, for instance, appeal with theoretical speed-ups of up 16× or more. But existing strategies for predicate evaluation and scans are not prepared for such large SIMD widths. In fact, even for smaller SIMD sizes it is not clear how, e. g., predicates that involve multiple data types and widths can be realized most efficiently.

This thesis studies and evaluates methods that make use of modern hardware technologies to accelerate scans, in particular SIMD-Scan, BitWeaving and ByteSlice. Starting from SIMD-Scan, methods to further reduce memory bandwidth are explored by skipping parts of the input efficiently or by reducing the output size by handling intermediate results more efficiently.

Abstract in German

In den vergangenen Jahren haben sich Hard- und Software sowie die Anforderungen an die Software so geändert, dass der Scan – das Durchsuchen einer Spalte in einer Datenbank – in In-Memory-Datenbanken immer wichtiger wird. Hauptspeicher ist günstig und kann heute große Mengen an Daten halten. In-Memory-Datenbanken sind verbreitet und ausgereift und werden an Schlüsselstellen in der Wirtschaft verwendet, wie etwa SAP HANA. Die Anforderungen an diese Datenbanken können oft nicht durch vorberechnete Indices erfüllt werden und benötigen anstelle dessen Scans.

Gleichwohl ist es immer noch unklar wie man die neusten Errungenschaften in der Hardware am besten für diese Scans nutzen kann. Breitere SIMD-Register zum Beispiel, könnten theoretisch eine Beschleunigung um das 16-fache erreichen. Aber bestehende Scan-Methoden sind nicht auf solch breite Register vorbereitet. Selbst für kleinere SIMD-Breiten ist es nicht klar wie Prädikate mit mehreren Datentypen am effizientesten realisiert werden können.

Diese Masterarbeit beschäftigt sich mit Methoden, die diese moderne Hardware ausnutzen um Scans zu Beschleunigung, mit einem Fokus auf SIMD-Scan, BitWeaving und ByteSlice. Vom Startpunkt des SIMD-Scan werden weitere Möglichkeiten untersucht um die benötigte Speicherbandbreite zu reduzieren, zum Beispiel durch Überspringen von Teilen der Eingabe oder durch Reduzierung der Ausgabemenge durch effizientere Verwaltung von Zwischenergebnissen.

Download

Document as PDF