Modularisierung leichtgewichtiger Kompressionsalgorithmen

Abstract

Im Kontext von In-Memory Datenbanksystemen nehmen leichtgewichtige Kompressionsalgorithmen eine entscheidende Rolle ein, um eine effiziente Speicherung und Verarbeitung groeßr Datenmengen im Hauptspeicher zu realisieren. Verglichen mit klassischen Komprimierungstechniken wie z.B. Huffman erzielen leichtgewichtige Kompressionsalgorithmen vergleichbare Kompressionsraten aufgrund der Einbeziehung von Kontextwissen und erlauben eine schnellere Kompression und Dekompression. Die Vielfalt der leichtgewichtigen Kompressionsalgorithmen hat in den letzten Jahren zugenommen, da ein groeßs Optimierungspotential u¨ber die Einbeziehung des Kontextwissens besteht. Um diese Vielfalt zu bew¨altigen, haben wir uns mit der Modularisierung von leichtgewichtigen Kompressionsalgorithmen besch¨aftigt und ein allgemeines Kompressionsschema entwickelt. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich verschiedene Algorithmen einfach realisieren.

EINFÜHRUNG

der Zwischenergebnisse etabliert. Auf der einen Seite sollten Zwischenergebnisse nicht mehr zum Beispiel durch entsprechend angepasste Code-Generierung [ 19 ] oder durch den Einsatz zusammengefu¨gter Operatoren [ 16 ] produziert werden. Auf der anderen Seite sollten Zwischenergebnisse (wenn sie beispielsweise nicht vermeidbar sind) so organisiert werden, dass eine effiziente Weiterverarbeitung erm¨oglicht wird.

Im Rahmen unserer aktuellen Forschung greifen wir uns den optimierten Einsatz leichtgewichtiger Kompressionsverfahren fu¨r Zwischenergebnisse in hauptspeicherzentrischen Datenbankarchitekturen heraus und haben zum Ziel, eine ausgewogene Anfrageverarbeitung auf Basis komprimierter Zwischenergebnisse zu entwickeln [ 13 ]. Mit der expliziten Kompression aller Zwischenergebnisse soll (i) die Effizienz einzelner Datenbankanfragen bzw. der Durchsatz einer Menge an Datenbankanfragen erh¨oht werden, da der Hauptspeicherbedarf fu¨r Zwischenergebnisse reduziert und der Mehraufwand zur Generierung der komprimierten Form m¨oglichst gering gehalten wird und (ii) die durchg¨angige Betrachtung der Kompression von den Basisdaten bis hin zur Anfrageverarbeitung etabliert wird.

Im Forschungsbereich der klassischen Kompression existiert eine Vielzahl an wissenschaftlichen Publikationen. Klassische Kompressionsverfahren, wie zum Beispiel arithmetisches Kodieren [ 26 ], Huffman [ 15 ] und Lempel-Ziv [ 30 ], erzielen hohe Kompressionsraten, sind jedoch rechenintensiv und werden deshalb oft als schwergewichtige Kompressionsverfahren bezeichnet. Speziell fu¨r den Einsatz in In-Memory Datenbanksystemen wurden leichtgewichtige Kompressionsalgorithmen entwickelt, die verglichen mit klassischen Verfahren aufgrund der Einbeziehung von Kontextwissen ¨ahnliche Kompressionsraten erzielen, aber sowohl eine viel schnellere Kompression als auch Dekompression erlauben. Beispiele fu¨r leichtgewichtige Kompressionsalgorithmen sind unter anderem Domain Kodierung (DC) [ 24 ], W¨orterbuch-basierte Kompression (Dict) [ 5, 8, 17 ], reihenfolgeerhaltende Kodierungen [ 5, 28 ], Laufl¨angenkodierung (RLE) [ 7, 21 ], Frame-ofReference (FOR) [ 12, 31 ] und verschiedene Arten von Nullkomprimierung [ 1, 20, 21, 23 ]. Die Anzahl der leichtgewichtigen Kompressionsalgorithmen hat in den letzten Jahren zugenommen, da ein groeßs Optimierungspotential u¨ber die Einbeziehung von Kontextwissen besteht.

Mit Blick auf unser Ziel der ausgewogenen Anfrageverarbeitung auf Basis komprimierter Zwischenergebnisse wollen wir eine breite Vielfalt an leichtgewichtigen Kompressionsalgorithmen unterstu¨tzen, um die jeweiligen Vorteile der Algorithmen effizient ausnutzen zu k¨onnen. Um dieses Ziel zu erreichen, haben wir uns mit der Modularisierung von

Abbildung 1: Allgemeines Schema fu¨r leichtgewichtige Komprimierungsalgorithmen. Kompressionsalgorithmen besch¨aftigt. Fu¨r diese Modularisierung haben wir eine Vielzahl von leichtgewichtigen Kompressionsalgorithmen systematisch analysiert und ein allgemeines Kompressionsschema bestehend aus wohldefinierten Modulen abgeleitet. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich h¨aufig verschiedene Algorithmen einfach darstellen. Des Weiteren wird durch die Darstellung eines Algorithmus und durch die Unterteilung in verschiedene, m¨oglichst unabh¨angige kleinere Module die Verst¨andlichkeit erleichtert. Unsere entwickelte Strukturierung bildet eine gute Basis zur abstrakten und implementierungsunabh¨angigen Betrachtung von leichtgewichtigen Kompressionsalgorithmen.

Im Abschnitt 2 fu¨hren wir unser neues Kompressionsschema fu¨r leichtgewichtige Kompressionsverfahren bestehend aus vier Modulen ein. Dieses neue Kompressionsschema nutzen wir in Abschnitt 3, um bekannte Muster zu definieren.

Im Anschluss daran gehen wir auf die Modularisierung konkreter Algorithmen exemplarisch im Abschnitt 4 ein. Der Artikel schlietß dann mit einer Zusammenfassung und einem Ausblick im Abschnitt 5.

KOMPRESSIONSSCHEMA

Mit dem Paradigma der Datenkompression aus den 1980er Jahren [ 25 ] gibt es bereits eine eher allgemein gehaltene Modularisierung fu¨r die Kompression von Daten im Kontext der Datenu¨bertragung. Diese unterteilt Kompressionsverfahren lediglich in ein Datenmodell, welches auf Grundlage bereits gelesener Daten erstellt und angepasst wird, und einen Kodierer, welcher eingehende Daten mithilfe des berechneten Datenmodells kodiert. Diese Modularisierung eignet sich fu¨r damals u¨bliche adaptive Kompressionsmethoden; greift aber fu¨r viele Verfahren zu kurz. Die gesamte Zerlegung eines Eingabedatenstroms wird beispielsweise aueßn vor gelasse n.

Bei vielen aktuellen und gerade semiadaptiven Verfahren mit mehreren P¨assen werden Daten mehrstufig zerlegt, um ein komplexes Datenmodell zu erzeugen. Auch das Zusammenfu¨gen der Daten wird im Normalfall wesentlich diffiziler realisiert als mit einer einfachen Konkatenation komprimierter Daten. Unser aus vier Modulen bestehendes allgemeines Kompressionsschema in Abbildung 1 ist eine Erweiterung des bisherigen Paradigmas der Datenkompression, das eine wesentlich detailliertere und komplexere Abbildung einer Vielzahl von leichtgewichtigen Algorithmen erlaubt. Eingabe fu¨r ein Kompressionsverfahren ist hierbei immer eine potentiell unendliche Sequenz von Daten. Ausgabe ist ein Strom aus komprimierten Daten.

Der Wortgenerator als erstes Modul zerlegt die Sequenz in endliche Teilsequenzen resp. einzelne Werte. Mit einem Datenstrom als Eingabe gibt ein Wortgenerator einen endlichen Anfang aus und verarbeitet den Rest der Eingabe ebenso, rekursiv. Ist die Eingabe des Wortgenerators endlich, kann ihre Zerlegung stattdessen auch nicht rekursiv, z.B. ein Optimierungsproblem sein. Wortgeneratoren erhalten als zweite Eingabe die Information, wie die Eingabesequenz zerlegt werden soll, als Berechnungsvorschrift. Entweder wird datenunabh¨angig eine Anzahl von Werten ausgegeben (z.B. immer 128 Werte oder immer ein Wert) oder datenabh¨angig aufgrund inhaltlicher Merkmale die L¨ange der auszugebenden Teilsequenz bestimmt. M¨oglich ist eine adaptive Zerlegung, so dass sich die Berechnungsvorschrift nach jeder Ausgabe einer Teilsequenz ¨andert. Als optionaler Datenfluss ist dies im Kompressionsschema durch eine unterbrochene Linie dargestellt.

