За счёт чего словарное кодирование уменьшает объём повторяющихся значений в колоночном хранилище?
Словарное кодирование заменяет повторяющиеся значения короткими числовыми кодами, а сами значения хранит один раз в отдельном словаре. Вместо многократного хранения длинных строк или других значений система хранит компактные ссылки на элементы словаря, поэтому объём данных и стоимость чтения обычно снижаются.
Аналитические системы часто читают один или несколько столбцов из большого набора данных. В таких столбцах значения нередко повторяются: статус заказа, регион, категория товара или идентификатор небольшого справочника.
Хранение каждого значения полностью приводит к избыточности. Словарное кодирование появилось как общий способ использовать повторяемость данных и особенно эффективно сочетается с колоночным хранением, где значения одного типа и одного столбца находятся рядом.
Предположим, столбец содержит миллионы строк, но всего несколько сотен различных значений. Если хранить каждую строку целиком, одинаковые значения многократно занимают место, увеличивают объём чтения с диска и нагрузку на пропускную способность хранилища.
Однако словарное кодирование не всегда выгодно. При почти уникальных значениях словарь становится большим, коды перестают быть существенно короче исходных данных, а дополнительное обращение к словарю может усложнить обработку.
Система строит словарь различных значений столбца. Например, значения Москва, Казань и Москва могут быть представлены словарём из двух элементов и последовательностью кодов 0, 1, 0. В основной области хранения остаются компактные коды, а исходные значения записываются один раз.
Размер кода можно выбирать с учётом количества уникальных значений. Если в сегменте не более 256 различных значений, достаточно однобайтового кода; при большем количестве уникальных значений потребуется более широкий код. Точная реализация зависит от системы и обычно работает на сегментах, блоках или других локальных фрагментах данных, а не обязательно на всей таблице.
Преимущество особенно заметно при низкой кардинальности, то есть небольшом числе различных значений относительно числа строк. Коды лучше помещаются в кэш, быстрее передаются между уровнями хранения и могут дополнительно хорошо сжиматься методами битовой упаковки или кодированием повторяющихся последовательностей.
При фильтрации система может сравнивать значение с элементами словаря и работать с кодами. Но для некоторых операций, например сортировки или вывода результата, может потребоваться обратное преобразование кодов в исходные значения. Если значения длинные или сложные, это преобразование тоже имеет стоимость.
Для столбцов с высокой кардинальностью словарное кодирование может дать небольшой выигрыш или даже стать невыгодным. Поэтому практические системы выбирают кодирование адаптивно: для одного сегмента применяют словарь, для другого используют более подходящее представление, например прямое хранение или специализированное сжатие.
Главный компромисс состоит в обмене места на дополнительную структуру и этап декодирования. Выигрыш зависит от длины исходных значений, количества уникальных значений, размера сегмента и характера запросов; само наличие словаря не гарантирует одинакового ускорения всех операций.
В витрине заказов столбец со статусом содержит 500 миллионов строк и только шесть возможных значений. Рассматривались три варианта: хранить строки напрямую, использовать словарь на всей таблице или строить локальные словари для отдельных сегментов.
Прямое хранение проще, но создаёт значительный объём повторяющихся данных. Один глобальный словарь экономит место, однако его обслуживание и декодирование могут стать менее удобными при перестройке больших объёмов. Локальные словари требуют дополнительной метаинформации, зато лучше адаптируются к составу данных каждого сегмента.
Выбрали локальное словарное кодирование с автоматическим отказом от него для сегментов с высокой кардинальностью. Это уменьшило объём хранения повторяющихся статусов и сохранило приемлемую скорость фильтрации, не заставляя редкие высококардинальные столбцы использовать неэффективное представление.
1. Всегда ли словарь должен строиться для всей таблицы?
Нет. Локальный словарь для блока или сегмента часто эффективнее глобального, потому что в отдельной части данных может встречаться меньше уникальных значений. Кроме того, локальная структура ограничивает объём словаря и позволяет независимо кодировать разные фрагменты.
Обратная сторона — один и тот же исходный текст может иметь разные коды в разных сегментах. Поэтому код нельзя интерпретировать без контекста соответствующего словаря, а операции, охватывающие много сегментов, должны учитывать их локальные таблицы соответствий.
2. Почему низкая кардинальность важнее просто большого количества строк?
Экономия определяется не числом строк сама по себе, а отношением числа уникальных значений к числу записей и размером исходных значений. Миллиард строк с десятью статусами хорошо подходит для словаря, а миллион почти уникальных идентификаторов — значительно хуже.
При высокой кардинальности словарь приближается по размеру к исходным данным, а коды требуют больше битов. В таком случае дополнительные затраты на словарь и декодирование могут не компенсироваться сокращением объёма.
3. Ускоряет ли словарное кодирование любой запрос к столбцу?
Нет. Оно прежде всего уменьшает объём хранения и чтения, а также может улучшить работу с кэшем. Фильтр по равенству иногда выполняется эффективно на кодах, но сортировки, группировки по сложным выражениям и возврат исходных значений могут потребовать декодирования.
Реальный эффект зависит от формата данных, размера сегментов, используемых дополнительных методов сжатия и плана выполнения запроса. Поэтому словарное кодирование следует оценивать по типичным запросам и фактической кардинальности, а не считать универсальным ускорителем.