Vortex - format de fichier colonnaire haute performance

• « The LLVM of columnar file formats »
• Un format de fichier colonnaire accompagné d’une boîte à outils pour manipuler des tableaux Apache Arrow compressés en mémoire, sur disque et sur le réseau
• Un successeur ambitieux à Apache Parquet, offrant des lectures en accès aléatoire 100 à 200 fois plus rapides et des scans 2 à 10 fois plus rapides, tout en conservant un taux de compression et un débit d’écriture presque identiques à ceux de Parquet avec zstd
  • Prend aussi en charge les très grandes tables (des dizaines de milliers de colonnes) ainsi que la décompression sur GPU
• Vortex est conçu pour jouer, pour les formats de fichiers colonnaires, un rôle comparable à celui d’Apache DataFusion pour les moteurs de requête
  • Autrement dit, il met l’accent sur une grande extensibilité, une vitesse très élevée et des fonctionnalités intégrées

[!WARNING] Toujours en développement actif

• Fonctionnalités principales :
  • Logical Types - Définition de schéma qui ne fait aucune hypothèse sur la disposition physique
  • Zero-Copy to Arrow - Les tableaux Vortex canonicalisés peuvent être convertis en tableaux Apache Arrow sans copie
  • Extensible Encodings - Ensemble de dispositions physiques sous forme de plugins. En plus des encodages compatibles Arrow, des encodages récents (FastLanes, ALP, FSST, etc.) sont fournis en extensions
  • Cascading Compression - Compression récursive possible des données via plusieurs encodages imbriqués
  • Pluggable Compression Strategies - Le compresseur intégré repose sur BtrBlocks, mais d’autres stratégies peuvent aussi être utilisées facilement
  • Compute - Noyaux de calcul de base opérant sur les données encodées (par ex. filter pushdown)
  • Statistics - Chaque tableau dispose de statistiques de synthèse calculées de manière optionnelle à la lecture. Elles peuvent être utilisées par les noyaux de calcul et les compresseurs
  • Serialization - Sérialisation sans copie des tableaux pour l’IPC et les formats de fichier
  • Columnar File Format (en cours) - Un format de fichier moderne stockant des données de tableaux compressés à l’aide de la bibliothèque serde de Vortex. Optimisé pour la lecture en accès aléatoire et les scans très rapides. Vise à succéder à Apache Parquet

Vue d’ensemble : logique vs physique

• L’un des principes centraux de conception de Vortex est la séparation stricte entre préoccupations logiques et physiques
  • Exemple : un tableau Vortex est défini par son type de données logique (le type des éléments scalaires) et son encodage physique (le type du tableau lui-même)
• Les encodages intégrés sont principalement conçus pour modéliser le format en mémoire d’Apache Arrow. Il existe aussi des encodages intégrés (sparse, chunked) utilisés comme briques utiles pour d’autres encodages. Les encodages d’extension servent principalement à modéliser des tableaux en mémoire compressés, comme l’encodage par longueur ou par dictionnaire
• vortex-serde est conçu pour gérer les détails physiques de bas niveau des tableaux Vortex. Le choix de l’encodage à utiliser et la manière de découper logiquement les données en chunks sont laissés à l’implémentation de Compressor
• L’une des propriétés singulières du format de fichier Vortex (en cours de développement) est qu’il encode la disposition physique des données dans le footer du fichier. Le format devient ainsi effectivement auto-descriptif et peut évoluer sans casser la compatibilité de la spécification du format
• Il est conçu pour prendre en charge la compatibilité ascendante en intégrant optionnellement un décodeur WASM dans le fichier lui-même. Cela devrait aider à éviter la rigidification rapide qui a affecté d’autres formats de fichiers colonnaires

Composants

Logical Types

• Le système de types de Vortex est encore en évolution. Types logiques actuels :
  • Null
  • Bool
  • Integer(8, 16, 32, 64)
  • Float(16, b16, 32, 64)
  • Binary
  • UTF8
  • Struct
  • List (implémentation partielle)
  • Date/Time/DateTime/Duration (implémentés comme types d’extension)
  • TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

