М.А. Смирнов
Обзор применения методов безущербного сжатия данных в СУБД
Часть 4
Содержание | Часть 1 | Часть 2 | Часть 3 | Часть 4

2. Использование сжатия данных в современных СУБД

Сжатие данных поддерживается практически во всех современных СУБД. Ниже дан обзор приемов экономного кодирования, применяемых в конкретных системах. Описания упорядочены в соответствии с алфавитным порядком наименований СУБД¹³.

ADABAS

СУБД ADABAS немецкой фирмы Software AG является системой уровня предприятия, предназначенной для использования в сложных приложениях с большим количеством активно работающих пользователей и жесткими требованиями к производительности и надежности.

Система ADABAS поддерживает сжатие таблиц базы данных [52]. В версии 6.2 реализованы два способа сжатия, работающих на уровне значений атрибутов:

1. сжатие по умолчанию, соответствующее использованию полей переменной длины, при котором из строковых значений устраняются завершающие пробелы, а из числовых значений удаляются ведущие нули;
2. сжатие отсутствующих значений; в этом случае в дополнение к использованию полей переменной длины экономно представляются последовательности отсутствующих значений, принадлежащих одной записи; таким образом может быть одновременно закодировано до 63 отсутствующих значений атрибутов, примыкающих друг к другу.

В [52] указывается, что встроенные методы сжатия позволяют сократить размер базы примерно в 2 раза относительно формы представления с полями фиксированной длины.

В версии 7.1.2 СУБД последовательности отсутствующих значений в конце строк полностью отсекаются и физически не сохраняются [31]. В этой версии используется и сжатие индексов, при котором устраняется повторение начальной части индексных значений, располагаемых друг за другом в индексной структуре.

DB2

Системы управления данными фирмы IBM традиционно содержат механизмы экономного кодирования информации. СУБД DB2 поддерживает сжатие данных как на программном уровне, так и на аппаратном [10, 32].

В версиях DB2 ниже 3-ей таблицы могли быть сжаты с помощью специальных процедур, ассоциируемых с таблицей при ее создании. В частности, предоставлялся исходный код типовой реализации алгоритма Хаффмана. Пользователи могли модифицировать алгоритм или создавать свои процедуры, реализующие иные алгоритмы. Ряд независимых производителей предлагал набор такого рода модулей.

Начиная с версии 3 DB2 поддерживает словарный метод сжатия, реализованный в аппаратной платформе S/390. В последнем случае кодирование-декодирование выполняется специальным процессорным модулем мейнфрейм-платформы S/390. Если процессорный модуль сжатия не доступен, то используется программная реализация. Алгоритм сжатия основан на одном из вариантов LZW, известном как метод Миллера-Уэгнама (Miller-Wegnam), или LZMW [32, 1]. В отличие от LZW, в методе Миллера-Уэгнама каждая фраза словаря представляет собой конкатенацию двух других фраз, а не фразы и символа алфавита данных. В DB2 сжатие выполняется на уровне строки и является полуадаптивным. Словарь строится при загрузке данных. В случае необходимости можно собрать статистику и реорганизовать словарь.

Сжатию может подвергаться как таблица, так и ее отдельные разделы. Соответственно, каждая сжатая таблица или раздел таблицы имеют свой словарь, размещаемый в заголовке объекта как метаинформация. Не все записи могут подвергаться кодированию. Если определяется, что для некоторой записи процедура сжатия не дает положительного эффекта, то запись помечается соответствующим флагом и сохраняется в исходном виде. Также записи могут не кодироваться, если это приводит к получению более 255 строк на страницу, что обусловлено ограничениями внутреннего устройства СУБД.

Словарь может включать в себя 512, 1024, 2048 и 4096 фраз. Объем словаря в байтах равен размеру во фразах, умноженному на 16.

В [32] отмечается, что выбор способа сжатия был обусловлен следующими аргументами:

• большинство колонок имеет небольшую длину, поэтому сжатие на уровне значений атрибутов неэффективно в первую очередь за счет необходимости указывать длину каждого закодированного значения; в результате в качестве сжимаемого блока выбрана строка;
• адаптивное сжатие строк без предварительных знаний не дает существенной экономии и проигрывает статическому, поскольку часто строки имеют длину в несколько десятков или несколько сотен байт и содержат неоднородную информацию;
• словарная схема типа LZW обеспечивает значительно более быстрое декодирование, чем арифметическое сжатие и кодирование по Хаффману с различными статистическими моделями, при одинаковой или большей степени сжатия типовых табличных данных.

