Переоткрывая хэш-индексы в PostgreSQL

Если вы работает с базами данных, то, скорее всего, знакомы с B-tree индексами. У них множество применений и они являются дефолтными типами индекса в большинстве движков баз данных. Если вы работаете с полнотекстовым поиском или пространственными данными, то скорее всего вы знакомы еще и с GIN и GIST индексами. Если вы работаете с массивными временными рядами, то слышали еще и о BRIN индексах.

Однако, есть еще один менее популярный тип, о котором большинство даже ничего не слышало. Пару версий PostgresSQL назад он был не то что даже непопулярен, но и строго не рекомендован к использованию. Однако в некоторых случаях он может обойти даже B-tree в плане производительности.

Сейчас мы переоткроем хэш-индекс!

Хэш-индекс

Название намекает, что индекс использует структуру данных «хэш-таблица». Эту структуру данных можно встретить во многих языках программирования. В Python это Dict, в Java HashMap, в JS Map.

Чтобы увидеть профиты использования хэш-индексов, следует понять принцип их работы.

Хэш-таблица

Хэш индекс использует хэш функцию. Эта функция отображает тип данных в 32-битное целое число — хэш-код. Хорошая хэш-функция раскидывает вычисляемые значения равномерно по всему доступному диапазону (всего около 4 миллиарда значений).

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

Простейшая хэш-функция для входящих целых чисел это деление по модулю. Делим число А на число Б и остаток от целочисленного деления считаем хэш-кодом. Например, чтобы раскидать числа по трем бакетам, используем функцию mod(3)

db=# SELECT n, mod(n, 3) AS bucket FROM generate_series(1, 10) AS n;  n  │ bucket ────┼────────   1 │      1   2 │      2   3 │      0   4 │      1   5 │      2   6 │      0   7 │      1   8 │      2   9 │      0  10 │      1

Когда новое значение добавляется в индекс, система применяет к нему хэш-функцию и помещает хэш-код и указатель на кортеж в бакет.

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

Коллизии

Нетрудно догадаться, что разные данные на входе могут привести к одному и тому же хэш-коду и бакету на выходе. Это называется коллизией. Например, хэш-функция mod(3) возвращает один и тот же код 2 для значений 2, 5, 8.

На деле система поступает хитрее. Сначала используем хэш-функцию для вычисления хэш-кода

db=# SELECT     hashtext('text'),     hashchar('c'),     hash_array(array[1,2,3]),     jsonb_hash('{"me": "haki"}'::jsonb),     timestamp_hash(now()::timestamp); ─[ RECORD 1 ]──┬──────────── hashtext       │ -451854347 hashchar       │ 203891234 hash_array     │ -325393530 jsonb_hash     │ -1784498999 timestamp_hash │ 1082344883

Затем используемmod(кол-во бакетов) для определения номера бакета. Это все равно может привести к тому, что несколько значений попадут в один и тот же бакет. Поэтому даже после того, как бакет идентифицирован, системе все еще необходимо просеять хэш-коды в корзине и перепроверить условие, чтобы отфильтровать только совпадающие кортежи.

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

Разделение индекса

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

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

Хэш-индексы

Хэш-индексы не рекомендовались к применению до 10 версии PostgreSQL. Если почитаете доки по индексам версии 9.6, то увидите прямое предостережение. Проблема была в том, что хэш-индексы не записывались в WAL — а значит не могли быть использованы в репликах и не восстанавливались автоматически после крэшей.

В версии 10 эти проблемы были устранены и хэш-индексы больше не несут черную метку.

Создание

Посмотрим на хэш-индексы в работе на примере сервиса коротких ссылок.

Сервисы короктих ссылок типа bit.ly или goo.gl создают короткий URL, который указывает на полноценный длинный URL. Например короткая ссылка https://short.url/hb9837 указывает на https://hakibenita.com/automating-the-boring-stuff-in-django-using-the-check-framework. Часть hb9837 называется ключом.

Создадим таблицу для хранения маппинга между длинными и короткими ссылками:

CREATE TABLE shorturl (     id serial primary key,     key text not null,     url text not null );

Таблица состоит из первичного ключа с автоинкрементом и двух текстовых полей. Создадим хэш и b-tree индексы для обоих полей.

