Индексы PostgreSQL: хэш против B-дерева

Dec 20 2022

Всегда ли вы знаете, когда использовать хэш-индекс вместо индекса b-дерева? Насколько значительной будет польза от выбора? Я не. Поэтому я провел небольшое исследование, чтобы выяснить эмпирическое правило.

Всегда ли вы знаете, когда использовать хэш-индекс вместо индекса b-дерева? Насколько значительной будет польза от выбора? Я не.

Поэтому я провел небольшое исследование, чтобы выяснить эмпирическое правило. И в этой статье я поделюсь результатами.

UPD : Статья обновлена.

К сожалению, в первой версии поста я допустил небольшую ошибку в бенчмарке, которую было сложно поймать. Подробнее об этом можно прочитать в этой статье .

Спойлер: хэш-индекс стал еще слаще.

Я пропускаю часть о b-tree и хэш- индексах, так как есть много ресурсов, которые вы можете прочитать. Однако я на секунду остановлюсь на описании хеша из официальной документации PostgreSQL .

Хэш-индексы хранят 32-битный хэш-код , полученный из значения индексированного столбца. Следовательно, такие индексы могут обрабатывать только простые сравнения на равенство . Планировщик запросов рассмотрит возможность использования хэш-индекса всякий раз, когда индексированный столбец участвует в сравнении с использованием оператора равенства.

Несмотря на то, что индекс b-дерева может хранить множество значений без снижения ожидаемой производительности, хэш-индекс имеет ограничение в 2 ³²-1 уникальных хеш-кодов (разные значения могут иметь одинаковые хеш-коды). Поэтому увеличение количества дубликатов (с точки зрения хэш-кодов) негативно сказывается на производительности индекса.

Ценности имеют высокую кардинальность. В идеале их хэш-коды также должны иметь высокую кардинальность.

Одной из причин, по которой индекс b-дерева является таким стандартным, является его гибкость, поскольку он поддерживает все операторы сравнения. Хэш-индекс, с другой стороны, поддерживает только операторы равенства .

Значения запрашиваются только с операторами равенства.

Теперь давайте проследим за тестами и сравним потребление памяти и производительность.

Прежде чем мы рассмотрим результаты, я хотел бы поделиться процедурами PL/pgSQL , которые я использовал для исследования метрик.

Приведенная random_stringниже процедура генерирует случайные строки заданной длины.

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

Результаты собираются с помощью PostgreSQL 15.1.

Давайте углубимся в сравнение потребления памяти. Ниже я опубликую серию графиков для 1.000, 10.000, 100.000 и 1.000.000 строк.