Построение словаря и сжатие может выполняться двумя способами с помощью двух различных утилит, LOAD и REORG. Утилита LOAD обеспечивает загрузку данных в таблицу. При этом записи, использованные для построения словаря, не сжимаются. Сжатие строк выполняется только после заполнения словаря. Это может заметно ухудшать сжатие для небольших таблиц. REORG обеспечивает экономное кодирование всех строк. В REORG выполняется построение словаря на основании выборки строк из всего массива данных сжимаемого объекта. При формировании выборки предпочтение отдается первым по порядку записям: чем дальше расположены записи от начала таблицы (раздела), тем с большим шагом они выбираются. Для улучшения сжатия сначала строится словарь размером вплоть до 2¹⁴ = 16384 фраз, что позволяет накопить более полную статистику, а затем уменьшается до допустимого объема удалением редко используемых элементов.

Утилита REORG используется и для перестройки словаря в случае необходимости. Например, после существенного изменения содержимого таблицы.

В буферном пуле страницы сохраняются сжатыми. Декодируются только выбираемые по запросу записи. При вставке и обновлении записей они сжимаются и записываются в буферный пул. Это позволяет уменьшить расход памяти под буферный пул и/или увеличить процент успешных попаданий в него.

Записи журнала (регистрационного файла СУБД), соответствующие сжатым строкам, также содержат данные в закодированном виде.

Следует отметить, что в DB2 версий 3-5 нет возможности сжимать индексы.

В [10] и [32] приводятся следующие результаты сравнения характеристик системы в зависимости от использования сжатия:

• процент сэкономленного пространства при сжатии с помощью утилиты LOAD равен 41% и 56% для данных с умеренной и высокой избыточностью соответственно, что эквивалентно степени сжатия в 2 и 2.3 раза;
• загрузка данных в таблицы посредством LOAD выполняется на 30% медленнее;
• сканирование таблиц выполняется в целом примерно в 2 раза быстрее, но при этом нагрузка на процессоры возрастает также двое (было задействовано программное кодирование-декодирование); показатели для случайного доступа практически не отличаются от соответствующих показателей для последовательного доступа;
• быстрота создания резервных копий и восстановления после сбоев также увеличилась в 2 раза.

Ingres

Система Ingres фирмы Computer Associates представляет собой промышленную СУБД, ориентированную на приложения уровня предприятия.

Следует отметить, что существуют две разновидности Ingres: свободно распространяемая “академическая” Ingres и коммерческая, разрабатываемая и продаваемая Computer Associates. “Академическая” Ingres (INteractive Graphics REtrieval System — интерактивная система доставки графических данных) является исходной версией системы, разработанной в Университете Беркли в 1970-х годах для демонстрации возможностей РСУБД. Поэтому есть серьезные основания считать Ingres первой реализацией РСУБД, ведь она была создана раньше канонического комплекса System R фирмы IBM. Коммерческая Ingres создавалась на основе “академической”, но в настоящее время это программы с принципиально разными характеристиками. Вся последующая информация касается исключительно коммерческой Ingres фирмы Computer Associates.

Текущие версии Ingres выпускаются под маркой Advantage Ingres. Предыдущими марками являлись наименования OpenIngres и Ingress II.

Источники, использованные при подготовке данного обзора, противоречивы относительно методов сжатия, применяемых в Ingres.

Из руководства администратору для версии 2.6 системы следует, что структуры, в которых размещаются данные, могут сжиматься за счет использования строк переменной длины при хранении текстовых полей и экономного кодирования отсутствующих значений (NULL) атрибутов любого типа [19]. При этом представляются в сжатом виде как собственно данные, так и индексная информация. В зависимости от типа структуры данных, может не поддерживаться сжатие первичных ключей и индексов. Таким образом, способы сжатия являются тривиальными.

В неформальном тексте “Ответы на часто задаваемые вопросы по Ingres” [30] указывается, что в версиях СУБД OpenIngres 1.x использовался метод сжатия LZW. Автор текста [30] не имеет непосредственного отношения к фирме Computer Associates, поэтому данную информацию нельзя считать заслуживающей доверия. Возможно, что метод LZW действительно применялся в ранних версиях, но не используется в современной Advantage Ingres.

Microsoft Access

Системообразующим компонентом “настольной” СУБД Microsoft Access является программа Microsoft Jet, обеспечивающая чтение и сохранение информации в базах данных. Начиная с версии 3 Microsoft Jet обеспечивается сжатие ключей в индексах [18]. Исходя из имеющейся информации тип метода сжатия не представляется возможным определить. В источнике лишь указывается, что в результате экономного кодирования устраняется дублирование значений ключей.

MySQL

MySQL относится к группе простых систем управления данными. Но в последние годы система получила большую популярность. Значительную роль в этом сыграли статус программы с открытым исходным кодом и простые интерфейсы взаимодействия с программами на языках программирования PHP, C, C++, Java и ряду других, что позволило без больших затрат встраивать MySQL в прикладные системы. Отсутствие в MySQL большого количества системных и вспомогательных функций, характерных для промышленных РСУБД, компенсируется высокой скоростью выполнения запросов на чтение. MySQL распространяется разработчиком, фирмой MySQL AB, под двумя лицензиями: "общедоступной" лицензии для открытого ПО General Public License (GPL) или альтернативной коммерческой лицензией. Базовая лицензия GPL диктует, в частности, необходимость распространения с исходным кодом как MySQL, так и непосредственно использующих ее программ.

