Сжатие
Для сжатия данных используются алгоритмы сжатия, ориентированные на хранение данных по столбцам. Показано [4], что выполнение операций над данными в сжатом формате позволяет на порядок повысить производительность обработки запросов. Интуитивно понятно, что данные, хранимые в столбцах, сжимаются лучше, чем данные, хранимые в строках. Алгоритмы сжатия лучше работают над данными с низкой энтропией информации (высоким уровнем локальности значений данных). Возьмем для примера таблицу базы данных, содержащую информацию о заказчиках (имя, номер телефона, адрес электронной почты, почтовый адрес и т.д.). При хранении данных по столбцам вместе хранятся все имена, все номера телефонов и т.д. Конечно, номера телефонов больше похожи один на другой, чем адреса электронной почты или имена. Кроме того, если данные отсортированы по значениям одного из столбцов, то этот столбец будет суперсжимаемым (например, последовательность одинаковых значений может кодироваться длиной этой серии).
Но, конечно, приведенное наблюдение непосредственно влияет только на степень сжатия. Дисковая память является дешевой и быстро еще более дешевеет (хотя сокращение числа требуемых дисков снижает уровень энергопотребления, фактор стоимости, становящийся все более важным). Однако сжатие способствует повышению производительности (в дополнение к снижению уровня требований к дисковой памяти), поскольку при наличии сжатых данных меньше времени занимают операции ввода-вывода при чтении данных с диска в основную память (или записи из основной памяти на диск). Следовательно, «тяжеловесные» схемы сжатия, оптимизирующие степень сжатия, такие как алгоритмы Лемпеля-Зива (Lempel-Ziv), Хаффмана (Huffman) или арифметического кодирования, могут оказаться менее пригодными, чем «легковесные» схемы, жертвующие степенью сжатия в пользу эффективности распаковки [4, 26]. На самом деле, сжатие может повысить производительность обработки запросов, даже если не принимать во внимание экономию ввода-вывода.
Если компонент выполнения запросов в колоночном хранилище сможет выполнять операции прямо над сжатыми данными, то распаковка вообще не потребуется, а производительность еще более повысится. Например, для схем продольного кодирования (run-length encoding) – где последовательность повторяющихся значений заменяется счетчиком числа значений и самим значением (например, 1; 1; 1; 2; 2 → 1?3; 2?2) – выполнение операций прямо над сжатыми данными дает возможность компоненту обработки запросов выполнять операцию над несколькими одинаковыми значениями столбца только один раз, что позволяет сократить расходы центрального процессора.
В предыдущей работе [4] авторы пришли к выводу, что наибольшее различие между сжатием в строчных и колоночных хранилищах проявляется в тех случаях, когда столбец отсортирован (или вторично отсортирован), и в нем содержатся группы повторяющихся значений. В колоночном хранилище исключительно легко работать с этими группами как с единым целым. В строчном хранилище этот процесс существенно усложняется наличием данных других атрибутов. Таким образом, вообще говоря, сжатие оказывает тем большее воздействие на производительность, чем у большего числа столбцов, упоминаемых в запросе, имеется некоторый порядок сортировки. В базе данных SSBM, используемой в описываемом исследовании, авторы не сохраняли несколько копий таблицы фактов в разных порядках сортировки, и поэтому можно было отсортировать только один из семнадцати столбцов этой таблицы (и еще два – отсортировать вторично). Поэтому сжатие в этом случае в меньшей степени (и в большей зависимости от вида запроса) воздействовало на производительность, чем могло бы быть при более активном использовании избыточности.
