Разбираемся с индексами на основе битовых карт

Джонатан Льюис (Jonathan Lewis)
http://www.jlcomp.demon.co.uk/

Перевод: Валерий Кравчук, OpenXS Initiative

Индексы на основе битовых карт - великое благо для некоторых видов приложений, но об их устройстве, использовании и побочных эффектах распространено очень много неверной информации. В этой статье описывается структура индексов на основе битовых карт и делается попытка разъяснить, почему возникли некоторые из наиболее типичных заблуждений, связанных с ними.

Общеизвестно, что...

Если провести простое исследование понимания разработчиками индексов на основе битовых карт, скорее всего, следующие комментарии окажутся наиболее типичными:

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

Третье утверждение, на самом деле, всего лишь следствие (возможно, не проверенное) второго. Причем, все три утверждения попадают в смутную зону между ложью и большим заблуждением.

Конечно, в этих утверждениях есть и небольшая доля правды, - достаточная, чтобы объяснить их происхождение.

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

Что такое индекс на основе битовой карты?

Индексы создаются, чтобы сервер Oracle мог максимально эффективно находить запрошенные строки. Индексы на основе битовых карт - не исключение, однако стратегия, лежащая в основе этих индексов, очень отличается от стратегии, на которой базируются индексы на основе B*-дерева. Чтобы продемонстрировать это, мы начнем с изучения содержимого нескольких блоков.

Рассмотрим SQL-сценарий на рис. 1.

create table t1
nologging
as
select
	rownum		id,
	mod(rownum,10)	btree_col,
	mod(rownum,10)	bitmap_col,
	rpad('x',200)	padding
from
	all_objects
where rownum <= 30000;

create index t1_btree on t1(btree_col);

create bitmap index t1_bit on t1(bitmap_col);

Рисунок 1. Пример данных.

Обратите внимание, что столбцы btree_col и bitmap_col заданы так, что содержат идентичные данные, - числа от 0 до 9, повторяющиеся циклически.

В базе данных версии 9.2 с размером блока 8 Кбайт результирующая таблица займет 882 блока. Индекс на основе B*-дерева будет иметь 57 листовых блоков, а индекс на основе битовых карт - 10 листовых блоков. Фрагмент листового блока индекса на основе B*-дерева

row#538[2016] flag: -----, lock: 0
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 40 c5 7d 00 09

row#538[2004] flag: -----, lock: 0
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 40 c5 7d 00 13

Фрагмент листового блока индекса на основе битовых карт

row#2[4495] flag: -----, lock: 0
col 0; len 2; (2):  c1 03
col 1; len 6; (6):  00 40 c5 62 00 00
col 2; len 6; (6):  00 40 c7 38 00 1f
col 3; len 3521; (3521):
       cb 02 08 20 80 fa 54 01
       04 10 fb 53 20 80 00 02
       fc 53 04 10 40 00 01 fa
       53 02 08 20 fb 53 40 00 . . .

Рисунок 2. Блоки данных, сброшенные в символьном виде.

Понятно, что индекс на основе битовых карт несколько плотнее упакован, чем индекс на основе B*-дерева. Чтобы увидеть эту упаковку, можно сбросить блоки данных индекса в символьном виде с помощью команд типа:

alter system
dump datafile x block y;

Результаты представлены на рис. 2. Учтите, однако, что информация, полученная в результате сброса блока в символьном виде, может иногда приводить к неверным выводам, поскольку часть ее - производная от данных, и порядок следования тоже изменен по отношению к реальному для ясности.

Блокируются ли таблицы при работе с индексами на основе битовых карт?

Обратившись к рис. 2, можно увидеть, что запись индекса на основе B*-дерева состоит из набора флагов, байта блокировки, и (в данном случае) двух столбцов данных. Эти два столбца, на самом деле, - проиндексированное значение и идентификатор строки, причем, для каждой строки в таблице имеется запись этого вида в индексе. (Если бы индекс был уникальным, содержимое каждой записи было бы таким же, но расположение немного отличалось бы).

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

Посмотрите, однако, на размер потока битов, - длина столбца в представленном примере составляет 3521 байт, или около 27000 битов. Около 12% составляют накладные расходы на контрольные суммы и т.п., поэтому эта запись может покрыть порядка 24000 строк таблицы. Но на всю запись имеется только один байт блокировки, тем самым, одна блокировка будет влиять на 24000 строк таблицы.

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

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

Последствия блокировок битовых карт

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

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

Тестовые данные: Создание структур данных для примера

create table t1 (id number, bit_col number);

insert into t1 values(0,1);
insert into t1 values(1,1);
insert into t1 values(2,2);
insert into t1 values(3,3);
insert into t1 values(4,4);