В версии 4.0.18 использование сжатия данных представлено в следующих аспектах [41].

1. Во-первых, имеется возможность создавать сжатые таблицы только для чтения. При этом создаются таблицы с индексно-последовательным методом доступа (ISAM), поэтому при использовании индексирования соответствующие структуры тоже содержат сжатые данные. Создание таких таблиц выполняется посредством утилиты Myisampack. Сжатие выполняется на уровне значения атрибута. Утилита позволяет экономно закодировать таблицу с помощью:

• упаковки битов;
• устранения колонок-констант, в том числе состоящих из неопределенных (NULL) значений;
• устранения ведущих и оконечных пробелов;
• устранения ведущих нулей;
• словаря значений атрибута;
• кодирования по Хаффману.

Методы могут применяться совместно, в том числе допускается каскадное использование. Таблицы кодов Хаффмана могут использоваться для декодирования сразу нескольких колонок. При сжатии таблицы генерируется статистика, которая используется оптимизатором запросов. Сжатая таблица может быть преобразована в обычную.

1. Во-вторых, экономно представляются индексные структуры типа B-дерева. Одинаковые префиксы значений и оконечные пробелы в B-дереве устраняются. Для улучшения сжатия ключи числовых форматов могут записываться старшими байтами вперед.

Кроме того, в версии 4.1.1 поддерживается кодирование-декодирование значения столбца с помощью функций Compress/Uncompress:

SELECT Uncompress(Compress("any string")); à "any string"

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

Oracle

РСУБД Oracle одноименной фирмы является наиболее распространенной промышленной системой управления данными. В настоящее время последней версией комплекса является Oracle9i Release 2.

В СУБД Oracle реализовано как сжатие таблиц, так и сжатие индексов. Но если экономное представление индексов использовалось еще в Oracle версий 7 и 8 [13], то полноценное сжатие таблиц поддерживается только в самой последней версии [45].

В Oracle версий 7 и 8 существовал особый вид структуры хранения данных под названием “индексная таблица” (index-organized table). Данные такой таблицы сохранялись совместно с индексной информацией (атрибуты первичного ключа такой таблицы описывались только в индексной структуре) [44]. При этом поддерживалось частичное сжатие значений составного первичного ключа в индексе. Значение составного ключа разделялось на две части: группирующая (префикс), общая для нескольких значений, и уникальная (суффикс). Префикс подвергался экономному кодированию. Возможно, при этом используется словарный алгоритм с сохранением упорядоченности, описанный одним из сотрудников корпорации Oracle в [6].

Табличное сжатие в Oracle9i Release 2 в первую очередь предназначено к использованию в системах поддержки принятия решений и OLAP-приложениях¹⁴. Сжатию могут быть подвергнуты целые таблицы, разделы таблиц и материализованные представления. Сжатие уменьшает используемый объем дискового пространства, снижает требования к размеру буфера данных и во многих случаях ускоряет обработку запросов, особенно для систем с медленным вводом-выводом информации.

Для сжатия таблиц используется метод словарного типа [45]. Сжимается или целиком столбец, или набор столбцов. Словарь формируется из значений атрибутов. Решение о добавлении значения столбца в словарь принимается на основании длины столбца и числа повторов значения. Короткие, а также редко встречающиеся значения в словарь не вносятся. Сжатие производится путем замены значения столбца на указатель на соответствующую фразу словаря. Размер словаря выбирается автоматически для каждой страницы во время загрузки данных. При этом таблица фраз и другая необходимая для декодирования информация сохраняется в каждой странице.

Для повышения степени сжатия может производиться переупорядочивание столбцов внутри одной страницы. Данное преобразование полностью скрыто от внешней среды. При значительных изменениях в данных словарь адаптируется.

В [45] утверждается, что внедрение алгоритма сжатия потребовало изменения только тех модулей, которые связаны с формированием блока и доступом к строкам и столбцам. Нет никакой разницы в функциональности, обеспечиваемой сжатыми и несжатыми таблицами.

Достигаемая степень сжатия и изменение скорости выполнения запросов зависят от характера данных и вида обращений к БД. В [45] приведены результаты тестирования для двух схем: типовое хранилище данных, организованное по схеме “звезда” и имеющее 1 таблицу фактов и 5 таблиц с измерениями, и стандартная схема из тестов TPC-H/TPC-R, ориентированных на оценку СППР. Последняя схема содержит 8 таблиц и является нормализованной, хотя ее структура не относится к типу “звезда”. Отмечаются следующие результаты:

• для первой схемы уменьшение размера базы составило 3.1 раза, при этом скорость выполнения типовых сложных запросов увеличилась на 13%;
• для второй схемы степень сжатия составила 1.4 раза, а общее повышение производительности равнялось 10%.

Первоначальный размер первой базы составлял 55 Гбайт, второй — 115 Гбайт. Для первого примера сжималась только таблица фактов и материализованные представления, поскольку размер таблиц с измерениями обычно мал для схем типа “звезда”. Для второго примера сжимались две самые большие таблицы. Подобно таблице фактов в первой схеме, эти таблицы содержали числовые данные. Разница в сжатии обусловлена в первую очередь большей мощностью множеств значений, принимаемых атрибутами таблиц во втором примере. Кроме того, распределения значений колонок для второй схемы более равномерны, что ухудшает сжатие.

Битовые индексы представляются в базах Oracle в экономном виде. В [13] указывается, что в Oracle версии 8 используется схема сжатия битовых индексов, описанная в патенте [5]. Этот метод сжатия, байтовое сжатие битовых карт, позволяет корректно сравнивать данные без их декодирования. Метод кратко описан выше в пункте “Сжатие битовых карт” параграфа “Сжатие индексных структур”.

В [37] утверждается, что в версии Oracle 8i Release 8.1.5 поддерживается частичное сжатие значений составного первичного ключа в индексе типа B-дерева, аналогичное экономному кодированию первичного ключа в индексных таблицах.

SAS System

Программный комплекс SAS System фирмы SAS Institute не является СУБД как таковой. Это сложная система для хранения, анализа и доставки информации. Хотя некоторые специалисты причисляют SAS System к системам управления статистическими базами данных [53], данный программный комплекс не обеспечивает транзакционную работу и имеет сравнительно скромную поддержку совместного доступа к данным на запись. Тем не менее, SAS System часто применяется при организации корпоративных хранилищ данных и создании OLAP-приложений.

В SAS System реализовано 2 метода сжатия данных, и при этом есть возможность программировать иные алгоритмы сжатия с помощью специального инструментального средства разработки [51]. Первым методом является кодированием длин серий (RLE). Эта техника очень эффективна для кодирования таблиц с текстовыми колонками, поскольку по умолчанию все строки любой таблицы в SAS System имеют одинаковую фиксированную длину. Вторым методом является метод сжатия Росса (Ross Data Compression)¹⁵. В этой технике применяется словарное сжатие со скользящим окном в сочетании с кодированием длин серий. Данные сжимаются по записям, т.е. единицей сжатия является строка. Метод ориентирован на сжатие числовых полей и хорошо работает при длине строки от нескольких сотен байтов и больше.

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

Также необходимо отметить возможность организации словарного сжатия значений атрибутов. Это обеспечивается механизмом форматов, позволяющим по-разному представлять данные. Можно задать такой формат, который поставит в соответствие числам строковые константы. Например, можно определить формат $regions., в соответствии с которым при обработке данных будут автоматически выполняться преобразования типа: 1 à “Европа”, 2 à “Азия” и т.п. Если сопоставить такой формат числовой колонке таблицы, то получится реализация словарного сжатия на уровне значений атрибута. В общем случае использование форматов требует определенного учета в прикладных программах, т.е. процесс работы с преобразованными данными не является “прозрачным”.

Sybase IQ

Sybase IQ — это высокопроизводительная СУБД, ориентированная на использование в системах поддержки принятия решений.

В [24] со ссылкой на одного из сотрудников фирмы Sybase указывается, что в Sybase IQ используется схема сжатия на основе LZ76¹⁶. При этом не поддерживается избирательное декодирование отдельных кортежей, сжимается целиком страница. В буферном пуле сохраняются как распакованные, так и сжатые версии страниц. В работе [25] того же автора утверждается, что схема сжатия в Sybase IQ сходна с алгоритмом сжатия, используемым в компрессоре Gzip. Указывается, что применяется коммерческая версия Gzip, разработанная фирмой Stacker. Поскольку Gzip использует формат сжатых данных Deflate [1] и, следовательно, реализует метод LZH, то можно сделать заключение об использовании в Sybase IQ словарной схемы типа LZ77 с последующим блочно-адаптивным кодированием по алгоритму Хаффмана.

Из руководства администратору СУБД [56], относящегося к Sybase IQ версий 11.2.x, следует, что в результате сжатия физические страницы (таблиц базы) размером 16 условных блоков преобразуются в логические. При стандартном размере блока в 4 кБайт размер физической страницы составляет 64 кБайт. Размер логической страницы может составлять 1, 2, 4, 8 и 16 блоков. Логические страницы размещаются последовательно во внешней памяти и считываются порциями, соответствующими размеру физической страницы. Таким образом, вне зависимости от характеристик данных и размера блока, максимальная степень сжатия равна 16. Размер физической страницы может быть уменьшен с используемых по умолчанию 16 блоков до 2, 4 или 8 блоков. В этих случаях максимальная степень сжатия уменьшается до 2, 4 и 8 соответственно, но требуется меньше оперативной памяти для буферов и выполнения декодирования.

