Index konstantního času pro sloupec řetězce v databázi Oracle

Hash clustery mohou poskytnout přístupový čas O(1), ale ne čas vynucení omezení O(1). V praxi je však konstantní přístupová doba hash clusteru horší než přístupová doba O(log N) běžného indexu b-stromu. Clustery se také obtížněji konfigurují a pro některé operace se špatně škálují.

Vytvořit Hash Cluster

drop table orders_cluster;
drop cluster cluster1;

create cluster cluster1
(
    MerchantID number,
    TransactionID varchar2(20)
)
single table hashkeys 10000; --This number is important, choose wisely!

create table orders_cluster
(
    id number,
    MerchantID number,
    TransactionID varchar2(20)
) cluster cluster1(merchantid, transactionid);

--Add 1 million rows.  20 seconds.
begin
    for i in 1 .. 10 loop
        insert into orders_cluster
        select rownum + i * 100000, mod(level, 100)+ i * 100000, level
        from dual connect by level <= 100000;
        commit;
    end loop;
end;
/

create unique index orders_cluster_idx on orders_cluster(merchantid, transactionid);

begin
    dbms_stats.gather_table_stats(user, 'ORDERS_CLUSTER');
end;
/

Vytvořit běžnou tabulku (pro srovnání)

drop table orders_table;

create table orders_table
(
    id number,
    MerchantID number,
    TransactionID varchar2(20)
) nologging;

--Add 1 million rows.  2 seconds.
begin
    for i in 1 .. 10 loop
        insert into orders_table
        select rownum + i * 100000, mod(level, 100)+ i * 100000, level
        from dual connect by level <= 100000;
        commit;
    end loop;
end;
/

create unique index orders_table_idx on orders_table(merchantid, transactionid);

begin
    dbms_stats.gather_table_stats(user, 'ORDERS_TABLE');
end;
/

Příklad trasování

SQL*Plus Autotrace je rychlý způsob, jak najít plán vysvětlení a sledovat I/O aktivitu na příkaz. Počet I/O požadavků je označen jako „konzistentní get“ a je to slušný způsob měření množství vykonané práce. Tento kód ukazuje, jak byla čísla generována pro jiné sekce. Dotazy je často nutné spustit více než jednou, aby se vše zahřálo.

SQL> set autotrace on;
SQL> select * from orders_cluster where merchantid = 100001 and transactionid = '2';

no rows selected


Execution Plan
----------------------------------------------------------
Plan hash value: 621801084

------------------------------------------------------------------------------------
| Id  | Operation         | Name           | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |                |     1 |    16 |     1   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS HASH| ORDERS_CLUSTER |     1 |    16 |     1   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("MERCHANTID"=100001 AND "TRANSACTIONID"='2')


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

SQL>

Najděte optimální hashkeys, kompromisy

Pro optimální výkon čtení by se všechny hašovací kolize měly vejít do jednoho bloku (všechny I/O Oracle se provádějí na blok, obvykle 8K). Správné nalezení ideálního úložiště je složité a vyžaduje znalost hashovacího algoritmu, velikosti úložiště (ne stejné jako velikost bloku) a počtu hash klíčů (segmentů). Oracle má výchozí algoritmus a velikost, takže je možné se zaměřit pouze na jeden atribut, počet hash klíčů.

Více hash klíčů vede k menšímu počtu kolizí. To je dobré pro výkon TABLE ACCESS HASH, protože existuje pouze jeden blok ke čtení. Níže je uveden počet konzistentních get pro různé velikosti hashkey. Pro srovnání je zahrnut i indexový přístup. S dostatkem hashkeys se počet bloků sníží na optimální počet, 1.

Method          Consistent Gets (for transactionid = 1, 20, 300, 4000, and 50000)
Index           4,  3,  3,  3,  3
Hashkeys 100    1, 31, 31, 31, 31
Hashkeys 1000   1,  3,  4,  4,  4
Hashkeys 10000  1,  1,  1,  1,  1

Více hash klíčů také vede k většímu množství bucketů, plýtvání místem a pomalejšímu provozu TABLE ACCESS FULL.

Table type      Space in MB
HeapTable       24MB
Hashkeys 100    26MB
hashkeys 1000   30MB
hashkeys 10000  81MB

Chcete-li reprodukovat mé výsledky, použijte vzorový dotaz jako select * from orders_cluster where merchantid = 100001 and transactionid = '1'; a změňte poslední hodnotu na 1, 20, 300, 4000 a 50000.

Porovnání výkonu

Konzistentní zisky jsou předvídatelné a snadno měřitelné, ale na konci dne záleží pouze na nástěnných hodinách. Překvapivě je přístup k indexu se 4krát konzistentnějším získáváním stále rychlejší než optimální scénář hash clusteru.

--3.5 seconds for b-tree access.
declare
    v_count number;
begin
    for i in 1 .. 100000 loop
        select count(*)
        into v_count
        from orders_table
        where merchantid = 100000 and transactionid = '1';
    end loop;
end;
/

--3.8 seconds for hash cluster access.
declare
    v_count number;
begin
    for i in 1 .. 100000 loop
        select count(*)
        into v_count
        from orders_cluster
        where merchantid = 100000 and transactionid = '1';
    end loop;
end;
/

Zkoušel jsem také test s proměnnými predikáty, ale výsledky byly podobné.

Změní se měřítko?

Ne, hash clustery se neškálují. Navzdory časové složitosti O(1) TABLE ACCESS HASH a časové složitosti O(log n) INDEX UNIQUE SCAN se zdá, že klastry hash nikdy nepřekonají indexy b-stromu.

Zkoušel jsem výše uvedený ukázkový kód s 10 miliony řádků. Hašovací cluster se načítal bolestně pomalu a stále nedosahoval výkonu indexu při výkonu SELECT. Zkoušel jsem to zvětšit až na 100 milionů řádků, ale vložení bude trvat 11 dní.

Dobrou zprávou je, že b*stromy se dobře škálují. Přidání 100 milionů řádků do výše uvedeného příkladu vyžaduje pouze 3 úrovně v indexu. Podíval jsem se na všechny DBA_INDEXES pro velké databázové prostředí (stovky databází a petabajt dat) - nejhorší index měl pouze 7 úrovní. A to byl patologický index na VARCHAR2(4000) sloupců. Ve většině případů vaše indexy b-stromu zůstanou mělké bez ohledu na velikost tabulky.

V tomto případě O(log n) porazí O(1).

Ale PROČ?

Špatný výkon hash clusteru je možná obětí pokusu společnosti Oracle zjednodušit věci a skrýt takové detaily, které jsou nezbytné k tomu, aby hash cluster dobře fungoval. Clustery se obtížně nastavují a používají správně a jen zřídka by stejně poskytly významný přínos. Oracle do nich v posledních několika desetiletích nevložil příliš mnoho úsilí.

Komentující mají pravdu, že jednoduchý index b-stromu je nejlepší. Není však zřejmé, proč by to měla být pravda, a je dobré se zamyslet nad algoritmy použitými v databázi.