CREATE INDEX shorturl_key_hash_index ON shorturl USING hash(key); CREATE UNIQUE INDEX shorturl_key_btree_index ON shorturl USING btree(key); CREATE INDEX shorturl_url_hash_index ON shorturl USING hash(url); CREATE INDEX shorturl_url_btree_index ON shorturl USING btree(url);

Кстати, из-за текущего ограничения, b-tree индекс может быть еще и уникальным, а хэш-индекс — нет.

Размер хэш-индекса

Сравним размеры индексов обоих типов:

CREATE EXTENSION "uuid-ossp";  DO $$ BEGIN     FOR i IN 0..1000000 loop         INSERT INTO shorturl (key, url) VALUES (         uuid_generate_v4(),         'https://www.supercool-url.com/' || round(random() * 10 ^ 6)::text     );     if mod(i, 10000) = 0 THEN         RAISE NOTICE 'rows:%  Hash key%  B-Tree key:%  Hash url:%  B-Tree url:%',             to_char(i, '9999999999'),             to_char(pg_relation_size('shorturl_key_hash_index'), '99999999999'),             to_char(pg_relation_size('shorturl_key_btree_index'), '99999999999'),             to_char(pg_relation_size('shorturl_url_hash_index'), '99999999999'),             to_char(pg_relation_size('shorturl_url_btree_index'), '99999999999');     END IF;     END LOOP; END; $$;

Чтобы лучше понять, как ведут себя оба индекса, отследим размер индексов по мере вставки строк в таблицу:

• Генерим 1кк коротких ссылок

• Каждые 10к строк логируем размеры всех созданных индексов

• Используем uuid_generate_v4 из пакета uuid-ossp для генерации коротких ссылок

• Генерим длинные ссылки с помощью 6-значного рандомного числа, делая их относительно уникальными

Запускаем функцию на PostgreSQL 13 и выводим результаты на чарт:

Что мы тут видим?

• Хэш индекс занимает меньше места, чем b-tree

• Хэш индекс растет инкрементально. В отличие от b-tree, растущего линейно по мере добавления строк, хэш растет рывками. Это происходит в моменты инциализации разделения индекса и аллокации дополнительной памяти под бакеты.

• Хэш индекс не зависит от размеры индексируемого ключа. Хэш-индекс хранит хэш-коды (целые числа), а b-tree индекс хранит собственно значения.

• Хэш-индекс не зависит от селективности индексируемого значения. Селективность столбца url отличается от селективности столбца key (который гораздо более уникален). Однако хэш-индексы обеих столбцов имеют схожий размер.

Запущенная нами функция имитирует нагрузку типа OLTP, когда в таблицу постоянно идет запись. Вот размеры индексов после завершения функции

db=# \di+ shorturl*           Name           │ Type  │ Table    │Size ─────────────────────────┼───────┼──────────┼──────── shorturl_key_btree_index │ index │ shorturl │ 73 MB shorturl_key_hash_index  │ index │ shorturl │ 37 MB shorturl_url_btree_index │ index │ shorturl │ 53 MB shorturl_url_hash_index  │ index │ shorturl │ 36 MB

Пока что размеры хэш-индекса вдвое меньше, чем размеры b-tree. Попробуем реиндексировать таблицу вручную, пересоздав индексы с нуля.

db=# REINDEX TABLE shorturl; REINDEX db=# \di+ shorturl*           Name           │ Type  │  Table   │ Size ─────────────────────────┼───────┼──────────┼─────── shorturl_key_btree_index │ index │ shorturl │ 56 MB shorturl_key_hash_index  │ index │ shorturl │ 32 MB shorturl_url_btree_index │ index │ shorturl │ 41 MB shorturl_url_hash_index  │ index │ shorturl │ 32 MB

Реиндексирование снижает размеры всех индексов, но некоторых заметнее. Но даже после реиндексирования раунд за хэш-индексами.

Параметр fillfactor

fillfactor влияет на механизм разделения хэш-индеса. Он определяет соотношение между хранимыми ссылками на кортежи и количеством бакетов. Чем меньше fillfactor, тем более «пустое» пространство в индексе.

Для b-tree это параметр по умолчанию 90, для хэш-индекса — 75. Чтобы наглядно продемонстрировать влияние fillfactor, сравним размеры хэш-индекса с разным его значением.

CREATE TABLE shorturl_ff (     id serial primary key,     key text not null,     url text not null );  CREATE INDEX shorturl_key_hash_index_025 ON shorturl_ff USING hash(key) WITH (fillfactor = 25); CREATE INDEX shorturl_key_hash_index_050 ON shorturl_ff USING hash(key) WITH (fillfactor = 50); CREATE INDEX shorturl_key_hash_index_075 ON shorturl_ff USING hash(key) WITH (fillfactor = 75); CREATE INDEX shorturl_key_hash_index_100 ON shorturl_ff USING hash(key) WITH (fillfactor = 100);  DO $$ BEGIN     RAISE NOTICE 'rows,25,50,75,100';     FOR i IN 0..1000000 LOOP         INSERT INTO shorturl_ff (key, url) VALUES (           uuid_generate_v4(),           'https://www.supercool-url.com/' || round(random() * 10 ^ 6)::text         );         IF mod(i, 10000) = 0 THEN             RAISE NOTICE '%,%,%,%,%',                 to_char(i, '9999999999'),                 pg_relation_size('shorturl_key_hash_index_025'),                 pg_relation_size('shorturl_key_hash_index_050'),                 pg_relation_size('shorturl_key_hash_index_075'),                 pg_relation_size('shorturl_key_hash_index_100');         END IF;     END LOOP; END; $$;

Чарт показывает, что меньший fillfactor заставляет бакеты делиться раньше, что приводит к большему общему размеру. В отличие от b-tree, который резервирует место под обновляемые строки, новые значения в хэш-индесе могут попасть в любой бакет. Учитывайте это, если решите влезть руками в настройки fillfactor

Производительность

Достижения баланса между размером индекса и скоростью доступа — ключ к БД здорового человека. Мы увидели, что хэш-индексы выигрывают в размере. А что насчет скорости?

Производительность при вставке

Когда вы вставляете строки в таблицу, эта же строка попадает во все назначенные на таблицу индексы. Поэтому множество индексов хотя и ускоряют операции чтения, но имеют противоположный эффект при операциях записи.

Пересоздадим нашу таблицу и на сей раз ограничимся единственным индексом

DROP TABLE IF EXISTS shorturl_hash; CREATE TABLE shorturl_hash (     id serial primary key,     key text not null,     url text not null ); CREATE INDEX shorturl_hash_hash_ix ON shorturl_hash USING hash(key);

Далее запишем 1кк записей и замерим общее время выполнения

DO $$ DECLARE     n INTEGER := 1000000;     duration INTERVAL := 0;     start TIMESTAMP;     uid TEXT;     url TEXT; BEGIN       FOR i IN 1..n LOOP         uid := uuid_generate_v4()::text;         url := 'https://www.supercool-url.com/' || round(random() * 10 ^ 6)::text;         start := clock_timestamp();           INSERT INTO shorturl_hash (key, url) VALUES (uid, url);         duration := duration + (clock_timestamp() - start);     END LOOP;     RAISE NOTICE 'Hash: total=% mean=%', duration, extract('epoch' from duration) / n; END; $$; 

Hash: total=00:00:09.764746 mean=9.764746e-06

Повторим то же самое, но уже с b-tree индексом

DO $$ DECLARE   n INTEGER := 100000;   duration INTERVAL := 0;   start TIMESTAMP;   keys TEXT[];  BEGIN   -- Fetch radom keys from the table   SELECT ARRAY_AGG(key) INTO keys   FROM (     SELECT key     FROM shorturl_btree     ORDER BY random()     LIMIT n   ) AS foo;      FOR i IN array_lower(keys, 1)..array_upper(keys, 1) LOOP       start := clock_timestamp();         PERFORM * FROM shorturl_btree WHERE key = keys[i];       duration := duration + (clock_timestamp() - start);   END LOOP;   RAISE NOTICE 'B-Tree: total=% mean=%', duration, extract('epoch' from duration) / n; END; $$;

B-Tree: total=00:00:10.822158 mean=1.0822158e-05

11 секунд. Тест далек от научной точности, но показывает некоторое превосходство хэш-индеса.

Производительность при чтении

В сервисе коротких ссылок нам важная скорость нахождения оригинальной ссылки по заданному ключу. Запустим следующий бенчмарк

