Índices PostgreSQL: Hash vs B-tree

Você sempre sabe quando usar o índice de hash sobre o índice de b-tree? Quão significativo seria o benefício da escolha? Eu não.

Então eu fiz uma pequena pesquisa para descobrir uma regra de ouro. E neste artigo, compartilharei os resultados.

UPD : O artigo foi atualizado.

Infelizmente, na primeira versão do post, cometi um pequeno erro no benchmark que foi difícil de pegar. Você pode ler mais sobre isso neste artigo .

Spoiler: o índice de hash é ainda mais doce agora.

Pulo a parte sobre b-tree e índices de hash , pois há muitos recursos que você pode ler. No entanto, paro por um segundo na descrição do hash da documentação oficial do PostgreSQL .

Os índices de hash armazenam um código de hash de 32 bits derivado do valor da coluna indexada. Portanto, esses índices só podem lidar com comparações de igualdade simples . O planejador de consulta considerará o uso de um índice de hash sempre que uma coluna indexada estiver envolvida em uma comparação usando o operador igual.

Apesar do índice b-tree, que pode armazenar muitos valores sem reduzir o desempenho esperado, o índice hash tem um limite de 2 ³²-1 de códigos hash únicos (valores diferentes podem ter os mesmos códigos hash). Portanto, aumentar o número de duplicatas (em termos de códigos hash) afeta negativamente o desempenho do índice.

Os valores têm alta cardinalidade. Idealmente, seus códigos de hash também têm alta cardinalidade.

Uma das razões pelas quais o índice b-tree é tão padrão é sua flexibilidade, pois suporta todos os operadores de comparação. O índice de hash, por outro lado, suporta apenas operadores de igualdade .

Os valores são consultados apenas com operadores de igualdade.

Agora, vamos seguir os benchmarks e comparar o consumo de memória e o desempenho.

Antes de analisarmos os resultados, gostaria de compartilhar os procedimentos PL/pgSQL que usei para pesquisar as métricas.

O random_stringprocedimento abaixo gera strings aleatórias de um determinado comprimento.

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

Os resultados são coletados usando o PostgreSQL 15.1.

Vamos mergulhar na comparação de consumo de memória. Abaixo, postarei uma série de gráficos para 1.000, 10.000, 100.000 e 1.000.000 linhas.

Vamos destacar algumas coisas que vemos nos gráficos:

• Os índices de hash são independentes de dados, o que significa que seu tamanho depende apenas do número de dados indexados;
• Quanto mais linhas você tiver, menos comprimento de string precisará para se beneficiar do índice de hash;
• Na maioria dos casos, o índice de hash consome muito menos memória do que o campo armazenado, enquanto que quando a b-tree requer mais do que o campo armazenado;
• O comprimento inicial onde vemos o benefício pode estar entre 15–30; no entanto, para simplificar a regra geral, diríamos pelo menos 25 .

Agora vamos pular para a comparação de desempenho.

Com base nos gráficos de comparação de desempenho, podemos dizer:

• em todos os casos, o desempenho é melhor com o índice hash ;
• as consultas selecionadas têm um aumento de 20 a 60% , aumentando com o número de linhas;
• as consultas de inserção têm um aumento de 10 a 80% , aumentando com o número de linhas;
• ambos os índices têm desempenho rápido e alguns podem negligenciar um ganho de 0,01 milissegundo.

• economize cerca de 1,5 GB no disco ( 50 vezes menor que o índice b-tree);
• fornecem um aumento de desempenho de 60 a 80% ( 0,02 a 0,04 ms por consulta).

Vamos concluir a regra de ouro :

• Os valores têm alta cardinalidade . Idealmente, seus códigos de hash também têm alta cardinalidade;
• Os valores são consultados apenas com operadores de igualdade ;
• Os comprimentos dos valores devem ter pelo menos 25 caracteres.