PostgreSQL-Indizes: Hash vs. B-Tree

Dec 20 2022

Wissen Sie immer, wann Sie den Hash-Index gegenüber dem B-Tree-Index verwenden müssen? Wie groß wäre der Nutzen aus der Wahl? Ich tu nicht. Also habe ich ein wenig recherchiert, um eine Faustregel herauszufinden.

Wissen Sie immer, wann Sie den Hash-Index gegenüber dem B-Tree-Index verwenden müssen? Wie groß wäre der Nutzen aus der Wahl? Ich tu nicht.

Also habe ich ein wenig recherchiert, um eine Faustregel herauszufinden. Und in diesem Artikel werde ich die Ergebnisse teilen.

UPD : Der Artikel wurde aktualisiert.

Leider ist mir in der ersten Post-Version ein kleiner Fehler im Benchmark unterlaufen, der schwer zu fangen war. Sie können mehr darüber in diesem Artikel lesen .

Spoiler: Der Hash-Index ist jetzt noch süßer.

Ich überspringe den Teil über B-Tree- und Hash - Indizes, da es viele Ressourcen gibt, die Sie lesen können. Ich unterbreche jedoch für eine Sekunde die Hash-Beschreibung aus der offiziellen Dokumentation von PostgreSQL .

Hash-Indizes speichern einen 32-Bit-Hash-Code , der vom Wert der indizierten Spalte abgeleitet wird. Daher können solche Indizes nur einfache Gleichheitsvergleiche verarbeiten . Der Abfrageplaner erwägt die Verwendung eines Hash-Index, wenn eine indizierte Spalte an einem Vergleich mit dem Gleichheitsoperator beteiligt ist.

Trotz des B-Tree-Index, der viele Werte speichern kann, ohne die erwartete Leistung zu beeinträchtigen, hat der Hash-Index eine Grenze von 2 ³²-1 eindeutiger Hash-Codes (verschiedene Werte können dieselben Hash-Codes haben). Daher wirkt sich die Erhöhung der Anzahl der Duplikate (in Bezug auf Hash-Codes) negativ auf die Indexleistung aus.

Werte haben eine hohe Kardinalität. Idealerweise haben ihre Hash-Codes auch eine hohe Kardinalität.

Einer der Gründe, warum der b-Tree-Index so standardisiert ist, ist seine Flexibilität, da er alle Vergleichsoperatoren unterstützt. Der Hash-Index hingegen unterstützt nur Gleichheitsoperatoren .

Werte werden nur mit Gleichheitsoperatoren abgefragt.

Folgen wir nun den Benchmarks und vergleichen Speicherverbrauch und Leistung.

Bevor wir uns die Ergebnisse ansehen, möchte ich die PL/pgSQL- Verfahren teilen, die ich zur Recherche der Metriken verwendet habe.

Die random_stringfolgende Prozedur generiert zufällige Zeichenfolgen einer bestimmten Länge.

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

Die Ergebnisse werden mit PostgreSQL 15.1 gesammelt.

Lassen Sie uns in den Speicherverbrauchsvergleich eintauchen. Unten werde ich eine Reihe von Diagrammen für 1.000, 10.000, 100.000 und 1.000.000 Zeilen posten.