DO $$ DECLARE   n INTEGER := 100000;   duration INTERVAL := 0;   start TIMESTAMP;   keys TEXT[];  BEGIN     -- Fetch radom keys from the table     SELECT ARRAY_AGG(key) INTO keys     FROM (       SELECT key       FROM shorturl_hash       ORDER BY random()       LIMIT n     ) AS foo;      FOR i IN array_lower(keys, 1)..array_upper(keys, 1) LOOP         start := clock_timestamp();         PERFORM * FROM shorturl_hash WHERE key = keys[i];         duration := duration + (clock_timestamp() - start);     END LOOP;     RAISE NOTICE 'Hash: total=% mean=%', duration, extract('epoch' from duration) / n; END; $$; 

Hash: total=00:00:00.590032 mean=5.90032e-06

Запрос 100к рандомных ключей по одному за раз занимает полсекунды.

Повторяем для b-tree

DO $$ DECLARE   n INTEGER := 100000;   duration INTERVAL := 0;   start TIMESTAMP;   keys TEXT[];  BEGIN   -- Fetch radom keys from the table   SELECT ARRAY_AGG(key) INTO keys   FROM (     SELECT key     FROM shorturl_btree     ORDER BY random()     LIMIT n   ) AS foo;      FOR i IN array_lower(keys, 1)..array_upper(keys, 1) LOOP       start := clock_timestamp();         PERFORM * FROM shorturl_btree WHERE key = keys[i];       duration := duration + (clock_timestamp() - start);   END LOOP;   RAISE NOTICE 'B-Tree: total=% mean=%', duration, extract('epoch' from duration) / n; END; $$;

B-Tree: total=00:00:00.923244 mean=9.23244e-06

Без драматичной разницы, но хэш-индекс опять впереди.

Ограничения

Ничто не дается бесплатно. У хэш-индексов много ограничений, проистекающих из свойств самих хэш-таблиц.

Хэш-индекс не может быть использован для организации уникального индекса

db=# CREATE UNIQUE INDEX shorturl_unique_key ON shorturl USING hash(key); ERROR:  access method "hash" does not support unique indexes

Хэш-индекс не может быть использован для составных индексов на несколько столбцов

db=# CREATE INDEX shorturl_key_and_url ON shorturl USING hash(key, url); ERROR:  access method "hash" does not support multicolumn indexes

Хэш-индекс не поддерживает сортировку

db=# CREATE INDEX shorturl_sorted_key ON shorturl USING hash(key desc); ERROR:  access method "hash" does not support ASC/DESC options

Хэш-индекс не годится для кластеризации

db=# CLUSTER shorturl USING shorturl_url_hash_index; ERROR:  cannot cluster on index "shorturl_url_hash_index" because access method does not support clustering

Не знаете, что делает команда CLUSTER и зачем вам ее использовать? Ознакомиться можно здесь.

Хэш-индекс не годится для поиска по интервалам

db=# EXPLAIN (COSTS OFF) SELECT * FROM shorturl WHERE key BETWEEN '1' AND '2';                                    QUERY PLAN ──────────────────────────────────────────────────────────────────────────────── Gather   -> Seq Scan on shorturl         Filter: ((key >= '1'::text) AND (key <= '2'::text)) 

Хэш-индекс не дружит с ORDER BY

db=# EXPLAIN (COSTS OFF) SELECT * FROM shorturl ORDER BY key LIMIT 10;                                     QUERY PLAN ──────────────────────────────────────────────────────────────────────────────── Limit   ->  Index Scan using shorturl_key_btree_index on shorturl

Можем для верности дропнуть b-tree индекс и убедиться в этом

db=# BEGIN; BEGIN db=# DROP INDEX shorturl_key_btree_index; DROP INDEX db=# EXPLAIN (COSTS OFF) SELECT * FROM shorturl ORDER BY key LIMIT 10;                    QUERY PLAN ─────────────────────────────────────────────────  Limit    ->  Gather Merge          Workers Planned: 2          ->  Sort                Sort Key: key                ->  Parallel Seq Scan on shorturl (6 rows) db=# rollback; ROLLBACK

Итог

Хэш-таблицы — очевидный выбор, когда нужен быстрый поиск данных по ключу. Однако нюансы реализации хэш-индексов до 10 версии PostgreSQL заставили DBA и разработчиков забыть о таком механизме.

Но что мы имеем в свежих версиях:

• Хэш-индекс был доработан и теперь абсолютно продакшн-реди.

• Хэш-индекс как правило занимает меньше места, чем аналогичный b-tree.

• Хэш-индекс незначительно выигрывает в производительности как при вставке, так и при чтении.

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

Если вы интересуетесь внутренностями системы, добро пожаловать в исходный код