Иерархические битовые индексы

Понятие битовых индексов (bitmap index) хорошо знакомо каждому проектировщику баз данных. Впервые введенные в 1987 году, они стали стандартным способом оптимизации запросов в промышленных СУБД: Oracle, Cache и др. Однако эффективность их использования сильно зависит как от запросов, так и от особенностей базы данных. В [1] раскрываются некоторые секреты и развенчиваются устойчивые заблуждения по поводу битовых индексов, но в целом литературы на русском языке крайне мало, а между тем в зависимости от задачи можно использовать не битовые индексы в виде, предоставляемом СУБД, а их модификацию, что существенно повышает эффективность поиска, причем затраты на такую модификацию с лихвой окупаются повышением производительности обработки запросов.

Выбор стратегии использования битовых индексов определяется рядом факторов, среди них:

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

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

Остановимся подробнее на третьем, наиболее важном для понимания концепции иерархических индексов. Желающим же ознакомиться с основными теоретическими достижениями по битовым индексам в их историческом развитии можно порекомендовать обзор [5].

Идея группирования достаточно проста — вместо того, чтобы создавать битовую строку для каждого отдельного значения свойства, весь диапазон значений делится на интервалы (bins), а битовая строка создается для каждого интервала. Например, битовые индексы для групп выглядят следующим образом: группа 0–11010010; группа 1–00000101; группа 2–00101000 (табл. 1). Помимо очевидного выигрыша по общему объему индексов, выигрыш в производительности достигается в том случае, если диапазон запроса по атрибуту полностью накрывает одну или несколько групп, — количество дизъюнкций битовых строк тогда сокращается до одного. Однако, помимо оптимального разбиения на группы, здесь возникает проблема, когда запрос лишь частично накрывает одну из групп и требуется дополнительная проверка для каждого значения из такой группы: удовлетворяет оно запросу или нет. Эта проблема получила название candidate checking, и для ее решения также предложено множество подходов. Но в целом, особенно с появлением хранилищ и озер данных, просто группирования, даже с всевозможными модификациями, оказалось недостаточно для достижения приемлемой производительности обработки запросов на больших базах данных. Продолжением концепции binning стали иерархические битовые индексы (Hierarchical Bitmap Indexes, HBI) — активно развивающееся сегодня направление оптимизации работы с базами данных.

Индексация времени

Время — величина, обладающая естественной иерархичностью, и существует множество единиц ее измерения, что ставит проектировщика перед задачей оптимального выбора. Представим CRM-систему с сущностью «Входящие звонки». Один из атрибутов — это время поступления звонка с точностью до секунды. Интенсивность поступления звонков в масштабах всей компании, эксплуатирующей СУБД, достаточна высока, таблица большая. Типичное приложение — генерация отчетов по звонкам с временным диапазоном в качестве фильтра (вывести информацию о звонках, поступивших в определенный период времени). Использование битовых индексов здесь означает, что для каждого значения времени, для которого зафиксирован хотя бы один звонок, создается битовая строка, возможно, состоящая из нескольких подстрок (chunks). При запросе берутся все имеющиеся индексы для значений, входящих в заданный диапазон, и путем их дизъюнкции вычисляется битовая строка, единицы которой соответствуют ID звонков, удовлетворяющих запросу и выводимых в итоговый отчет.

Зависимость трудоемкости обработки запроса от значения крупного индекса

Применение битовых индексов для промышленных объемов данных не дает приемлемой производительности — отчеты генерируются слишком медленно. Узкое место — количество индексов, подпадающих под условия фильтра запроса. При большом диапазоне запроса и высокой интенсивности занесения в базу новых записей возникает ощутимая задержка: все строки нужно загрузить в память и выполнить над ними дизъюнкцию. Какую выбрать иерархию для максимальной эффективности? Даже если предположить, что, помимо секундного (мелкого) индекса, имеется в наличии только один крупный, какому интервалу времени он должен соответствовать? Если крупный индекс выбрать слишком маленьким (скажем, две секунды), это может дать мизерный эффект (количество крупных индексов, необходимых для обслуживания запроса, может остаться практически тем же), а если слишком большим, он может оказаться бесполезен, если длина запроса в среднем меньше него. Ключевыми исходными данными для оптимизации являются две функции распределения вероятностей: занесения записей в базу и длины запроса. Зная распределения этих случайных величин, можно выбрать размер крупного индекса, минимизирующий среднее значение третьей случайной величины — общей суммы количества крупного и мелкого индексов, «накрываемых» запросом на входном потоке событий. Но, чтобы оптимизировать некоторую целевую функцию, нужно уметь ее вычислять — по двум распределениям и выбранной иерархии вычислить среднее число всех битовых индексов, необходимых для обслуживания запроса.

