Розбираємося з індексами на основі бітових карт, Інші СУБД, Бази даних, статті

Зміст



Індекси на основі бітових карт – велике благо для деяких видів додатків, але про їх пристрої, використанні і побічних ефектах поширене дуже багато невірної інформації. У цій статті описується структура індексів на основі бітових карт і робиться спроба роз’яснити, чому виникли деякі з найбільш типових помилок, пов’язаних з ними.

Загальновідомо, що …


Якщо провести просте дослідження розуміння розробниками індексів на основі бітових карт, швидше за все, наступні коментарі виявляться найбільш типовими:


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

Звичайно, в цих твердженнях є і невелика частка правди, – достатня, щоб пояснити їхнє походження.

Мета цієї статті – розібратися в структурі індексів на основі бітових карт, перевірити істинність даних тверджень і спробувати з’ясувати переваги індексів на основі бітових карт, а також якою ціною ці переваги досягаються.

Що таке індекс на основі бітової карти?


Індекси створюються, щоб сервер 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 байт, або близько 27 000 бітів. Близько 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 різних значень, навряд чи, на перший погляд, потрапляє під визначення “з невеликою кількістю різних значень”.

Звичайно, описові вирази типу “невеликий”, “маленький”, “близький до нуля” вимагають певного уточнення. Наприклад, чи близько значення 10 000 до нуля? Якщо порівнювати з десятьма мільярдами, то так!

Не використовуйте невизначені вирази на кшталт “невелику кількість”. У більшості випадків, при виборі індексів на основі бітових карт необхідно враховувати тільки два чинники. По-перше, кількість різних блоків в таблиці, в яких може перебувати типове значення індексу – це основний фактор вибору окремого індексу. Зміна структури індексу з B *-дерева на набір бітових карт не зробить цей індекс в це відносно краще чудесним чином. По-друге, використовуваний оптимізатором Oracle механізм комбінування декількох бітових індексів робить їх справді корисними.

Розглянемо наступний приклад, заснований на даних по приблизно 64-мільйонному населенню Великобританії.


Кожному критерію окремо відповідає дуже багато людей, але скільки карооких темноволосих жінок у віці 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 допоможе отримати від них максимальну користь.

Треба запам’ятати такі ключові факти:


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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*