Indeks B*-drzewo a wyszukiwanie wartości NULL

Nie każdy programista pamięta, że struktura indeksu B*-drzewo pomija wartości NULL, czego efektem jest odmowa użycia takiego indeksu do realizacji predykatu IS NULL. Łatwo zaobserwować takie zjawisko wykonując prosty eksperyment. Poniższa tabela DUZA_Z_NULLAMI(A,B) zawiera pół miliona rekordów, wśród których jeden rekord posiada wartość NULL w kolumnie A. Na kolumnie tej utworzony został indeks DEMO_IDX1. Obejrzyjmy plany wykonania dwóch zapytań – jedno wyszukuje rekord według konkretnej niepustej wartości kolumny A, drugie – wyszukuje rekord z wartością pustą.

SQL> select * from duza_z_nullami where a=99999;
...
Plan wykonywania
--------------------------------------------------------------------------------
| Id | Operation                  | Name           | Rows | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------------
| 0  | SELECT STATEMENT           |                | 1    | 206   | 4 (0)      |
| 1  | TABLE ACCESS BY INDEX ROWID| DUZA_Z_NULLAMI | 1    | 206   | 4 (0)      |
|* 2 | INDEX RANGE SCAN           | DEMO_IDX1      | 1    |       | 3 (0)      |
--------------------------------------------------------------------------------
Statystyki
----------------------------------------------------------
151 recursive calls
0 db block gets
24 consistent gets
0 physical reads
...
SQL> select * from duza_z_nullami where a is null;
...
Plan wykonywania
----------------------------------------------------------------------
| Id | Operation        | Name           | Rows | Bytes | Cost (%CPU)|
----------------------------------------------------------------------
| 0  | SELECT STATEMENT |                | 1    | 206   | 4193 (1)   |
|* 1 | TABLE ACCESS FULL| DUZA_Z_NULLAMI | 1    | 206   | 4193 (1)   |
----------------------------------------------------------------------
...
Statystyki
----------------------------------------------------------
1 recursive calls
0 db block gets
15435 consistent gets
0 physical reads

Zgodnie z oczekiwaniami, do wyszukiwania rekordów według wysoce selektywnego predykatu A=99999 wykorzystany został indeks B*-drzewo, natomiast zapytanie posługujące sie predykatem IS NULL (skądinąd bardzo selektywnym) nie mogło użyć indeksu gdyż brakuje w nim referencji do wartości NULL.
Jak sobie poradzić w takiej sytuacji? Rozwiązania są trzy: (1) zastąpić indeks B*-drzewo indeksem bitmapowym, (2) utworzyć indeks funkcyjny na wyrażeniu NVL(), (3) utworzyć indeks złożony (skonkatenowany) na kolumnie A i jakiejś kolumnie niepustej. Zastąpienie indeksu B*-drzewo indeksem bitmapowym nie jest zwykle dobrym pomysłem ze względu na rozłączne obszary zastosowań tych dwóch typów indeksów (B*-drzewo dla kolumn o wysokiej kardynalności, bitmapowy dla kolumn o niskiej kardynalności). Indeks funkcyjny to pomysł dobry, wymaga jednak modyfikacji treści zapytania. Oto przykład:

SQL> create index demo_idx2 on duza_z_nullami(nvl(a,-1));
...
SQL> select * from duza_z_nullami where nvl(a,-1)=-1;
...
Plan wykonywania
--------------------------------------------------------------------------------
| Id | Operation                  | Name           | Rows | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------------
| 0  | SELECT STATEMENT           |                | 5243 | 1054K | 65 (0)     |
| 1  | TABLE ACCESS BY INDEX ROWID| DUZA_Z_NULLAMI | 5243 | 1054K | 65 (0)     |
|* 2 | INDEX RANGE SCAN           | DEMO_IDX2      | 2097 |       | 3 (0)      |
--------------------------------------------------------------------------------
...
Statystyki
----------------------------------------------------------
24 recursive calls
0 db block gets
7 consistent gets
2 physical reads

Indeks został użyty, zgodnie z oczekiwaniami. Moim ulubionym rozwiązaniem jest jednak utworzenie indeksu złożonego, w którym druga kolumna jest stałą. Oto przykład:

SQL> create index demo_idx3 on duza_z_nullami(a,1);
...
SQL> select * from duza_z_nullami where a is null;
...
Plan wykonywania
--------------------------------------------------------------------------------
| Id | Operation                  | Name           | Rows | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------------
| 0  | SELECT STATEMENT           |                | 1    | 206   | 4 (0)      |
| 1  | TABLE ACCESS BY INDEX ROWID| DUZA_Z_NULLAMI | 1    | 206   | 4 (0)      |
|* 2 | INDEX RANGE SCAN           | DEMO_IDX3      | 1    |       | 3 (0)      |
--------------------------------------------------------------------------------
...
Statystyki
----------------------------------------------------------
1 recursive calls
0 db block gets
4 consistent gets
2 physical reads

Zaletą ostatniego rozwiązania jest brak konieczności modyfikacji treści zapytania SQL – występuje w nim nadal predykat IS NULL. Dlaczego jednak tym razem referencja do NULL znajduje się w indeksie B*-drzewo? Otóż w przypadku indeksów złożonych, referencja jest pomijana tylko wtedy, gdy wszystkie indeksowane kolumny maja wartość NULL.
A czy indeks złożony na (A,1) jest dużo większy od indeksu funkcyjnego na NVL(A,-1)? W ramach mojego eksperymentu zmierzone rozmiary indeksów były takie: indeks funkcyjny – 1167 bloków, indeks złożony – 1386 bloków.

2 thoughts on “Indeks B*-drzewo a wyszukiwanie wartości NULL

    • Zamiast przykładowego „-1” moglibyśmy użyć dowolnej innej wartości, która nie występuje w sposób naturalny w kolumnie A w tabeli (bo wtedy oprócz rekordów z NULL odczytalibyśmy też rekordy, które „przypadkiem” zawierają właśnie tę wartość). W podanym przykładzie milcząco założyliśmy, że kolumna A przechowuje liczby naturalne, więc „-1” mogło bezpiecznie reprezentować NULL. Równie dobrze moglibyśmy zamiast „-1” użyć „-9999999” albo „-2”, itp.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *