Bitmap-индекс или B*tree-индекс: какой и когда применять?

Источник: oracle

Вивек Шарма

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

Известная мудрость гласит, что bitmap-индексы более применимы для столбцов, имеющих мало различающихся значений - таких как ПОЛ, СЕМЕЙНОЕ_ПОЛОЖЕНИЕ и РОДСТВО. Однако, это предположение не всегда верно. В реальности применение bitmap-индекса всегда целесообразно в системах, в которых данные редко изменяются многими одновременно работающими задачами. Фактически, как я далее продемонстрирую в этой статье, bitmap-индекс для столбца со 100% уникальными значениями (этот столбец может быть первичным ключом) может быть также эффективен, как и индекс B*tree.

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

Сравнение индексов

Среди недостатков bitmap-индекса для уникального столбца есть потребность в достаточно большом пространстве (и поэтому Oracle не рекомендует его). Однако, размер bitmap-индекса зависит от селективности столбца, на котором он построен, а также от распределения данных. Поэтому bitmap-индекс на столбец ПОЛ будет меньше, чем B*tree-индекс на тот же самый столбец. С другой стороны, bitmap-индекс для EMPNO (кандидат в первичные ключи) будет намного больше, чем B*tree-индекс на этот же столбец. Однако, так как к системам поддержки принятия решений (decision-support systems - DSS) имеют доступ меньшее число пользователей, чем к системам обработки транзакций (transaction-processing systems - OLTP), то ресурсы - это не проблема для этих приложений.

Для иллюстрации этого, я создал две таблицы, TEST_NORMAL и TEST_RANDOM. В таблицу TEST_NORMAL добавил миллион строк с помощью PL/SQL-блока, а затем эти строки вставил в таблицу TEST_RANDOM в произвольном порядке:

Create table test_normal (empno number(10), ename varchar2(30), sal number(10));

Begin
For i in 1..1000000
Loop
   Insert into test_normal 
   values(i, dbms_random.string('U',30), dbms_random.value(1000,7000));
   If mod(i, 10000) = 0 then
   Commit;
  End if;
End loop;
End;
/
  
Create table test_random 
as 
select /*+ append */ * from test_normal order by dbms_random.random;

SQL> select count(*) "Total Rows" from test_normal;

Total Rows
----------
   1000000

Elapsed: 00:00:01.09

SQL> select count(distinct empno) "Distinct Values" from test_normal;

Distinct Values
---------------
        1000000

Elapsed: 00:00:06.09
SQL> select count(*) "Total Rows" from test_random;

Total Rows
----------
   1000000

Elapsed: 00:00:03.05
SQL> select count(distinct empno) "Distinct Values" from test_random;

Distinct Values
---------------
        1000000

Elapsed: 00:00:12.07

Заметьте, что таблица TEST_NORMAL заполнена последовательно, а таблица TEST_RANDOM создана с произвольным порядком записей и поэтому содержит неорганизованные данные. В этой таблице столбец EMPNO имеет 100% различных значений и является хорошим кандидатом в первичные ключи. Если определить этот столбец как первичный ключ, будет создан B*tree-индекс, а не bitmap-индекс, потому что Oracle не поддерживает bitmap-индексы для первичных ключей.

Чтобы проанализировать поведение этих индексов, выполним следующие шаги:

Для TEST_NORMAL:
1. Создаем bitmap-индекс для столбца EMPNO и выполняем несколько запросов с предикатом равенства.
2. Создаем B*tree индекс для столбца EMPNO, выполняем несколько запросов с предикатом равенства и сравниваем операции логического и физического ввода/вывода этих запросов, выполняемые для извлечения результатов для этих наборов значений.
Для TEST_RANDOM:
1. То же самое что и Шаг 1A.
2. То же самое что и Шаг 1B.
Для TEST_NORMAL:
1. То же самое что и Шаг 1A, только запросы выполняем с диапазоном предикатов.
2. То же самое что и Шаг 1B, только запросы выполняем с диапазоном предикатов. Сравниваем статистику.
Для TEST_RANDOM:
1. То же самое что и Шаг 3A.
2. То же самое что и Шаг 3B.
Для TEST_NORMAL:
1. Создаем bitmap-индекс для столбца SAL, и затем выполняем несколько запросов с предикатом равенства и несколько с диапазонным предикатом.
2. Создаем B*tree индекс для столбца SAL, и затем выполняем несколько запросов с предикатом равенства и несколько с диапазонным предикатом (тот же набор значений, как на Шаге 5A). Сравниваем операции ввода/вывода запросов, выполняемые для извлечения результатов.
Добавляем столбец GENDER в обе таблицы, и выполним update этого столбца, установив три возможных значения: M для мужского пола, F для женского пола, и null, если пол не задан. Значения этого столбца устанавливаются по одному и тому же условию.
Создаем bitmap-индекс для этого столбца, и затем выполняем несколько запросов с предикатом равенства.
Создаем B*tree индекс для столбца GENDER, и затем выполняем несколько запросов с предикатом равенства. Сравниваем результаты с Шагом 7.

