Sonntag, November 02, 2014

Bitmap-Index zur Zeilenzählung

Auf die folgende Idee hat mich Richard Foote mit dem jüngsten Artikel seiner Serie zur Index Advanced Compression gebracht, in dem er erläutert, dass Bitmap-Indizes aufgrund ihrer extremen Komprimierbarkeit weiterhin ihre Bedeutung behalten (ein paar Anmerkungen zur Serie habe ich hier notiert). In einer Tabelle, bei der die exakte Kenntnis der Satzanzahl von extremer Bedeutung ist, könnte man diese Information durch Ergänzung eines Bitmap-Index auf einer Spalte mit konstantem Wert sehr effektiv ermitteln. Dazu ein kleines Beispiel:

drop table t;
 
create table t (
    id not null
  , padding
  , count_helper
)  
as
select rownum id
     , lpad('*', 50, '*') padding
     , cast(null as number) count_helper
  from dual
connect by level <= 100000;

create bitmap index t_bix on t(count_helper);
 
create unique index t_ix on t(id);
 
set autot trace
 
select count(*) from t;

-------------------------------------------------------------------------------
| Id  | Operation                     | Name  | Rows  | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |       |     1 |     3   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE               |       |     1 |            |          |
|   2 |   BITMAP CONVERSION COUNT     |       |   100K|     3   (0)| 00:00:01 |
|   3 |    BITMAP INDEX FAST FULL SCAN| T_BIX |       |            |          |
-------------------------------------------------------------------------------

Statistiken
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          7  consistent gets
          3  physical reads
          0  redo size
        365  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

alter index t_bix invisible;

select count(*) from t;

----------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Cost (%CPU)| Time     |
----------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    30  (10)| 00:00:01 |
|   1 |  SORT AGGREGATE       |      |     1 |            |          |
|   2 |   INDEX FAST FULL SCAN| T_IX |   100K|    30  (10)| 00:00:01 |
----------------------------------------------------------------------

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

Der Bitmap-Index auf der Spalte count_helper, die nur NULL-Werte enthält (was den Bitmap-Index - anders als einen B*Tree-Index - nicht berührt) ist winzig und erlaubt die Berechnung der Satzanzahl durch einen sehr billigen BITMAP CONVERSION COUNT: Grundlage sind die minimale und die maximale rowid und die Kenntnis der Anzahl dazwischen liegender Elemente. Wenn man den Bitmap Index als invisible markiert, wird der eindeutige B*Tree-Index auf der (NOT NULL-) Spalte id verwendet, der ebenfalls über einen FAST FULL SCAN eingelesen wird, was aber bei diesem sehr viel größeren Segment sehr viel mehr Arbeit hervorruft (263 consistent gets gegenüber 7 für den bitmap-Fall). Dass der B*Tree-Index so viel größer ist, liegt in erster Linie daran, dass er in den Leaf-Blöcken die rowids der zugehörigen Sätze explizit enthalten muss (während der bitmap-Index eine Offset-basierte Speicherung verwendet). Als NULL-Wert am Satzende bringt der count_helper auch keine deutliche Vergrößerung der Tabelle mit sich. Trotzdem ist diese Idee natürlich nur in ganz speziellen Fällen relevant - nämlich wenn die Kenntnis der genauen Satzanzahl relevant ist und wenn keine massiven konkurrierenden DML-Operationen stattfinden. Aufgrund der massiven Locking-Probleme, die bitmap-Indizes mit sich bringen, sind sie für OLTP-Systeme grundsätzlich eher ungeeignet. Und wenn nur eine ungefähre Kenntnis der Satzanzahl erforderlich ist, kann in 12.1.0.2 auch die neue APPROX_COUNT_DISTINCT verwendet werden. Eine weitere Alternative zum bitmap-Index könnte auch eine Materialized View sein, die die Aggregation in ein zusätzliches Hilfsobjekt verschiebt. Aus Gründen der Vorsicht habe ich die Idee als Kommentar in Richard Footes Blog untergebracht und mir von ihm noch mal bestätigen lassen, dass mir an dieser Stelle kein relevanter Punkt entgangen ist.

Keine Kommentare:

Kommentar veröffentlichen

Hinweis: Nur ein Mitglied dieses Blogs kann Kommentare posten.