Das Datenmodell des Paradigmas der Datenkompression wird durch das Modul der Parameterberechnung ersetzt. So k¨onnen bei semiadaptiven Verfahren fu¨r endliche Sequenzen statistische Werte berechnet werden, wie zum Beispiel ein Referenzwert fu¨r Frame-of-Reference-Verfahren (FOR) oder eine gemeinsame Bitweite, mit der alle Werte der endlichen Sequenz kodiert werden k¨onnen. M¨oglicherweise gibt es feste Eingabeparameter, beispielsweise eine Auswahl an erlaubten Bitweiten. Eine adaptive Parameterberechnung zeichnet sich durch einen Startwert als festen Eingabeparameter aus und eine Ausgabe, die im n¨achsten Schritt wieder als Eingabe und so dem Modul der Parameterberechnung als Ged¨achtnis dient. Beispielsweise ben¨otigen Differenzkodierungsverfahren eine adaptive Parameterberechnung.

Der Kodierer erh¨alt einen atomaren Eingabewert sowie m¨oglicherweise berechnete oder feste Parameter, die fu¨r die Kodierung des Eingabewertes ben¨otigt werden. Solche Parameter k¨onnen z.B. Referenzwerte, Bitweiten oder gar Mappings sein, die die Abbildung einzelner Werte in einen Code definieren. Ein Kodierer bildet einen Eingabewert eineindeutig auf einen anderen Wert ab, was fu¨r die Dekodierbarkeit notwendig ist. Ausgabe eines Kodierers ist ein komprimierter Wert, der sich m¨oglicherweise durch einen Deskriptor wie einer L¨angenangabe bei einer Abbildung in einen variablen Code auszeichnet, um die Dekodierbarkeit zu gew¨ahrleisten.

Soll eine endliche Sequenz, die der Wortgenerator ausgibt, noch weiter zerlegt werden, kann das gesamte Schema noch einmal mit einer Rekursion aufgerufen werden. Dabei geht eine endliche Sequenz wieder in einen Wortgenerator ein und wird dabei zerlegt, weiterverarbeitet und als komprimierte Sequenz wieder zusammengefu¨gt. Diese komprimierte Sequenz ist Ausgabe der Rekursion.

Das letzte Modul des Zusammenfu¨gens erh¨alt als Eingabe einen komprimierten Datenstrom, n¨amlich die Ausgametrische Eingabesequenz Berchnungsvorschrift Abbildung 2: Modularisierung semiadaptiver Frameo-fR-ef erenceV-erfahren. ben des Kodierers resp. der Rekursion. Es gibt verschiedene M¨oglichkeiten Daten zusammenzufu¨gen. Im einfachsten Fall gibt es keine Deskriptoren, alle komprimierten Werte vc werden nacheinander zusammengefu¨gt (notiert als vcn). Geh¨ort zu jedem komprimierten Wert ein Deskriptor d, so k¨onnen beispielsweise immer Paare aus Deskriptoren und komprimierten Werten konkateniert werden (notiert als (d : vc)n) oder immer eine bestimmte Anzahl l von Deskriptoren, gefolgt von den zugeh¨origen komprimierten Werten (notiert als (dl : vcl)n). Gerade bei semiadaptiven Verfahren mit Rekursionen ist es m¨oglich, dass gemeinsame Deskriptoren fu¨r mehrere Werte vom Modul der Parameterberechnung ausgegeben und mit gespeichert werden mu¨ssen, so dass verschiedene Anordnungen bei der Konkatenation aller Werte denkbar sind.

KOMPRESSIONSMUSTER

Bekannte Kompressionstechniken wie zum Beispiel Differenzkodierung, Frame-of-Reference (FOR), W ¨orterbuchkompression, Bitvektoren, Laufl¨angenkodierung (RLE) oder die Unterdru¨ckung fu¨hrender Nullen lassen sich mit dem allgemeinen Kompressionsschema als Muster ausdru¨cken. Das bedeutet, dass gewisse modulare Anordnungen und Inhalte einzelner Module durch die Begriffsdefinition der Techniken festgelegt, andere inhaltliche Aspekte sowie andere in Beziehung stehende Module hingegen nicht n¨aher spezifiziert sind. 3.1

Muster Frameo-fR-eference (FOR)