Решение этой задачи методами теории вероятностей предложено в [2], а представление о практическом «выхлопе» этого решения можно получить из рисунка. Новая запись в базе появлялась в среднем каждые 30 секунд (параметр экспоненциального распределения равен 0,033), а средняя длина интервала поискового запроса — 1000 секунд (параметр равен 0,001). На рисунке изображены зависимости среднего числа индексов от длины интервала для крупного индекса в случае одного крупного индекса (тонкая линия) и двух (толстая линия), где второй крупный индекс равен одному часу. Из графика видно, что минимум действительно существует, достигается примерно в диапазоне 345–350 секунд и равен 5,7 индекса для тонкой линии и 5,2 для толстой. В нулевой точке, когда отсутствует какая-либо иерархия, трудоемкость значительна, а применение HBI позволило получить прирост производительности как минимум в пять раз. Что и было подтверждено как при нагрузочном тестировании, так и в ходе промышленной эксплуатации CRM.

Иерархические индексы берут свое начало с работы [4] и были введены для выполнения запросов по атрибутам-множествам (Set-Valued Attributes), допустимых стандартом SQL3.

Рассмотрим таблицу Purchases (trans id, cust id, products), хранящую записи о покупках клиента. В таблице три поля: ID транзакции (покупки), ID клиента, купленные им продукты. Типовые запросы можно разделить на запрос подмножества (subset query), когда ищутся покупки, в состав которых входит заданный набор продуктов; запрос покрывающего множества (superset query), когда ищутся покупки, в состав которых входят покупки только из заданного множества; запрос подобия (similarity query), когда ищутся покупки, совпадающие с данным множеством с точностью до установленного порога подобия. Вот как мог бы выглядеть subset query на SQL для количества покупок с молоком и маслом:

SELECT COUNT (DISTINCT A.cust id)

FROM Purchases A, Purchases B

WHERE A.trans id = B.trans id

AND A.item = ‘milk’ AND B.item = ‘butter’;

Такой запрос нельзя назвать эффективным: во -первых, из-за «тяжелой» операции self-join для таблицы покупок; во -вторых, добавление еще одного продукта в запрос приводит к изменению предложения FROM; и, наконец, запрос в целом теряет естественность и трудно читается.

Идея HBI состоит в том, чтобы пронумеровать все значения, которые могут быть элементами set-атрибута, и параметризовать его двумя числами: l — длина индексного узла, d — количество уровней иерархии. Тогда любое значение set-атрибута (некоторое множество) может быть представлено деревом битовых индексов. Такое представление позволяет свести выполнение запроса с условием по set-атрибуту к небольшому количеству эффективных логических операций над битовыми строками, равному d. Поясним это на примере subset-запроса. Пусть значение set-атрибута S= {2, 3, 9, 12, 13, 14, 38, 40}, l=4, d=3. Тогда это значение можно представить в виде дерева битовых индексов (табл. 2). На первом уровне находится единственный узел — корень (root node), на последнем — узлы-листья (leaf nodes), на остальных — внутренние узлы (inner nodes).

Номера позиций единиц в листьях соответствуют значениям элементов S (нумерация от единицы). Пустые узлы (empty nodes), состоящие только из нулей, — эти узлы не хранятся в виде индекса на диске. Пусть имеется запрос q= {9, 13, 40}. Используя индексное дерево для S, нужно определить, удовлетворяет множество этому запросу или нет.

Связный список узлов для множества S — K (S) = {1010,1011,0100,0110,1001,1100, 0101}, для множества q K (q) = {1010,0011,0100,1000,1000,0001}. Конъюнкция корневых узлов дает K1 (q) =1010 — сравнение корневых узлов не противоречит тому, что множество S накрывает множество q. Далее продвигаемся по узлам первого уровня множества q. Один шаг вдоль уровня множества q может соответствовать нескольким шагам вдоль того же уровня множества S (множество S может включать элементы, не входящие в q). Конъюнкция K2 (S) =1011 и K2 (q) =0011 дает K2 (q), конъюнкция K3 (S) =0100 и K3 (q) =0100 дает K3 (q) — и на втором уровне проверка пройдена успешно. Начинаем проход по узлам третьего уровня множества q. Чтобы сопоставить первому из этих узлов, равному 1000, узел множества S, первый узел третьего уровня множества S 0110 нужно пропустить: он соответствует единице, стоящей на первой позиции узла второго уровня 1011, а этой единицы на втором уровне множества q нет — узел равен 0011. Поэтому конъюнкцию узла множества q 1000 осуществляем с узлом третьего уровня 1001 множества S. Она равна 1000 — пройдено. Нетрудно видеть, что оставшиеся две проверки также проходят. Таким образом, множество S запросу q удовлетворяет. Благодаря использованию HBI отпадает необходимость в использовании join, а трудоемкость выполнения запроса с условием по set-атрибуту становится логарифмической — это округленный в большую сторону логарифм максимального значения элемента set-атрибута по основанию l.

