Indexation : HASH - partie 2

Les haches ne sont pas près d’abattre Yggdrasil

      Dans cette première partie, nous avons découvert que les index HASH étaient à leur avantage, conformément à la théorie, en remplacement des B-Tree pour indexer les chaînes de caractères et réaliser ensuite des tests d’égalité. Cette efficacité conduit le planner à être plus optimiste dans son estimation du coût d’un Index Scan via un index Hash que via un B-Tree.
      Cet optimisme n’est-il pas excessif dans certains cas ? Pour le savoir, nous allons reprendre la table GEANTS mais cette fois avec 10 millions de lignes, créer une table temporaire CHAOS avec 1 millions de lignes de GEANTS sélectionnées aléatoirement. Nous allons ensuite tenter une jointure entre les 2 tables, d’abord sans index, puis avec un index HASH sur la colonne DEVISE de GEANTS, DEVISE étant la colonne utilisée pour la jointure. Les mêmes tests sont ensuite réalisés en remplaçant CHAOS par ORDO, une table comprenant aussi 1 million de lignes de GEANTS, mais sans tri aléatoire.
      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 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,10000000,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 10000000 analyze geants; ANALYZE create temporary table chaos as select devise from geants order by random() fetch first 1000000 rows only; SELECT 1000000 analyze chaos; ANALYZE show work_mem; work_mem ---------- 4MB show random_page_cost; random_page_cost ------------------ 4 show seq_page_cost; seq_page_cost --------------- 1 explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN ------------------------------------------------------------------------------ Hash Join (cost=38647.00..1391103.27 rows=2289427 width=16) Hash Cond: ((g.devise)::text = (c.devise)::text) -> Seq Scan on geants g (cost=0.00..263935.00 rows=10000000 width=49) -> Hash (cost=18334.00..18334.00 rows=1000000 width=33) -> Seq Scan on chaos c (cost=0.00..18334.00 rows=1000000 width=33) select idu from chaos c join geants g on (c.devise = g.devise); Time: 15272,610 ms (00:15,273) ... Time: 14825,993 ms (00:14,826) ... Time: 15887,924 ms (00:15,888) create index geants_h1 on geants using hash(devise); CREATE INDEX Time: 39562,703 ms (00:39,563) explain select idu from chaos c join geants g on (c.devise = g.devise); QUERY PLAN --------------------------------------------------------------------------------- Nested Loop (cost=0.00..860162.00 rows=2289427 width=16) -> Seq Scan on chaos c (cost=0.00..18334.00 rows=1000000 width=33) -> Index Scan using geants_h1 on geants g (cost=0.00..0.82 rows=2 width=49) Index Cond: ((devise)::text = (c.devise)::text) select idu from chaos c join geants g on (c.devise = g.devise); Time: 36465,809 ms (00:36,466) ... Time: 36397,282 ms (00:36,397) ... Time: 36520,213 ms (00:36,520) create temporary table ordo as select devise from geants fetch first 1000000 rows only; SELECT 1000000 analyze ordo; ANALYZE explain select idu from ordo o join geants g on (o.devise = g.devise); QUERY PLAN --------------------------------------------------------------------------------- Nested Loop (cost=0.00..270041.00 rows=2289433 width=16) -> Seq Scan on ordo o (cost=0.00..18334.00 rows=1000000 width=33) -> Index Scan using geants_h1 on geants g (cost=0.00..0.23 rows=2 width=49) Index Cond: ((devise)::text = (o.devise)::text) select idu from ordo o join geants g on (o.devise = g.devise); Time: 25156,134 ms (00:25,156) ... Time: 25117,249 ms (00:25,117) ... Time: 25045,355 ms (00:25,045) drop index geants_h1; DROP INDEX explain select idu from ordo o join geants g on (o.devise = g.devise); QUERY PLAN ----------------------------------------------------------------------------- Hash Join (cost=38647.00..1391103.33 rows=2289433 width=16) Hash Cond: ((g.devise)::text = (o.devise)::text) -> Seq Scan on geants g (cost=0.00..263935.00 rows=10000000 width=49) -> Hash (cost=18334.00..18334.00 rows=1000000 width=33) -> Seq Scan on ordo o (cost=0.00..18334.00 rows=1000000 width=33) select idu from ordo o join geants g on (o.devise = g.devise); Time: 15937,708 ms (00:15,938) ... Time: 16218,175 ms (00:16,218) ... Time: 16464,392 ms (00:16,464) SET WORK_MEM="32MB"; SET select idu from ordo o join geants g on (o.devise = g.devise); Time: 14212,488 ms (00:14,212) ... Time: 14133,606 ms (00:14,134) ... Time: 14219,777 ms (00:14,220)

      Le serveur est assez équilibé et dispose de 32Go de RAM, c’est à dire une quantité suffisante pour mettre les données en cache. De toute façon, même sans inciter le planner à privilégier le passage par les index, il choisit les boucles imbriquées lorsque l’index HASH est présent.
      Le coût global des boucles imbriquées impliquant 1 million d’INDEX SCAN est estimé comme largement inférieur à celui de la jointure de type HASH JOIN. Et pourtant les faits démentent cet optimisme : 25s et même 36s avec les boucles imbriquées dans un cas très défavorable contre 16s voire moins de 15s en augmentant la mémoire de travail sans l’index.
      Certes, si le but était de renvoyer les premiers résultats le plus rapidement possible, alors le coût de 0 contre 38647 est assez réaliste. Mais si le but était d’obtenir tout le jeu de résultats de la manière la plus efficace alors c’est raté : le coût de 270 000 contre 1 400 000 est largement sous-évalué.

Conclusion

      Tester l’égalité entre chaînes de caractères peut être rendu plus performant gràce à l’indexation HASH.
      Il faut cependant veiller aux excès d’optimisme du planner en ce qui concerne les Index Scan lorsque les index utilisent la méthode HASH, notamment si vos clés sont des chaînes de caractères et que vous réalisez des jointures sur de larges volumes de données. A confirmer bien sûr sur VOTRE environnement. Comme d’habitude, les résultats peuvent en effet grandement varier en fonction des ressources à disposition.

Mise à jour : 26/05/2017