QVD-файлы — что внутри, часть 3

Автор: admin от 24-06-2019, 15:35, посмотрело: 30

В первой статье о структуре QVD-файла я описал общую структуру и достаточно подробно остановился на метаданных, во второй — на хранении колонок (символов). В этой статье я опишу формат хранения информации о строках, подытожу, расскажу о планах и достижениях.



Итак (вспоминаем) QVD-файл соответствует реляционной таблице, в QVD файле таблица хранится в виде двух косвенно связанных частей:



Таблицы символов (термин мой) содержат уникальные значения каждой колонки исходной таблицы. О них я рассказывал во второй статье.



Таблица строк содержит строки исходной таблицы, каждая строка хранит индексы значений колонки (поля) строки в соответствующей таблице символов. Именно об этои и будет эта статья.



На примере нашей таблички (помните — из первой части)



SET NULLINTERPRET =<sym>;
tab1:
LOAD * INLINE [
    ID, NAME
    123.12,"Pete"
    124,12/31/2018
    -2,"Vasya"   
    1,"John"
    <sym>,"None"
];

В таблице строк нашего QVD файла этой табличке будет соответствовать 5 строк — всегда точное соответствие: сколько строк в таблице, столько строк в таблице строк QVD файла.


Строка в таблице строк состоит из целых неотрицательных чисел, каждое из этих чисел — индекс в соответствующую таблицу символов. На логическом уровне все просто, осталось уточнить нюансы и привести пример (разобрать — как представлена в QVD наша табличка).


Формат таблицы строк


Таблица строк состоит из K * N байт, где



  • K — количество строк исходной таблицы (значение тэга "NoOfRecords" метаданных)

  • N — байтовая длина строки таблицы симовлов (значение тэга "RecordByteSize" метаданных)


Таблица строк начинается со смещения "Offset" (тэг метаданных) относительно начала бинарной части файла.


Информация о таблице строк (длина, размер строки, смещение) хранится в общей части метаданных.


Формат строки таблицы строк


Все строки таблицы строк имеют одинаковый формат и представляют из себя конкатенацию "чисел без знака". Длина числа — минимально достаточна для представления конкретного поля: длина зависит от количества уникальных значений конкретного поля.


Для полей с одним значением (как я уже писал) эта длина будет равна нулю (это значение одинаково в каждой строке исходной таблицы и хранится в соответствующей таблице символов).


Для полей с двумя значениями эта длина будет равна единице (возможные значения индекса в таблице символов — 0 и 1), и так далее.


Поскольку совокупная длина строки таблицы строк должна быть кратна байту, длина "последнего символа" выравнивается до границы байта (увидим ниже, когда будем разбирать нашу табличку).


Информация о формате каждого поля хранится в разделе метаданных, посвященных этому полю (остановимся чуть подробнее ниже), длина битового представления поля хранится в тэге "BitWidth".


Хранение значений NULL


Как хранить отсутствующие значения? Воздерживаясь от рассуждений на тему "почему", отвечу так: насколько я понял, NULL значениям соответствует следующая комбинация



  • тэг "Bias" соответствующего поля принимает значение "-2" (всего же мне попалось два возможных значения этого тэга — "0" и "-2")

  • индекс поля для той строки, где это поле есть NULL, равен 0


Соответственно, все остальные индексы в колонке, имеющей NULL значения, увеличены на 2 — увидим на нашем примере чуть ниже.


Порядок следования полей в строке


Порядок следования полей в строке таблицы строк соответствует битовому смещению поля, которое хранится в тэге "BitOffset" раздела метаданных, относящихся к данному полю.


Разберем наш пример (см. метаданные в части первой этой серии).


Поле "ID"



  • битовое смещение 0 — поле будет "самым правым"

  • битовая длина 3 — поле будет занимать в строке таблицы строк 3 бита

  • Bias равен "-2" — поле имеет NULL значения, все индексы увеличены на 2


Поле "NAME"



  • битовое смещение 3 — поле расположено "левее" поля ID на 3 бита

  • битовая длина 5 — поле будет занимать в строке таблицы строк 5 бит (выровнено до границы байта)

  • Bias равен "0" — поле не имеет NULL значений, все индексы "честные"


Представление нашей таблички


Давайте посмотрим на реальные "нолики и единички" — я буду приводить фрагменты QVD файла в виде двоичного представления "в шестнадцатеричном формате" (так компактнее).


Сначала вся бинарная часть целиком (выделена розовым, метаданные обрезаны — уж больно их много...)