create bitmap index t1_bit on t1(bit_col);

Изменение одной строки

update t1 set bit_col = 2 where id = 1;

(0,1)                   битовая карта "откуда"
(1,1) -> (1,2)          заблокированная строка
(2,2)                   битовая карта "куда"
(3,3)
(4,4)

Рисунок 3. Готовимcя к тестированию изменений.

Обратите внимание, что изменен проиндексированный столбец лишь одной строки таблицы. Если сбросить в символьном виде блоки индекса и таблицы, окажется, что байт блокировки установлен для одной строки таблицы, но заблокированы две секции индекса на основе битовых карт. Это секция для близких строк с текущим значением 1 в проиндексированном столбце (секция, "откуда" убирается строка) и секция для близких строк со значением 2 (секция, "куда" переносится строка). (На самом деле, эти две секции битовых карт скопированы, и обе копии заблокированы).

Теперь осталось разобраться, насколько "агрессивно" блокирует сервер Oracle в данном случае.

Ответ может показаться несколько неожиданным для тех, кто мыслит категориями "индексы на основе битовых карт приводят к блокированию таблицы".

Вполне можно сделать следующие изменения (каждое - в отдельном тесте).

Изменить строку в секции "откуда", если это изменение не затрагивает столбец индекса на основе битовых карт.

update t1
set id = 5
where id = 0;

Изменить строку в секции "куда", если это изменение не затрагивает столбец индекса на основе битовых карт.

update t1
set id = 6
where bit_col = 2;

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

Конечно, конфликты блокирвок возможны, - например, ни один из следующих операторов не сможет изменить заблокированную строку таблицы, но их выполнение вызовет ожидание соответствующим сеансом снятия блокировки "TX" в режиме 4 (разделяемой блокировки)

update t1
set bit_col = 4
where id = 2; -- bit_col = 2

update t1
set bit_col = 2
where id = 3 -- bit_col = 3

Учтите, однако, что для возникновения проблемы необходимо выполнение двух условий. Во-первых, необходимо изменять проиндексированный столбец, а во-вторых, изменяемая строка должна покрываться ранее заблокированной секцией битовой карты, т.е. должна быть "сравнительно близко" от другой, изменяемой в настоящий момент, причем, конфликт может вызывать очень ограниченный набор значений (в нашем примере, 4).

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

update t1
set bit_col = 4
where bit_col = 3;

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

Проблемы с битовыми картами

Конечно, при использовании битовых карт возникает ряд проблем, выходящих за рамки конфликтов при изменении.

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

Более того, даже последовательное выполнение операторов ЯМД, затрагивающих индексы на основе битовых карт, может куда существеннее сказаться на производительности, чем можно было предположить.

Я уже подчеркивал, что простое изменение одной строки обычно приводит к копированию всей соответствующей секции битовой карты. Вернемся к Рис. 1 и вспомним, насколько большой может быть секция битовой карты. В этом примере она была размером 3500 байтов (в Oracle 9 максимальный размер составляет около половины блока). Можно обнаружить, что небольшое изменение данных может очень существенно повлиять на размер любого изменяемого вследствие этого индекса на основе битовых карт.

Может, вам и повезет, но, в общем случае, стоит исходить из предположения, что даже последовательные пакетные изменения будут выполняться эффективнее, если удалить индексы на основе битовых карт перед их выполнением, а затем пересоздать.

Столбцы с небольшим количеством значений

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

Это утверждение, действительно, достаточно верное, - если его соответствующим образом уточнить и разъяснить. К сожалению, многие, в результате, думают, что индекс на основе битовых карт чудесным образом настолько эффективен, что его можно использовать для доступа к большим частям таблицы способом, не считающимся целесообразным при использовании индекса на основе B*-дерева.

Классическим примером применимости индекса на основе битовых карт является экстремальный случай столбца, представляющего пол. В этом столбце может быть всего два значения (или три, если включить требуемое стандартом ISO значение "n/a" - неизвестен). Мы будем чуть менее экстремальны и рассмотрим пример, основанный на странах, образующих Соединенное Королевство: Англия, Ирландия, Шотландия и Уэльс.

Пусть используются блоки размером 8 Кбайт и строки (весьма типичным) размером 200 байтов, что дает 40 строк в блоке. Вставим в таблицу несколько миллионов строк, обеспечив равномерно случайное распределение по странам. Таким образом, в среднем в каждом блоке будет по 10 строк для каждой страны.

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

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

Конечно, описательные выражения типа "небольшой", "маленький", "близкий к нулю" требуют определенного уточнения. Например, близко ли значение 10000 к нулю? Если сравнивать с десятью миллиардами, то да!