Шаги с 1 по 4 выполняются для столбца с высокой селективностью (100% различных значений), Шаг 5 для столбца со средней селективностью, а Шаги 7 и 8 с низкой селективностью.

Шаг 1A (для TEST_NORMAL)

На этом шаге мы создадим bitmap-индекс на таблицу TEST_NORMAL и затем проверим размер индекса, его фактор кластеризации, и размер таблицы. Затем мы выполним несколько запросов с предикатом равенства и зафиксируем количество операций ввода/вывода запросов, использующих этот bitmap-индекс.

SQL> create bitmap index normal_empno_bmx on test_normal(empno);
Index created.
Elapsed: 00:00:29.06

SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.
Elapsed: 00:00:19.01

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3* where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_BMX');
 
SEGMENT_NAME                               Size in MB
------------------------------------       ---------------
TEST_NORMAL                                50
NORMAL_EMPNO_BMX                           28

Elapsed: 00:00:02.00
SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                             CLUSTERING_FACTOR
------------------------------         ---------------------------------
NORMAL_EMPNO_BMX                       1000000

Elapsed: 00:00:00.00

Вы видите, что размер индекса 28MB и что фактор кластеризации равен количеству строк в таблице. Теперь выполним запросы с предикатом равенства по различным наборам значений:

SQL> set autotrace only
SQL> select * from test_normal where empno=&empno;
Enter value for empno: 1000
old   1: select * from test_normal where empno=&empno
new   1: select * from test_normal where empno=1000

Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_EMPNO_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        515  bytes sent via SQL*Net to client
        499  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Шаг 1B (для TEST_NORMAL)

Теперь удалим этот bitmap-индекс и создадим B*tree индекс на столбец EMPNO. Как и раньше, проверим размер индекса и фактор кластеризации и выполним эти же запросы по тем же наборам значений, чтобы сравнить ввод/вывод.

SQL> drop index NORMAL_EMPNO_BMX;
Index dropped.

SQL> create index normal_empno_idx on test_normal(empno);
Index created.

SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3  where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_IDX');

SEGMENT_NAME                               Size in MB
----------------------------------         ---------------
TEST_NORMAL                                50
NORMAL_EMPNO_IDX                           18

SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                            CLUSTERING_FACTOR
----------------------------------    ----------------------------------
NORMAL_EMPNO_IDX                      6210

Видно, что B*tree индекс меньше, чем bitmap-индекс на столбец EMPNO. Фактор кластеризации B*tree индекса существенно ближе к количеству блоков таблицы; поэтому B*tree индекс эффективен для запросов с диапазонным предикатом.

Теперь выполним эти же запросы по тому же набору значений, используя наш B*tree индекс.

SQL> set autot trace
SQL> select * from test_normal where empno=&empno;
Enter value for empno: 1000
old   1: select * from test_normal where empno=&empno
new   1: select * from test_normal where empno=1000

Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
   2    1     INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)

Statistics
----------------------------------------------------------
         29  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        515  bytes sent via SQL*Net to client
        499  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Видно, что когда запросы выполнены по набору различающихся значений, число consistent gets и physical reads идентично для bitmap и B*tree индексов на 100% уникальном столбце.

BITMAP		EMPNO	*BTREE**
consistent gets	physical reads	EMPNO	consistent gets	physical reads
5	0	1000	5	0
5	2	2398	5	2
5	2	8545	5	2
5	2	98008	5	2
5	2	85342	5	2
5	2	128444	5	2
5	2	858	5	2

Шаг 2A (для TEST_RANDOM)

Теперь выполним такой же эксперимент над TEST_RANDOM:

SQL> create bitmap index random_empno_bmx on test_random(empno);
Index created.

SQL> analyze table test_random compute statistics for table for all indexes for all indexed columns;
Table analyzed.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3* where segment_name in ('TEST_RANDOM','RANDOM_EMPNO_BMX');
 
