Cache conscious column organization in in-memory column stores

Kostenmodelle sind ein essentieller Teil von Datenbanksystemen und bilden die Basis für Optimierungen von Ausführungsplänen. Durch Abschätzungen der Kosten können die entsprechend schnellsten Operatoren und Algorithmen zur Abarbeitung einer Anfrage ausgewählt und ausgeführt werden. Hauptspeicherresidente Datenbanken verschieben den Fokus von I/O Operationen hin zu Zugriffen auf den Hauptspeicher und CPU Kosten, verglichen zu Datenbanken deren primäre Kopie der Daten auf Sekundärspeicher liegt und deren Kostenmodelle sich in der Regel auf die kostendominierenden Zugriffe auf das Sekundärmedium beschränken. Kostenmodelle für Zugriffe auf Hauptspeicher unterscheiden sich jedoch fundamental von Kostenmodellen für Systeme basierend auf Festplatten, so dass alte Modelle nicht mehr greifen. Diese Arbeit präsentiert eine detaillierte Parameterdiskussion, sowie ein Kostenmodell basierend auf Cache-Zugriffen zum Abschätzen der Laufzeit von Datenbankoperatoren in spaltenorientierten und hauptspeicherresidenten Datenbanken wie das Selektieren von Werten einer Spalte mittels einer Gleichheitsbedingung oder eines Wertebereichs, das Nachschlagen der Werte einzelner Positionen oder dem Hinzufügen neuer Werte. Dabei werden Kostenfunktionen für die Operatoren erstellt, welche auf unkomprimierten Spalten, mittels Substitutionskompression komprimierten Spalten sowie bit-komprimierten Spalten operieren. Des Weiteren werden Baumstrukturen als Index Strukturen auf Spalten und Wörterbüchern in die Betrachtung gezogen. Abschließend werden partitionierte Spalten eingeführt, welche aus einer lese- und einer schreib-optimierten Partition bestehen. Neu Werte werden in die schreiboptimierte Partition eingefügt und periodisch von einem Attribut-Merge-Prozess mit der leseoptimierten Partition zusammengeführt. Beschrieben wird eine Effiziente Implementierung für den Attribut-Merge-Prozess und ein Hauptspeicher-bandbreitenbasiertes Kostenmodell aufgestellt.