Indexation : HASH - partie 1

La fin du bannissement ?

      Les Hash Index existent depuis très longtemps dans PostgreSQL mais leur usage était découragé pour plusieurs raisons. D’abord parce qu’il n’était pas évident qu’ils permettaient d’obtenir de meilleures performances que les index B-Tree, tout en étant plus lourds que ces derniers. Ensuite et surtout parce qu’ils n’étaient pas journalisés. Il fallait donc les reconstruire après un crash et ils étaient incompatibles avec les hot standby par exemple.
      La restriction sur les performances a disparu de la documentation en 8.4. La restriction sur la journalisation a été levée en version 10. Les Hash Index présentent-ils vraiment un avantage dans les cas où ils sont théoriquement supérieurs aux B-Tree ? Il faut d’abord déterminer un cas d’utilisation. Pour cela nous allons nous appuyer sur le livre de Guillaume Lelarge "Architecture et notions avancées" dans lequel il écrit que les Hash Index reposent sur un principe simple. Plutôt que d’indexer la valeur de la colonne, c’est un entier correspondant à la valeur de hachage de cette colonne qui est indexé. Quel intérêt ? Tester l’égalité entre 2 entiers est plus rapide que d’autres tests d’égalité.
      Si votre critère est un intervalle entre 2 TIMESTAMP ou si la colonne à indexer est de type SMALLINT alors passez votre chemin. Mais si la requête implique de tester des égalités sur une colonne texte alors ce principe est potentiellement intéressant. La réalité rejoint-elle la théorie dans un environnement disposant d’une mémoire vive suffisante pour mettre complètement en cache les données ? Démonstration avec PostgreSQL 10 beta :

select version(); version ----------------------------------------------------------------------------------------------------- PostgreSQL 10beta1 on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18) 6.3.0 20170516, 64-bit (1 ligne) create table geants( idg integer generated always as identity, idu uuid, genre char(1), taille smallint, masse smallint, actif boolean, devise varchar(128), pw smallint, heureux boolean, couleur varchar(8), veteran boolean, clan smallint, gabarit varchar(8), revenu integer, pm smallint, berserk boolean, tutelaire smallint, ere varchar(10), cyclope boolean); CREATE TABLE CREATE EXTENSION IF NOT EXISTS "uuid-ossp"; NOTICE: l'extension "uuid-ossp" existe déjà, poursuite du traitement CREATE EXTENSION WITH serie(i, r1) AS (SELECT generate_series(1,1000000,1), random()) insert into geants(idu, genre, taille, masse, actif, devise, pw, heureux, couleur, veteran, clan, gabarit, revenu, pm, berserk, tutelaire, ere, cyclope) select uuid_generate_v4(), case when random() < 0.45 then 'M' else 'F' end, 200 + (trunc(random() * 200 + 1)), 300 + (trunc(random() * 200 + 1)), case when random() < 0.01 then false when random() > 0.5 and random() < 0.99 then false else true end, upper(md5(random()::text)), (trunc(random()*100 + 1)), case when random() < 0.1 then false else true end, case when r1 <= 0.29998 then 'GRIS' when r1 <= 0.59998 then 'NOIR' else 'BLEU' end, case when random() < 0.9 then false else true end, (trunc(random()*1000 + 1)), case when r1 <= 0.29999 then 'PETIT' when r1 <= 0.59999 then 'MOYEN' else 'GRAND' end, (trunc(random()*1000000 + 1)), (trunc(random()*10 + 1)), case when r1 <= 0.3 then true when r1 <= 0.6 then false else null end, (trunc(random()*10 + 1)), case when r1 <= 0.30001 then 'TAUREAU' when r1 <= 0.60001 then 'LICORNE' else 'DRAGON' end, case when r1 <= 0.30002 then true when r1 <= 0.60002 then false else null end from serie; INSERT 0 1000000 analyze geants; ANALYZE create temporary table chaos as select devise from geants order by random() fetch first 50000 rows only; SELECT 50000 analyze chaos; ANALYZE explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN -------------------------------------------------------------------------- Hash Join (cost=1933.00..55046.03 rows=54603 width=16) Hash Cond: ((g.devise)::text = (c.devise)::text) -> Seq Scan on geants g (cost=0.00..26394.00 rows=1000000 width=49) -> Hash (cost=917.00..917.00 rows=50000 width=33) -> Seq Scan on chaos c (cost=0.00..917.00 rows=50000 width=33) (5 lignes) select idu from chaos c join geants g on (c.devise = g.devise); Temps : 917,133 ms ... Temps : 940,826 ms ... Temps : 908,716 ms create index geants_i1 on geants(devise); CREATE INDEX Time: 7825,385 ms (00:07,825) \di+ geants_i1 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+-----------+-------+--------------+--------+--------+------------- public | geants_i1 | index | postgres | geants | 56 MB | (1 ligne) set random_page_cost=1; SET explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN --------------------------------------------------------------------------------- Nested Loop (cost=0.42..47146.00 rows=54603 width=16) -> Seq Scan on chaos c (cost=0.00..917.00 rows=50000 width=33) -> Index Scan using geants_i1 on geants g (cost=0.42..0.91 rows=1 width=49) Index Cond: ((devise)::text = (c.devise)::text) (4 lignes) select idu from chaos c join geants g on (c.devise = g.devise); Time: 1015,554 ms (00:01,016) ... Time: 1020,591 ms (00:01,021) ... Time: 1036,417 ms (00:01,036) create index geants_h1 on geants using hash(devise); CREATE INDEX Time: 3744,218 ms (00:03,744) \di+ geants_h1 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+-----------+-------+--------------+--------+--------+------------- public | geants_h1 | index | postgres | geants | 32 MB | (1 ligne) explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN --------------------------------------------------------------------------------- Nested Loop (cost=0.00..22784.00 rows=54603 width=16) -> Seq Scan on chaos c (cost=0.00..917.00 rows=50000 width=33) -> Index Scan using geants_h1 on geants g (cost=0.00..0.43 rows=1 width=49) Index Cond: ((devise)::text = (c.devise)::text) (4 lignes) select idu from chaos c join geants g on (c.devise = g.devise); Temps : 546,828 ms ... Temps : 557,282 ms ... Temps : 549,019 ms

      Les données varchar de la colonne devise ont toujours une longueur de 32 caractères. Le Hash Index obtenu a été créé en 3s7 et sa taille est inférieure (32Mo) à celle de l’index B-Tree (56Mo) qui a été créé en 7s8.
      Un plan d’exécution impliquant une boucle comprenant 50000 index scan montre un net avantage de l’index Hash (0s55) sur l’index B-Tree (1s). Il faut noter que l’index B-Tree dont l’utilisation a été implicitement conseillée au planner en positionnant random_page_cost à 1 n’est pas convaincant. En effet, sans index, la requête basée sur un hash join exécuté à 100% en mémoire durait 0s9.
      Les index B-Tree permettent depuis la version 9.2 d’éviter complètement de passer par la table lorsque toutes les colonnes nécessaires à la requête sont indexées. Les Index Hash tiennent-ils toujours la comparaison contre un index B-Tree composite adapté à la requête exécutée dans la première partie ? Démonstration :

drop index geants_h1; DROP INDEX create index geants_h2 on geants using hash(devise, idu); ERREUR: la méthode d'accès "hash" ne supporte pas les index multi-colonnes create index geants_i2 on geants(devise, idu); CREATE INDEX Time: 8893,841 ms (00:08,894) \di+ geants_i2 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+-----------+-------+--------------+--------+--------+------------- public | geants_i2 | index | postgres | geants | 74 MB | (1 ligne) vacuum geants; VACUUM explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN ------------------------------------------------------------------------------------------------ Merge Join (cost=4819.99..32577.97 rows=54603 width=16) Merge Cond: ((c.devise)::text = (g.devise)::text) -> Sort (cost=4819.41..4944.41 rows=50000 width=33) Sort Key: c.devise -> Seq Scan on chaos c (cost=0.00..917.00 rows=50000 width=33) -> Index Only Scan using geants_i2 on geants g (cost=0.55..24462.55 rows=1000000 width=49) (6 lignes) select idu from chaos c join geants g on (c.devise = g.devise); Temps : 962,747 ms ... Temps : 957,969 ms ... Temps : 954,536 ms set work_mem="32MB"; SET explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN ------------------------------------------------------------------------------------------------ Hash Join (cost=1542.55..32800.58 rows=54603 width=16) Hash Cond: ((g.devise)::text = (c.devise)::text) -> Index Only Scan using geants_i2 on geants g (cost=0.55..24462.55 rows=1000000 width=49) -> Hash (cost=917.00..917.00 rows=50000 width=33) -> Seq Scan on chaos c (cost=0.00..917.00 rows=50000 width=33) (5 lignes) select idu from chaos c join geants g on (c.devise = g.devise); Temps : 535,615 ms ... Temps : 540,736 ms ... Temps : 530,329 ms

      L’Index Only Scan a un effet positif puisque le temps passe sous la seconde, il est même possible de passer à 0s54. Mais il faut d’abord noter que l’Index Only Scan n’est possible que parce le B-Tree composite a été construit spécialement pour cette requête. Si par la suite nous nous intéressions à la colonne MASSE en plus de la colonne IDU l’avantage serait annulé.
      Il faut ensuite noter que le temps consacré à créer l’index est passé à 8s9 et qu’il occupe 74Mo d’espace disque. Pour permettre de réaliser une jointure hash en mémoire, le paramètre work_mem a par ailleurs été augmenté dans la session (32Mo au lieu de 4Mo). Cette augmentation générale des moyens est cependant tout juste suffisante pour battre le Hash Index et ses 0s55.
      L’indexation hash confirme donc bien en pratique son avantage théorique dans un cas qui lui est favorable. Mais attention aux excès d’enthousiasme !

Mise à jour : 17/05/2017