SEGMENT_NAME                               Size in MB
------------------------------------       ---------------
TEST_RANDOM                                50
RANDOM_EMPNO_BMX                           28

SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                             CLUSTERING_FACTOR
------------------------------         ---------------------------------
RANDOM_EMPNO_BMX                       1000000

Опять статистика (размер и фактор кластеризации) идентична для этих индексов со статистикой по таблице TEST_NORMAL:

SQL> select * from test_random where empno=&empno;
Enter value for empno: 1000
old   1: select * from test_random where empno=&empno
new   1: select * from test_random where empno=1000

Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP INDEX (SINGLE VALUE) OF 'RANDOM_EMPNO_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        515  bytes sent via SQL*Net to client
        499  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Шаг 2B (для TEST_RANDOM)

Теперь, на Шаге 1B (видимо, должно быть 2В - примечание перев.) удалим bitmap-индекс и создадим B*tree индекс на столбец EMPNO.

SQL> drop index RANDOM_EMPNO_BMX;
Index dropped.

SQL> create index random_empno_idx on test_random(empno);
Index created.

SQL> analyze table test_random compute statistics for table for all indexes for all indexed columns;
Table analyzed.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3  where segment_name in ('TEST_RANDOM','RANDOM_EMPNO_IDX');

SEGMENT_NAME                               Size in MB
----------------------------------         ---------------
TEST_RANDOM                                50
RANDOM_EMPNO_IDX                           18

SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                            CLUSTERING_FACTOR
----------------------------------    ----------------------------------
RANDOM_EMPNO_IDX                      999830

Результат показывает, что размер индекса равен размеру этого индекса для таблицы TEST_NORMAL, но фактор кластеризации более близок к количеству строк, что делает этот индекс неэффективным для запросов с диапазонным предикатом (его мы увидим на Шаге 4). Этот фактор кластеризации не будет влиять на запросы с предикатом равенства, потому что строки имеют 100% различающихся значений и количество строк на значение равно 1.

Теперь выполним запросы с предикатом равенства и тем же самым набором значений.

SQL> select * from test_random where empno=&empno;
Enter value for empno: 1000
old   1: select * from test_random where empno=&empno
new   1: select * from test_random where empno=1000

Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
   2    1     INDEX (RANGE SCAN) OF 'RANDOM_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        515  bytes sent via SQL*Net to client
        499  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Опять результаты полностью идентичны полученным на Шаге 1A и Шаге 1B. Распределение данных не повлияло на количество consistent gets и physical reads для уникального столбца.

Шаг 3A (для TEST_NORMAL)

На этом шаге мы создадим bitmap-индекс (как на Шаге 1A). Мы знаем размер и фактор кластеризации индекса, который равен количеству строк таблицы. Теперь выполним несколько запросов с диапазонными предикатами.

SQL> select * from test_normal where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old   1: select * from test_normal where empno between &range1 and &range2
new   1: select * from test_normal where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:00.03

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=451 Card=2299 Bytes=78166)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=451 Card=2299 Bytes=78166)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        331  consistent gets
          0  physical reads
          0  redo size
     111416  bytes sent via SQL*Net to client
       2182  bytes received via SQL*Net from client
        155  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       2300  rows processed

Шаг 3B (для TEST_NORMAL)

На этом шаге выполним запросы по таблице TEST_NORMAL с B*tree индексом.

SQL> select * from test_normal where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old   1: select * from test_normal where empno between &range1 and &range2
new   1: select * from test_normal where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:00.02

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=23 Card=2299 Bytes=78166)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=23 Card=2299 Bytes=78166)
   2    1     INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=8 Card=2299)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        329  consistent gets
         15  physical reads
          0  redo size
     111416  bytes sent via SQL*Net to client
       2182  bytes received via SQL*Net from client
        155  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       2300  rows processed

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

BITMAP		EMPNO (Range)	*BTREE**
consistent gets	physical reads	EMPNO (Range)	consistent gets	physical reads
331	0	1-2300	329	0
285	0	8-1980	283	0
346	19	1850-4250	344	16
427	31	28888-31850	424	28
371	27	82900-85478	367	23
2157	149	984888-1000000	2139	35

Как видите, что количество consistent gets и physical reads обоих индексов опять почти идентичны. Последний диапазон (984888-1000000) возвратил целых 15,000 строк, т.е. наибольшее количество строк из всех извлеченных по остальным диапазонам. Поэтому, когда мы запросили full scan по таблице (указав хинт /*+ full(test_normal) */ ), количество consistent gets и physical reads было 7,239 и 5,663, соответственно.

