Vortex - Hochleistungsfähiges spaltenorientiertes Dateiformat

• "The LLVM of columnar file formats"
• Ein spaltenorientiertes Dateiformat mit einem Toolkit zur Verarbeitung komprimierter Apache-Arrow-Arrays über Speicher, Festplatte und Netzwerk hinweg
• Als ambitionierter Nachfolger von Apache Parquet unterstützt es 100- bis 200-mal schnellere Random-Access-Lesezugriffe und 2- bis 10-mal schnellere Scans, bei nahezu identischer Kompressionsrate und Schreibdurchsatz wie Parquet mit zstd
  • Unterstützt auch sehr große Tabellen (mit zehntausenden Spalten) sowie Dekomprimierung auf der GPU
• Vortex ist darauf ausgelegt, für spaltenorientierte Dateiformate eine ähnliche Rolle zu spielen wie Apache DataFusion für Query-Engines
  • Das heißt: hohe Erweiterbarkeit, sehr hohe Geschwindigkeit und ein umfangreicher Lieferumfang

[!Hinweis] > Es befindet sich noch in aktiver Entwicklung

• Hauptfunktionen:
  • Logical Types - Schemadefinitionen ohne Annahmen über das physische Layout
  • Zero-Copy to Arrow - kanonisierte Vortex-Arrays lassen sich per Zero-Copy in Apache-Arrow-Arrays umwandeln
  • Extensible Encodings - eine pluginartige Menge physischer Layouts. Zusätzlich zu Arrow-kompatiblen Encodings werden moderne Encodings (FastLanes, ALP, FSST usw.) als Erweiterungen bereitgestellt
  • Cascading Compression - Daten können rekursiv mit mehreren verschachtelten Encodings komprimiert werden
  • Pluggable Compression Strategies - der eingebaute Compressor basiert auf BtrBlocks, andere Strategien lassen sich aber leicht einsetzen
  • Compute - grundlegende Compute-Kernel, die direkt auf kodierten Daten arbeiten (z. B. Filter-Pushdown)
  • Statistics - jedes Array verfügt über zusammenfassende Statistiken, die beim Lesen optional berechnet werden. Sie können von Compute-Kerneln und Kompressoren verwendet werden
  • Serialization - Zero-Copy-Serialisierung von Arrays für IPC und Dateiformate
  • Columnar File Format (in Arbeit) - ein modernes Dateiformat zum Speichern komprimierter Array-Daten mit der Vortex-serde-Bibliothek. Optimiert für Random-Access-Lesezugriffe und sehr schnelle Scans. Ziel ist es, Apache Parquet abzulösen

Überblick: Logical vs Physical

• Eines der zentralen Designprinzipien von Vortex ist die strikte Trennung zwischen logischen und physischen Belangen
  • Beispiel: Ein Vortex-Array wird über den logischen Datentyp (den Typ der skalaren Elemente) und die physische Kodierung (den Typ des Arrays selbst) definiert
• Die eingebauten Encodings sind in erster Linie dafür ausgelegt, das Apache-Arrow-In-Memory-Format zu modellieren. Es gibt außerdem eingebaute Encodings (sparse, chunked), die als nützliche Bausteine für andere Encodings dienen. Erweiterungs-Encodings sind vor allem dafür gedacht, komprimierte In-Memory-Arrays wie Längenkodierung oder Dictionary-Encoding zu modellieren
• vortex-serde ist dafür ausgelegt, die physisch niedrigstufigen Details von Vortex-Arrays zu behandeln. Welche Encodings verwendet werden oder wie Daten logisch in Chunks aufgeteilt werden, bleibt der jeweiligen Compressor-Implementierung überlassen
• Eine der besonderen Eigenschaften des (in Entwicklung befindlichen) Vortex-Dateiformats ist, dass das physische Layout der Daten im Footer der Datei kodiert wird. Dadurch wird das Dateiformat faktisch selbstbeschreibend und kann weiterentwickelt werden, ohne die Kompatibilität der Dateiformat-Spezifikation zu brechen
• Zur Unterstützung der Vorwärtskompatibilität ist vorgesehen, optional einen WASM-Decoder direkt in die Datei einzubetten. Das soll helfen, die schnelle Verhärtung zu vermeiden, unter der andere spaltenorientierte Dateiformate gelitten haben

Komponenten

Logical Types

• Das Vortex-Typsystem befindet sich noch im Wandel. Aktuelle logische Typen:
  • Null
  • Bool
  • Integer (8, 16, 32, 64)
  • Float (16, b16, 32, 64)
  • Binary
  • UTF8
  • Struct
  • List (teilweise implementiert)
  • Date/Time/DateTime/Duration (als Erweiterungstypen implementiert)
  • TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

