En el primer artículo sobre la estructura del archivo QVD, describí la estructura general y me detuve en los metadatos con suficiente detalle, y el segundo sobre el almacenamiento de columnas (caracteres). En este artículo, describiré el formato para almacenar información sobre cadenas, resumir y hablar sobre planes y logros.
Entonces (recuerde) el archivo QVD corresponde a la tabla relacional, en el archivo QVD la tabla se almacena en dos partes conectadas indirectamente:
Las tablas de caracteres (mi término) contienen valores únicos para cada columna en la tabla de origen. Hablé de ellos en el segundo artículo.
La tabla de filas contiene las filas de la tabla de origen, cada fila almacena los índices de los valores de columna (campo) de la fila en la tabla de símbolos correspondiente. De esto se tratará este artículo.
En el ejemplo de nuestro plato (recuerde, de la primera parte)
SET NULLINTERPRET =<sym>; tab1: LOAD * INLINE [ ID, NAME 123.12,"Pete" 124,12/31/2018 -2,"Vasya" 1,"John" <sym>,"None" ];
En la tabla de filas de nuestro archivo QVD, esta etiqueta corresponderá a 5 filas, siempre una coincidencia exacta: cuántas filas hay en la tabla, cuántas filas hay en la tabla de filas del archivo QVD.
Una fila en la tabla de filas consta de enteros no negativos, cada uno de estos números es un índice en la tabla de símbolos correspondiente. En el nivel lógico, todo es simple, queda por aclarar los matices y dar un ejemplo (desmontar, ya que nuestra placa de identificación se presenta en QVD).
La tabla de filas consta de K * N bytes, donde
- K: el número de filas en la tabla de origen (el valor de la etiqueta de metadatos "NoOfRecords")
- N - longitud de byte de la fila de la tabla de símbolos (el valor de la etiqueta de metadatos "RecordByteSize")
La tabla de líneas comienza con el desplazamiento "Offset" (etiqueta de metadatos) relativo al comienzo de la parte binaria del archivo.
La información sobre la tabla de filas (longitud, tamaño de fila, desplazamiento) se almacena en la parte general de los metadatos.
Todas las filas de la tabla de filas tienen el mismo formato y son una concatenación de "números sin signo". La longitud del número es mínimamente suficiente para representar un campo específico: la longitud depende del número de valores únicos de un campo en particular.
Para los campos con un valor (como ya escribí), esta longitud será cero (este valor es el mismo en cada fila de la tabla de origen y se almacena en la tabla de símbolos correspondiente).
Para campos con dos valores, esta longitud será igual a uno (los posibles valores de índice en la tabla de símbolos son 0 y 1), y así sucesivamente.
Dado que la longitud total de la fila de la tabla de filas debe ser un múltiplo del byte, la longitud del "último carácter" está alineada con el límite del byte (ver más abajo cuando analizaremos nuestra placa).
La información sobre el formato de cada campo se almacena en la sección de metadatos dedicada a este campo (nos detendremos un poco más abajo), la longitud de la representación de bits del campo se almacena en la etiqueta "BitWidth".
Almacenar valores NULL
¿Cómo almacenar valores perdidos? Absteniéndome de discutir el tema de por qué, responderé de esta manera: tal como lo entiendo, la siguiente combinación corresponde a valores NULL
- La etiqueta "Bias" del campo correspondiente toma el valor "-2" (en general, encontré dos valores posibles de esta etiqueta: "0" y "-2")
- el índice de campo para la fila donde este campo es NULL es 0
En consecuencia, todos los demás índices en la columna con valores NULL aumentan en 2; veremos en nuestro ejemplo un poco más bajo.
El orden de los campos en la fila.
El orden de los campos en la fila de la tabla de filas corresponde al desplazamiento de bits del campo, que se almacena en la etiqueta "BitOffset" de la sección de metadatos relacionada con este campo.
Analicemos nuestro ejemplo (ver metadatos en la primera parte de esta serie).
Campo de identificación
- desplazamiento de bit 0: el campo será el "más a la derecha"
- longitud de bit 3: el campo ocupará 3 bits en una fila de una tabla de filas
- El sesgo es "-2": el campo tiene valores NULL, todos los índices se incrementan en 2
Campo "NOMBRE"
- Desplazamiento de 3 bits: el campo se encuentra a la izquierda del campo ID en 3 bits.
- longitud de bit 5: el campo ocupará 5 bits en la fila de la tabla de filas (alineado con el límite de bytes)
- El sesgo es "0": el campo no tiene valores NULL, todos los índices son "honestos"
Presentación de nuestra placa de identificación.
Veamos los "ceros y unos" reales: daré fragmentos del archivo QVD como una representación binaria "en formato hexadecimal" (muy compacto).
Primero, toda la parte binaria (resaltada en rosa, los metadatos se truncan, duelen muchos de ellos ...)
Suficientemente compacto, de acuerdo. Echemos un vistazo más de cerca: justo después de los metadatos hay tablas de símbolos (los metadatos, por cierto, en este archivo terminaron con un salto de línea y un byte cero - técnicamente esto sucede, cero bytes después de que los metadatos deben omitirse ...).
La primera tabla de símbolos se resalta en la figura a continuación.
Vemos:
El primer valor único del campo ID es
- El tipo "6" (el primer byte asignado) es un número de coma flotante con una cadena (consulte el segundo artículo)
- después del primer byte, 8 de los siguientes bytes es un número binario representado en coma flotante
- después de ellos viene la representación de cadena, muy conveniente (no es necesario recordar, cuál era el número), que termina con un byte cero
Los tres valores únicos restantes son del tipo 5 (un número entero con una cadena): los valores son "124", "-2" y "1" (fáciles de ver a lo largo de las líneas).
En la figura a continuación, resalté la segunda tabla de símbolos (para el campo "NOMBRE")
El primer valor único del campo "NOMBRE" es el tipo "4" (el primer byte asignado), una cadena que termina en cero.
Los otros cuatro valores únicos son también las cadenas "31/12/2018", "Vaysa", "John" y "Ninguno".
Ahora: la tabla de filas (resaltada en la figura a continuación)
Como se esperaba - 5 bytes (5 líneas por un byte).
La primera línea (correspondiente a la línea 123.12, "Pete" de nuestro plato)
El valor de la cadena es el byte "02" (binario 000000010).
Sepáralo (recuerda la descripción anterior)
- derecha 3 bits (binario 010, en nuestra opinión es 2) - este es un índice en la tabla de símbolos del campo "ID"
- tenemos el campo "ID" contiene NULL, por lo que el índice aumenta en 2, es decir el índice resultante es 0, que corresponde al carácter "123.12".
- los siguientes 5 bits (binario y decimal 0) es el índice en la tabla de símbolos del campo "NOMBRE", no contiene NULL, por lo tanto, este es el índice "Pete" en la tabla de símbolos.
Segunda fila (124.12 / 31/2018) en la tabla de filas
Valor - byte "0B" (binario 00001011)
- derecha 3 bits (binario 011, en nuestra opinión es 3) - este es el índice en la tabla de símbolos del campo "ID"
- tenemos el campo "ID" contiene NULL, por lo que el índice aumenta en 2, es decir el índice resultante es 1, que corresponde al símbolo "124".
- los siguientes 5 bits (binario y decimal 1) es el índice en la tabla de símbolos del campo "NOMBRE", no contiene NULL, por lo que este es el índice "31/12/2018" en la tabla de símbolos.
Bueno y así sucesivamente, echemos un vistazo rápido a la última línea : allí la teníamos, "Ninguna" (es decir, NULL y la cadena "Ninguna"):
El valor es el byte "20" (binario 0010000)
- derecha 3 bits (binario y decimal 0): este es el índice en la tabla de símbolos del campo "ID"
- tenemos el campo "ID" contiene NULL, por lo que el índice aumenta en 2, es decir el índice final es -2, que corresponde al valor NULL.
- los siguientes 5 bits (binario 100, decimal 4) es el índice en la tabla de símbolos del campo "NOMBRE", no contiene NULL, por lo que este es el índice "Ninguno" en la tabla de símbolos.
IMPORTANTE No puedo encontrar un ejemplo que confirme esto, pero encontré archivos que contenían un índice final de -1 para valores NULL. Por lo tanto, en mis programas considero NULL todos los campos cuyo índice final es negativo.
Filas más largas en una tabla de filas
Al final del análisis del formato QVD, me detendré brevemente en matices importantes: las líneas largas en la tabla de filas almacenan campos en el orden de derecha a izquierda, donde el campo con desplazamiento de cero bits será el más a la derecha (como describí anteriormente). PERO el orden de bytes es inverso, es decir el primer byte será el más a la derecha (y contendrá el campo "derecho" - un campo con desplazamiento de cero bits), el último byte será el primero (es decir, contendrá el campo más "izquierdo" - un campo con el máximo desplazamiento de bits).
Se debe dar un ejemplo, pero no sobrecargarse con detalles. Echemos un vistazo a dicha etiqueta (cito un fragmento; para obtener líneas largas en la tabla de filas, debe aumentar el número de valores únicos).
tab2: LOAD * INLINE [ ID, VAL, NAME, PHONE, SINGLE 1, 100001, "Pete1", "1234567890", "single value" 2, 200002, "Pete2", "2234567890", "single value" ... ];
Breve información sobre los campos (exprimir metadatos):
- ID: ancho 8 bits, desplazamiento de bit - 0, sesgo - 0
- VAL: ancho 5 bits, desplazamiento de bits - 8, sesgo - 0
- NOMBRE: ancho 6 bits, desplazamiento de bit - 18, sesgo - 0
- TELÉFONO: ancho 5 bits, desplazamiento de bits - 13, sesgo - 0
- INDIVIDUAL: ancho 0 bits (tiene un valor)
La tabla de filas consta de cadenas con una longitud de 3 bytes, respectivamente, en la fila de la tabla de filas, los datos sobre los campos se descompondrán lógicamente de la siguiente manera:
- primeros 6 bits - campo "NOMBRE"
- 5 bits siguientes - campo "TELÉFONO"
- luego 5 bits - campo "VAL"
- últimos 8 bits - campo ID
La secuencia lógica se convierte en bytes físicos en el orden inverso, es decir.
- el campo "ID" ocupa completamente el primer byte (que en la secuencia lógica es el último)
- el campo "VAL" ocupa los 5 bits inferiores del segundo byte
- el campo "TELÉFONO" ocupa los 3 bits superiores del segundo byte y los 2 bits inferiores del tercer byte
- el campo "NOMBRE" ocupa los 6 bits superiores del tercer byte
Veamos ejemplos, así es como se ve la primera fila de la tabla de filas (resaltada en rosa)
Valores de campo
- ID - binario 00000000, decimal 0
- VAL - binario 00010, decimal 2, restar 2 del sesgo - obtener 0
- TELÉFONO - binario 00010, decimal 2, restar 2 del sesgo - obtener 0
- NOMBRE - binario 000000, decimal 0
Es decir, la primera línea contiene los primeros caracteres de las tablas de caracteres correspondientes.
En general, es conveniente comenzar a analizar desde la primera línea: generalmente contiene ceros como índice (el archivo QVD está construido de tal manera que los valores de la primera línea entran primero en la tabla de caracteres).
Veamos la segunda línea para arreglar
Valores de campo
- ID - binario 00000001, decimal 1
- VAL - binario 00011, decimal 3, restar 2 del sesgo - obtener 1
- TELÉFONO - binario 00011, decimal 3, reste 2 del sesgo - obtenga 1
- NOMBRE - binario 000001, decimal 1
Es decir, la segunda línea contiene los segundos caracteres de las tablas de caracteres correspondientes.
Compartiré un poco de experiencia: cómo técnicamente "leo" QVD.
La primera versión fue escrita en python (la ennobleceré y la pondré en github).
Los principales problemas se aclararon rápidamente:
- las tablas de símbolos solo se pueden leer "en una fila" (es imposible leer el número de símbolo N sin leer todos los caracteres anteriores)
- los archivos reales no caben en la RAM
- de las operaciones más lentas (excepto para trabajar con archivos): operaciones de bits (desempaquetar una fila de una tabla de cadenas)
- el rendimiento disminuye mucho en archivos QVD "anchos" (cuando hay muchas columnas)
Algunos de estos problemas pueden resolverse cambiando el lenguaje (de python a C, por ejemplo). Parte requirió alguna acción adicional.
La implementación actual bastante rápida se ve así: la lógica general se implementa en python, y las operaciones más críticas se llevan a cabo en programas C separados que se ejecutan en paralelo.
En breve
- las tablas de símbolos se escriben en archivos, los índices se crean adicionalmente para campos de texto, por lo tanto, es posible leer el número de símbolo N
- trabajar con QVD y archivos con tablas de símbolos implementadas a través de archivos mapeados en memoria (mucho más rápido)
- primero, en paralelo (con un límite en el número de procesadores), los archivos se crean con tablas de símbolos (e índices)
- luego en paralelo (con una restricción similar) se leen las filas de la tabla de filas y se crean archivos csv (en HDFS)
- el último paso es convertir estos archivos a una tabla ORC (usando las herramientas de Hive)
- en C implementó la creación de archivos con tablas de símbolos y la creación de un archivo CSV para un rango de líneas
No quiero dar cifras de rendimiento: requerirán vinculación al hardware, a nivel cualitativo resulta que se copia el archivo QVD a la tabla ORC a la velocidad de copia de datos a través de la red. O, en otras palabras, tomar datos de QVD es bastante realista (a nivel de hogar).
También implementé la lógica de crear archivos QVD: funciona bastante rápido en Python (aparentemente, aún no he alcanzado grandes volúmenes, no hay necesidad. Llegaré allí, lo reescribiré de la misma manera que la versión de "lectura").
Planes futuros
¿Qué sigue?
- Planeo diseñar la versión de Python del código en github (esta versión le permitirá "explorar" el archivo QVD - ver metadatos, leer y escribir caracteres, cadenas. La versión es lo más simple y obviamente más lenta posible - sin archivos para tablas de caracteres, con lectura secuencial, utilizando bibliotecas estándar para trabajar con bits, etc.)
- Pienso en hacer algo para los pandas (como read_qvd ()), restringe que será lento en Python, así como el hecho de que obviamente no todos los QVD "encajarán" en la memoria, por lo tanto
- Pienso en hacer que el archivo QVD sea una fuente de datos para Spark: no debería haber este problema con "no entrar en la memoria" (y el lenguaje allí, scala, está más cerca del hardware)
En lugar de un epílogo
Durante mucho tiempo estuve dando vueltas y más vueltas a los archivos QVD, parecía que "todo es complicado allí". Resultó que era difícil, pero no muy bueno, un buen ímpetu fue Github, que mencioné en la primera parte (una especie de catalizador). Entonces fue una cuestión de tecnología. Yo y todos notamos (una confirmación más): todo se puede hacer en la programación, la pregunta es tiempo y motivación.
Espero no estar muy cansado de los detalles, estoy listo para responder preguntas (en los comentarios o de cualquier otra manera). Si habrá una continuación, definitivamente escribiré.