Indici PostgreSQL: Hash vs B-tree

Sai sempre quando usare l'indice hash sull'indice b-tree? Quanto sarebbe significativo il vantaggio derivante dalla scelta? Io non.

Quindi ho fatto una piccola ricerca per trovare una regola empirica. E in questo articolo condividerò i risultati.

UPD : L'articolo è stato aggiornato.

Sfortunatamente, nella prima versione del post, ho commesso un piccolo errore nel benchmark che è stato difficile da rilevare. Puoi leggere di più a riguardo in questo articolo .

Spoiler: l'indice hash è ancora più dolce ora.

Salto la parte sugli indici b-tree e hash poiché ci sono molte risorse che puoi leggere. Tuttavia, mi fermo per un secondo sulla descrizione dell'hash dalla documentazione ufficiale di PostgreSQL .

Gli indici hash memorizzano un codice hash a 32 bit derivato dal valore della colonna indicizzata. Pertanto, tali indici possono gestire solo semplici confronti di uguaglianza . Il pianificatore di query prenderà in considerazione l'utilizzo di un indice hash ogni volta che una colonna indicizzata è coinvolta in un confronto utilizzando l'operatore uguale.

Nonostante l'indice b-tree, che può memorizzare molti valori senza ridurre le prestazioni previste, l'indice hash ha un limite di 2 ³²-1 di codici hash univoci (valori diversi possono avere gli stessi codici hash). Pertanto, l'aumento del numero di duplicati (in termini di codici hash) influisce negativamente sulle prestazioni dell'indice.

I valori hanno una cardinalità elevata. Idealmente, anche i loro codici hash hanno un'elevata cardinalità.

Uno dei motivi per cui l'indice b-tree è così standard è la sua flessibilità perché supporta tutti gli operatori di confronto. L'indice hash, d'altra parte, supporta solo gli operatori di uguaglianza .

I valori vengono interrogati solo con operatori di uguaglianza.

Ora seguiamo i benchmark e confrontiamo il consumo di memoria e le prestazioni.

Prima di esaminare i risultati, vorrei condividere le procedure PL/pgSQL che ho utilizzato per ricercare le metriche.

La random_stringprocedura seguente genera stringhe casuali di una determinata lunghezza.

-- 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);

I risultati vengono raccolti utilizzando PostgreSQL 15.1.

Immergiamoci nel confronto del consumo di memoria. Di seguito, posterò una serie di grafici per 1.000, 10.000, 100.000 e 1.000.000 righe.

Evidenziamo alcune cose che vediamo nei grafici:

• Gli indici hash sono indipendenti dai dati, il che significa che la loro dimensione dipende solo dal numero di dati indicizzati;
• Più righe hai, minore è la lunghezza della stringa necessaria per beneficiare dell'indice hash;
• Nella maggior parte dei casi, l'indice hash consuma molta meno memoria del campo memorizzato, mentre quando il b-tree richiede più del campo memorizzato;
• La lunghezza iniziale in cui vediamo il vantaggio potrebbe essere compresa tra 15 e 30; tuttavia, per semplificare la regola empirica, diremmo almeno 25 .

Ora passiamo al confronto delle prestazioni.

Sulla base dei grafici per il confronto delle prestazioni, possiamo dire:

• in tutti i casi la performance è migliore con l' indice hash ;
• le query selezionate hanno un aumento del 20-60% , aumentando con il numero di righe;
• le query di inserimento hanno un aumento del 10-80% , aumentando con il numero di righe;
• entrambi gli indici si comportano velocemente e alcuni potrebbero trascurare un guadagno di 0,01 millisecondi.

• risparmiare circa 1,5 GB sul disco ( 50 volte più piccolo dell'indice b-tree);
• ti dà un aumento delle prestazioni del 60-80% ( 0,02-0,04 ms per query).

Concludiamo la regola empirica :

• I valori hanno una cardinalità elevata . Idealmente, anche i loro codici hash hanno un'elevata cardinalità;
• I valori vengono interrogati solo con operatori di uguaglianza ;
• Le lunghezze dei valori devono essere lunghe almeno 25 caratteri.