• Vortex enthält standardmäßig "Flat"-Encodings, die für Zero-Copy mit Apache Arrow ausgelegt sind. Sie stellen die kanonische Repräsentation jedes logischen Datentyps dar. Derzeit unterstützte kanonische Encodings:
  • Null
  • Bool
  • Primitive (Integer, Float)
  • Struct
  • VarBin (Binary, UTF8)
  • VarBinView (Binary, UTF8)
  • Extension
  • Weitere Encodings sollen hinzukommen

Compressed Encodings

• Vortex enthält eine Sammlung hochgradig datenparalleler und vektorisierter Encodings. Jedes dieser Encodings entspricht einer komprimierten In-Memory-Array-Implementierung, sodass die Dekomprimierung aufgeschoben werden kann. Derzeit sind folgende Encodings vorhanden:
  • Adaptive Lossless Floating Point (ALP)
  • BitPacked (FastLanes)
  • Constant
  • Chunked
  • Delta (FastLanes)
  • Dictionary
  • Fast Static Symbol Table (FSST)
  • Frame-of-Reference
  • Run-end Encoding
  • RoaringUInt
  • RoaringBool
  • Sparse
  • ZigZag
  • Weitere Encodings sollen hinzukommen

Compression

• Die Standard-Kompressionsstrategie von Vortex basiert auf dem BtrBlocks-Paper
  • Vereinfacht gesagt wird für jeden Daten-Chunk mindestens ca. 1 % der Daten als Stichprobe genommen
  • Anschließend wird versucht, den Chunk (rekursiv) mit einer Menge leichtgewichtiger Encodings zu komprimieren
  • Die leistungsstärkste Encoding-Kombination wird ausgewählt, um den gesamten Chunk zu kodieren
  • Das klingt zwar sehr aufwendig, aber mit grundlegenden Statistiken über den Chunk lassen sich viele Encodings kostengünstig ausschließen, sodass der Suchraum nicht explodiert

Compute

• Vortex ermöglicht es, dass jedes Encoding seine Implementierung von Compute-Funktionen spezialisiert, um Dekomprimierung nach Möglichkeit zu vermeiden. Beispielsweise ist es günstiger, bei der Filterung eines Dictionary-kodierten UTF8-Arrays zunächst das Dictionary zu filtern
• Vortex will kein vollständiger Compute-Engine sein, sondern lediglich die grundlegenden Compute-Operationen implementieren, die für effiziente Scans und Pushdown erforderlich sein können

Statistics

• Vortex-Arrays verfügen über verzögert berechnete zusammenfassende Statistiken
• Anders als bei anderen Array-Bibliotheken können diese Statistiken aus Festplattenformaten wie Parquet übernommen und bis zur Compute-Engine erhalten bleiben
• Die Statistiken können von Compute-Kerneln und Kompressoren verwendet werden
• Aktuelle Statistiken:
  • BitWidthFreq
  • TrailingZeroFreq
  • IsConstant
  • IsSorted
  • IsStrictSorted
  • Max
  • Min
  • RunCount
  • TrueCount
  • NullCount

Serialization / Deserialization (Serde)

• Ziele der vortex-serde-Implementierung:
  • Unterstützung von Scans (Spaltenprojektion + Zeilenfilterung) mit Zero-Copy und ohne Heap-Allokationen
  • Unterstützung von Random Access in konstanter oder nahezu konstanter Zeit
  • Weitergabe von Statistik-Informationen wie Sortierung an Verbraucher
  • Bereitstellung eines IPC-Formats zum Senden von Arrays zwischen Prozessen
  • Bereitstellung eines erweiterbaren, erstklassigen Dateiformats zum Speichern spaltenorientierter Daten auf Festplatte oder in Object Storage

Integration mit Apache Arrow

• Apache Arrow ist der De-facto-Standard für Interoperabilität bei spaltenorientierten Array-Daten. Entsprechend ist Vortex so konzipiert, dass es maximal kompatibel mit Apache Arrow ist
• Alle Arrow-Arrays können per Zero-Copy in Vortex-Arrays umgewandelt werden. Aus Arrow-Arrays erzeugte Vortex-Arrays können wiederum per Zero-Copy zurück in Arrow umgewandelt werden
• Dabei ist zu beachten, dass Vortex und Arrow unterschiedliche, aber komplementäre Ziele verfolgen
• Vortex unterscheidet sich von Arrow durch die explizite Trennung von logischen Typen und physischen Encodings. Dadurch kann Vortex komplexere Arrays modellieren und dennoch eine logische Schnittstelle bereitstellen
  • Beispiel: Vortex kann ein UTF8-ChunkedArray modellieren, bei dem der erste Chunk run-length-kodiert und der zweite Chunk dictionary-kodiert ist. In Arrow sind RunLengthArray und DictionaryArray inkompatible, separate Typen und können daher nicht auf diese Weise kombiniert werden