Не используйте неопределенные выражения вроде "небольшое количество". В большинстве случаев, при выборе индексов на основе битовых карт необходимо учитывать только два фактора. Во-первых, количество различных блоков в таблице, в которых может находиться типичное значение индекса - это основной фактор выбора отдельного индекса. Изменение структуры индекса с B*-дерева на набор битовых карт не сделает этот индекс в это отношении лучше чудесным образом. Во-вторых, используемый оптимизатором Oracle механизм комбинирования нескольких битовых индексов делает их действительно полезными.

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

• 50 миллионов имеет карие глаза
• 35 миллионов - женщины
• 17 миллионов - темноволосые
• 1,8 миллиона живет в районе Бирмингема
• 1,2 миллиона имеет возраст 25 лет
• 750000 работает в Лондоне

Каждому критерию отдельно соответствует очень много людей, но сколько кареглазых темноволосых женщин в возрасте 25 лет живет в Бирмингеме и работает в Лондоне? Где-то пару десятков.

create table junk as
select rownum id
from   all_objects
where  rownum <= 8000;

create table t1 nologging pctfree 0
as
select /*+ ordered use_nl(v2) */
	 'x'			facts,
	 mod(rownum,2)	sex,
	 mod(rownum,3)	eyes,
	 mod(rownum,7)	hair,
	 mod(rownum,31)	town,
	 mod(rownum,47)	age,
	 mod(rownum,79)	work,
from
	 junk v1, junk v2;

create bitmap index i1 on t1(sex) nologging pctfree 0;

create bitmap index i2 on t1(eyes) nologging pctfree 0;

create bitmap index i3 on t1(hair) nologging pctfree 0;

create bitmap index i4 on t1(town) nologging pctfree 0;

create bitmap index i5 on t1(age) nologging pctfree 0;

create bitmap index i6 on t1(work) nologging pctfree 0;

analyze table t1 estimate statistics;

Рисунок 4. Моделируем население Великобритании.

Отдельный индекс (будь-то на основе B*-дерева или битовых карт) по любому из этих столбцов будет абсолютно бесполезен для выполнения такого запроса к таким данным в СУБД Oracle.

Многостолбцовый индекс на основе B*-дерева по соответствующим шести столбцам может существенно помочь, пока нас не заинтересуют мужчины ростом 180 см. с бородой вместо темноволосых и кареглазых женщин.

Можете поэкспериментировать (см. рис. 4), но понадобиться около 2,0 Гбайт места на диске и пару часов работы процессора с тактовой частотой порядка 500 МГц.

Из-за нехватки места я построил модель поменьше, эмулирующую население порядка 36 миллионов. Время построения и размеры объектов для компьютера с тактовой частотой процессора 600 МГц, ОС Win2000 и сервером Oracle версии 9.2.0.1 представлены в следующей таблице.

Объект	Размер (Мбайт)	Время построения (мин:сек)
T1	845	16:12
I1 (sex)	11	1:39
I2 (eyes)	16	1:43
I2 (hair)	37	2:17
I4 (town)	40	2:25
I5 (age)	42	2:28
I6 (work)	45	2:42

Обратите, в частности, внимание на суммарный объем индексов, - 191 Мбайт. Всего лишь один многостолбцовый индекс по тем же шести столбцам (даже с максимальным сжатием) займет минимум 430 Мбайт, а сколько процессорного времени потребуется на его построение, - я вообще не знаю, да и немногие системы позволят построить этот индекс в памяти, поскольку для этого требуется установить параметру sort_area_size значение около 900 Мбайт.

Итак, что же могут дать все эти битовые индексы? Рассмотрим запрос:

select count(facts) 
from t1 
where eyes = 1 
and sex = 1 
and hair = 1
and town = 15 
and age = 25 
and work = 40;

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

При использовании полного шестистолбцового индекса объемом 430 Мбайт этот запрос выполнился бы, вероятно, за время, необходимое для выполнения около 10 физических чтений (один блок таблицы для каждой строки и пару дополнительных блоков индекса), - буквально за доли секунды.

При наличии заданных ранее битовых индексов запрос выполнялся пять секунд. Большая часть этого времени ушла на сканирования диапазонов индексов, требующие физического считывания блоков индекса в память. Фактический план выполнения представлен на рис. 5.

SORT (AGGREGATE)
  TABLE ACCESS (BY INDEX ROWID) OF T1
    BITMAP CONVERSION (TO ROWIDS)
      BITMAP AND
        BITMAP INDEX (SINGLE VALUE) OF I6
        BITMAP INDEX (SINGLE VALUE) OF I5
        BITMAP INDEX (SINGLE VALUE) OF I4