Предложенный подход предназначался только для достаточно узкой задачи обработки именно set-атрибутов таблиц и не предполагал наличия у диапазона значений естественной иерархии, но все это инициировало дальнейшие исследования в направлении более широкого применения HBI.

Идеи, высказанные в [3], в общем-то, очевидны, но тем не менее их должен был кто-то впервые заявить. Объектом изучения этой работы являются хранилища данных (data warehouses, весьма распространенный объект, когда речь идет о битовых индексах) и присущая им организация хранения данных, когда некую таблицу сущностей (fact table) сопровождает набор таблиц, хранящих все возможные значения атрибутов этих сущностей (dimension tables). Типовым запросом к такой таблице является звездчатый запрос (star query), требующий выборки записей из таблицы сущностей при наложении некоторых условий на значения различных атрибутов. Обычным способом выполнения таких запросов является операция соединения (join) между таблицей сущностей и каждой из таблиц атрибутов. Наличие у атрибута естественной иерархии позволяет построить для него каскад битовых индексов, ускоряющих выборку данных и избавляющих от необходимости выполнять join. Рассмотрим простой пример (табл. 3).

Предположим, что в десяти записях таблицы сущностей значения атрибута «Продукт» следуют в заданном порядке, причем для этого атрибута имеется более высокий уровень иерархии — «Категории», для категории существует своя таблица (в данном случае из двух записей) и свои битовые индексы. В случае, когда диапазон запрашиваемых продуктов накрывает всю категорию, например «Ноутбуки», нет необходимости выполнять дизъюнкцию (логическое ИЛИ) для всех пяти битовых индексов этой категории — запрашиваемую выборку сразу дает битовый индекс «Ноутбуки». Более того, если в запросе требуется учесть только четыре из пяти продуктов категории, можно применить XOR (исключающее ИЛИ) над индексом по всей категории и индексом для продукта, не охваченного запросом. Это даст снижение количества дизъюнктов — битовых строк — с пяти до двух. В работе [3] этот подход был протестирован на большой базе данных аукционных продаж — быстродействие оказалось намного выше, чем в случае использования обычных битовых индексов Oracle.

***

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

Литература

1. Льюис Д. Разбираемся с индексами на основе битовых карт. URL: http://citforum.ru/database/oracle/bitmap_index/ (дата обращения: 10.08.2018).
2. Труб И. И. Вероятностная модель иерархических индексов баз данных // Программные системы и вычислительные методы. — 2017. — № 4. — С. 15–31. URL: http://www.nbpublish.com/library_read_article.php?id=24437 (дата обращения: 10.08.2018).
3. Chmiel J., Morzy T., Wrembel R. HOBI: Hierarchically Organized Bitmap Index for Indexing Dimensional Data. — In Proc. of the Eleventh International Conference on Data Warehousing and Knowledge Discovery (DaWaK). — 2009, August. — P. 87–98.
4. Morzy M., Morzy T., Nanopoulos A., Manolopoulos Y. Hierarchical Bitmap Index: an Efficient and Scalable Indexing Technique for Set-Valued Attributes. — In Proc. «Advances in Databases and Information Systems, Seventh East European Conference, ADBIS 2003, Dresden, Germany, September 3–6, 2003», volume 2798 of Lecture Notes in Computer Science, P. 236–252. — Springer, 2003.
5. Otoo E., Wu K. Accelerating Queries on Very Large Datasets. — In book «Sceintific Data Management. Challenges, Technology and Deployment» (edited by Arie Shoshani, Doron Rotem), P. 183–234. — Chapman & Hall/CRC, 2010. — 558 p.

Илья Труб (itrub@yandex.ru) — ведущий инженер-программист, Исследовательский центр Samsung (Москва). Статья подготовлена на основе материалов выступления автора на конференции «Технологии управления данными 2018».