=Paper=
{{Paper
|id=Vol-1366/paper11.pdf
|storemode=property
|title=Modularisierung leichtgewichtiger
Kompressionsalgorithmen
|pdfUrl=https://ceur-ws.org/Vol-1366/paper11.pdf
|volume=Vol-1366
|dblpUrl=https://dblp.org/rec/conf/gvd/HildebrandtHDL15
}}
==Modularisierung leichtgewichtiger
Kompressionsalgorithmen==
https://ceur-ws.org/Vol-1366/paper11.pdf
Modularisierung leichtgewichtiger
Kompressionsalgorithmen
Juliana Hildebrandt, Dirk Habich, Patrick Damme, Wolfgang Lehner
Technische Universität Dresden
Database Systems Group
01189 Dresden, Germany
firstname.lastname@tu-dresden.de
ABSTRACT der Zwischenergebnisse etabliert. Auf der einen Seite soll-
Im Kontext von In-Memory Datenbanksystemen nehmen ten Zwischenergebnisse nicht mehr zum Beispiel durch ent-
leichtgewichtige Kompressionsalgorithmen eine entscheiden- sprechend angepasste Code-Generierung [19] oder durch den
de Rolle ein, um eine effiziente Speicherung und Verarbei- Einsatz zusammengefügter Operatoren [16] produziert wer-
tung großer Datenmengen im Hauptspeicher zu realisieren. den. Auf der anderen Seite sollten Zwischenergebnisse (wenn
Verglichen mit klassischen Komprimierungstechniken wie z.B. sie beispielsweise nicht vermeidbar sind) so organisiert wer-
Huffman erzielen leichtgewichtige Kompressionsalgorithmen den, dass eine effiziente Weiterverarbeitung ermöglicht wird.
vergleichbare Kompressionsraten aufgrund der Einbeziehung Im Rahmen unserer aktuellen Forschung greifen wir uns den
von Kontextwissen und erlauben eine schnellere Kompressi- optimierten Einsatz leichtgewichtiger Kompressionsverfah-
on und Dekompression. Die Vielfalt der leichtgewichtigen ren für Zwischenergebnisse in hauptspeicherzentrischen Da-
Kompressionsalgorithmen hat in den letzten Jahren zuge- tenbankarchitekturen heraus und haben zum Ziel, eine aus-
nommen, da ein großes Optimierungspotential über die Ein- gewogene Anfrageverarbeitung auf Basis komprimierter Zwi-
beziehung des Kontextwissens besteht. Um diese Vielfalt schenergebnisse zu entwickeln [13]. Mit der expliziten Kom-
zu bewältigen, haben wir uns mit der Modularisierung von pression aller Zwischenergebnisse soll (i) die Effizienz einzel-
leichtgewichtigen Kompressionsalgorithmen beschäftigt und ner Datenbankanfragen bzw. der Durchsatz einer Menge an
ein allgemeines Kompressionsschema entwickelt. Durch den Datenbankanfragen erhöht werden, da der Hauptspeicher-
Austausch einzelner Module oder auch nur eingehender Pa- bedarf für Zwischenergebnisse reduziert und der Mehrauf-
rameter lassen sich verschiedene Algorithmen einfach reali- wand zur Generierung der komprimierten Form möglichst
sieren. gering gehalten wird und (ii) die durchgängige Betrachtung
der Kompression von den Basisdaten bis hin zur Anfrage-
verarbeitung etabliert wird.
1. EINFÜHRUNG Im Forschungsbereich der klassischen Kompression exis-
Die Bedeutung von In-Memory Datenbanksystemen steigt tiert eine Vielzahl an wissenschaftlichen Publikationen. Klas-
zunehmend sowohl im wissenschaftlichen als auch im kom- sische Kompressionsverfahren, wie zum Beispiel arithmeti-
merziellen Kontext. In-Memory Datenbanksysteme verfol- sches Kodieren [26], Huffman [15] und Lempel-Ziv [30], er-
gen einen hauptspeicherzentrischen Architekturansatz, der zielen hohe Kompressionsraten, sind jedoch rechenintensiv
sich dadurch auszeichnet, dass alle performancekritischen und werden deshalb oft als schwergewichtige Kompressions-
Operationen und internen Datenstrukturen für den Zugriff verfahren bezeichnet. Speziell für den Einsatz in In-Memory
der Hauptspeicherhierarchie (z.B. effiziente Nutzung der Ca- Datenbanksystemen wurden leichtgewichtige Kompressions-
chehierarchie etc.) ausgelegt sind. Üblicherweise gehen In- algorithmen entwickelt, die verglichen mit klassischen Ver-
Memory Datenbanksysteme davon aus, dass alle relevanten fahren aufgrund der Einbeziehung von Kontextwissen ähnli-
Datenbestände auch vollständig in den Hauptspeicher eines che Kompressionsraten erzielen, aber sowohl eine viel schnel-
Rechners oder eines Rechnerverbundes abgelegt werden kön- lere Kompression als auch Dekompression erlauben. Beispie-
nen. Die Optimierung der internen Datenrepräsentationen le für leichtgewichtige Kompressionsalgorithmen sind unter
wird damit extrem wichtig, da jeder Zugriff auf ein Zwi- anderem Domain Kodierung (DC) [24], Wörterbuch-basierte
schenergebnis genau so teuer ist wie ein Zugriff auf die Ba- Kompression (Dict) [5, 8, 17], reihenfolgeerhaltende Kodie-
sisdaten [13]. rungen [5, 28], Lauflängenkodierung (RLE) [7, 21], Frame-of-
Für In-Memory Datenbanksysteme haben sich zwei ortho- Reference (FOR) [12, 31] und verschiedene Arten von Null-
gonale Optimierungstechniken für die effiziente Behandlung komprimierung [1, 20, 21, 23]. Die Anzahl der leichtgewich-
tigen Kompressionsalgorithmen hat in den letzten Jahren
zugenommen, da ein großes Optimierungspotential über die
Einbeziehung von Kontextwissen besteht.
Mit Blick auf unser Ziel der ausgewogenen Anfragever-
arbeitung auf Basis komprimierter Zwischenergebnisse wol-
len wir eine breite Vielfalt an leichtgewichtigen Kompressi-
onsalgorithmen unterstützen, um die jeweiligen Vorteile der
27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- Algorithmen effizient ausnutzen zu können. Um dieses Ziel
banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. zu erreichen, haben wir uns mit der Modularisierung von
Copyright is held by the author/owner(s).
54
veränderter Wert
Rest
Eingabesequenz
potentiell
unendliche
Eingabe-
sequenz feste Parameter-
Parameter berechnung kodierte
Wort- Sequenz
komprimierter Zusammenfügen
generator
Kodierer/ Wert
Parameter/ feste Rekursion
Menge Parameter
zulässiger
Nachrichten/. . . Deskriptor
veränderte
Parameter/ Wort:
Menge zulässiger endliche Sequenz
Nachrichten/. . .
Abbildung 1: Allgemeines Schema für leichtgewichtige Komprimierungsalgorithmen.
Kompressionsalgorithmen beschäftigt. Für diese Modulari- tenstrom als Eingabe gibt ein Wortgenerator einen endlichen
sierung haben wir eine Vielzahl von leichtgewichtigen Kom- Anfang aus und verarbeitet den Rest der Eingabe ebenso,
pressionsalgorithmen systematisch analysiert und ein allge- rekursiv. Ist die Eingabe des Wortgenerators endlich, kann
meines Kompressionsschema bestehend aus wohldefinierten ihre Zerlegung stattdessen auch nicht rekursiv, z.B. ein Op-
Modulen abgeleitet. Durch den Austausch einzelner Module timierungsproblem sein. Wortgeneratoren erhalten als zwei-
oder auch nur eingehender Parameter lassen sich häufig ver- te Eingabe die Information, wie die Eingabesequenz zerlegt
schiedene Algorithmen einfach darstellen. Des Weiteren wird werden soll, als Berechnungsvorschrift. Entweder wird date-
durch die Darstellung eines Algorithmus und durch die Un- nunabhängig eine Anzahl von Werten ausgegeben (z.B. im-
terteilung in verschiedene, möglichst unabhängige kleinere mer 128 Werte oder immer ein Wert) oder datenabhängig
Module die Verständlichkeit erleichtert. Unsere entwickelte aufgrund inhaltlicher Merkmale die Länge der auszugeben-
Strukturierung bildet eine gute Basis zur abstrakten und im- den Teilsequenz bestimmt. Möglich ist eine adaptive Zerle-
plementierungsunabhängigen Betrachtung von leichtgewich- gung, so dass sich die Berechnungsvorschrift nach jeder Aus-
tigen Kompressionsalgorithmen. gabe einer Teilsequenz ändert. Als optionaler Datenfluss ist
Im Abschnitt 2 führen wir unser neues Kompressionssche- dies im Kompressionsschema durch eine unterbrochene Linie
ma für leichtgewichtige Kompressionsverfahren bestehend dargestellt.
aus vier Modulen ein. Dieses neue Kompressionsschema nut- Das Datenmodell des Paradigmas der Datenkompression
zen wir in Abschnitt 3, um bekannte Muster zu definieren. wird durch das Modul der Parameterberechnung ersetzt. So
Im Anschluss daran gehen wir auf die Modularisierung kon- können bei semiadaptiven Verfahren für endliche Sequenzen
kreter Algorithmen exemplarisch im Abschnitt 4 ein. Der statistische Werte berechnet werden, wie zum Beispiel ein
Artikel schließt dann mit einer Zusammenfassung und ei- Referenzwert für Frame-of-Reference-Verfahren (FOR) oder
nem Ausblick im Abschnitt 5. eine gemeinsame Bitweite, mit der alle Werte der endlichen
Sequenz kodiert werden können. Möglicherweise gibt es feste
2. KOMPRESSIONSSCHEMA Eingabeparameter, beispielsweise eine Auswahl an erlaubten
Bitweiten. Eine adaptive Parameterberechnung zeichnet sich
Mit dem Paradigma der Datenkompression aus den 1980er
durch einen Startwert als festen Eingabeparameter aus und
Jahren [25] gibt es bereits eine eher allgemein gehaltene Mo-
eine Ausgabe, die im nächsten Schritt wieder als Eingabe
dularisierung für die Kompression von Daten im Kontext der
und so dem Modul der Parameterberechnung als Gedächt-
Datenübertragung. Diese unterteilt Kompressionsverfahren
nis dient. Beispielsweise benötigen Differenzkodierungsver-
lediglich in ein Datenmodell, welches auf Grundlage bereits
fahren eine adaptive Parameterberechnung.
gelesener Daten erstellt und angepasst wird, und einen Ko-
Der Kodierer erhält einen atomaren Eingabewert sowie
dierer, welcher eingehende Daten mithilfe des berechneten
möglicherweise berechnete oder feste Parameter, die für die
Datenmodells kodiert. Diese Modularisierung eignet sich für
Kodierung des Eingabewertes benötigt werden. Solche Para-
damals übliche adaptive Kompressionsmethoden; greift aber
meter können z.B. Referenzwerte, Bitweiten oder gar Map-
für viele Verfahren zu kurz. Die gesamte Zerlegung eines
pings sein, die die Abbildung einzelner Werte in einen Code
Eingabedatenstroms wird beispielsweise außen vor gelassen.
definieren. Ein Kodierer bildet einen Eingabewert eineindeu-
Bei vielen aktuellen und gerade semiadaptiven Verfahren mit
tig auf einen anderen Wert ab, was für die Dekodierbarkeit
mehreren Pässen werden Daten mehrstufig zerlegt, um ein
notwendig ist. Ausgabe eines Kodierers ist ein komprimier-
komplexes Datenmodell zu erzeugen. Auch das Zusammen-
ter Wert, der sich möglicherweise durch einen Deskriptor wie
fügen der Daten wird im Normalfall wesentlich diffiziler rea-
einer Längenangabe bei einer Abbildung in einen variablen
lisiert als mit einer einfachen Konkatenation komprimier-
Code auszeichnet, um die Dekodierbarkeit zu gewährleisten.
ter Daten. Unser aus vier Modulen bestehendes allgemei-
Soll eine endliche Sequenz, die der Wortgenerator ausgibt,
nes Kompressionsschema in Abbildung 1 ist eine Erweite-
noch weiter zerlegt werden, kann das gesamte Schema noch
rung des bisherigen Paradigmas der Datenkompression, das
einmal mit einer Rekursion aufgerufen werden. Dabei geht
eine wesentlich detailliertere und komplexere Abbildung ei-
eine endliche Sequenz wieder in einen Wortgenerator ein und
ner Vielzahl von leichtgewichtigen Algorithmen erlaubt. Ein-
wird dabei zerlegt, weiterverarbeitet und als komprimier-
gabe für ein Kompressionsverfahren ist hierbei immer eine
te Sequenz wieder zusammengefügt. Diese komprimierte Se-
potentiell unendliche Sequenz von Daten. Ausgabe ist ein
quenz ist Ausgabe der Rekursion.
Strom aus komprimierten Daten.
Das letzte Modul des Zusammenfügens erhält als Ein-
Der Wortgenerator als erstes Modul zerlegt die Sequenz in
gabe einen komprimierten Datenstrom, nämlich die Ausga-
endliche Teilsequenzen resp. einzelne Werte. Mit einem Da-
55
Rest Rekursion
Eingabesequenz
Deskriptor
metrische mref
Eingabe-
sequenz
Parameter-
Wort- berechnung
generator Referenz- kodierte
wert mref Rest Zusammenfügen Zusammenfügen Sequenz
Berchnungs- Eingabesequenz (mref : vcn ) (mref : vcn )m
vorschrift
Kodierer
vc = m − mref
veränderte Berech-
nungsvorschrift statischer
endliche Wort-
Sequenz me- generator
trischer Werte k = 1
1 metrischer
Wert m
Abbildung 2: Modularisierung semiadaptiver Frame-of-Reference-Verfahren.
ben des Kodierers resp. der Rekursion. Es gibt verschiedene Parameter und berechnet die Differenz aus beiden Werten.
Möglichkeiten Daten zusammenzufügen. Im einfachsten Fall Das Modul des Zusammenfügens konkateniert den Referenz-
gibt es keine Deskriptoren, alle komprimierten Werte vc wer- wert mit allen kodierten Werten (mref : vcn ). Notwendig ist
den nacheinander zusammengefügt (notiert als vcn ). Gehört die Speicherung des Referenzwertes aber nur, wenn dessen
zu jedem komprimierten Wert ein Deskriptor d, so können Kenntnis beim Dekodieren nicht vorausgesetzt werden kann.
beispielsweise immer Paare aus Deskriptoren und kompri- Dies ist durch einen optionalen Pfeil dargestellt. Im darge-
mierten Werten konkateniert werden (notiert als (d : vc )n ) stellten Beispiel werden die Werte des Eingabedatenstroms
oder immer eine bestimmte Anzahl l von Deskriptoren, ge- als Differenz zum Referenzwert mref = 273 kodiert. Der Re-
folgt von den zugehörigen komprimierten Werten (notiert ferenzwert sei beim Dekodieren aus dem Kontext bekannt.
als (dl : vcl )n ). Gerade bei semiadaptiven Verfahren mit Re- Meist gehört es zum Selbstverständnis, dass der Referenz-
kursionen ist es möglich, dass gemeinsame Deskriptoren für wert für eine endliche Sequenz wie in Abbildung 2 aus den
mehrere Werte vom Modul der Parameterberechnung aus- gegebenen Daten berechnet und als Deskriptor gespeichert
gegeben und mit gespeichert werden müssen, so dass ver- wird. Nach welchen Regeln der erste dargestellte Wortge-
schiedene Anordnungen bei der Konkatenation aller Werte nerator endliche Sequenzen ausgibt, ist dabei nicht spezifi-
denkbar sind. ziert. Das dargestellte Muster kann eine potentiell unendli-
che Sequenz als Eingabe erhalten. Es kann auch in einem
3. KOMPRESSIONSMUSTER größeren Zusammenhang mit anderen Modulen stehen und
nur eine endliche Teilsequenz weiter zerlegen. Im Modul der
Bekannte Kompressionstechniken wie zum Beispiel Dif-
Parameterberechnung wird aus der endlichen Sequenz, die
ferenzkodierung, Frame-of-Reference (FOR), Wörterbuch-
der erste Wortgenerator ausgibt, der Referenzwert mref be-
kompression, Bitvektoren, Lauflängenkodierung (RLE) oder
rechnet. Zum Beispiel kann als Referenzwert der kleinste
die Unterdrückung führender Nullen lassen sich mit dem all-
Wert der endlichen Sequenz gewählt werden. Die endliche
gemeinen Kompressionsschema als Muster ausdrücken. Das
Sequenz geht in eine Rekursion ein. Arrangement und Inhalt
bedeutet, dass gewisse modulare Anordnungen und Inhalte
der Module innerhalb der Rekursion entsprechen der Mo-
einzelner Module durch die Begriffsdefinition der Techniken
dularisierung statischer Frame-of-Reference-Verfahren (vgl.
festgelegt, andere inhaltliche Aspekte sowie andere in Be-
Abb. 3). Der Wortgenerator innerhalb der Rekursion gibt
ziehung stehende Module hingegen nicht näher spezifiziert
einzelne metrische Werte aus. Der Kodierer berechnet die
sind.
Differenz aus Eingabe- und Referenzwert. Alle Werte wer-
3.1 Muster Frame-of-Reference (FOR) den gemeinsam mit dem Referenzwert konkateniert. Alle so
komprimierten endlichen Sequenzen, die der erste dargestell-
Für die allgemeine Definition des FOR muss die Eingabe-
te Wortgenerator ausgegeben hat, werden am Ende zusam-
sequenz aus metrischen Werten bestehen, wie zum Beispiel
mengefügt, von Interesse sind für die allgemeinere Definition
aus natürlichen Zahlen. Diese werden als Differenz zum Refe-
des FOR jedoch nur die Module innerhalb der Rekursion.
renzwert mref kodiert. Abbildung 3 zeigt das entsprechende
Kompressionsschema. Der Wortgenerator gibt vom Anfang
der Sequenz jeweils einen Integerwert m aus. Der Kodierer 3.2 Muster Symbolunterdrückung
erhält neben den Eingabewerten den Referenzwert mref als Unter dem Begriff Symbolunterdrückung werden sehr ver-
schiedene Komprimierungsverfahren zusammengefasst, Prä-
senzbits sowie Lauflängenkodierung explizit für Nullen, die
Rest
Eingabesequenz
in potentiell unendliche Sequenzen auftauchen [6], Lauflän-
genkodierung von Nullen und Leerzeichen [21] oder auch die
Zusammen- (25 : 28 : Eliminierung führender und damit redundanter Nullen bei
30 : . . . )
fügen
(mref : vcn )
binär kodierten Zahlen. Diese Methoden haben gemeinsam,
statischer dass es im Zeichenvorrat ein ausgezeichnetes Symbol s gibt,
(298 : 301 : Kodierer oder vcn
Wort- mref = 273
303 : . . . ) vc = m − mref
generator welches sich meist semantisch von allen anderen abhebt und
k=1 metrischer
Wert m
öfter auftaucht als andere Werte. Das ausgezeichnete Symbol
wird im Wortgenerator oder im Kodierer anders behandelt
als andere Symbole. Im Falle von Präsenzbits ist dieses Sym-
Abbildung 3: Modularisierung statischer Frame-of- bol der NULL-Wert. Nullen sind das neutrale Element der
Reference-Verfahren. Addition. Die genaue Anzahl führender Nullen beeinflusst
56
Additionsoperationen nicht und ist damit an sich schon eine Wert w einer endlichen Sequenz hat eine komprimierte Form
redundante Information. Leerzeichen dienen in allen Spra- vc und eine Lauflänge n. Beide werden entweder zusammen
chen dazu, Wörter voneinander zu separieren. Die Anzahl oder in der Gruppe aus Deskriptoren und einer Gruppe aus
an Wiederholungen von Leerzeichen zwischen konkatenier- komprimierten Werten gespeichert.
ten Wörtern besitzt auf semantischer Ebene keinerlei Be-
deutung. Viele der Algorithmen, aber nicht alle, nutzen hier- 4. ALGORITHMEN-MODULARISIERUNG
für RLE-Kompressionen. Für Symbolunterdrückungen lässt
Die vorgestellten und auch weitere Muster finden sich in
sich allgemein keine Modularisierung darstellen, da es sich
verschiedenen Kompressionsalgorithmen, oft auch kombiniert
einfach nur durch die Sonderbehandlung eines Symbols aus-
oder auf mehreren Rekursionsebenen miteinander verwoben,
zeichnet. In Kombination mit einer Lauflängenkodierung ge-
wieder. Sich ähnelnde Algorithmen unterscheiden sich meist
lingt aber eine Modularisierung mit unserem Schema.
nur geringfügig in manchen Modulen oder sogar nur in Pa-
Merkmal der Lauflängenkodierung ist das Vorhandensein
rametern, die in ein Modul eingehen. Beispielsweise ähneln
von Läufen wn , endlichen Sequenzen der Länge n aus ein
sich die Algorithmen varint-PU und varint-SU [22] - letzte-
und demselben Wert w. Werden wirklich einfach nur Läufe
rer ist besser bekannt als VByte [11, 10, 9] - sehr. VByte ko-
von Werten kodiert, so reicht das simple Kompressionssche-
diert 32-Bit-Integerwerte mit ein bis 5 Bytes, wobei ein Byte
ma in Abbildung 4 aus. Der Wortgenerator unterteilt den
aus einem Deskriptorbit und 7 Datenbits besteht. Ebenso ist
dies bei varint-PU der Fall, beide Algorithmen unterscheiden
Rest sich nur in der Anordnung der Daten- und Deskriptorbits.
Eingabesequenz
Während bei VByte ein Bit pro zusammenhängendem Byte
potentiell
unendliche als Deskriptor dient, steht bei varint-PU der gesamte De-
Eingabe-
vc skriptor an einem Ende des komprimierten Integerwertes.
sequenz kodierte
Wort- Kodierer Zusammen- Sequenz Ein Beispiel zeigt Abbildung 6. Nicht belegte Bits bedeu-
w 7→ vc fügen
generator
wn n 7→ d (d : vc )m ten, dass diese im Beispiel nicht benötigt und weggelassen
Berechnungs- d werden. Der Integerwert wird in komprimierter Form mit 3
vorschrift
statt 4 Bytes kodiert.
Beide Formate haben den gleichen modularen Aufbau (sie-
Abbildung 4: Modularisierung einer einfachen Lauf- he Abbildung 7). Der rekursive statische Wortgenerator gibt
längenkodierung. immer eine Zahl aus. Da die Kodierung der Eingabe bei die-
sen Algorithmen soweit spezifiziert ist, dass die Zahlen als
Eingabedatenstrom in Läufe. Im Kodierer werden dann der 32-Bit-Integerwerte kodiert sind, ist die ausgegebene Zahl
Wert w und die Lauflänge n kodiert. Läufe können auch ein eingebetteter Lauf von der Form 0l 1w1 . . . w31−l (bzw.
in einer Sequenz zum Beispiel als führende Nullen einge- 032 für den Wert 0). Der Deskriptor bw/7 gibt die Anzahl der
bettet sein. Solche Fälle liegen im Schnittbereich zwischen für die Datenbits benötigten 7-Bit-Einheiten an. Allein aus
Symbolunterdrückung und Lauflängenkodierung. Dies ist für dem komprimierten Wert ohne Deskriptor ist die Lauflänge
statische Verfahren in Abbildung 5 dargestellt. Die Infor- der bei der Kodierung unterschlagenen Nullen nicht ermit-
mationen über Sequenzlängen des ausgezeichneten Wertes s telbar, schon weil eine Folge von Werten nicht mehr deko-
werden bei statischen Verfahren beim Zusammenfügen zum dierbar ist. Die Lauflänge ist allein aus dem Deskriptor (und
Beispiel in der Form (d(n) : vc )m gespeichert. Dabei ist d(n) dem Wissen, dass es sich um 32-Bit-Integerwerte handelt)
eine eineindeutige Abbildung. ersichtlich. Somit ist das Lauflängenmuster bei varint-SU
Sollen mehrere mit 32 Bits kodierte Werte mit geringerer, und varint-PU begründbar. Da das Zeichen 0 eine Sonder-
aber einheitlicher Bitweite gespeichert werden, wird für die stellung einnimmt, weil führende Nullen als Lauf betrachtet
Unterdrückung führender Nullen ein semiadaptives Schema werden, findet sich hier, wie bei allen varint-Algorithmen,
benötigt (nicht dargestellt). Die gemeinsame Bitweite bw ist auch eine Symbolunterdrückung. Beide Algorithmen unter-
Ausgabe der Parameterberechnung und kann als Deskriptor scheiden sich im Kompressionsschema nur im Modul des Zu-
angegeben werden, bw = d(n) ist eine Funktion von n, der sammenfügens. Das Symbol : wird hier als Konkatenati-
Anzahl der führenden Nullen, die entfernt wurden. Jeder onssymbol für abzählbar viele Werte verwendet.
Ein weiteres Beispiel für einen modularisierten Algorith-
mus ist FOR mit Binary Packing (nicht dargestellt), der
Rest
sich durch marginale Veränderungen und weitere Definitio-
potentiell Eingabesequenz nen aus dem Kompressionsschema für semiadaptive FOR-
unendliche
vc
Verfahren (Abb. 2) ergibt. Beim Binary Packing wird für
Eingabe-
sequenz eine endliche Sequenz von n binär kodierten Integerwerten
Zusammen-
fügen
kodierte z.B. zu 32 Bits eine gemeinsame Bitweite bw berechnet, mit
Sequenz
Wort-
generator Kodierer (d(n) : vc )m der alle n Werte kodiert werden können. Die erste Änderung
oder im Kompressionsschema betrifft die Parameterberechnung.
(d(n)l : vcl )m
Bedingungen Zusätzlich zum Referenzwert für eine endliche Sequenz, die
(eingebetteter)
Deskriptor der erste Wortgenerator ausgibt, muss die gemeinsame Bit-
Lauf w = sn
bzw. w ∈ W ⋆ sn W ⋆
d(n) weite bw berechnet und ausgegeben werden. Die zweite Än-
derung betrifft den Kodierer innerhalb der Rekursion. Nach
der Berechnung der Differenz aus Eingabe- und Referenz-
Abbildung 5: Modularisierung von symbolunter- wert wird der so erhaltene Werte mit Bitweite bw binär ko-
drückenden Verfahren mit Lauflängenkodierung als diert. Im Modul des Zusammenfügens muss dann bw als ein
statische Kompressionsverfahren. weiterer gemeinsamer Deskriptor zum Beispiel in der Form
57
Deskriptorbit Datenbits
1 0 1 1 1 1 0 1
varint-SU 1 0 1 0 1 1 0 1
0 0 0 0 0 1 1 0
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
32 24 16 8 0
1 0 1 1 1 1 0 1
1 0 1 0 1 1 0 1
0 0 0 0 0 1 1 0
varint-PU
Deskriptorbits Datenbits
Abbildung 6: Datenformat varint-SU und varint-PU.
Rest Zusammenfügen
Eingabesequenz bw/ 7 unär:
varint-SU: kodierte
potentiell b1 . . . bbw = 01bw/ 7 −1 bw/ 7 n Sequenz
/7
unendliche Kodierer
bw/ 7 = max({⌈ 32− l : bi : v7·i −6 . . . v7·i
Eingabe- 7 ⌉, 1}) i =1
sequenz 0l 1w1 . . . w31−l 7→ varint-PU:
statischer vc = v1 . . . vbw ·7 (bw/ 7 : vc )n
rekursiver 0bw/ 7 ·7−32+l 1w1 . . . w31−l , /7
Wort- 0l 1w1 . . . w31−l 032 7→ 07
generator
4 Bytes/ oder 032
1 Integerwert
Abbildung 7: Modularisierung der Algorithmen varint-SU und varint-PU.
(mref : bw : v nc ) gespeichert werden. Die Modularisierung dene, möglichst unabhängige kleinere Module, welche über-
dieses Algorithmus zeichnet sich durch die Muster FOR, schaubare Operationen ausführen, verbessert. Die Struktu-
Lauflängenkodierung und Symbolunterdrückung aus. rierung durch das entwickelte Schema bildet aus unserer
Nicht für alle Algorithmen ist diese recht einfache Modu- Sicht eine gute Basis zur abstrakten Betrachtung von leicht-
larisierung ausreichend. Auf PFOR basierende Algorithmen gewichtigen Kompressionsalgorithmen. Als Muster können
[31, 29, 27, 18] kodieren die meisten Eingabewerte aus natür- nicht nur bestimmte Techniken, sondern auch andere Ei-
lichen Zahlen mit der gleichen Bitweite bw. Die größeren, die genschaften von Kompressionsalgorithmen dargestellt wer-
nicht mit der Bitweite bw kodierbar sind, werden allerdings den. Statische Verfahren wie z.B. varint-SU und varint-PU
als Ausnahme deklariert und auf andere Weise kodiert und bestehen nur aus Wortgenerator, Kodierer und dem Modul
an anderer Stelle gespeichert. Dafür benötigt das erweiterte des Zusammenfügens. Adaptive Verfahren haben einen ad-
Schema ein Splitmodul, welches Daten aufgrund inhaltlicher aptiven Wortgenerator, eine adaptive Parameterberechnung
Merkmale in verschiedene Gruppen aufteilt und ausgibt. Für oder beides. Semiadaptive Verfahren zeichnen sich durch ei-
jede dieser Gruppen muss ein separater Kodierer verfügbar ne Parameterberechnung und eine Rekursion aus, in deren
sein, wobei die kodierten Werte aller Gruppen am Ende ge- Wortgenerator oder Kodierer die Ausgabe der Parameterbe-
meinsam zusammengefügt werden. rechnung eingeht.
Durch die Möglichkeit Module sehr passend zusammen-
zustellen und mit Inhalt zu füllen, ergibt sich ein mächti-
5. ZUSAMMENFASSUNG UND AUSBLICK ges Werkzeug für den automatisierten Bau von Algorith-
Unser entwickeltes Kompressionsschema bestehend aus vier men. Das Kompressionsschema bietet eine aus unserer Sicht
Modulen ist durchaus geeignet, um eine Vielzahl verschiede- fundierte Grundlage und eröffnet die Möglichkeit, für einen
ner leichtgewichtiger Kompressionsalgorithmen gut zu mo- gegebenen Kontext sehr gezielt speziell zugeschnittene Algo-
dularisieren und systematisch darzustellen. Durch den Aus- rithmen mit bestimmten Eigenschaften wie zum Beispiel der
tausch einzelner Module oder auch nur eingehender Parame- Art der Anpassbarkeit zusammenzubauen. Weiterhin kön-
ter lassen sich verschiedene Algorithmen mit dem gleichen nen verschiedene Muster wie FOR, Differenzkodierung, Sym-
Kompressionsschema darstellen. Einige Module und Modul- bolunterdrückung oder Lauflängenkodierung an den Kon-
gruppen tauchen in verschiedenen Algorithmen immer wie- text angepasst eingesetzt werden und das auf verschiedens-
der auf, wie zum Beispiel die gesamte Rekursion, die das Bi- ten Ebenen miteinander kombiniert.
nary Packing ausmacht, die sich in allen PFOR- und Simple- Für die Fortführung dieses Gedankens ist es notwendig,
Algorithmen [2, 3, 29, 27, 4] findet. Die Verständlichkeit ei- einen noch stärkeren Zusammenhang zwischen Kontextwis-
nes Algorithmus wird durch die Unterteilung in verschie- sen und passender Schemazusammenstellung sowie passen-
58
den Parametereingaben herzustellen. Des Weiteren wird ge- [12] J. Goldstein, R. Ramakrishnan, and U. Shaft.
rade für das theoretische Grundkonzept eine passende prak- Compressing relations and indexes. In ICDE
tische Umsetzung angegangen. Für die praktische Umset- Conference, pages 370–379, 1998.
zung wird ein Framework bestehend aus den eingeführten [13] D. Habich, P. Damme, and W. Lehner. Optimierung
Modulen anvisiert, so dass der Zusammenbau leichtgewichti- der Anfrageverarbeitung mittels Kompression der
ger Kompressionsalgorithmen wie beschrieben realisiert wer- Zwischenergebnisse. In BTW 2015, pages 259–278,
den kann. Die größte Herausforderung bei der praktischen 2015.
Umsetzung wird die Effizienz der Algorithmen sein. Um eine [14] C. Hänsch, T. Kissinger, D. Habich, and W. Lehner.
vergleichbare Effizienz zu den bisherigen Implementierungen Plan operator specialization using reflective compiler
erzielen zu können, sind unterschiedliche Ansätze notwendig. techniques. In BTW 2015, pages 363–382, 2015.
Ein vielversprechender Ansatz dabei ist die Spezialisierung [15] D. A. Huffman. A method for the construction of
von generischen Code mit dem Einsatz spezieller Compiler- minimum-redundancy codes. Proceedings of the
techniken, wie wir es in [14] angesprochen haben. Über die Institute of Radio Engineers, 40(9):1098–1101,
Spezialisierung kann hochoptimierter Ausführungscode er- September 1952.
zeugt werden, wobei das vorhandene Hintergrundwissen zur [16] T. Kissinger, B. Schlegel, D. Habich, and W. Lehner.
Codeoptimierung dem Compiler beigebracht werden muss. QPPT: query processing on prefix trees. In CIDR
2013, 2013.
Acknowledgments [17] T. J. Lehman and M. J. Carey. Query processing in
Diese Arbeit ist im Rahmen des DFG-finanzierten Projektes main memory database management systems. In
”Leichtgewichtige Kompressionsverfahren zur Optimierung SIGMOD Conference, pages 239–250, 1986.
komplexer Datenbankanfragen”(LE-1416/26-1) entstanden. [18] D. Lemire and L. Boytsov. Decoding billions of
integers per second through vectorization. CoRR,
6. LITERATUR abs/1209.2137, 2012.
[1] D. Abadi, S. Madden, and M. Ferreira. Integrating [19] T. Neumann. Efficiently compiling efficient query
compression and execution in column-oriented plans for modern hardware. PVLDB, 4(9):539–550,
database systems. In SIGMOD, pages 671–682, 2006. 2011.
[2] V. N. Anh and A. Moffat. Inverted index compression [20] H. K. Reghbati. An overview of data compression
using word-aligned binary codes. Inf. Retr., techniques. IEEE Computer, 14(4):71–75, 1981.
8(1):151–166, Jan. 2005. [21] M. A. Roth and S. J. V. Horn. Database compression.
[3] V. N. Anh and A. Moffat. Improved word-aligned SIGMOD Record, 22(3):31–39, 1993.
binary compression for text indexing. IEEE Trans. on [22] A. A. Stepanov, A. R. Gangolli, D. E. Rose, R. J.
Knowl. and Data Eng., 18(6):857–861, June 2006. Ernst, and P. S. Oberoi. Simd-based decoding of
[4] V. N. Anh and A. Moffat. Index compression using posting lists. In CIKM, pages 317–326, 2011.
64-bit words. Softw. Pract. Exper., 40(2):131–147, Feb. [23] T. Westmann, D. Kossmann, S. Helmer, and
2010. G. Moerkotte. The implementation and performance
[5] G. Antoshenkov, D. B. Lomet, and J. Murray. Order of compressed databases. SIGMOD Record,
preserving compression. In ICDE, pages 655–663, 29(3):55–67, 2000.
1996. [24] T. Willhalm, N. Popovici, Y. Boshmaf, H. Plattner,
[6] J. Aronson. Computer science and technology: data A. Zeier, and J. Schaffner. Simd-scan: Ultra fast
compression — a comparison of methods. NBS special in-memory table scan using on-chip vector processing
publication 500-12, Department of Commerce, units. PVLDB, 2(1):385–394, 2009.
National Bureau of Standards, Institute for Computer [25] R. N. Williams. Adaptive Data Compression. 1991.
Sciences and Technology, Washington, DC, USA, June [26] I. H. Witten, R. M. Neal, and J. G. Cleary. Arithmetic
1977. ERIC Document Number: ED149732. coding for data compression. Communications ACM,
[7] M. A. Bassiouni. Data compression in scientific and 30(6):520–540, 1987.
statistical databases. IEEE Transactions on Software [27] H. Yan, S. Ding, and T. Suel. Inverted index
Engineering, 11(10):1047–1058, 1985. compression and query processing with optimized
[8] P. A. Boncz, S. Manegold, and M. L. Kersten. document ordering. In WWW, pages 401–410, 2009.
Database architecture optimized for the new [28] A. Zandi, B. Iyer, and G. Langdon. Sort order
bottleneck: Memory access. In VLDB, pages 54–65, preserving data compression for extended alphabets.
1999. In Data Compression Conference, pages 330 –339,
[9] S. Büttcher, C. Clarke, and G. V. Cormack. 1993.
Information Retrieval: Implementing and Evaluating [29] J. Zhang, X. Long, and T. Suel. Performance of
Search Engines. The MIT Press, 2010. compressed inverted list caching in search engines. In
[10] B. Croft, D. Metzler, and T. Strohman. Search WWW, pages 387–396, 2008.
Engines: Information Retrieval in Practice. [30] J. Ziv and A. Lempel. A universal algorithm for
Addison-Wesley Publishing Company, USA, 1st sequential data compression. IEEE Transactions on
edition, 2009. Information Theory, 23:337–343, 1977.
[11] J. Dean. Challenges in building large-scale information [31] M. Zukowski, S. Heman, N. Nes, and P. Boncz.
retrieval systems: invited talk. In R. A. Baeza-Yates, Super-scalar ram-cpu cache compression. In ICDE,
P. Boldi, B. A. Ribeiro-Neto, and B. B. Cambazoglu, page 59, 2006.
editors, WSDM, page 1. ACM, 2009.
59