Рисунок 5. План выполнения.

В этом плане выполнения запроса следует отметить два интересных момента. Во-первых, сервер Oracle проигнорировал три "худших" (т.е., наименее избирательных) индекса. Во-вторых, хотя время выполнения - заметное, но размеры индексов настолько малы, что имеет смысл подумать об их размещении в достаточно большом KEEP-пуле, buffer_pool_keep (в Oracle 9 его размер задается параметром db_keep_cache_size), чтобы избежать физических чтений. Этот вариант вряд ли подходит для нескольких многостолбцовых индексов на основе B*-дерева, поддерживающих такие же запросы.

Давайте подумаем о проигнорированных индексах, - в плане может использоваться практически любое количество индексов на основе битовых карт. Я видел случаи, когда сервер Oracle использовал более пяти таких индексов (это предел для способа доступа and_equal при использовании одностолбцовых индексов на основе B*-дерева).

Три оставшихся индекса были проигнорированы не из-за какого-то искусственного ограничения. Стоимостной оптимизатор сравнил стоимость чтения каждого дополнительного индекса с достигаемой дополнительной точностью, и не выбрал их. Так что, индексы на основе битовых карт по классическому столбцу (пол) обычно игнорируются, несмотря на противоположные утверждения. (Удалите конструкцию work = 40 из запроса и убедитесь, что индекс по столбцу sex в этом случае используется).

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

Размеры

Размер индексов и возможность максимальной буферизации необходимо, конечно, учитывать при определении стоимости, вот почему часто возникает вопрос, - насколько большим будет индекс на основе битовых карт?

В представленном выше примере я попытался воссоздать наихудший случай, максимально затруднив серверу Oracle получение преимуществ от сжатия.

В худшем случае, размер битовой карты в битах будет составлять:

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

Добавьте около 10 процентов на информацию контрольных сумм и накладные расходы, и поделите на 8, чтобы получить размер в байтах.

К счастью, сервер Oracle позволяет предпринять ряд действий для сокращения размера индекса, наиболее действенным из которых является команда, сообщающая серверу, сколько в точности строк в блоке помещается в худшем случае для данной таблицы:

Alter table XXX
      minimize records_per_block;

Однако помимо информирования сервера Oracle с помощью этой команды, очень существенное влияние на размер индекса имеет кластеризация данных.

В примере я создал максимально разбросанные данные. Например, столбец town последовательно получает значения от 0 до 30. Если реструктурировать (по сути, отсортировать) данные так, что информация для всех городов с кодом 0 хранится вместе, а затем идется вся информация для городов с кодом 1, размер индекса можно сократить с 40 Мбайт практически до 7 Мбайт.

Это существенное сокращение размера - еще один повод пересмотреть утверждение о "небольшом количестве различных значений". Потенциальная выгода от наличия индекса на основе битовых карт зависит от кластеризации данных (как и потенциальная выгода от наличия индекса на основе B*-дерева, конечно же). При принятии решения о создании индексов на основе битовых карт, не сбрасывайте со счетов столбцы с "большим" количеством различных значений. Если каждое значение встречается "много" раз, и строки для каждого значения в достаточной степени кластеризованы, то индекс на основе битовых карт очень даже подходит. В таблице со 100 миллионами строк столбец, имеющий 10000 различных значений, может оказаться отличным кандидатом для создания по нему индекса на основе битовых карт.

Вывод

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

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

Надо запомнить следующие ключевые факты:

• Если индекс на основе B*-дерева не является эффективным механизмом доступа к данным, маловероятно, что он станет намного эффективнее, если создавать индекс на основе битовых карт.
• Индексы на основе битовых карт обычно создаются быстрее и могут занимать удивительно мало места.
• Размер индекса на основе битовых карт существенно зависит от распределения данных.
• Индексы на основе битовых карт обычно выбираются стоимостным оптимизатором, если для выполнения запроса можно использовать несколько таких индексов.
• Изменения столбцов, входящих в индексы на основе битовых карт, а также вставки и удаления данных могут вызывать существенные конфликты блокировок.
• Изменения столбцов, входящих в индексы на основе битовых карт, а также вставки и удаления данных могут весьма существенно "ухудшать" индексы.

Помните также, что оптимизатор улучшается в каждой версии Oracle. Граница между механизмами для индексов на основе B*-дерева и битовых карт существенно размывается за счет развития технологий сжатия индексов, просмотра индексов с пропуском (index skip scans), а также преобразования деревьев в битовые карты.

*Сылки: Oracle 9i Release 2 Datawarehousing Guide, Глава 6.