Шаг 4A (для TEST_RANDOM)

На этом шаге мы выполним запросы с диапазонными предикатами по таблице TEST_RANDOM с bitmap-индексом и сверим последовательные consistent gets и physical reads. Здесь вы увидите влияние фактора кластеризации.

SQL>select * from test_random where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old   1: select * from test_random where empno between &range1 and &range2
new   1: select * from test_random where empno between 1 and 2300

2300 rows selected.
Elapsed: 00:00:08.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=453 Card=2299 Bytes=78166)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=453 Card=2299 Bytes=78166)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP INDEX (RANGE SCAN) OF 'RANDOM_EMPNO_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       2463  consistent gets
       1200  physical reads
          0  redo size
     111416  bytes sent via SQL*Net to client
       2182  bytes received via SQL*Net from client
        155  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       2300  rows processed

Шаг 4B (для TEST_RANDOM)

На этом шаге мы выполним запросы с диапазонным предикатом по таблице TEST_RANDOM с B*tree индексом. Повторю, что фактор кластеризации этого индекса был очень близок к количеству строк в таблице (и поэтому неэффективен). Ниже показано, что об этом сообщает оптимизатор:

SQL> select * from test_random where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old   1: select * from test_random where empno between &range1 and &range2
new   1: select * from test_random where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:03.04

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=613 Card=2299 Bytes=78166)
   1    0   TABLE ACCESS (FULL) OF 'TEST_RANDOM' (Cost=613 Card=2299 Bytes=78166)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       6415  consistent gets
       4910  physical reads
          0  redo size
     111416  bytes sent via SQL*Net to client
       2182  bytes received via SQL*Net from client
        155  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       2300  rows processed

Оптимизатор предпочел full scan таблицы, а не использование индекса, потому что фактор кластеризации:

BITMAP		EMPNO (Range)	*BTREE**
consistent gets	physical reads	EMPNO (Range)	consistent gets	physical reads
2463	1200	1-2300	6415	4910
2114	31	8-1980	6389	4910
2572	1135	1850-4250	6418	4909
3173	1620	28888-31850	6456	4909
2762	1358	82900-85478	6431	4909
7254	3329	984888-1000000	7254	4909

Только для последнего диапазона (984888-1000000) оптимизатор предпочел full scan таблицы с bitmap-индексом, тогда как для всех остальных диапазонов он предпочел full scan таблицы с B*tree индексом. Это несоответствие образовалось вследствие фактора кластеризации: Оптимизатор не принимает во внимание значение фактора кластеризации, когда генерирует план выполнения с использованием bitmap-индекса, тогда как для B*tree индекса, он это делает. В этом сценарии bitmap-индекс выполняется более эффективно, чем B*tree индекс.

Нижеследующие шаги показывают более интересные детали об этих индексах.

Шаг 5A (для TEST_NORMAL)

Создаем bitmap-индекс на столбец SAL таблицы TEST_NORMAL. Этот столбец имеет нормальную селективность.

SQL> create bitmap index normal_sal_bmx on test_normal(sal);
Index created.

SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.

Теперь давайте получим размер индекса и фактор кластеризации.

SQL>select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2* from user_segments
  3* where segment_name in ('TEST_NORMAL','NORMAL_SAL_BMX');

SEGMENT_NAME                                Size in MB
------------------------------              --------------
TEST_NORMAL                                 50
NORMAL_SAL_BMX                              4

SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                             CLUSTERING_FACTOR
------------------------------         ----------------------------------
NORMAL_SAL_BMX                         6001

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

SQL> set autot trace
SQL> select * from test_normal where sal=&sal;
Enter value for sal: 1869
old   1: select * from test_normal where sal=&sal
new   1: select * from test_normal where sal=1869

164 rows selected.
Elapsed: 00:00:00.08

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=39 Card=168 Bytes=4032)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=39 Card=168 Bytes=4032)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        165  consistent gets
          0  physical reads
          0  redo size
       8461  bytes sent via SQL*Net to client
        609  bytes received via SQL*Net from client
         12  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        164  rows processed

И затем с диапазонными предикатами:

SQL> select * from test_normal where sal between &sal1 and &sal2;
Enter value for sal1: 1500
Enter value for sal2: 2000
old   1: select * from test_normal where sal between &sal1 and &sal2
new   1: select * from test_normal where sal between 1500 and 2000

