Hash-kluster kan tillhandahålla O(1)-åtkomsttid, men inte O(1)-begränsningstid. I praktiken är emellertid den konstanta åtkomsttiden för ett hashkluster sämre än O(log N) åtkomsttiden för ett vanligt b-trädindex. Dessutom är kluster svårare att konfigurera och skalas inte bra för vissa operationer.
Skapa Hash-kluster
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;
/
Skapa en vanlig tabell (för jämförelse)
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;
/
Spårningsexempel
SQL*Plus Autotrace är ett snabbt sätt att hitta förklaringsplanen och spåra I/O-aktivitet per sats. Antalet I/O-förfrågningar är märkta som "konsekventa hämtar" och är ett anständigt sätt att mäta mängden utfört arbete. Den här koden visar hur siffrorna genererades för andra avsnitt. Frågorna behöver ofta köras mer än en gång för att värma upp saker.
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>
Hitta optimala hashnycklar, avvägningar
För optimal läsprestanda bör alla hashkollisioner passa i ett block (all Oracle I/O görs per block, vanligtvis 8K). Att få den perfekta lagringen rätt är svårt och kräver att man känner till hashalgoritmen, lagringsstorleken (inte samma som blockstorleken) och antalet hashnycklar (hinkarna). Oracle har en standardalgoritm och storlek så det är möjligt att fokusera på endast ett attribut, antalet hash-nycklar.
Fler hash-nycklar leder till färre kollisioner. Detta är bra för TABLE ACCESS HASH-prestanda eftersom det bara finns ett block att läsa. Nedan är antalet konsekventa gets för olika hashkey-storlekar. För jämförelse ingår också en indexåtkomst. Med tillräckligt många hashnycklar minskar antalet block till det optimala antalet, 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
Fler hash-nycklar leder också till fler hinkar, mer slöseri med utrymme och en långsammare BORDÅTKOMST FULL operation.
Table type Space in MB
HeapTable 24MB
Hashkeys 100 26MB
hashkeys 1000 30MB
hashkeys 10000 81MB
För att återskapa mina resultat, använd en exempelfråga som select * from orders_cluster where merchantid = 100001 and transactionid = '1'; och ändra det sista värdet till 1, 20, 300, 4000 och 50000.
Prestandajämförelse
Konsekventa gets är förutsägbara och lätta att mäta, men i slutet av dagen är det bara väggklockans tid som spelar roll. Överraskande nog är indexåtkomsten med 4 gånger mer konsekventa gets fortfarande snabbare än det optimala hash-kluster-scenariot.
--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;
/
Jag provade också testet med variabla predikat men resultaten var liknande.
Skalar den?
Nej, hash-kluster skalas inte. Trots O(1)-tidskomplexiteten för TABLE ACCESS HASH och O(log n)-tidskomplexiteten för INDEX UNIQUE SCAN, verkar hashkluster aldrig överträffa b-tree-index.
Jag provade ovanstående exempelkod med 10 miljoner rader. Hash-klustret var smärtsamt långsamt att ladda och underpresterade fortfarande indexet på SELECT-prestanda. Jag försökte skala upp den till 100 miljoner rader men infogningen skulle ta 11 dagar.
Den goda nyheten är att b*trees skalar bra. Att lägga till 100 miljoner rader till exemplet ovan kräver bara 3 nivåer i indexet. Jag tittade på alla DBA_INDEXES för en stor databasmiljö (hundratals databaser och en petabyte data) - det sämsta indexet hade bara 7 nivåer. Och det var ett patologiskt index på VARCHAR2(4000) kolumner. I de flesta fall kommer dina b-tree-index att förbli ytliga oavsett tabellstorlek.
I detta fall slår O(log n) O(1).
Men VARFÖR?
Dålig hashklusterprestanda är kanske ett offer för Oracles försök att förenkla saker och dölja den typ av detaljer som krävs för att få ett hashkluster att fungera bra. Kluster är svåra att installera och använda på rätt sätt och skulle sällan ge någon betydande fördel ändå. Oracle har inte lagt ner mycket ansträngning på dem under de senaste decennierna.
Kommentatorerna har rätt i att ett enkelt b-trädsindex är bäst. Men det är inte självklart varför det skulle vara sant och det är bra att tänka på algoritmerna som används i databasen.