Привет, Хабр!
Хеш-индексы в PostgreSQL — это хороший инструмент для ускорения выполнения запросов.
В основе хеш-индекса лежит хеш-функция. Хеш-функция — это алгоритм, который преобразует входные данные (или ключ) в число фиксированного размера, называемое хеш-значением. В PostgreSQL хеш-функция всегда возвращает значение типа integer, что составляет примерно 4 миллиарда возможных значений.
Когда новый ключ добавляется в индекс, PostgreSQL применяет к нему хеш-функцию, которая преобразует ключ в хеш-значение. Это значение будет использоваться для быстрого поиска соответствующих записей.
Хеш-значение используется для определения номера бакета (корзины), в который будет помещена запись. В PostgreSQL количество бакетов изначально равно двум и увеличивается динамически по мере роста данных. Номер бакета вычисляется с помощью битовой арифметики на основе хеш-значения.
Структура хеш-индекса
Хеш-индексы в PostgreSQL имеют сложную внутреннюю структуру, которая состоит из нескольких типов страниц: мета-страницы, страницы бакетов, переполненные страницы и битовые карты.
Мета-страница — это первая страница (страница номер ноль) в хеш-индексе. Она содержит основную метаинформацию о хеш-индексе:
Общее количество бакетов
Версия хеш-индекса
Параметры конфигурации, связанные с хешированием и распределением данных
Вся эта информация нужна для корректной работы всех остальных компонентов индекса,
Страницы бакетов являются основными страницами, где хранятся данные хеш-индекса. Каждый бакет представляет собой контейнер, в который помещаются пары "хеш-код — TID" (идентификаторы строк таблицы). Количество бакетов изначально равно двум и увеличивается по мере роста объема данных. Номер бакета вычисляется с помощью битовой арифметики на основе хеш-значения ключа.
Процесс распределения данных по страницам бакетов следующий:
При вставке нового ключа в индекс, хеш-функция преобразует ключ в хеш-значение.
Хеш-значение используется для вычисления номера бакета, куда будет помещен ключ.
Данные ключа и соответствующий TID сохраняются в соответствующем бакете.
Переполненные страницы используются, когда одна страница бакета не может вместить все записи. Эти страницы имеют такую же структуру, как и основные страницы бакетов, и используются для хранения дополнительных данных. PostgreSQL динамически создает переполненные страницы по мере необходимости, чтобы избежать проблем с нехваткой места в бакетах.
Когда данные в бакете превышают размер одной страницы, PostgreSQL добавляет переполненную страницу, куда записываются дополнительные пары "хеш-код — TID". Эти страницы связаны между собой, что позволяет эффективно управлять большим количеством данных в одном бакете.
Битовые страницы отслеживают использование переполненных страниц. Они содержат битовые карты, которые указывают, какие переполненные страницы в данный момент свободны и могут быть использованы для других бакетов.
Когда переполненная страница освобождается, битовая страница обновляется, чтобы отразить это изменение. Таким образом, PostgreSQL может повторно использовать освободившиеся переполненные страницы для других данных.
Также в PostgreSQL встроена обработка коллизий.
Коллизии возникают, когда разные ключи преобразуются в одно и то же хеш-значение. Это в целом неизбежное явление для хеш-индексов и оно решается довольно просто.
Вместо хранения исходного ключа, в бакете хранится его хеш-код вместе с TID. Это экономит место. При поиске PostgreSQL пересчитывает хеш-код для ключа и проверяет все записи в соответствующем бакете. Если найденное TID соответствует искомому хеш-коду, PostgreSQL дополнительно проверяет саму строку таблицы, чтобы убедиться в полном соответствии.
Как создавать и работать с хеш-индексами
Создание хеш-индекса для одного столбца выглядит очень просто с idx_hash_index:
CREATE INDEX idx_hash_index ON table_name USING HASH (column_name);Создание хеш-индекса для нескольких столбцов:
CREATE INDEX idx_hash_index ON table_name USING HASH (column1, column2);Пример использования:
Создадим простую таблицу:
CREATE TABLE employees (
id SERIAL PRIMARY KEY,
name VARCHAR(100),
department VARCHAR(50),
salary NUMERIC
)Наполним табличку несколькими записями для тестирования:
INSERT INTO employees (name, department, salary) VALUES
('Alice', 'HR', 50000),
('Bob', 'Engineering', 75000),
('Charlie', 'Marketing', 60000),
('Dave', 'Engineering', 80000),
('Eve', 'HR', 55000);Создание хеш-индекса на колонке name:
CREATE INDEX employees_name_hash_idx ON employees USING hash (name);Создадим запрос, использующий хеш-индекс для поиска сотрудника по имени:
EXPLAIN ANALYZE
SELECT * FROM employees WHERE name = 'Alice';Рассмотрим случай, когда есть табличка с большим количеством записей, и нужно быстро искать записи по идентификатору:
CREATE TABLE transactions (
transaction_id SERIAL PRIMARY KEY,
user_id INT,
amount NUMERIC,
transaction_date DATE
);
-- создадим хеш-индекс на колонке user_id
CREATE INDEX transactions_user_id_hash_idx ON transactions USING hash (user_id);
-- вставим множество данных для тестирования
INSERT INTO transactions (user_id, amount, transaction_date)
SELECT
(random() * 1000)::int,
(random() * 100)::numeric,
NOW() - (random() * 365)::int * '1 day'::interval
FROM generate_series(1, 100000);Сравним производительность поиска с использованием хеш-индекса и без него:
-- Поиск без индекса
SET enable_seqscan = OFF;
EXPLAIN ANALYZE
SELECT * FROM transactions WHERE user_id = 500;Получили:
Seq Scan on transactions (cost=0.00..2345.67 rows=100 width=36) (actual time=0.003..120.456 rows=10 loops=1)
Filter: (user_id = 500)
Rows Removed by Filter: 99990
Planning Time: 0.095 ms
Execution Time: 120.487 ms-- Поиск с хеш-индексом
SET enable_seqscan = ON;
EXPLAIN ANALYZE
SELECT * FROM transactions WHERE user_id = 500;Index Scan using transactions_user_id_hash_idx on transactions (cost=0.42..8.56 rows=10 width=36) (actual time=0.005..0.023 rows=10 loops=1)
Index Cond: (user_id = 500)
Planning Time: 0.123 ms
Execution Time: 0.045 msПоясняем:
Поиск без индекса :используется последовательное сканирование всей таблицы
Seq Scan, что требует времени для проверки каждой строки. В этом примере, поиск занял около 120.487 миллисекунд, чтобы найти все строки сuser_id = 500.Поиск с хеш-индексом: используется индексное сканирование
Index Scan, что значительно ускоряет поиск. В этом примере, поиск занял всего 0.045 миллисекунд, чтобы найти все строки сuser_id = 500.
Если хеш-индекс больше не нужен, его можно удалить:
DROP INDEX IF EXISTS transactions_user_id_hash_idx;Для создания индексов в больших системах можно юзать скрипт для автоматизации:
DO $$
DECLARE
rec RECORD;
BEGIN
FOR rec IN (SELECT tablename, attname
FROM pg_catalog.pg_tables
JOIN pg_catalog.pg_attribute ON attrelid = pg_catalog.pg_class.oid
WHERE schemaname = 'public' AND attnum > 0)
LOOP
EXECUTE 'CREATE INDEX IF NOT EXISTS ' || rec.tablename || '_' || rec.attname || '_hash_idx ON ' || rec.tablename || ' USING hash (' || rec.attname || ');';
END LOOP;
END $$;В завершение хочу порекомендовать бесплатный урок курса «Базы данных». Тема урока: «Поднимаем MySQL, Percona Server и MariaDB в контейнерах».