83743 rows selected.
Elapsed: 00:00:05.00

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes=2001024)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=83376 Bytes=2001024)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
      11778  consistent gets
       5850  physical reads
          0  redo size
    4123553  bytes sent via SQL*Net to client
      61901  bytes received via SQL*Net from client
       5584  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
      83743  rows processed

Теперь удалим bitmap-индекс и создадим B*tree индекс на TEST_NORMAL.

SQL> create index normal_sal_idx on test_normal(sal);
Index created.

SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.

Взгляните на размер индекса и фактор кластеризации.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3  where segment_name in ('TEST_NORMAL','NORMAL_SAL_IDX');

SEGMENT_NAME                         Size in MB
------------------------------       ---------------
TEST_NORMAL                          50
NORMAL_SAL_IDX                       17

SQL> select index_name, clustering_factor from user_indexes;

INDEX_NAME                           CLUSTERING_FACTOR
------------------------------       ----------------------------------
NORMAL_SAL_IDX                       986778

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

Теперь для тестов; сначала предикаты равенства:

SQL> set autot trace
SQL> select * from test_normal where sal=&sal;
Enter value for sal: 1869
old   1: select * from test_normal where sal=&sal
new   1: select * from test_normal where sal=1869

164 rows selected.
Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=169 Card=168 Bytes=4032)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=169 Card=168 Bytes=4032)
   2    1     INDEX (RANGE SCAN) OF 'NORMAL_SAL_IDX' (NON-UNIQUE) (Cost=3 Card=168)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        177  consistent gets
          0  physical reads
          0  redo size
       8461  bytes sent via SQL*Net to client
        609  bytes received via SQL*Net from client
         12  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        164  rows processed

...и затем диапазонные предикаты:

SQL> select * from test_normal where sal between &sal1 and &sal2;
Enter value for sal1: 1500
Enter value for sal2: 2000
old   1: select * from test_normal where sal between &sal1 and &sal2
new   1: select * from test_normal where sal between 1500 and 2000

83743 rows selected.
Elapsed: 00:00:04.03

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes
          =2001024)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=83376
          Bytes=2001024)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
      11778  consistent gets
       3891  physical reads
          0  redo size
    4123553  bytes sent via SQL*Net to client
      61901  bytes received via SQL*Net from client
       5584  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
      83743  rows processed

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

BITMAP		SAL (Equality)	*BTREE**		Извлечено строк
consistent gets	physical reads	SAL (Equality)	consistent gets	physical reads	Извлечено строк
165	0	1869	177	164
169	163	3548	181	167
174	166	6500	187	172
75	69	7000	81	73
177	163	2500	190	175

BITMAP		SAL (Range)	*BTREE**		Извлечено строк
consistent gets	physical reads	SAL (Range)	consistent gets	physical reads	Извлечено строк
11778	5850	1500-2000	11778	3891	83743
11765	5468	2000-2500	11765	3879	83328
11753	5471	2500-3000	11753	3884	83318
17309	5472	3000-4000	17309	3892	166999
39398	5454	4000-7000	39398	3973	500520

Для диапазонных предикатов оптимизатор предпочитает full scan таблицы для всех различных наборов значений - он не использует индексы вообще - в то время как для предикатов равенства оптимизатор использует индексы. И опять количество consistent gets и physical reads совпадает.

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

Шаг 6 (добавление столбца GENDER)

Перед выполнением теста в отношении столбца с низкой селективностью, давайте добавим столбец GENDER в эту таблицу и выполним для него update со значениями M, F, и null.

SQL> alter table test_normal add GENDER varchar2(1);
Table altered.

SQL> select GENDER, count(*) from test_normal group by GENDER;

S     COUNT(*)
-     ----------
F     333769
M     499921
      166310

3 rows selected.

Размер bitmap-индекса по этому столбцу примерно 570KB, как показано ниже:

SQL> create bitmap index normal_GENDER_bmx on test_normal(GENDER);
Index created.
Elapsed: 00:00:02.08

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3  where segment_name in ('TEST_NORMAL','NORMAL_GENDER_BMX');

SEGMENT_NAME                        Size in MB
------------------------------      ---------------
TEST_NORMAL                         50
NORMAL_GENDER_BMX                   .5625

2 rows selected.

С другой стороны, B*tree индекс на этот столбец имеет размер 13MB, который намного больше, чем bitmap-индекс на этот столбец.

SQL> create index normal_GENDER_idx on test_normal(GENDER);
Index created.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
  2  from user_segments
  3  where segment_name in ('TEST_NORMAL','NORMAL_GENDER_IDX');