• Vortex inclut par défaut des encodages « Flat » conçus pour être zero-copy avec Apache Arrow. Ils constituent la représentation canonique de chaque type de données logique. Encodages canoniques actuellement pris en charge :
  • Null
  • Bool
  • Primitive (Integer, Float)
  • Struct
  • VarBin (Binary, UTF8)
  • VarBinView (Binary, UTF8)
  • Extension
  • D’autres encodages seront ajoutés

Compressed Encodings

• Vortex comprend un ensemble d’encodages hautement parallèles sur les données et vectorisés. Chacun correspond à une implémentation de tableau en mémoire compressé, ce qui permet de retarder la décompression. Encodages actuellement disponibles :
  • 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
  • D’autres encodages seront ajoutés

Compression

• La stratégie de compression par défaut de Vortex est basée sur l’article BtrBlocks
  • En pratique, un échantillon représentant au minimum ~1 % des données est prélevé pour chaque chunk
  • Ensuite, une compression (récursive) est testée avec un ensemble d’encodages légers
  • La combinaison d’encodages la plus performante est choisie pour encoder l’ensemble du chunk
  • Cela peut sembler très coûteux, mais avec de simples statistiques de base sur le chunk, de nombreux encodages peuvent être éliminés à faible coût, évitant ainsi une explosion de l’espace de recherche

Compute

• Vortex permet à chaque encodage de spécialiser l’implémentation des fonctions de calcul afin d’éviter autant que possible la décompression. Par exemple, pour filtrer un tableau UTF8 encodé par dictionnaire, il est plus économique de filtrer d’abord le dictionnaire
• Vortex cherche uniquement à implémenter les opérations de calcul de base nécessaires à des scans efficaces et au pushdown, et non à devenir un moteur de calcul complet

Statistics

• Les tableaux Vortex disposent de statistiques de synthèse calculées à la demande
• Contrairement à d’autres bibliothèques de tableaux, ces statistiques peuvent être remplies depuis des formats disque comme Parquet et préservées jusqu’au moteur de calcul
• Les statistiques peuvent être utilisées par les noyaux de calcul et les compresseurs
• Statistiques actuelles :
  • BitWidthFreq
  • TrailingZeroFreq
  • IsConstant
  • IsSorted
  • IsStrictSorted
  • Max
  • Min
  • RunCount
  • TrueCount
  • NullCount

Serialization / Deserialization (Serde)

• Objectifs de l’implémentation vortex-serde :
  • Prendre en charge les scans (projection de colonnes + filtrage de lignes) sans copie et sans allocation sur le heap
  • Prendre en charge l’accès aléatoire en temps constant ou quasi constant
  • Transmettre au consommateur des informations statistiques telles que l’ordre de tri
  • Fournir un format IPC pour l’envoi de tableaux entre processus
  • Fournir un format de fichier extensible et de tout premier plan pour stocker des données colonnaires sur disque ou dans un object storage

Intégration avec Apache Arrow

• Apache Arrow est le standard de facto de l’interopérabilité pour les données de tableaux colonnaires. Il est donc naturel que Vortex soit conçu pour être aussi compatible que possible avec Apache Arrow
• Tous les tableaux Arrow peuvent être convertis en tableaux Vortex sans copie. Les tableaux Vortex créés à partir de tableaux Arrow peuvent ensuite être reconvertis en Arrow sans copie
• Il faut noter que Vortex et Arrow ont des objectifs différents, mais complémentaires
• Vortex se distingue d’Arrow par une séparation explicite entre types logiques et encodages physiques. Cela permet à Vortex de modéliser des tableaux plus complexes tout en exposant une interface logique
  • Exemple : Vortex peut modéliser un ChunkedArray UTF8 dont le premier chunk est encodé en run-length et le second par dictionnaire. Dans Arrow, RunLengthArray et DictionaryArray sont des types distincts incompatibles et ne peuvent donc pas être combinés de cette manière