Эффективность сжатия существенно определяется тем, что таблицы в Sybase IQ сохраняются по колонкам, а не построчно.

В [4] указывается использование сжатия при представлении битовых индексов в Sybase IQ. В [25] отмечается, что битовые индексы сжимаются с помощью того же словарного метода, что и данные. Из руководства администратору [56] следует, что система обеспечивает сжатие индексных структур любого вида с помощью метода сжатия одного типа.

Teradata

Комплекс Teradata фирмы NCR является реляционной СУБД и позиционируется на рынке производителем как средство ведения больших хранилищ данных. Таким образом, данная СУБД ориентирована на использование в системах поддержки принятия решений.

Teradata версии 2 Release 5.0 поддерживает словарное сжатие таблиц на уровне значений колонок [40]. Каждая колонка может быть независимо закодирована с помощью словаря наиболее часто используемых значений этого атрибута. Размер словаря должен быть равен 2ⁿ-1, n = 1…8, и составляет максимум 255. Если атрибут может принимать неопределенное значение (NULL), то оно сжимается независимо. Словарь для каждой колонки сохраняется в заголовке таблицы. В заголовке каждой строки имеются флаги для указания факта сжатия значений колонок. Ссылка на фразу словаря для сжатого значения атрибута также записывается в заголовке строки.

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

На основании ряда экспериментов над несколькими реальными базами данных в [40] указывается, что применяемый метод сжатия должен обеспечивать среднюю степень сжатия в 2 и более раз для типовых хранилищ данных, при этом ожидаемое уменьшение времени выполнения запросов составляет несколько десятков процентов.

В [40] также отмечается, что в Teradata версии 2 Release 4.0 словарь для отдельной колонки мог состоять только из одного элемента.

Сравнение и выводы

Фирмы-производители стараются избежать корректного сравнения их продукции с конкурирующим ПО и препятствуют появлению полной информации о поведении СУБД на стандартных тестовых наборах. Поэтому не представляется в настоящее время возможным сопоставить комплексы по степени сжатия и влиянию компрессии на скорость работы. Таблица 3 содержит сравнение систем по наличию сжатия данных и применяемым алгоритмам экономного кодирования.

Таблица 3

Система	Сжатие таблиц	Сжатие индексов	Уровень сжатия таблиц	Метод сжатия таблиц	Заявляемая степень сжатия
ADABAS, версия 7.1.2	X	X	Значение атрибута	Поля переменной длины, кодирование отсутствующих значений	2
DB2, версия 5	X	.	Строка	Кодирование по статическому словарю LZMW	2-2.3
Ingres, версия 2.6	X	X	Значение атрибута	Поля переменной длины, кодирование отсутствующих значений	?
Microsoft Access, ядро MS Jet 3.0	.	X	.	.	.
MySQL, версия 4.0.18	X	X	Значение атрибута	Кодирование по Хаффману, устранение серий нулей и пробелов, упаковка битов, словарь значений атрибута	1.7-3.3
Oracle, версия 9i Release 2	X	X	Значение атрибута	Статический словарь значений атрибута	1.4-3.1
SAS System, версия 8.2	X	.	Строка	Кодирование длин серий и словарное сжатие со скользящим окном	?
Sybase IQ, версия 11.2	X	X	Страница	Словарное сжатие со скользящим окном типа LZH	?
Teradata, версия 2 Release 5.0	X	?	Значение атрибута	Статический словарь значений атрибута	2

Примечание: “X” обозначает факт наличия сжатия, “.” — отсутствие сжатия, “?” — отсутствие достаточной информации.

Все рассмотренные промышленные системы управления данными поддерживают такой способ экономного кодирования информации, как использование полей переменной длины. Но лишь ряд СУБД реализует более сложные методы сжатия. Показательно, что в этом случае для сжатия табличных данных используются исключительно словарные методы. Предпочтение отдается сжатию на уровне значения атрибута, что упрощает работы по выборке и по кодированию-декодированию данных при выполнении запросов. С другой стороны, сжатие на уровне строк и страниц должно способствовать улучшению степени сжатия в первую очередь текстовых данных и может иметь в этом свое преимущество. Заявляемая производителями степень сжатия БД составляет 2 и более раз.

