Index PostgreSQL : Hash vs B-tree

Dec 20 2022

Savez-vous toujours quand utiliser l'index de hachage sur l'index b-tree ? Quelle serait l'importance du bénéfice du choix ? Je ne sais pas. J'ai donc fait une petite recherche pour trouver une règle de base.

Savez-vous toujours quand utiliser l'index de hachage sur l'index b-tree ? Quelle serait l'importance du bénéfice du choix ? Je ne sais pas.

J'ai donc fait une petite recherche pour trouver une règle de base. Et dans cet article, je partagerai les résultats.

UPD : L'article a été mis à jour.

Malheureusement, dans la première version du post, j'ai fait une petite erreur dans le benchmark qui était difficile à attraper. Vous pouvez en savoir plus à ce sujet dans cet article .

Spoiler: l'index de hachage est encore plus doux maintenant.

Je saute la partie sur les index b-tree et hash car il y a beaucoup de ressources que vous pouvez lire. Cependant, je m'arrête une seconde sur la description du hachage de la documentation officielle de PostgreSQL .

Les index de hachage stockent un code de hachage 32 bits dérivé de la valeur de la colonne indexée. Par conséquent, de tels index ne peuvent gérer que des comparaisons d'égalité simples . Le planificateur de requêtes envisagera d'utiliser un index de hachage chaque fois qu'une colonne indexée est impliquée dans une comparaison utilisant l'opérateur égal.

Malgré l'index b-tree, qui peut stocker de nombreuses valeurs sans réduire les performances attendues, l'index de hachage a une limite de 2 ³²-1 de codes de hachage uniques (différentes valeurs peuvent avoir les mêmes codes de hachage). Par conséquent, l'augmentation du nombre de doublons (en termes de codes de hachage) affecte négativement les performances de l'index.

Les valeurs ont une cardinalité élevée. Idéalement, leurs codes de hachage ont également une cardinalité élevée.

L'une des raisons pour lesquelles l'index b-tree est si standard est sa flexibilité car il prend en charge tous les opérateurs de comparaison. L'index de hachage, en revanche, ne prend en charge que les opérateurs d'égalité .

Les valeurs sont interrogées uniquement avec des opérateurs d'égalité.

Maintenant, suivons les benchmarks et comparons la consommation de mémoire et les performances.

Avant d'examiner les résultats, je voudrais partager les procédures PL/pgSQL que j'ai utilisées pour rechercher les métriques.

La random_stringprocédure ci-dessous génère des chaînes aléatoires d'une longueur donnée.

-- returns a randomized string of given length
CREATE OR REPLACE FUNCTION random_string(length integer)
RETURNS text AS
$$
DECLARE
    chars text[] := '{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}';
    result text := '';
    i integer := 0;
BEGIN
    FOR i IN 1..length LOOP
        result := result || chars[ceil(61 * random()) + 1];
    END LOOP;
    RETURN result;
END
$$ LANGUAGE plpgsql;

-- executes a given query for every string in strings
-- returns an average time for a single execution in milliseconds
CREATE OR REPLACE FUNCTION benchmark(query text, strings varchar[])
RETURNS numeric AS
$$
DECLARE
    _start_ts timestamptz;
    _end_ts   timestamptz;
    string    varchar;
BEGIN
    _start_ts := clock_timestamp();
    FOREACH string IN ARRAY strings LOOP
        EXECUTE format(query) using string;
    END LOOP;
    _end_ts := clock_timestamp();

    RETURN 1000 * (extract(epoch FROM _end_ts - _start_ts)) /
           array_length(strings, 1);
END
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION test(length integer, count numeric)
RETURNS TABLE (
    sample_length integer,
    unique_ratio decimal, -- in percentage
    hash_index_size bigint, -- in kilobytes
    btree_index_size bigint, -- in kilobytes
    column_size bigint, -- in kilobytes
    hash_select_query decimal, -- in milliseconds
    btree_select_query decimal, -- in milliseconds
    hash_insert_query decimal, -- in milliseconds
    btree_insert_query decimal -- in milliseconds
) AS
$$
DECLARE
    strings varchar[];
BEGIN
    CREATE TABLE IF NOT EXISTS hash_table(example varchar);
    CREATE TABLE IF NOT EXISTS btree_table(example varchar);

    INSERT INTO hash_table (SELECT random_string(length) FROM generate_series(1, count));
    INSERT INTO btree_table (SELECT example FROM hash_table);

    ANALYSE hash_table; -- this is critical for hash index
    ANALYSE btree_table;

    CREATE INDEX IF NOT EXISTS hash_index ON hash_table USING hash(example);
    CREATE INDEX IF NOT EXISTS btree_index ON btree_table USING btree(example);

    ANALYSE hash_table;
    ANALYSE btree_table;

    strings := array_agg(random_string(length)) FROM generate_series(1, 100);

    RETURN QUERY
    SELECT (SELECT length(example) FROM hash_table LIMIT 1),
        round(count(DISTINCT example)::decimal / count(*) * 100, 2) AS unique_ratio,
       pg_relation_size('hash_index') / 1024 AS hash_index_size,
       pg_relation_size('btree_index') / 1024 AS btree_index_size,
       pg_table_size('hash_table') / 1024 AS column_size,
       benchmark('SELECT example FROM hash_table WHERE example = $1', strings) AS hash_select_query,
       benchmark('SELECT example FROM btree_table WHERE example = $1', strings) AS btree_select_query,
       benchmark('INSERT INTO hash_table VALUES($1)', strings) AS hash_insert_query,
       benchmark('INSERT INTO btree_table VALUES($1)', strings) AS btree_insert_query
    FROM hash_table;

    DROP TABLE IF EXISTS hash_table;
    DROP TABLE IF EXISTS btree_table;
END
$$ LANGUAGE plpgsql;

SELECT (test(length, 1000)).*
FROM (VALUES (3), (5), (7), (10), (25), (100), (255), (355), (512), (755), (835), (1024)) s(length);

Les résultats sont rassemblés à l'aide de PostgreSQL 15.1.

Plongeons-nous dans la comparaison de la consommation de mémoire. Ci-dessous, je publierai une série de graphiques pour 1 000, 10 000, 100 000 et 1 000 000 lignes.

Index PostgreSQL&nbsp;: Hash vs B-tree

Index PostgreSQL : Hash vs B-tree