Dans le premier article sur la structure du fichier QVD, j'ai décrit la structure générale et me suis attardé sur les métadonnées de manière suffisamment détaillée, et le second sur le stockage des colonnes (caractères). Dans cet article, je vais décrire le format de stockage des informations sur les chaînes, résumer et parler des plans et des réalisations.
Donc (rappelez-vous) le fichier QVD correspond à la table relationnelle, dans le fichier QVD la table est stockée en deux parties indirectement connectées:
Les tables de caractères (mon terme) contiennent des valeurs uniques pour chaque colonne de la table source. J'en ai parlé dans le deuxième article.
La table de lignes contient les lignes de la table source, chaque ligne stocke les indices des valeurs de colonne (champ) de la ligne dans la table de symboles correspondante. C'est à ce sujet que sera cet article.
Sur l'exemple de notre assiette (rappelez-vous - de la première partie)
SET NULLINTERPRET =<sym>; tab1: LOAD * INLINE [ ID, NAME 123.12,"Pete" 124,12/31/2018 -2,"Vasya" 1,"John" <sym>,"None" ];
Dans la table de lignes de notre fichier QVD, cette étiquette correspondra à 5 lignes - toujours une correspondance exacte: combien de lignes se trouvent dans la table, combien de lignes se trouvent dans la table de lignes du fichier QVD.
Une ligne de la table de lignes se compose d'entiers non négatifs, chacun de ces nombres est un index dans la table de symboles correspondante. Au niveau logique, tout est simple, il reste à clarifier les nuances et à donner un exemple (démonter - comme notre plaque signalétique est présentée dans QVD).
La table des lignes se compose de K * N octets, où
- K - le nombre de lignes dans la table source (la valeur de la balise de métadonnées "NoOfRecords")
- N - longueur d'octet de la ligne de la table des symboles (la valeur de la balise de métadonnées "RecordByteSize")
La table de lignes commence par le décalage "Offset" (balise de métadonnées) par rapport au début de la partie binaire du fichier.
Les informations sur la table de lignes (longueur, taille de ligne, décalage) sont stockées dans la partie générale des métadonnées.
Toutes les lignes du tableau de lignes ont le même format et sont une concaténation de "nombres non signés". La longueur du nombre est au minimum suffisante pour représenter un champ spécifique: la longueur dépend du nombre de valeurs uniques d'un champ particulier.
Pour les champs avec une valeur (comme je l'ai déjà écrit), cette longueur sera nulle (cette valeur est la même dans chaque ligne de la table source et est stockée dans la table de symboles correspondante).
Pour les champs à deux valeurs, cette longueur sera égale à un (les valeurs d'index possibles dans la table des symboles sont 0 et 1), etc.
Étant donné que la longueur totale de la ligne du tableau de lignes doit être un multiple de l'octet, la longueur du "dernier caractère" est alignée sur la limite de l'octet (voir ci-dessous lorsque nous analyserons notre plaque).
Les informations sur le format de chaque champ sont stockées dans la section métadonnées dédiée à ce champ (nous nous attarderons un peu plus loin), la longueur de la représentation bit du champ est stockée dans la balise "BitWidth".
Stockage des valeurs NULL
Comment stocker les valeurs manquantes? En m'abstenant de discuter du pourquoi, je répondrai de cette façon: si je comprends bien, la combinaison suivante correspond aux valeurs NULL
- la balise "Bias" du champ correspondant prend la valeur "-2" (dans l'ensemble, je suis tombé sur deux valeurs possibles de cette balise - "0" et "-2")
- l'index de champ pour la ligne où ce champ est NULL est 0
En conséquence, tous les autres indices de la colonne avec des valeurs NULL sont augmentés de 2 - nous verrons dans notre exemple un peu plus bas.
L'ordre des champs de la ligne
L'ordre des champs dans la ligne du tableau de lignes correspond au décalage binaire du champ, qui est stocké dans la balise "BitOffset" de la section de métadonnées liée à ce champ.
Analysons notre exemple (voir les métadonnées dans la première partie de cette série).
Champ d'identification
- décalage de bit 0 - le champ sera le plus à droite
- longueur de bit 3 - le champ occupera 3 bits dans une ligne d'une table de lignes
- Le biais est "-2" - le champ a des valeurs NULL, tous les index sont augmentés de 2
Champ "NOM"
- décalage de bit 3 - le champ est situé à gauche du champ ID de 3 bits
- longueur de bits 5 - le champ occupera 5 bits dans la ligne de la table de lignes (aligné sur la limite d'octets)
- Le biais est "0" - le champ n'a pas de valeurs NULL, tous les indices sont "honnêtes"
Présentation de notre plaque signalétique.
Regardons les vrais "zéros et uns" - je donnerai des fragments du fichier QVD sous forme de représentation binaire "au format hexadécimal" (si compact).
Tout d'abord, toute la partie binaire (le surligné en rose, les métadonnées sont tronquées - ça fait mal à beaucoup d'entre elles ...)
Assez compact, d'accord. Examinons de plus près - juste après les métadonnées, il y a des tables de symboles (les métadonnées, en passant, dans ce fichier se terminent par un saut de ligne et un octet zéro - techniquement, cela se produit, zéro octet après que les métadonnées doivent être ignorées ...).
La première table de symboles est mise en évidence dans la figure ci-dessous.
On voit:
La première valeur unique du champ ID est
- type "6" (le premier octet alloué) est un nombre à virgule flottante avec une chaîne (voir le deuxième article)
- après le premier octet, 8 des octets suivants est un nombre à virgule flottante représenté binaire
- après eux vient la représentation sous forme de chaîne - très pratique (pas besoin de se rappeler - quel était le nombre), se terminant par un octet zéro
Les trois valeurs uniques restantes sont de type 5 (un entier avec une chaîne) - les valeurs sont "124", "-2" et "1" (faciles à voir le long des lignes).
Dans la figure ci-dessous, j'ai mis en surbrillance la deuxième table des symboles (pour le champ "NOM")
La première valeur unique du champ "NAME" est de type "4" (le premier octet alloué) - une chaîne se terminant par zéro.
Les quatre autres valeurs uniques sont également les chaînes "31/12/2018", "Vaysa", "John" et "None".
Maintenant - le tableau des lignes (mis en évidence dans la figure ci-dessous)
Comme prévu - 5 octets (5 lignes par un octet).
La première ligne (correspondant à la ligne 123.12, "Pete" de notre assiette)
La valeur de chaîne est l'octet "02" (binaire 000000010).
Séparez-le (rappelez-vous la description ci-dessus)
- à droite 3 bits (binaire 010, à notre avis c'est 2) - c'est un index dans la table des symboles du champ "ID"
- nous avons le champ "ID" contient NULL, donc l'index est augmenté de 2, c'est-à-dire l'indice résultant est 0, ce qui correspond au caractère "123.12".
- les 5 bits suivants (binaire et décimal 0) est l'index dans la table des symboles du champ "NAME", il ne contient pas NULL, c'est donc l'index "Pete" dans la table des symboles.
Deuxième rangée (124.12 / 31/2018) dans le tableau des rangées
Valeur - octet "0B" (binaire 00001011)
- à droite 3 bits (binaire 011, à notre avis c'est 3) - c'est l'index dans la table des symboles du champ "ID"
- nous avons le champ "ID" contient NULL, donc l'index est augmenté de 2, c'est-à-dire l'indice résultant est 1, ce qui correspond au symbole "124".
- les 5 bits suivants (binaire et décimal 1) est l'index dans la table des symboles du champ "NAME", il ne contient pas NULL, c'est donc l'index "31/12/2018" dans la table des symboles.
Eh bien et ainsi de suite, jetons un coup d'œil à la dernière ligne - là nous l'avons eu, "None" (c'est-à-dire NULL et la chaîne "None"):
La valeur est l'octet "20" (binaire 0010000)
- à droite 3 bits (binaire et décimal 0) - c'est l'index dans la table des symboles du champ "ID"
- nous avons le champ "ID" contient NULL, donc l'index est augmenté de 2, c'est-à-dire l'indice final est -2, ce qui correspond à la valeur NULL.
- les 5 bits suivants (binaire 100, décimal 4) est l'index dans la table des symboles du champ "NAME", il ne contient pas NULL, c'est donc l'index "None" dans la table des symboles.
IMPORTANT Je ne trouve pas d'exemple confirmant cela, mais je suis tombé sur des fichiers contenant un index final de -1 pour les valeurs NULL. Par conséquent, dans mes programmes, je considère NULL tous les champs dont l'indice final est négatif.
Lignes plus longues dans un tableau de lignes
À la fin de l'analyse du format QVD, je m'attarderai brièvement sur les nuances importantes - les longues lignes dans les champs de stockage de la table de lignes dans l'ordre de droite à gauche, où le champ avec un décalage de zéro bit sera le plus à droite (comme je l'ai décrit ci-dessus). MAIS l' ordre des octets est inversé, c'est-à-dire le premier octet sera le plus à droite (et contiendra le champ "droit" - un champ avec un décalage de bit nul), le dernier octet sera le premier (c'est-à-dire, contiendra le champ le plus "gauche" - un champ avec un décalage de bit maximum).
Un exemple doit être donné, mais pas surchargé de détails. Regardons une telle étiquette (je cite un fragment - pour obtenir de longues lignes dans la table des lignes, vous devez augmenter le nombre de valeurs uniques).
tab2: LOAD * INLINE [ ID, VAL, NAME, PHONE, SINGLE 1, 100001, "Pete1", "1234567890", "single value" 2, 200002, "Pete2", "2234567890", "single value" ... ];
Informations succinctes sur les champs (retrait des métadonnées):
- ID: largeur 8 bits, décalage de bits - 0, polarisation - 0
- VAL: largeur 5 bits, décalage de bits - 8, polarisation - 0
- NOM: largeur 6 bits, décalage de bits - 18, biais - 0
- TÉLÉPHONE: largeur 5 bits, décalage de bits - 13, polarisation - 0
- SINGLE: largeur 0 bits (a une valeur)
La table de lignes se compose de chaînes d'une longueur de 3 octets, respectivement, dans la ligne de la table de lignes, les données sur les champs seront décomposées logiquement comme suit:
- 6 premiers bits - champ "NAME"
- 5 bits suivants - champ "PHONE"
- puis 5 bits - champ "VAL"
- 8 derniers bits - champ ID
La séquence logique est convertie en octets physiques dans l'ordre inverse, c'est-à-dire
- le champ "ID" occupe complètement le premier octet (qui dans la séquence logique est le dernier)
- le champ "VAL" occupe les 5 bits inférieurs du deuxième octet
- le champ "PHONE" occupe les 3 bits supérieurs du deuxième octet et les 2 bits inférieurs du troisième octet
- le champ "NAME" occupe les 6 bits supérieurs du troisième octet
Regardons des exemples, voici à quoi ressemble la première ligne du tableau des lignes (surlignée en rose)
Valeurs de champ
- ID - binaire 00000000, décimal 0
- VAL - binaire 00010, décimal 2, soustraire 2 du biais - obtenir 0
- PHONE - binaire 00010, décimal 2, soustrayez 2 du biais - obtenez 0
- NOM - binaire 000000, décimal 0
C'est-à-dire que la première ligne contient les premiers caractères des tables de caractères correspondantes.
En général, il est pratique de commencer l'analyse à partir de la première ligne - il contient généralement des zéros en tant qu'index (le fichier QVD est construit de telle manière que les valeurs de la première ligne pénètrent d'abord dans la table des caractères).
Regardons la deuxième ligne pour corriger
Valeurs de champ
- ID - binaire 00000001, décimal 1
- VAL - binaire 00011, décimal 3, soustrayez 2 du biais - obtenez 1
- TÉLÉPHONE - binaire 00011, décimal 3, soustrayez 2 du biais - obtenez 1
- NOM - binaire 000001, décimal 1
C'est-à-dire que la deuxième ligne contient les seconds caractères des tables de caractères correspondantes.
Je vais partager une petite expérience - comment je "lis" techniquement QVD.
La première version a été écrite en python (je vais l'anoblir et la mettre sur github).
Les principaux problèmes sont rapidement apparus:
- les tables de symboles ne peuvent être lues que «consécutivement» (il est impossible de lire le numéro de symbole N sans lire tous les caractères précédents)
- les vrais fichiers ne rentrent pas dans la RAM
- des opérations les plus lentes (sauf pour travailler avec des fichiers) - opérations sur les bits (décompresser une ligne d'une table de chaînes)
- les performances diminuent fortement sur les fichiers QVD "larges" (quand il y a beaucoup de colonnes)
Certains de ces problèmes peuvent être résolus en changeant le langage (de python à C, par exemple). La pièce a nécessité une action supplémentaire.
L'implémentation actuelle plutôt rapide ressemble à ceci - la logique générale est implémentée en python, et les opérations les plus critiques sont effectuées dans des programmes C séparés fonctionnant en parallèle.
Peu de temps
- les tables de symboles sont écrites dans des fichiers, des index sont en outre créés pour les champs de texte, il est ainsi possible de lire le numéro de symbole N
- travailler avec QVD et des fichiers avec des tables de symboles implémentées via des fichiers mappés en mémoire (donc plus rapide)
- tout d'abord, en parallèle (avec une limite sur le nombre de processeurs), des fichiers sont créés avec des tables de symboles (et index)
- puis en parallèle (avec une restriction similaire) les lignes de la table des lignes sont lues et les fichiers csv sont créés (en HDFS)
- la dernière étape consiste à convertir ces fichiers en une table ORC (à l'aide des outils Hive)
- en C implémenté la création de fichiers avec des tables de symboles et la création d'un fichier CSV pour une gamme de lignes
Je ne veux pas donner de chiffres pour les performances - ils nécessiteront une liaison avec le matériel, au niveau qualitatif, il s’avère que le fichier QVD est copié dans la table ORC à peu près à la vitesse de copie des données sur le réseau. Ou, en d'autres termes, prendre des données de QVD est assez réaliste (au niveau du ménage).
J'ai également implémenté la logique de création de fichiers QVD - cela fonctionne assez rapidement sur python (apparemment, je n'ai pas encore atteint de gros volumes - ce n'est pas nécessaire. J'y arriverai - je vais le réécrire de la même manière que la version "lecture").
Plans futurs
Et ensuite:
- J'ai l'intention de mettre la version Python du code dans github (cette version vous permettra "d'explorer" le fichier QVD - voir les métadonnées, lire et écrire des caractères, des chaînes. La version est aussi simple et évidemment lente que possible - sans fichiers pour les tables de caractères, avec lecture séquentielle, en utilisant des bibliothèques standard pour travailler avec bits, etc.)
- Je pense à faire quelque chose pour les pandas (comme read_qvd ()), cela restreint le fait qu'il sera lent sur python, ainsi que le fait que tous les QVD ne "rentrent" pas dans la mémoire, donc
- Je pense à faire du fichier QVD une source de données pour Spark - il ne devrait pas y avoir ce problème avec "ne pas entrer dans la mémoire" (et la langue là-bas - scala - est plus proche du matériel)
Au lieu d'une postface
Pendant longtemps, j'ai fait le tour des fichiers QVD, il semblait que "tout y est compliqué". Il s'est avéré que c'était difficile, mais pas très, une bonne impulsion était github, que j'ai mentionné dans la première partie (une sorte de catalyseur). C'était alors une question de technologie. Note de moi et de tout le monde (une confirmation de plus) - tout peut être fait dans la programmation, la question est le temps et la motivation.
J'espère que je ne suis pas très fatigué des détails, je suis prêt à répondre aux questions (dans les commentaires ou de toute autre manière). S'il y a une suite - j'écrirai.