Если вы работает с базами данных, то, скорее всего, знакомы с 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, сравним размеры хэш-индекса с разным его значением.
Code
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кк записей и замерим общее время выполнения
Code
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 индексом
Code
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-0511 секунд. Тест далек от научной точности, но показывает некоторое превосходство хэш-индеса.
Производительность при чтении
В сервисе коротких ссылок нам важная скорость нахождения оригинальной ссылки по заданному ключу. Запустим следующий бенчмарк
Code
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
Code
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.
Хэш-индекс незначительно выигрывает в производительности как при вставке, так и при чтении.
Хэш-индекс имеет много ограничений, которые сводят его применимость к узкому ряду задач.
Если вы интересуетесь внутренностями системы, добро пожаловать в исходный код
outlingo
А можно было просто написать - "применяйте хэш-индексы там где нужен поиск по ключу, он очень хорош в этом, а для всего остального он не подходит"
panzerfaust Автор
Так все технические посты станут похожи на набор афоризмов и "мысли умных людей".