Fu¨r die allgemeine Definition des FOR muss die Eingabesequenz aus metrischen Werten bestehen, wie zum Beispiel aus natu¨rlichen Zahlen. Diese werden als Differenz zum Referenzwert mref kodiert. Abbildung 3 zeigt das entsprechende Kompressionsschema. Der Wortgenerator gibt vom Anfang der Sequenz jeweils einen Integerwert m aus. Der Kodierer erh¨alt neben den Eingabewerten den Referenzwert mref als

Rest

Eingabesequenz (298 : 301 : 303 : . . . ) k=1 statischer

Wortgenerator

Kodierer mref = 273 vc = m − mref metrischer Wert m

Zusammen- (25 : 28 :

fügen 30 : . . . ) (mref : vcn) oder vcn Abbildung 3: Modularisierung statischer Frameo-fReferenceV-erfahren.

Parameter und berechnet die Differenz aus beiden Werten. Das Modul des Zusammenfu¨gens konkateniert den Referenzwert mit allen kodierten Werten (mref : vcn). Notwendig ist die Speicherung des Referenzwertes aber nur, wenn dessen Kenntnis beim Dekodieren nicht vorausgesetzt werden kann. Dies ist durch einen optionalen Pfeil dargestellt. Im dargestellten Beispiel werden die Werte des Eingabedatenstroms als Differenz zum Referenzwert mref = 273 kodiert. Der Referenzwert sei beim Dekodieren aus dem Kontext bekannt.

Meist geh¨ort es zum Selbstverst¨andnis, dass der Referenzwert fu¨r eine endliche Sequenz wie in Abbildung 2 aus den gegebenen Daten berechnet und als Deskriptor gespeichert wird. Nach welchen Regeln der erste dargestellte Wortgenerator endliche Sequenzen ausgibt, ist dabei nicht spezifiziert. Das dargestellte Muster kann eine potentiell unendliche Sequenz als Eingabe erhalten. Es kann auch in einem gr¨oeßren Zusammenhang mit anderen Modulen stehen und nur eine endliche Teilsequenz weiter zerlegen. Im Modul der Parameterberechnung wird aus der endlichen Sequenz, die der erste Wortgenerator ausgibt, der Referenzwert mref berechnet. Zum Beispiel kann als Referenzwert der kleinste Wert der endlichen Sequenz gew¨ahlt werden. Die endliche Sequenz geht in eine Rekursion ein. Arrangement und Inhalt der Module innerhalb der Rekursion entsprechen der Modularisierung statischer Frame-of-Reference-Verfahren (vgl. Abb. 3). Der Wortgenerator innerhalb der Rekursion gibt einzelne metrische Werte aus. Der Kodierer berechnet die Differenz aus Eingabe- und Referenzwert. Alle Werte werden gemeinsam mit dem Referenzwert konkateniert. Alle so komprimierten endlichen Sequenzen, die der erste dargestellte Wortgenerator ausgegeben hat, werden am Ende zusammengefu¨gt, von Interesse sind fu¨r die allgemeinere Definition des FOR jedoch nur die Module innerhalb der Rekursion. 3.2

Muster Symbolunterdrückung

Unter dem Begriff Symbolunterdru¨ckung werden sehr verschiedene Komprimierungsverfahren zusammengefasst, Pr¨asenzbits sowie Laufl¨angenkodierung explizit fu¨r Nullen, die in potentiell unendliche Sequenzen auftauchen [ 6 ], Laufl¨angenkodierung von Nullen und Leerzeichen [ 21 ] oder auch die Eliminierung fu¨hrender und damit redundanter Nullen bei bin¨ar kodierten Zahlen. Diese Methoden haben gemeinsam, dass es im Zeichenvorrat ein ausgezeichnetes Symbol s gibt, welches sich meist semantisch von allen anderen abhebt und ¨ofter auftaucht als andere Werte. Das ausgezeichnete Symbol wird im Wortgenerator oder im Kodierer anders behandelt als andere Symbole. Im Falle von Pr¨asenzbits ist dieses Symbol der NULL-Wert. Nullen sind das neutrale Element der Addition. Die genaue Anzahl fu¨hrender Nullen beeinflusst Additionsoperationen nicht und ist damit an sich schon eine redundante Information. Leerzeichen dienen in allen Sprachen dazu, W¨orter voneinander zu separieren. Die Anzahl an Wiederholungen von Leerzeichen zwischen konkatenierten W¨ortern besitzt auf semantischer Ebene keinerlei Bedeutung. Viele der Algorithmen, aber nicht alle, nutzen hierfu¨r RLE-Kompressionen. F u¨r Symbolunterdru¨ckungen l¨asst sich allgemein keine Modularisierung darstellen, da es sich einfach nur durch die Sonderbehandlung eines Symbols auszeichnet. In Kombination mit einer Laufl¨angenkodierung gelingt aber eine Modularisierung mit unserem Schema.

