Les clusters de hachage peuvent fournir un temps d'accès O(1), mais pas un temps d'application de contrainte O(1). Cependant, en pratique, le temps d'accès constant d'un cluster de hachage est pire que le temps d'accès O (log N) d'un index b-tree régulier. De plus, les clusters sont plus difficiles à configurer et ne s'adaptent pas bien à certaines opérations.
Créer un cluster de hachage
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;
/
Créer un tableau normal (pour comparaison)
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;
/
Exemple de suivi
SQL*Plus Autotrace est un moyen rapide de trouver le plan d'exécution et de suivre l'activité d'E/S par instruction. Le nombre de requêtes d'E/S est étiqueté comme « obtentions cohérentes » et constitue un moyen décent de mesurer la quantité de travail effectué. Ce code montre comment les numéros ont été générés pour les autres sections. Les requêtes doivent souvent être exécutées plusieurs fois pour réchauffer les choses.
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>
Trouvez les clés de hachage optimales et les compromis
Pour des performances de lecture optimales, toutes les collisions de hachage doivent tenir dans un bloc (toutes les E/S Oracle sont effectuées par bloc, généralement 8K). Obtenir le bon stockage idéal est délicat et nécessite de connaître l'algorithme de hachage, la taille du stockage (différente de la taille du bloc) et le nombre de clés de hachage (les compartiments). Oracle a un algorithme et une taille par défaut, il est donc possible de se concentrer sur un seul attribut, le nombre de clés de hachage.
Plus de clés de hachage entraînent moins de collisions. C'est bon pour les performances de TABLE ACCESS HASH car il n'y a qu'un seul bloc à lire. Vous trouverez ci-dessous le nombre d'obtentions cohérentes pour différentes tailles de clés de hachage. Pour comparaison, un accès à l'index est également inclus. Avec suffisamment de hashkeys, le nombre de blocs diminue jusqu'au nombre optimal, 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
Plus de clés de hachage entraînent également plus de compartiments, plus d'espace perdu et une opération TABLE ACCESS FULL plus lente.
Table type Space in MB
HeapTable 24MB
Hashkeys 100 26MB
hashkeys 1000 30MB
hashkeys 10000 81MB
Pour reproduire mes résultats, utilisez un exemple de requête comme select * from orders_cluster where merchantid = 100001 and transactionid = '1'; et changez la dernière valeur en 1, 20, 300, 4000 et 50000.
Comparaison des performances
Les gains réguliers sont prévisibles et faciles à mesurer, mais en fin de compte, seule l'heure de l'horloge murale compte. Étonnamment, l'accès à l'index avec des obtentions 4 fois plus cohérentes est toujours plus rapide que le scénario de cluster de hachage optimal.
--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;
/
J'ai aussi essayé le test avec des prédicats variables mais les résultats étaient similaires.
Est-ce que cela évolue ?
Non, les clusters de hachage ne sont pas évolutifs. Malgré la complexité temporelle O(1) de TABLE ACCESS HASH et la complexité temporelle O(log n) de INDEX UNIQUE SCAN, les clusters de hachage ne semblent jamais surpasser les index b-tree.
J'ai essayé l'exemple de code ci-dessus avec 10 millions de lignes. Le cluster de hachage était extrêmement lent à charger et sous-performait toujours l'index sur les performances SELECT. J'ai essayé de le mettre à l'échelle jusqu'à 100 millions de lignes, mais l'insertion allait prendre 11 jours.
La bonne nouvelle est que les b*trees évoluent bien. L'ajout de 100 millions de lignes à l'exemple ci-dessus ne nécessite que 3 niveaux dans l'index. J'ai regardé tous les DBA_INDEXES pour un grand environnement de bases de données (des centaines de bases de données et un pétaoctet de données) - le pire index n'avait que 7 niveaux. Et c'était un index pathologique sur VARCHAR2(4000) Colonnes. Dans la plupart des cas, vos index b-tree resteront peu profonds quelle que soit la taille de la table.
Dans ce cas, O(log n) bat O(1).
Mais POURQUOI ?
Les mauvaises performances du cluster de hachage sont peut-être une victime de la tentative d'Oracle de simplifier les choses et de masquer le type de détails nécessaires au bon fonctionnement d'un cluster de hachage. Les clusters sont difficiles à configurer et à utiliser correctement et offriraient de toute façon rarement un avantage significatif. Oracle n'y a pas consacré beaucoup d'efforts au cours des dernières décennies.
Les commentateurs ont raison de dire qu'un simple index b-tree est le meilleur. Mais la raison pour laquelle cela devrait être vrai n'est pas évidente et il est bon de réfléchir aux algorithmes utilisés dans la base de données.
