Índices de PostgreSQL: Hash vs B-tree

Dec 20 2022

¿Siempre sabe cuándo usar el índice hash sobre el índice b-tree? ¿Qué tan significativo sería el beneficio de la elección? Yo no. Así que investigué un poco para encontrar una regla general.

¿Siempre sabe cuándo usar el índice hash sobre el índice b-tree? ¿Qué tan significativo sería el beneficio de la elección? Yo no.

Así que investigué un poco para encontrar una regla general. Y en este artículo, compartiré los resultados.

UPD : El artículo fue actualizado.

Desafortunadamente, en la primera versión posterior, cometí un pequeño error en el punto de referencia que fue difícil de detectar. Puedes leer más sobre esto en este artículo .

Spoiler: el índice hash es aún más dulce ahora.

Me salteo la parte sobre los índices hash y de árbol b, ya que hay muchos recursos que puedes leer. Sin embargo, me detengo por un segundo en la descripción hash de la documentación oficial de PostgreSQL .

Los índices hash almacenan un código hash de 32 bits derivado del valor de la columna indexada. Por lo tanto, dichos índices solo pueden manejar comparaciones de igualdad simples . El planificador de consultas considerará usar un índice hash siempre que una columna indexada esté involucrada en una comparación usando el operador igual.

A pesar del índice b-tree, que puede almacenar muchos valores sin reducir el rendimiento esperado, el índice hash tiene un límite de 2 ³²-1 de códigos hash únicos (diferentes valores pueden tener los mismos códigos hash). Por lo tanto, aumentar la cantidad de duplicados (en términos de códigos hash) afecta negativamente el rendimiento del índice.

Los valores tienen alta cardinalidad. Idealmente, sus códigos hash también tienen alta cardinalidad.

Una de las razones por las que el índice b-tree es tan estándar es su flexibilidad porque admite todos los operadores de comparación. El índice hash, por otro lado, solo admite operadores de igualdad .

Los valores se consultan solo con operadores de igualdad.

Ahora, sigamos los puntos de referencia y comparemos el consumo de memoria y el rendimiento.

Antes de analizar los resultados, me gustaría compartir los procedimientos PL/pgSQL que utilicé para investigar las métricas.

El random_stringsiguiente procedimiento genera cadenas aleatorias de una longitud dada.

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

Los resultados se recopilan utilizando PostgreSQL 15.1.

Profundicemos en la comparación del consumo de memoria. A continuación, publicaré una serie de gráficos para 1.000, 10.000, 100.000 y 1.000.000 de filas.