SEGMENT_NAME                       Size in MB
------------------------------     ---------------
TEST_NORMAL                        50
NORMAL_GENDER_IDX                  13

2 rows selected.

Теперь, если выполнить запрос с предикатом равенства, оптимизатор не будет использовать индекс, ни bitmap, ни B*tree. А предпочтет full scan по таблице.

SQL> select * from test_normal where GENDER is null;
166310 rows selected.
Elapsed: 00:00:06.08

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=166310 Bytes=4157750)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=166310 Bytes=4157750)

SQL> select * from test_normal where GENDER='M';

499921 rows selected.

Elapsed: 00:00:16.07

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=499921 Bytes=12498025)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=499921Bytes=12498025)

SQL>select * from test_normal where GENDER='F'
 /

333769 rows selected.

Elapsed: 00:00:12.02

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=333769 Byte
          s=8344225)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=333769
           Bytes=8344225)

Заключение

Теперь, когда мы поняли, как оптимизатор реагирует на эти технические приемы, давайте проверим сценарий, который подробно демонстрирует наилучшее применение bitmap- и B*tree индексов.

Наряду с bitmap-индексом по столбцу GENDER, создадим еще один bitmap-индекс на столбец SAL и затем выполним несколько запросов. Запросы будут выполнены и с B*tree индексами на эти столбцы.

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

Итак:

SQL>select * from test_normal 
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';

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

SQL>select * from test_normal 
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
1453 rows selected.
Elapsed: 00:00:02.03

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=198 Card=754 Bytes=18850)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=198 Card=754 Bytes=18850)
   2    1     BITMAP CONVERSION (TO ROWIDS)
   3    2       BITMAP AND
   4    3         BITMAP OR
   5    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
   6    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
   7    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
   8    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
   9    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
  10    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
  11    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
  12    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
  13    4           BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
  14    3         BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_GENDER_BMX'

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       1353  consistent gets
        920  physical reads
          0  redo size
      75604  bytes sent via SQL*Net to client
       1555  bytes received via SQL*Net from client
         98  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       1453  rows processed

И с B*tree-индексом:

SQL>select * from test_normal 
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
1453 rows selected.
Elapsed: 00:00:03.01

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=754 Bytes=18850)
   1    0   TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=754 Bytes=18850)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       6333  consistent gets
       4412  physical reads
          0  redo size
      75604  bytes sent via SQL*Net to client
       1555  bytes received via SQL*Net from client
         98  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       1453  rows processed

Отсюда видно, что с B*tree индексом, оптимизатор предпочитает full scan по таблице, в то время как в случае с bitmap-индексом, для ответа на запрос он использует индекс. Вы можете проследить за производительностью с помощью количества требуемых операций ввода/вывода, выполняемых для извлечения результата.

Получается, bitmap-индексы лучше всего подходят для DSS-систем независимо от селективности, по следующим причинам:

С bitmap-индексами оптимизатор может эффективно отвечать на запросы, которые включают AND, OR или XOR. (Oracle поддерживает динамическое преобразование B*tree-to-bitmap, однако это может быть неэффективно).
С bitmap-индексами оптимизатор может отвечать на запросы, когда выполняется поиск или подсчет null-ов. Значения null также индексируются в bitmap-индексах (в отличие от B*tree индексов).
Более существенно, что bitmap-индексы в DSS системах поддерживают ad hoc запросы, в то время как B*tree нет. А точнее, если имеется таблица с 50 столбцами и пользователи часто выполняют запросы по 10 из них- иногда комбинации из всех 10 столбцов, а иногда по одному столбцу-создание B*tree индекса будет очень сложным. Если создать 10 bitmap-индексов по всем этим столбцам, все запросы могут использовать эти индексы, выполняется ли запрос по всем 10 столбцам, по 4 или 6 из 10, или по одному столбцу. Хинт AND_EQUAL обеспечивает эту функциональность для B*tree индексов, однако не более, чем пять индексов, которые могут использоваться запросом. Это ограничение не налагается на bitmap-индексы.

С другой стороны, B*tree индексы хорошо применимы для OLTP-приложений, в которых пользовательские запросы достаточно сложны (и хорошо оптимизированы перед промышленным применением), в отличие от ad hoc запросов, которые не такие частые и выполняются во время непиковых нагрузок. Так как данные часто обновляются и удаляются из OLTP-приложений, bitmap-индексы могут повлечь серьезные проблемы блокировки.

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

Ссылки по теме