[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_1.png[/img]


Достаточно компактно, согласитесь. Давайте вглядимся повнимательнее — сразу после метаданных расположены таблицы символов (метаданные, кстати, в данном файле окончились переводом строки и нулевым байтом — технически такое бывает, нулевые байты после метаданных нужно пропускать...).


Первая таблица символов выделена на рисунке ниже.


[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_2.png[/img]


Видим:


Первое уникальное значение поля "ID" это



  • тип "6" (первый выделенный байт) — плавающее число со строкой (см. вторую статью)

  • после первого байта 8 следующих байт — это бинарно предствавленное "плавающее" число

  • после них идет строковое представление — очень удобно (не надо вспоминать — какое же было число), заканчивающееся нулевым байтом


Остальные три уникальных значения имеют тип 5 (целое число со строкой) — значения "124", "-2" и "1" (легко видеть по строкам).


На рисунке ниже выделил вторую таблицу символов (для поля "NAME")


[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_3.png[/img]


Первое уникальное значение поля "NAME" — тип "4" (первый выделенный байт) — строка, заканчивающаяся нулем.


Остальные четыре уникальных значения — также строки "12/31/2018", "Vaysa", "John" и "None".


Теперь — таблица строк (выделил на рисунке ниже)


[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_4.png[/img]


Как и ожидалось — 5 байт (5 строк по одному байту).


Первая строка (соответствующая строке 123.12, "Pete" нашей таблички)


Значение строки — байт "02" (бинарно 000000010).


Разделим его (вспоминаем описание выше)



  • правые 3 бита (двоичные 010, по-нашему это 2) — это индекс в таблицу символов поля "ID"

  • у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен 0, что соответствует символу "123.12".

  • следующие 5 бит (двоичный и десятичный 0) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "Pete" в таблице символов.


Вторая строка (124,12/31/2018) в таблице строк


Значение — байт "0B" (бинарно 00001011)



  • правые 3 бита (двоичные 011, по-нашему это 3) — это индекс в таблицу символов поля "ID"

  • у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен 1, что соответствует символу "124".

  • следующие 5 бит (двоичная и десятичная 1) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "12/31/2018" в таблице символов.


Ну и так далее, давайте посмотрим быстренько на последнюю строку — там у нас было ,"None" (т.е. NULL и строка "None"):

Значение — байт "20" (бинарно 0010000)



  • правые 3 бита (двоичный и десятичный 0) — это индекс в таблицу символов поля "ID"

  • у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен -2, что и соответствует значению NULL.

  • следующие 5 бит (двоичные 100, десятичная 4) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "None" в таблице символов.


ВАЖНО не могу найти пример, подтверждающий это, но мне попадались файлы, которые содержали итоговый индекс -1 для NULL значений. Поэтому в своих программах я считаю NULL-ами все поля, итоговый индекс которых отрицателен.


Более длинные строки в таблице строк


В завершение разбора формата QVD кратко остановлюсь на важных нюансах — длинные строки в таблице строк хранят поля в порядке "справа — налево", где самым правым будет поле с нулевым битовым смещением (как я и описывал выше). НО порядок байтов — обратный, т.е. первый байт будет самым правым (и будет содержать "правое" поле — поле с нулевым битовым смещением), последний — первым (т.е. содержать самое "левое" поле — поле с максимальным битовым смещением).


Нужно привести пример, но не перегрузить деталями. Давайте рассмотрим такую табличку (привожу фрагмент — чтобы получить длинные строки в таблице строк необходимо увеличить количество уникальных значений).


tab2:
LOAD * INLINE [
    ID, VAL, NAME, PHONE, SINGLE
    1, 100001, "Pete1", "1234567890", "single value"
    2, 200002, "Pete2", "2234567890", "single value"
...
];


В кратком виде информация о полях (выжимка из метаданных):




  • ID: ширина 8 бит, битовое смещение — 0, bias — 0

  • VAL: ширина 5 бит, битовое смещение — 8, bias — 0

  • NAME: ширина 6 бит, битовое смещение — 18, bias — 0

  • PHONE: ширина 5 бит, битовое смещение — 13, bias — 0

  • SINGLE: ширина 0 бит (имеет одно значение)



Таблица строк состоит из строк длиной 3 байта, соответственно, в строке таблицы строк данные о полях логически разложатся так:




  • первые 6 бит — поле "NAME"

  • следующие 5 бит — поле "PHONE"

  • далее 5 бит — поле "VAL"

  • последние 8 бит — поле "ID"



Логическая последовательность преобразуется в физическую перестановкой байт в обратном порядке, т.е.




  • поле "ID" полностью занимает первый байт (который в логической последовательности — последний)

  • поле "VAL" занимает младшие 5 бит второго байта

  • поле "PHONE" занимает старшие 3 бита второго байта и младшие 2 бита третьего байта

  • поле "NAME" занимает старшие 6 бит третьего байта



Посмотрим на примерах, вот как выглядит первая строка таблицы строк (выделена розовым)



[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_5.png[/img]



Значения полей




  • ID — бинарно 00000000, десятичный 0

  • VAL — бинарно 00010, десятичная 2, вычитаем 2 за счет bias — получаем 0

  • PHONE — бинарно 00010, десятичная 2, вычитаем 2 за счет bias — получаем 0

  • NAME — бинарно 000000, десятичный 0



Т.е первая строка содержит первые символы из соотвествующих таблиц символов.



Вообще удобно начинать разбор именно с первой строки — она, как правило, содержит нули в качестве индекса (так уж строится QVD файл, что в таблицу символов первыми попадают значения из первой строки).



Давайте для закрепления посмотрим еще на вторую строку



[img]http://mybizcloud.ru/wiki/lib/exe/fetch.php?cache=&media=datalake:qvd_bin_7.png[/img]



Значения полей




  • ID — бинарно 00000001, десятичная 1

  • VAL — бинарно 00011, десятичная 3, вычитаем 2 за счет bias — получаем 1

  • PHONE — бинарно 00011, десятичная 3, вычитаем 2 за счет bias — получаем 1

  • NAME — бинарно 000001, десятичная 1



Т.е вторая строка содержит вторые символы из соотвествующих таблиц символов.



Эффективный разбор формата



Немного поделюсь опытом — как я технически "читал" QVD.



Первая версия была написана на питоне (я ее облагорожу и выложу в github).



Достаточно быстро выяснились основные проблемы:




  • таблицы символов можно читать только "подряд" (невозможно считать символ номер N, не прочитав всех предыдущих символов)

  • реальные файлы "не влезают" в оперативную память

  • из наиболее медленных операций (кроме работы с файлами) — битовые операции (распаковка строки таблицы строк)

  • производительность сильно "проседает" на "широких" QVD файлах (когда много колонок)



Часть из этих проблем может быть решена сменой языка (с питона на Си, например). Часть потребовала каких-то дополнительных действий.



Текущая достаточно быстрая реализация выглядит так — общая логика реализована на питоне, а наиболее критичные операции вынесены в отдельные Си программы, запускаемые параллельно.



Коротко




  • таблицы символов пишутся в файлы, для текстовых полей дополнительно создаются индексы, тем самым есть возможность считать символ номер N

  • работа с QVD и файлами с таблицами символов реализована через memory mapped files (так быстрее)

  • сначала параллельно (с ограничением по количеству процессоров) создаются файлы с таблицами символами (и индексами)

  • далее параллельно (с аналогичным ограничением) читаются строки таблицы строк и создаются csv файлы (в HDFS)

  • последним шагом эти файлы преобразуются в ORC таблицу (средствами Hive)

  • на Си реализовано создание файлов с таблицами символов и создание CSV файла для диапазона строк



По производительности цифр давать не хочу — они потребуют привязки к железу, на качественном уровне получается скопировать QVD файл в ORC таблицу примерно со скоростью копирования данных по сети. Или, другими словами, взять данные из QVD вполне реально (на бытовом уровне).



Я также реализовал логику создания QVD файлов — она достаточно быстро работает на питоне (видимо, я еще не дошел до больших объемов — нет потребности. Дойду — перепишу аналогично "читающему" варианту).



Планы на будущее



Что дальше:




  • планирую выложить Питон версию кода в github (эта версия позволит "исследовать" QVD файл — смотреть метаданные, читать и писать символы, строки. Версия максимально простая и заведомо медленная — без файлов для таблиц символов, с последовательным чтением, использованием стандартных библиотек для работы с битами и т.п.)

  • думаю о том, чтобы сделать что-то для pandas (типа read_qvd()), сдерживает то, что на питоне это будет медленно, а также то, что заведомо не всякий QVD "влезет" в память, поэтому

  • думаю о том, чтобы сделать QVD файл источником данных для Spark-а — там этой проблемы с "не влезанием" в память быть не должно (да и язык там — scala — более приближен к железу)



Вместо послесловия



Давно я ходил вокруг да около QVD файлов, казалось, что "там все сложно". Оказалось, что сложно, но не очень, хорошим толчком послужил github, который я упомянул в первой части (своего рода катализатор). Дальше уже было дело техники. Себе и всем на заметку (еще одно подтверждение) — в программировании все можно сделать, вопрос во времени и мотивации.



Надеюсь, не очень утомил подробностями, готов ответить на вопросы (в комментариях или любым другим способом). Если будет продолжение — обязательно напишу.



Источник: Хабр / Интересные публикации

Теги: qvd qlikview

Категория: iOS

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *