Привет, Хабр!

Хеш-индексы в 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 в контейнерах».

• Регистрация доступна по ссылке