panzerfaust Jul 14 2023 at 12:30

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

10 min

9.7K

Analytics

Translation

Если вы работает с базами данных, то, скорее всего, знакомы с 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 и выводим результаты на чарт:

Hash vs. B-Tree index size — Размер индексов Hash vs B-Tree

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

Хэш индекс занимает меньше места, чем 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;
$$;

Hash index size with different fillfactor values — Размеры хэш-индекса с разными значениями fillfactor

Чарт показывает, что меньший 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-05

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

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

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

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.
Хэш-индекс незначительно выигрывает в производительности как при вставке, так и при чтении.
Хэш-индекс имеет много ограничений, которые сводят его применимость к узкому ряду задач.

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

Tags:

Hubs: