ALP: Adaptive Lossless Floating-Point Compression

Zusammenfassung

IEEE-754-Doubles repräsentieren die meisten reellen Werte nicht exakt und führen Rundungsfehler bei Berechnungen und der [De]Serialisierung nach Text ein. Diese Rundungsfehler verhindern den Einsatz bestehender leichtgewichtiger Kompressionsschemata wie Delta und Frame Of Reference (FOR); kürzlich wurden jedoch neue Verfahren vorgeschlagen: Gorilla, Chimp128, PseudoDecimals (PDE), Elf und Patas. Ihre Kompressionsraten sind jedoch nicht besser als die allgemeiner Kompressoren wie Zstd, während [De]Kompression deutlich langsamer ist als bei Delta und FOR. Wir schlagen ALP vor und bewerten es; ALP verbessert diese früheren Verfahren deutlich sowohl in Geschwindigkeit als auch in der Kompressionsrate. Wir haben ALP nach sorgfältiger Untersuchung der Datensätze entwickelt, mit denen die früheren Verfahren bewertet wurden. Für Geschwindigkeit ist ALP auf vektorisierte Ausführung ausgelegt. Das erwies sich auch als Schlüssel zur besseren Kompressionsrate, weil wir Gemeinsamkeiten innerhalb von Vektoren als Kompressionschancen nutzen konnten. ALP ist ein adaptives Verfahren, das eine stark erweiterte Variante von PseudoDecimals [31] verwendet, um Doubles verlustfrei als Ganzzahlen zu kodieren, wenn sie als Dezimalzahlen entstanden sind, und andernfalls die vorderen Bits der Doubles vektorisiert komprimiert. Die hohen Geschwindigkeiten stammen aus unserer Implementierung in Skalarcode, der automatisch vektorisiert, aus Bausteinen unserer FastLanes-Bibliothek [6] sowie aus einem effizienten zweistufigen Kompressionsalgorithmus, der zuerst Row-Groups und dann Vektoren sampelt.

Implementierung

Der ALP-Algorithmus ist das Standardkompressionsverfahren für Gleitkommazahlen in DuckDB.