Merkmal der Laufl¨angenkodierung ist das Vorhandensein von L¨aufen wn, endlichen Sequenzen der L¨ange n aus ein und demselben Wert w. Werden wirklich einfach nur L¨aufe von Werten kodiert, so reicht das simple Kompressionsschema in Abbildung 4 aus. Der Wortgenerator unterteilt den

Eingabedatenstrom in L¨aufe. Im Kodierer werden dann der Wert w und die Laufl¨ange n kodiert. L¨aufe k¨onnen auch in einer Sequenz zum Beispiel als fu¨hrende Nullen eingebettet sein. Solche F¨alle liegen im Schnittbereich zwischen Symbolunterdru¨ckung und Laufl¨angenkodierung. Dies ist fu¨r statische Verfahren in Abbildung 5 dargestellt. Die Informationen u¨ber Sequenzl¨angen des ausgezeichneten Wertes s werden bei statischen Verfahren beim Zusammenfu¨gen zum Beispiel in der Form (d(n) : vc)m gespeichert. Dabei ist d(n) eine eineindeutige Abbildung.

Sollen mehrere mit 32 Bits kodierte Werte mit geringerer, aber einheitlicher Bitweite gespeichert werden, wird fu¨r die Unterdru¨ckung fu¨hrender Nullen ein semiadaptives Schema ben¨otigt (nicht dargestellt). Die gemeinsame Bitweite bw ist Ausgabe der Parameterberechnung und kann als Deskriptor angegeben werden, bw = d(n) ist eine Funktion von n, der Anzahl der fu¨hrenden Nullen, die entfernt wurden. Jeder

Wert w einer endlichen Sequenz hat eine komprimierte Form vc und eine Laufl¨ange n. Beide werden entweder zusammen oder in der Gruppe aus Deskriptoren und einer Gruppe aus komprimierten Werten gespeichert. 4.

ALGORITHMENM-ODULARISIERUNG

Die vorgestellten und auch weitere Muster finden sich in verschiedenen Kompressionsalgorithmen, oft auch kombiniert oder auf mehreren Rekursionsebenen miteinander verwoben, wieder. Sich ¨ahnelnde Algorithmen unterscheiden sich meist nur geringfu¨gig in manchen Modulen oder sogar nur in Parametern, die in ein Modul eingehen. Beispielsweise ¨ahneln sich die Algorithmen varint-PU und varint-SU [ 22 ] - letzterer ist besser bekannt als VByte [ 11, 10, 9 ] - sehr. VByte kodiert 32-Bit-Integerwerte mit ein bis 5 Bytes, wobei ein Byt e aus einem Deskriptorbit und 7 Datenbits besteht. Ebenso ist dies bei varint-PU der Fall, beide Algorithmen unterscheid en sich nur in der Anordnung der Daten- und Deskriptorbits.

W¨ahrend bei VByte ein Bit pro zusammenh¨angendem Byte als Deskriptor dient, steht bei varint-PU der gesamte Deskriptor an einem Ende des komprimierten Integerwertes.

Ein Beispiel zeigt Abbildung 6. Nicht belegte Bits bedeuten, dass diese im Beispiel nicht ben¨otigt und weggelassen werden. Der Integerwert wird in komprimierter Form mit 3 statt 4 Bytes kodiert.

Beide Formate haben den gleichen modularen Aufbau (siehe Abbildung 7). Der rekursive statische Wortgenerator gibt immer eine Zahl aus. Da die Kodierung der Eingabe bei diesen Algorithmen soweit spezifiziert ist, dass die Zahlen als 32-Bit-Integerwerte kodiert sind, ist die ausgegebene Zah l ein eingebetteter Lauf von der Form 0l1w1 . . . w31−l (bzw. 032 fu¨r den Wert 0). Der Deskriptor bw/7 gibt die Anzahl der fu¨r die Datenbits ben¨otigten 7-Bit-Einheiten an. Allein aus dem komprimierten Wert ohne Deskriptor ist die Laufl¨ange der bei der Kodierung unterschlagenen Nullen nicht ermittelbar, schon weil eine Folge von Werten nicht mehr dekodierbar ist. Die Laufl¨ange ist allein aus dem Deskriptor (und dem Wissen, dass es sich um 32-Bit-Integerwerte handelt) ersichtlich. Somit ist das Laufl¨angenmuster bei varint-SU und varint-PU begr u¨ndbar. Da das Zeichen 0 eine Sonderstellung einnimmt, weil fu¨hrende Nullen als Lauf betrachtet werden, findet sich hier, wie bei allen varint-Algorithmen, auch eine Symbolunterdru¨ckung. Beide Algorithmen unterscheiden sich im Kompressionsschema nur im Modul des Zusammenfu¨gens. Das Symbol : wird hier als Konkatenationssymbol fu¨r abz¨ahlbar viele Werte verwendet.

Ein weiteres Beispiel fu¨r einen modularisierten Algorithmus ist FOR mit Binary Packing (nicht dargestellt), der sich durch marginale Ver¨anderungen und weitere Definitionen aus dem Kompressionsschema fu¨r semiadaptive FORVerfahren (Abb. 2) ergibt. Beim Binary Packing wird fu¨r eine endliche Sequenz von n bin¨ar kodierten Integerwerten z.B. zu 32 Bits eine gemeinsame Bitweite bw berechnet, mit der alle n Werte kodiert werden k¨onnen. Die erste A¨nderung im Kompressionsschema betrifft die Parameterberechnung.

Zus¨atzlich zum Referenzwert fu¨r eine endliche Sequenz, die der erste Wortgenerator ausgibt, muss die gemeinsame Bitweite bw berechnet und ausgegeben werden. Die zweite A¨nderung betrifft den Kodierer innerhalb der Rekursion. Nach der Berechnung der Differenz aus Eingabe- und Referenzwert wird der so erhaltene Werte mit Bitweite bw bin¨ar kodiert. Im Modul des Zusammenfu¨gens muss dann bw als ein weiterer gemeinsamer Deskriptor zum Beispiel in der Form varint-SU 0 1 1 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 1 24 16 8 0 Deskriptorbit

Datenbits

Abbildung 7: Modularisierung der Algorithmen varintS-U un d varintP-U. (mref : bw : vnc) gespeichert werden. Die Modularisierung dieses Algorithmus zeichnet sich durch die Muster FOR, Laufl¨angenkodierung und Symbolunterdru¨ckung aus.

Nicht fu¨r alle Algorithmen ist diese recht einfache Modularisierung ausreichend. Auf PFOR basierende Algorithmen [ 31, 29, 27, 18 ] kodieren die meisten Eingabewerte aus natu¨rlichen Zahlen mit der gleichen Bitweite bw. Die gr¨oeßren, die nicht mit der Bitweite bw kodierbar sind, werden allerdings als Ausnahme deklariert und auf andere Weise kodiert und an anderer Stelle gespeichert. Dafu¨r ben¨otigt das erweiterte Schema ein Splitmodul, welches Daten aufgrund inhaltlicher Merkmale in verschiedene Gruppen aufteilt und ausgibt. Fu¨r jede dieser Gruppen muss ein separater Kodierer verfu¨gbar sein, wobei die kodierten Werte aller Gruppen am Ende gemeinsam zusammengefu¨gt werden.

5. ZUSAMMENFASSUNG UND AUSBLICK

Unser entwickeltes Kompressionsschema bestehend aus vier Modulen ist durchaus geeignet, um eine Vielzahl verschiedener leichtgewichtiger Kompressionsalgorithmen gut zu modularisieren und systematisch darzustellen. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich verschiedene Algorithmen mit dem gleichen Kompressionsschema darstellen. Einige Module und Modulgruppen tauchen in verschiedenen Algorithmen immer wieder auf, wie zum Beispiel die gesamte Rekursion, die das Binary Packing ausmacht, die sich in allen PFOR- und SimpleAlgorithmen [ 2, 3, 29, 27, 4 ] findet. Die Verst¨andlichkeit eines Algorithmus wird durch die Unterteilung in verschiedene, m¨oglichst unabh¨angige kleinere Module, welche u¨berschaubare Operationen ausfu¨hren, verbessert. Die Strukturierung durch das entwickelte Schema bildet aus unserer Sicht eine gute Basis zur abstrakten Betrachtung von leichtgewichtigen Kompressionsalgorithmen. Als Muster k¨onnen nicht nur bestimmte Techniken, sondern auch andere Eigenschaften von Kompressionsalgorithmen dargestellt werden. Statische Verfahren wie z.B. varint-SU und varint-PU bestehen nur aus Wortgenerator, Kodierer und dem Modul des Zusammenfu¨gens. Adaptive Verfahren haben einen adaptiven Wortgenerator, eine adaptive Parameterberechnung oder beides. Semiadaptive Verfahren zeichnen sich durch eine Parameterberechnung und eine Rekursion aus, in deren Wortgenerator oder Kodierer die Ausgabe der Parameterberechnung eingeht.

Durch die M¨oglichkeit Module sehr passend zusammenzustellen und mit Inhalt zu fu¨llen, ergibt sich ein m¨achtiges Werkzeug fu¨r den automatisierten Bau von Algorithmen. Das Kompressionsschema bietet eine aus unserer Sicht fundierte Grundlage und er¨offnet die M¨oglichkeit, fu¨r einen gegebenen Kontext sehr gezielt speziell zugeschnittene Algorithmen mit bestimmten Eigenschaften wie zum Beispiel der Art der Anpassbarkeit zusammenzubauen. Weiterhin k¨onnen verschiedene Muster wie FOR, Differenzkodierung, Symbolunterdru¨ckung oder Laufl¨angenkodierung an den Kontext angepasst eingesetzt werden und das auf verschiedensten Ebenen miteinander kombiniert.

Fu¨r die Fortfu¨hrung dieses Gedankens ist es notwendig, einen noch st¨arkeren Zusammenhang zwischen Kontextwissen und passender Schemazusammenstellung sowie passenden Parametereingaben herzustellen. Des Weiteren wird gerade fu¨r das theoretische Grundkonzept eine passende praktische Umsetzung angegangen. Fu¨r die praktische Umsetzung wird ein Framework bestehend aus den eingefu¨hrten Modulen anvisiert, so dass der Zusammenbau leichtgewichtiger Kompressionsalgorithmen wie beschrieben realisiert werden kann. Die gr¨otße Herausforderung bei der praktischen Umsetzung wird die Effizienz der Algorithmen sein. Um eine vergleichbare Effizienz zu den bisherigen Implementierungen erzielen zu k¨onnen, sind unterschiedliche Ans¨atze notwendig. Ein vielversprechender Ansatz dabei ist die Spezialisierung von generischen Code mit dem Einsatz spezieller Compilertechniken, wie wir es in [ 14 ] angesprochen haben. U¨ber die Spezialisierung kann hochoptimierter Ausfu¨hrungscode erzeugt werden, wobei das vorhandene Hintergrundwissen zur Codeoptimierung dem Compiler beigebracht werden muss.

Acknowledgments

Diese Arbeit ist im Rahmen des DFG-finanzierten Projektes L”eichtgewichtige Kompressionsverfahren zur Optimierun g komplexer Datenbankanfragen(”LE-1416/26-1) entstanden .

References

6. LITERATUR

[1] D. Abadi , S. Madden , and M. Ferreira . Integrating compression and execution in column-oriented database systems . In SIGMOD , pages 6716 - 82 , 2006 .

[2] V. N. Anh and A. Moffat . Inverted index compression using word-aligned binary codes . Inf. Retr. , 8 ( 1 ): 1511 - 66 , Jan. 2005 .

[3] V. N. Anh and A. Moffat . Improved word-aligned binary compression for text indexing . IEEE Trans. on Knowl. and Data Eng ., 18 ( 6 ): 8578 - 61 , June 2006 .

[4] V. N. Anh and A. Moffat . Index compression using 64-bit words . Softw. Pract . Exper., 40 ( 2 ): 1311 - 47 , Feb. 2010 .

[5] G. Antoshenkov , D. B. Lomet , and J. Murray . Order preserving compression . In ICDE , pages 6556 - 63 , 1996 .

[6] J. Aronson . Computer science and technology: data compression - a comparison of methods . NBS special publication 500-12 , Department of Commerce, National Bureau of Standards, Institute for Computer Sciences and Technology , Washington, DC, USA, June 1977 . ERIC Document Number: ED149732 .

[7] M. A. Bassiouni . Data compression in scientific and statistical databases . IEEE Transactions on Software Engineering , 11 ( 10 ): 10471 - 058 , 1985 .

[8] P. A. Boncz , S. Manegold , and M. L. Kersten . Database architecture optimized for the new bottleneck: Memory access . In VLDB , pages 546 - 5 , 1999 .

[9] S. Bu ¨ttcher, C. Clarke, and G. V. Cormack . Information Retrieval: Implementing and Evaluating Search Engines . The MIT Press, 2010 .

[10] B. Croft , D. Metzler , and T. Strohman . Search Engines: Information Retrieval in Practice. Addison-Wesley Publishing Company, USA, 1st edition , 2009 .

[11] J. Dean . Challenges in building large-scale informati on retrieval systems: invited talk . In R. A. Baeza-Yates , P. Boldi , B. A. Ribeiro-Neto , and B. B. Cambazoglu, editors, WSDM, page 1. ACM , 2009 .

[12] J. Goldstein , R. Ramakrishnan , and U. Shaft . Compressing relations and indexes . In ICDE Conference , pages 3703 - 79 , 1998 .

[13] D. Habich , P. Damme , and W. Lehner . Optimierung der Anfrageverarbeitung mittels Kompression der Zwischenergebnisse . In BTW 2015 , pages 2592 - 78 , 2015 .

[14] C. H¨ansch , T. Kissinger, D. Habich , and W. Lehner . Plan operator specialization using reflective compiler techniques . In BTW 2015 , pages 3633 - 82 , 2015 .

[15] D. A. Huffman . A method for the construction of minimum-redundancy codes . Proceedings of the Institute of Radio Engineers , 40 ( 9 ): 10981 - 101 , September 1952 .

[16] T. Kissinger , B. Schlegel , D. Habich , and W. Lehner . QPPT: query processing on prefix trees . In CIDR 2013 , 2013 .

[17] T. J. Lehman and M. J. Carey . Query processing in main memory database management systems . In SIGMOD Conference , pages 2392 - 50 , 1986 .

[18] D. Lemire and L. Boytsov . Decoding billions of integers per second through vectorization . CoRR, abs/1209.2137 , 2012 .

[19] T. Neumann . Efficiently compiling efficient query plans for modern hardware . PVLDB , 4 ( 9 ): 5395 - 50 , 2011 .

[20] H. K. Reghbati . An overview of data compression techniques . IEEE Computer , 14 ( 4 ): 717 - 5 , 1981 .

[21] M. A. Roth and S. J. V. Horn . Database compression . SIGMOD Record , 22 ( 3 ): 313 - 9 , 1993 .

[22] A. A. Stepanov , A. R. Gangolli , D. E. Rose , R. J. Ernst , and P. S. Oberoi . Simd-based decoding of posting lists . In CIKM , pages 3173 - 26 , 2011 .

[23] T. Westmann , D. Kossmann , S. Helmer , and G. Moerkotte. The implementation and performance of compressed databases . SIGMOD Record , 29 ( 3 ): 556 - 7 , 2000 .

[24] T. Willhalm , N. Popovici , Y. Boshmaf , H. Plattner , A. Zeier , and J. Schaffner . Simd-scan: Ultra fast in-memory table scan using on-chip vector processing units . PVLDB , 2 ( 1 ): 3853 - 94 , 2009 .

[25] R. N. Williams . Adaptive Data Compression . 1991 .

[26] I. H. Witten , R. M. Neal , and J. G. Cleary . Arithmetic coding for data compression . Communications ACM , 30 ( 6 ): 5205 - 40 , 1987 .

[27] H. Yan , S. Ding , and T. Suel . Inverted index compression and query processing with optimized document ordering . In WWW , pages 4014 - 10 , 2009 .

[28] A. Zandi , B. Iyer , and G. Langdon . Sort order preserving data compression for extended alphabets . In Data Compression Conference , pages 330 3 - 39 , 1993 .

[29] J. Zhang , X. Long , and T. Suel . Performance of compressed inverted list caching in search engines . In WWW , pages 3873 - 96 , 2008 .

[30] J. Ziv and A. Lempel . A universal algorithm for sequential data compression . IEEE Transactions on Information Theory , 23 : 3373 - 43 , 1977 .

[31] M. Zukowski , S. Heman , N. Nes , and P. Boncz . Super-scalar ram-cpu cache compression . In ICDE, page 59 , 2006 .