Таким образом, реализации методов сжатия в СУБД отстают от современных достижений в этой сфере научной деятельности. Поддержка сжатия часто связана с ограничениями по типу данных и уменьшением функциональности сжатых объектов. Слабо используются прогрессивные разработки в сжатии числовых и структурированных текстовых данных, в том числе позволяющие оперировать непосредственно закодированными данными при обработке запроса. Не уделяется внимание вопросу сжатия результирующих наборов, позволяющего значительно повысить производительность в распределенных информационных системах с малой пропускной способностью каналов связи. Возможно, в существующих системах недостаточно эффективно решается задача построения плана выполнения запроса с учетом факта сжатия данных, поскольку в доступных источниках этот вопрос не акцентируется.

Заключение: перспективные направления в области использования сжатия данных в СУБД

Применение сжатия данных в СУБД является перспективной и развивающейся областью знаний. Практическая польза от использования сжатия, выражающаяся в сокращении расходов памяти и повышении производительности системы, перевешивает трудности, связанные с эффективной реализацией поддержки экономного кодирования. Это в итоге должно сломить консерватизм фирм-производителей СУБД и заставить реализовать полноценную поддержку сжатия данных в их продуктах. Скорее всего, этот процесс уже начался вследствие введения поддержки сжатия табличных данных в последней версии СУБД Oracle, являющейся основным продуктом соответствующего сектора рынка.

Вместе с тем имеется целый спектр актуальных проблем, определяющих перспективные направления исследований.

1. Слабо исследованы возможности создания эффективных методов сжатия, позволяющих учитывать структуру данных. Например, если БД содержит временные ряды некоторых показателей, что характерно для хранилищ данных, то существуют сильные зависимости как по вертикали (по столбцу), так и по горизонтали (по строке).
2. Открыт вопрос экономного кодирования результатов выполнения запросов. Задача актуальна в первую очередь для распределенных вычислительных систем, имеющих малую или недостаточную пропускную способность каналов связи.
3. Обеспечение действительно высокой производительности СУБД при использовании сжатия возможно только при комплексном изменении механизма выполнения запросов. В частности, оптимизация плана выполнения запроса должна производиться с максимально точным учетом всех эффектов использования сжатия. С другой стороны, используемый метод сжатия должен иметь способы адаптации, учитывающие статистику работы оптимизатора.
4. Увеличение разницы в скорости процессора и элементов памяти диктует необходимость пересмотра устоявшихся взглядов. Использование более сложных методов, требующих значительного объема вычислений, но предоставляющих бо́льшую степень сжатия может повысить реальную производительность СУБД. По этой причине может быть целесообразен переход от применения сжатия на уровне значения атрибута к уровню страницы.

Благодарности

Автор благодарен Вадиму Юкину и Роману Волынцу за дискуссию и ряд дельных замечаний и предложений. Также большое спасибо д-ру Ви-Кеонгу Нг (Wee-Keong Ng) и Жимону Грабовски (Szymon Grabowski) за предоставленные статьи.

