Hash-klynger kan give O(1)-adgangstid, men ikke O(1)-begrænsningstid. I praksis er den konstante adgangstid for en hash-klynge imidlertid værre end O(log N)-adgangstiden for et almindeligt b-træindeks. Desuden er klynger sværere at konfigurere og skalerer ikke godt til nogle operationer.
Opret Hash-klynge
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;
/
Opret en almindelig tabel (til sammenligning)
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;
/
Sporingseksempel
SQL*Plus Autotrace er en hurtig måde at finde forklaringsplanen og spore I/O-aktivitet pr. sætning. Antallet af I/O-anmodninger er mærket som "konsistente gets" og er en anstændig måde at måle mængden af udført arbejde. Denne kode viser, hvordan tallene blev genereret for andre sektioner. Forespørgslerne skal ofte køres mere end én gang for at varme tingene op.
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>
Find optimale hashnøgler, afvejninger
For optimal læseydelse bør alle hash-kollisioner passe i én blok (al Oracle I/O udføres pr. blok, normalt 8K). Det er svært at få den ideelle opbevaring rigtigt og kræver at kende hash-algoritmen, lagerstørrelsen (ikke det samme som blokstørrelsen) og antallet af hash-nøgler (bøtterne). Oracle har en standardalgoritme og -størrelse, så det er muligt kun at fokusere på én egenskab, nemlig antallet af hash-nøgler.
Flere hash-nøgler fører til færre kollisioner. Dette er godt for TABLE ACCESS HASH ydeevne, da der kun er én blok at læse. Nedenfor er antallet af ensartede gets for forskellige hashkey-størrelser. Til sammenligning er der også inkluderet en indeksadgang. Med nok hashkeys falder antallet af blokke til det optimale antal, 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
Flere hash-nøgler fører også til flere spande, mere spildplads og en langsommere BORDADGANG FULD operation.
Table type Space in MB
HeapTable 24MB
Hashkeys 100 26MB
hashkeys 1000 30MB
hashkeys 10000 81MB
For at reproducere mine resultater skal du bruge en eksempelforespørgsel som select * from orders_cluster where merchantid = 100001 and transactionid = '1'; og ændre den sidste værdi til 1, 20, 300, 4000 og 50000.
Sammenligning af ydeevne
Konsistente gets er forudsigelige og nemme at måle, men i slutningen af dagen er det kun vægurets tid, der betyder noget. Overraskende nok er indeksadgangen med 4 gange mere ensartede gets stadig hurtigere end det optimale hash-klyngescenarie.
--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;
/
Jeg prøvede også testen med variable prædikater, men resultaterne var ens.
Skalerer det?
Nej, hash-klynger skaleres ikke. På trods af O(1)-tidskompleksiteten af TABLE ACCESS HASH og O(log n)-tidskompleksiteten af INDEX UNIQUE SCAN, ser hash-klynger aldrig ud til at overgå b-tree-indekser.
Jeg prøvede ovenstående eksempelkode med 10 millioner rækker. Hash-klyngen var smertefuldt langsom at indlæse og underpræsterede stadig indekset for SELECT-ydeevne. Jeg forsøgte at skalere den op til 100 millioner rækker, men indsættelsen skulle tage 11 dage.
Den gode nyhed er, at b*trees skalerer godt. Tilføjelse af 100 millioner rækker til ovenstående eksempel kræver kun 3 niveauer i indekset. Jeg kiggede på alle DBA_INDEXES for et stort databasemiljø (hundredevis af databaser og en petabyte data) - havde det dårligste indeks kun 7 niveauer. Og det var et patologisk indeks på VARCHAR2(4000) kolonner. I de fleste tilfælde vil dine b-tree-indekser forblive lavvandede uanset tabellens størrelse.
I dette tilfælde slår O(log n) O(1).
Men HVORFOR?
Dårlig hash-klynge-ydelse er måske et offer for Oracles forsøg på at forenkle tingene og skjule den slags detaljer, der er nødvendige for at få en hash-klynge til at fungere godt. Klynger er svære at konfigurere og bruge korrekt og vil sjældent give en væsentlig fordel alligevel. Oracle har ikke lagt en stor indsats i dem i de sidste par årtier.
Kommentatorerne har ret i, at et simpelt b-træindeks er bedst. Men det er ikke indlysende, hvorfor det skulle være sandt, og det er godt at tænke på de algoritmer, der bruges i databasen.