[Перевод] Неочевидные проблемы с UUID ключами в PostgreSQL

9882eb3e788cee509db7f1ae124879e5

Оригинал статьи Ants Aasma

Существует множество причин использования универсального уникального идентификатора (UUID) в качестве первичного ключа таблиц баз данных. Например:

  • генерация ключей, независимо от базы данных

  • перенос наборов связанных записей из одной базы в другую без необходимости перенумерации

Однако, при всех выгодах, использование UUID имеет недостатки. Наиболее существенной проблемой является потеря связи между логическим и физическим порядками записей.

Самый распространенный способ получения UUID — случайный выбор 128-битного числа. (Если вас беспокоит возможность повтора случайных значений: выиграть джекпот в лотерее два раза подряд является гораздо более вероятным событием, чем повтор двух случайных 128-битных чисел). Стандартом генерации случайного 128-битного числа сейчас является UUID v4. В нем заданы фиксированные значения шести бит, что оставляет 122 бита для случайного выбора, но и этого вполне достаточно для всех практических целей. В PostgreSQL для получения UUID по стандарту v4 используется функция gen_random_uuid ().

Проблемы случайных чисел

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

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

Эксперимент

Для начала создадим таблицу записей с тремя идентификаторами: 1) из обычной последовательности, 2) случайный UUID, 3) последовательный UUID (используя метод UUID v7, который скоро будет стандартизирован). Добавим 100 байт заполнителя для каждой строки для реалистичности. В таблице будет 10 миллионов записей.

locality=# create table records (id int8 not null, uuid_v4 uuid not null, uuid_v7 uuid not null, filler text);
CREATE TABLE
Time: 98.515 ms
locality=# insert into records select id, gen_random_uuid(), uuid_generate_v7(), repeat(' ', 100) from generate_series(1, 10000000) id;
INSERT 0 10000000
Time: 28050.965 ms (00:28.051)

Добавим уникальный индекс для каждого из столбцов id, как в обычной таблице, и запустим VACUUM ANALYZE.

locality=# create index on records (id);
CREATE INDEX
Time: 1689.437 ms (00:01.689)
locality=# create index on records (uuid_v4);
CREATE INDEX
Time: 2378.215 ms (00:02.378)
locality=# create index on records (uuid_v7);
CREATE INDEX
Time: 1956.945 ms (00:01.957)
locality=# vacuum analyze records;
VACUUM
Time: 281.858 ms

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

locality=# select relname, pg_size_pretty(pg_relation_size(oid)), pg_prewarm(oid) from pg_class where relname like 'records%';
       relname       | pg_size_pretty | pg_prewarm 
---------------------+----------------+------------
 records             | 1662 MB        |     212766
 records_id_idx      | 214 MB         |      27422
 records_uuid_v4_idx | 301 MB         |      38506
 records_uuid_v7_idx | 301 MB         |      38506
(4 rows)
 
Time: 283.849 ms

Выполним пару index-only запросов, чтобы посмотреть как работают созданные индексы:

locality=# SELECT COUNT(id) FROM records;
  count  
----------
 10000000
(1 row)
 
Time: 526.486 ms
locality=# SELECT COUNT(uuid_v4) FROM records;
  count  
----------
 10000000
(1 row)
 
Time: 1213.813 ms (00:01.214)

Запрос по индексу с UUID примерно в два раза медленнее, но и размер самого UUID вдвое больше чем int8, так что пока все бьется, верно?

Теперь посмотрим на запрос по последовательному индексу по UUID (v7).

locality=# SELECT COUNT(uuid_v7) FROM records;
  count  
----------
 10000000
(1 row)
 
Time: 541.322 ms

Вот тут уже интересно. Похоже, что снижение скорости выполнения запроса вызвано использованием случайной последовательности, а не размером идентификатора. Смотрим планы запросов.

locality=# EXPLAIN (BUFFERS, ANALYZE, TIMING OFF) SELECT COUNT(id) FROM records;
                                                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=202422.47..202422.48 rows=1 width=8) (actual rows=1 loops=1)
   Buffers: shared hit=27332
   ->  Index Only Scan using records_id_idx on records  (cost=0.43..177422.46 rows=10000002 width=8) (actual rows=10000000 loops=1)
         Heap Fetches: 0
         Buffers: shared hit=27332
 Planning Time: 0.056 ms
 Execution Time: 777.764 ms
(7 rows)
locality=# EXPLAIN (BUFFERS, ANALYZE, TIMING OFF) SELECT COUNT(uuid_v4) FROM records;
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=213506.47..213506.48 rows=1 width=8) (actual rows=1 loops=1)
   Buffers: shared hit=8562960
   ->  Index Only Scan using records_uuid_v4_idx on records  (cost=0.43..188506.46 rows=10000002 width=16) (actual rows=10000000 loops=1)
         Heap Fetches: 0
         Buffers: shared hit=8562960
 Planning Time: 0.058 ms
 Execution Time: 1430.684 ms
(7 rows)

Ну и ну. Что тут происходит с обращениями к общим буферам в запросе со случайным UUID? Чтобы понять это, придется разобраться с тем как работает index-only сканирование в PostgreSQL.

Как работает index-only сканирование

В индексах PostgreSQL отсутствуют метаданные, по которым определяется видимость записей таблицы для текущего запроса. Таким образом, даже если мы читаем только индекс, нам все равно приходится проверять должна ли запись (tuple) быть включена в результаты запроса, а для этого требуется прочитать запись из индексируемой таблицы, где эти метаданные есть. И это довольно затратная операция, особенно в случае больших таблиц.

Оптимизация

В PostgreSQL необходимость чтения данных индексируемой таблицы учтена и оптимизирована. При очистке (vacuum) PostgreSQL отслеживает, какие страницы (блоки) полностью доступны для всех — это называется «видимость страницы». Данные по видимости страниц доступны в карте видимости (файл с суффиксом _vm, который хранится в том же каталоге что и данные таблицы). Для каждой страницы таблицы БД размером 8Кб карта видимости использует два бита (первый бит отмечает доступность для всех) — то есть карта видимости занимает в 32 768 раз меньше места, чем сама таблица, и поэтому легко кэшируется. При выполнении index-only выборки если карта видимости говорит, что страница, на которой находится запись, видна всем, то чтение записи из таблицы можно пропустить и сэкономить кучу времени.

Но ведь обе наших выборки обращаются к карте видимости, откуда же разница в результатах? Ответ заключается в том, что доступ к странице в общих буферах не является бесплатным — он включает блокировку, поиск в довольно большой хэш-таблице и запись отметки об уже просмотренных страницах. Если следующая запись в индексе ссылается на ту же самую страницу таблицы, что и предыдущая, все эти действия можно пропустить. Ну, вы поняли куда я клоню…

В чем проблема

Каждая страница карты видимости содержит данные о 8 192×8/2 = 32 768 страницах таблицы или 256 Мб. В случае с последовательным индексом близкие по значению идентификаторы практически всегда относятся к одной и той же странице карты видимости, поэтому оптимизация работает отлично. Однако, при случайных значениях UUID вероятность того, что два последовательных идентификатора ссылаются на одну и ту же страницу, составляет всего 1 из 7 (256 Mb / 1662 Mb — размер таблицы). Это приводит к необходимости выполнения около 6/7×10M ~ 8,5M дополнительных обращений к буферу для проверки видимости, что и отражено в плане запроса. Обращение к буферу стоит недорого, но оно не бесплатно, а уж если повторить его 8,5 миллионов раз, то разница в расходе ресурсов становится очевидной.

Для проверки посмотрим на план запроса с использованием индекса по последовательному UUID.

locality=# EXPLAIN (BUFFERS, ANALYZE, TIMING OFF) SELECT COUNT(uuid_v7) FROM records;
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=213506.47..213506.48 rows=1 width=8) (actual rows=1 loops=1)
   Buffers: shared hit=39126
   ->  Index Only Scan using records_uuid_v7_idx on records  (cost=0.43..188506.46 rows=10000002 width=16) (actual rows=10000000 loops=1)
         Heap Fetches: 0
         Buffers: shared hit=39126
 Planning Time: 0.058 ms
 Execution Time: 790.872 ms
(7 rows)

Как видим, количество обращений к общим буферам для индекса по UUID увеличилось относительно индекса по int8 пропорционально размеру данных в индексе (16 байт UUID / 8 байт int8).

Выводы

Мораль этой истории в том, что нужно учитывать физическую структуру данных: она может оказаться значимой в самых неожиданных местах. Использование случайных величин, как правило, является худшим из того что можно сделать для физической структуры, поэтому, если хочется непременно использовать UUID, попробуйте использовать последовательный вариант. UUID v7 — хороший вариант. Надеюсь, он появится в PostgreSQL 17. Your cache hit rates will thank you.

© Habrahabr.ru