Литература

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2002. – 384 с.
2. Дейт К. Д. Введение в системы баз данных. – 7-е изд. – М.: Вильямс, 2001. – 1072 с.
3. Alsberg P. A. Space and Time Savings Through Large Data Base Compression and Dynamic Restructuring. Proc. IEEE 63(8):1114-1122, August 1975.
4. Amer-Yahia S. and Johnson T. Optimizing queries on compressed bitmaps. In Proc. of VLDB, pp. 329–338, 2000.
5. Antoshenkov G. Byte Aligned Data Compression. U.S. Patent No: 5,363,098, October 1993.
6. Antoshenkov G. Dictionary-based order-preserving string compression. In VLDB Journal, 6(1):26-39, 1997.
7. Babu S., Garofalakis M., Rastogi R. SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables. Proc. of ACM SIGMOD'2001, Santa Barbara, CA, May 2001, pp. 283-294.
8. Bassiouni M., Mukherjee A., Tzannes N. Experiments on Improving the Compression of Special Data Types. Proc. IEEE Data Compression Conference, Snowbird, Utah, April 8-11, 1991, p. 433.
9. Bell T.C., Moffat A., and Witten I.H. Compressing the Digital Library. 1994.
10. Bruni, P. and Naidoo, R. DB2 for OS/390 and Data Compression. First Edition. IBM Redbook, SG24-5261-00, 1998, 170 p.
11. Buchsbaum A. L., Caldwell D. F., Church K. W., Fowler G. S., and Muthukrishnan S. Engineering the compression of massive tables: an experimental approach. Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000.
12. Cannane A., Williams H. E., and Zobel J. A General-Purpose Compression Scheme for Databases. Proc. IEEE Data Compression Conference, p. 519, 1999.
13. Chan C.Y. and Ioannidis Y.E. An Efficient Bitmap Encoding Scheme for Selection Queries. Proc. ACM SIGMOD Intl' Conference, Philadelphia, Pennsylvania, June 1999, pp. 215-226.
14. Chen Z. Building Compressed Database Systems. A Dissertation Presented to the Faculty of the Graduate School of Cornell University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy, Aug. 2002.
15. Chen Z., Gehrke J., Korn F. Query Optimization in Compressed Database Systems. Proc. 2001 ACM-SIGMOD Int. Conf. Management of Data, pp. 271-282, Santa Barbara, CA, May 2001.
16. Chen Z., Seshadri P. An Algebraic Compression Framework for Query Results. Proceedings of the International Conference on Data Engineering ICDE'99, San Diego, CA, March, pp. 177-188, 1999.
17. Cockshott W. P., Gilchrist J., McGregor D., Murray P., and Wilson J. Compressed, Memory Resident, Databases. 1996.
18. Collins K. Jet 3.0 Performance Overview White Paper. Microsoft Corporation. Jet Program Management. 1995.
19. Computer Associates. Advantage Ingres Database Administrator’s Guide 2.6. 2002.
20. Cormack G. V. Data Compression in Database Systems. Comm. of ACM, 28(12):1336-1342, December 1985.
21. Eggers S., Olken F., and Shoshani A. A Compression Technique for Large Statistical databases. Proc. VLDB Conf., September 1981.
22. Eggers S., and Shoshani A. Efficient Access of Compressed Data Performance. Proc. VLDB, Montreal, Oct. 1980, p. 205.
23. Gallager R.G. Variations on a theme by Huffman. IEEE Transactions on Information Theory, 24(6):668-674, Nov. 1978.
24. Goldstein J. Improved query processing and data representation techniques. A dissertation submitted in partial fulfillment of the requirements for the degree of doctor of philosophy (computer sciences) at the University of Wisconsin – Madison. 1999.
25. Goldstein J., Ramakrishnan R., and Shaft U.. Compressing relations and indexes. Proc. IEEE Conf. on Data Engineering, Orlando, FL, USA, pp. 370-379, 1998.
26. Goyal K., Ramamritham K., Datta A., Thomas H. Indexing and Compression in Data Warehouses. Technical Report, Indian Institute of Technology, Bombay, April 1999.
27. Goyal K. B., Ramamritham K., Datta A., Thomas H. M. Indexing and Compression in Data Warehouses. Proceedings of the Int'l. Workshop Design and Management of Data Warehouses '99, Heidelberg, Germany, June 14-15, 1999.
28. Graefe G. Query Evaluation Techniques for Large Databases. ACM Computing Surveys 25(2), June 1993, p. 73-170.
29. Graefe G. and Shapiro L. D. Data Compression and Database Performance. In Proceedings of the ACM/IEEE-Computer Science Symposium on Applied Computing, Kansas City, MO, 1991.
30. Hann R.. Ingres Frequently Asked Questions. 1997.
31. Hubley M., Fairchild A. Software AG Adabas. Gartner Product Report. 2001.
32. Iyer B. R. and Wilhite D. Data Compression Support in Databases. In Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, pp. 695-704. 1994.
33. Johnson T. Performance Measurements of Compressed Bitmap Indices. Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999 (VLDB'99), Edinburgh, Scotland, UK, pp. 278-289.
34. Korn F., Jagadish H. V., and Faloutsos C. Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences. 1997 ACM SIGMOD International Conference on Management of Data, pp. 289-300, Tucson, AZ, May 1997.
35. Lekatsas H. and Wolf W. Random Access Decompression using Binary Arithmetic Coding. IEEE Data Compression Conference, pp. 306-315, Snowbird, UT, March, 1999.
36. Li J., Rotem D., Wong H. A New Compression Method with Fast Searching on Large Databases. Proceedings of 13th International Conference on Very Large Data Bases, 1987, Brighton, pp. 311-318.
37. Miled Z. B., Li H., Bukhres O., Bem M., Jones R., Oppelt R.. Data Compression in a Pharmaceutical Drug Candidate Database. Informatica 17, 2001.
38. Moffat A. and Zobel J. Coding for compression in full-text retrieval systems. In Proc. IEEE Data Compression Conference, pp. 72-81, Snowbird, Utah, March 1992. IEEE Computer Society Press, Los Alamitos, California.
39. Moffat A. and Zobel J. Compression and fast indexing for multi-gigabyte text databases. Australian Computer Journal, 26(1):1-9, 1994.
40. Morris M. Teradata Multi-Value Compression V2R5.0. A Teradata White Paper, EB-3099, July 2002.
41. MySQL AB (2004). MySQL Reference Manual for version 4.0.18.
42. Ng W. K. and Ravishankar C. V. Block-Oriented Compression Techniques for Large Statistical Databases. Knowledge and Data Engineering, 9(2):314-328, 1997.
43. Ng W. K., Ravishankar C.V. Relational Database Compression Using Augmented Vector Quantization. ICDE 1995: 540-549.
44. Ng W. K., Ravishankar C.V., Chinya V. Data compression system and method representing records as differences between sorted domain ordinals representing field values. US Patent 5,603,022. Feb. 1997.
45. Oracle Corp. Oracle Online Documentation Library. 2001.
46. Poess M. Table Compression in Oracle9i Release 2: A Performance Analysis. An Oracle White Paper, January 2003.
47. Qiang J. Querying and Mining Semantic Compressed Databases. A term paper submitted for PhD qualifier examination. School of Computing, National University of Singapore, 2002.
48. Ray G. Data Compression in Databases. Master's Thesis, Dept. of Computer Science and Automation, Indian Institute of Science, June 1995.
49. Ray G., Haritsa J., and Seshadri S. Database compression: A performance enhancement tool. In Proc. COMAD, Pune, India, December 1995.
50. Roth M. A. and Van Horn S. Database compression. ACM SIGMOD Record, 22(3):31-39, Sept. 1993.
51. Ruth S. and Keutzer P. Database Compression for Large Business Files. Datamation, 18, Sept. 1972, p. 62.
52. SAS Institute Inc., SAS OnlineDoc®, Version 8, Cary, NC: SAS Institute Inc., 1999.
53. Software AG. ADABAS DBA Reference Manual. 1997.
54. Srivastava J., Ngo H. Statistical Databases. Technical Report.
55. Stockinger K. Multi-Dimensional Bitmap Indices for Optimising Data Access within Object Oriented Databases at CERN. PhD. Nov. 2001.
56. Stockinger K., Wu K., Shoshani A. Strategies for Processing ad hoc Queries on Large Data Warehouses. Proc. DOLAP’02, November 4–9, 2002, McLean, Virginia, USA.
57. Sybase, Inc. Sybase IQ Administration Guide, 1997.
58. Vo B.D., Vo K-P. Using Column Dependency to Compress Tables. Proc. IEEE Data Compression Conference, Snowbird, Utah, March 23-25, 2004, pp. 92-101.
59. Westmann T., Kossmann D., Helmer S., and Moerkotte G. The implementation and performance of compressed databases. Technical Report 3/98, Universitat Mannheim, 1998. Отчет был напечатан: Westmann T., Kossmann D., Helmer S., and Moerkotte G.. The Implementation and Performance of Compressed Databases. SIGMOD Record, 29(3):55-67, 2000.
60. Witten I.H., Bell T.C., and Nevill C.G.. Indexing and compressing full-text databases for CD-ROM. Journal of Information Science, 17:265-271, 1992.
61. Wu K., Otoo E., and Shoshani A. Compressing Bitmap Indexes for Faster Search Operations. In Proceedings of SSDBM 2002
    Preprint as LBNL-49627, 2002.
62. Wu K., Otoo E., and Shoshani A. Compressed bitmap indices for efficient query processing. Technical report LBNL/PUB-3161, Lawrence Berkeley National Laboratory, Berkeley, CA, 2001.
63. Zandi A., Iyer B., and Langdon G. Sort Order Preserving Data Compression for Extended Alphabets. IEEE Data Compression Conf., Snowbird, Utah, March 30 – April 1, 1993, pp. 330-339.
64. Ziv J., Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, Vol. 23(3), pp.337-343, May 1977.
65. Ziv J. and Lempel A. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, Vol. 24(5), pp.530-536, Sept. 1978.

Содержание | Часть 1 | Часть 2 | Часть 3 | Часть 4

 

Подстрочные примечания

¹³ Отсутствие в обзоре данных об Microsoft SQL Server — одном из основных продуктов на рынке СУБД — объясняется не антипатиями автора, как некоторые могли подумать, а отсутствием какой-либо информации об использовании экономного кодирования данных в этой системе.
¹⁴ OLAP — On-Line Analytical Processing — технология обработки многомерной информации в реальном времени, связанная с динамическим составлением интерактивных отчетов табличного и графического вида. Интерактивные отчеты представляют сводные сведения о массиве многомерной информации, полученные путем агрегирования данных по каким-то измерениям или иерархическим уровням измерений массива информации, и, как минимум, позволяют динамически изменять уровень агрегации. Эффективная поддержка OLAP требует особого устройства базы данных, поэтому OLAP обычно используется совместно с многомерными базами данных или РБД, организованными по принципам хранилищ данных (data warehouse).
¹⁵ Судя по описанию в [52], это действительно алгоритм Э. Росса, опубликованный с исходным кодом реализации в журнале "The C Users Journal": E. Ross. A Simple Data Compression Technique. The C Users Journal, 10(10):113-120, Oct. 1992.
¹⁶ J. Ziv and A. Lempel. On the complexity of finite sequences. IEEE Transactions on Information Theory, 22(1):75-81, 1976.