06.07.2021 06:21
vadv 28 11400 Источник

"Хочешь ускорить запросы, построй индекс" – классический первый шаг по увеличению производительности в PostgreSQL. Вот только на практике можно встретить ситуацию, когда индексы в PostgreSQL есть, но тормоза никуда не делись. Не все индексы являются эффективными. Одна из возможных причин тормозов индексов – это отсутствие корреляции данных. Давайте сегодня поговорим о пенальти, которые дают расположение данных на производительность – почему это происходит и как это можно предотвратить.

Корреляция между физическим и логическим порядком значений
Корреляция между физическим и логическим порядком значений

Как можно идентифицировать равномерные и неравномерные данные

В системном представлении pg_stats для каждой таблицы есть поле correlation. В документации сказано, что это "статистическая корреляция между физическим порядком строк и логическим порядком значений столбца".

Давайте создадим таблицу:

CREATE EXTENSION IF NOT EXISTS "uuid-ossp";
CREATE TABLE example (corr, uncorr) AS
   SELECT i, uuid_generate_v4()
   FROM generate_series(1, 100000) AS i;
ANALYZE example;

Как мы видим, физическое распределение по полю corr происходит по возрастанию, а по полю uncorr – совсем рандомно:

select correlation from pg_stats where tablename = 'example' and attname = 'corr';
-[ RECORD 1 ]--
correlation | 1

select correlation from pg_stats where tablename = 'example' and attname = 'uncorr';
-[ RECORD 1 ]--------------
correlation | -0.0013047641

Давайте договоримся называть данные, у которых correlation близка к 1 или -1 – равномерными данными. А данные, у которых корреляция близка к нулю – неравномерными.

Для ускорения операций с данными используются индексы. Мы будем говорить о ситуации, когда над неравномерными данными построен индекс.

Перед тем, как двигаться дальше, давайте вспомним о базовых вещах насчёт индексов:

  • Данные и индексы PostgreSQL хранит в блоках, и для того, чтобы прочитать или записать одну строку из блока, PostgreSQL прочитает или запишет блок полностью (с оговоркой).

  • Любое чтение и запись блока происходит через Буферный менеджер (Buffer Manager), который аллоцирует блоки в Буферном кэше (Buffer pool). Чтение или запись приводит к тому, что клиентскому запросу (бакенду), выполняющему запрос, необходимо высвободить место в буферном кэше. Если приходится вытеснять "грязную" (не синхронизированную с диском страницу) бакенду придется записать страницу на диск.

  • B-Tree хранит данные в отсортированном виде, где каждый элемент индекса указывает на ctid (физическое расположение данных). Значение ctid состоит из двух цифр: Block и Number. Тут Block – это номер блока на странице; например, блок 0 указывает на область данных 0-8kB, а блок 10 – на область данных 80kB-88kB. Number – это номер "строки" в блоке.

  • Индексы PostgreSQL не хранят видимости. Это означает, что данные, расположенные в ctid, могут быть логически удалены и должны быть отфильтрованы при выполнении запроса. Таким образом обращение к индексу почти всегда вызывает чтение данных в таблице (обратите внимание на Heap Fetches в explain, подробнее тут).

Равномерные и неравномерные индексы

Соседние значения в индексе, построенном на неравномерных данных, могут указывать на данные, которые расположены физически далеко, в разных блоках таблицы. В нашем случае, 'aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa'::uuid и 'aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaab'::uuid с большой вероятностью (около 99.9%) будут разнесены хаотично по разным блокам таблицы.

Взглянем на содержимое индекса, выбираем для примера блок 21:

CREATE INDEX corr_idx ON example (corr);
CREATE INDEX uncorr_idx ON example (uncorr);
ANALYZE example;

CREATE EXTENSION IF NOT EXISTS pageinspect;

-- убеждаемся, что блок 21 в индексе – обычный лист btree-индекса (l)
SELECT corr.type, uncorr.type FROM bt_page_stats('corr_idx', 21) as corr, bt_page_stats('uncorr_idx', 21) as uncorr;
 type | type
------+------
 l    | l

-- соединяем index items с данными таблицы по ctid: (block, item)
SELECT bt.ctid as corr_heap_ctid, e.corr, e.uncorr FROM bt_page_items('uncorr_idx', 21) as bt INNER JOIN example e on e.ctid = bt.ctid LIMIT 5 OFFSET 1;
 corr_heap_ctid | corr  |                uncorr
----------------+-------+--------------------------------------
 (5,77)         |   862 | 0cc6e023-8c62-4a89-a066-d3879c99667d
 (227,155)      | 35794 | 0cc83303-ab36-4cb7-8f02-48ac8d1c22e4
 (158,92)       | 24898 | 0cc93ffe-b54d-4d81-b7da-946aac5e9268
 (177,10)       | 27799 | 0cc943c6-6551-45d9-ad02-69331a76773d
 (98,136)       | 15522 | 0cca5867-9c1c-43e2-95fa-a5479e4a39cd

-- тоже самое для равномерного индекса
SELECT bt.ctid as corr_heap_ctid, e.corr, e.uncorr FROM bt_page_items('corr_idx', 21) as bt INNER JOIN example e on e.ctid = bt.ctid LIMIT 5 OFFSET 1;
 corr_heap_ctid | corr |                uncorr
----------------+------+--------------------------------------
 (44,47)        | 6955 | 99e1675e-d402-4413-90cf-79c7b4bad88d
 (44,48)        | 6956 | 3dd37835-8c24-4f13-b284-e533763cb65d
 (44,49)        | 6957 | 1a18c970-f294-4a97-a31d-fae556c70be5
 (44,50)        | 6958 | fbbb36ce-93c0-4068-9e0a-a3d367cc725c
 (44,51)        | 6959 | d72c1154-23d3-4544-87b3-d7038c5be31b

В равномерном же индексе соседние значения указывают на один и тот же блок физических данных. Кстати, для равномерных данных в PostgreSQL был придуман BRIN-индекс, который хранит равномерные данные более эффективно, чем B-Tree.

В неравномерном индексе мы видим, что "соседние" (отсортированные) строки указывают на большое количество разных блоков в таблице.

Один блок неравномерного индекса указывает на большое количество блоков с данными в таблице
Один блок неравномерного индекса указывает на большое количество блоков с данными в таблице

Проблемы неравномерного индекса

Давайте кратко сформулируем основные проблемы неравномерного индекса:

  • Низкий page hit (переиспользование страниц буферного кэша) самого индекса: нет "горячих частей", таких, как компактное хранение всех id текущего дня в ограниченном количестве блоков индекса.

  • Рандомное чтение heap для проверки видимости значений в индексе, если не используется bitmap heap scan.

  • Дорогое обслуживание индекса: такие операции, как reindex/vacuum, вызывают дополнительное чтение и запись при ограниченном количестве буферного кэша.

С равномерными данными таблица делиться на "горячую" и "холодную" часть. В этом случае buffer pool (буферный кэш) более рационально используется, что приводит к уменьшению IOPS
С равномерными данными таблица делиться на "горячую" и "холодную" часть. В этом случае buffer pool (буферный кэш) более рационально используется, что приводит к уменьшению IOPS

Неравномерный индекс на чтении

Частный пример неравномерных данных – это UUID v4, который мы использовали в примере в самом начале. Гораздо чаще в реальной жизни можно встретить пример неравномерных данных, реализованных на менее специфических типах данных: int, varchar. Проведём надуманный, но жизненный эксперимент:

CREATE TABLE test_read (
    id bigserial primary key,
    user_id int not null,
    created_at timestamptz not null default current_timestamp,
    value int
);
CREATE INDEX idx_test_read_user_id_created_at on test_read (user_id, created_at desc);

Заполним данные:

\set user_id random(1, 2000)
begin;
 insert into test_read (user_id) values (:user_id);
end;

Начнём читать данные – последние N-операций пользователя:

explain (analyze,buffers) select value from test_read where user_id = 200 order by created_at limit 1000;
                                                                               QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.57..3883.09 rows=1000 width=12) (actual time=0.044..1.769 rows=1000 loops=1)
   Buffers: shared hit=969
   ->  Index Scan Backward using idx_test_read_user_id_created_at on test_read  (cost=0.57..252547.29 rows=65047 width=12) (actual time=0.042..1.664 rows=1000 loops=1)
         Index Cond: (user_id = 200)
         Buffers: shared hit=969

Как мы видим, в худшем случае придётся прочитать с диска почти столько страниц (совершить пропорциональное количество IOPS), сколько собираемся вернуть строчек:

кол-во строк

кол-во буферов (? IOPS)

10

14

100

100

1000

969

Происходит это из-за того, что как мы и говорили, строчки по конкретному пользователю разбросаны по разным страницам. Давайте отсортируем физическое расположение по пользователю при помощи команды CLUSTER:

cluster test_read using test_read_user_id_idx;

кол-во строк

кол-во буферов (? IOPS)

10

11

100

53

1000

408

Таким образом, получили почти двухкратный выигрыш. Пойдём дальше и выполним СLUSTER прямо по интересующему нас индексу:

cluster test_read USING idx_test_read_user_id_created_at;

кол-во строк

кол-во буферов (? IOPS)

10

5

100

6

1000

19

Благодаря тому, что физическая сортировка в базе совпадает с индексом, мы получили 50-кратный прирост по IOPS.

Конечно же, стоит ещё раз упомянуть, что CLUSTER не устанавливает физическую сортировку для новых данных и сортировка также теряется при обновлении исторических данных. Кроме команды CLUSTER, для кластеризации данных можно ещё воспользоваться стронней утилитой pg_repack.

Неравномерный индекс при наполнении

Что делать, если ваш индекс должен быть рандомным, как в примере с UUID v4? Давайте посмотрим, чтобы было придумано для того, чтобы превратить рандомные данные в равномерные.

Последовательный UUID

Идея простая: сгенерируем UUID, префикс которого зависит от какого-нибудь равномерно нарастающего значения: времени или счётчика. Тогда данные будут изменяться монотонно, и ближайшие сгенерированные значения с большей долей вероятностью окажутся на одной странице индекса.

Примеры реализации в PostgreSQL: tvondra/sequential-uuids от компании 2ndquadrant (сообщение в блоге).

Пример генерации значений, зависящий от времени
postgres=# select uuid_time_nextval();
          uuid_time_nextval
--------------------------------------
 2853857f-7563-4f06-92b1-9d10491e2854
(1 row)

postgres=# \watch 0.1
Fri 25 Jun 2021 06:11:19 AM UTC (every 0.1s)

          uuid_time_nextval
--------------------------------------
 28539092-f737-4bba-8036-7892e1ff9657
(1 row)

Fri 25 Jun 2021 06:11:19 AM UTC (every 0.1s)

          uuid_time_nextval
--------------------------------------
 285399a9-a908-4310-b95a-a977d771ada2
(1 row)

Fri 25 Jun 2021 06:11:19 AM UTC (every 0.1s)

          uuid_time_nextval
--------------------------------------
 28538529-0db4-4836-a002-341e912122ae
(1 row)

ULID

Идея похожа на предыдущую, но равномерная часть здесь больше:

 01AN4Z07BY      79KA1307SR9X4MV3

|----------|    |----------------|
 Timestamp          Randomness
  10chars            16chars
   48bits             80bits

В данном случае генерация может быть поручена  как клиенту, так PostgreSQL.

Пример генерации ULID на python-клиенте и plpgsql
-- curl https://raw.githubusercontent.com/geckoboard/pgulid/master/pgulid.sql | psql

postgres=# select now(), generate_ulid();
               now              |       generate_ulid
 -------------------------------+----------------------------
 2021-06-25 06:59:39.391656+00 | 01F90ZF2805C8GGXSA879VHWP5

postgres=# select now(), generate_ulid();
             now              |       generate_ulid
------------------------------+----------------------------
2021-06-25 06:59:39.84068+00 | 01F90ZF2P1BDGRW3JCXSAKK8CJ

# pip3 install ulid-py

>>> import ulid, time
>>> from datetime import datetime
генерация ulid на указанную дату
>>> ulid.from_timestamp(datetime.strptime('2000/01/01 00:00:00', '%Y/%m/%d %H:%M:%S'))
<ULID('00VHN2NR40QBMGKSF91V5HRVXP')>
>>> ulid.from_timestamp(datetime.strptime('2000/01/01 00:00:00', '%Y/%m/%d %H:%M:%S'))
<ULID('00VHN2NR40GFCHAMWYYW2MVYMC')>
проворот счетчика произойдет еще не скоро :)
>>> ulid.from_timestamp(datetime.strptime('3000/01/01 00:00:00', '%Y/%m/%d %H:%M:%S'))
<ULID('0XHZCTG540KKD2KAYJP2ZMQFPM')>
Примеры конвертации
# восстановить время из ULID, который сгенерировал plpgsql,
# можно с точностью до ms

>>> v = ulid.parse('01F90ZF2805C8GGXSA879VHWP5')
>>> print(v.timestamp().datetime);
2021-06-25 06:59:39.392000+00:00
# ULID совместим с UUID

>>> uuid.UUID(bytes=ulid.from_timestamp(time.time()).bytes)
UUID('017a422e-2c1c-b378-ac7f-411bbe4d6714')
>>> uuid.UUID(bytes=ulid.from_timestamp(time.time()).bytes)
UUID('017a422e-2e3d-4e8d-84fa-c63b21462531')
# UUID тоже можно превратить в ULID

>>> ulid.from_uuid(uuid.UUID('017a422e-2c1c-b378-ac7f-411bbe4d6714'))
<ULID('01F912WB0WPDWARZT13EZ4TSRM')>
>>> ulid.from_uuid(uuid.UUID('017a422e-2e3d-4e8d-84fa-c63b21462531'))
<ULID('01F912WBHX9T6R9YP67CGMC99H')>

Таким образом, в отличие от предыдущей реализации seq UUID:

  • не имеет проблем с wrap around в обозримом времени;

  • позволяет из ULID восстановить время, когда он был сгенерирован;

  • обеспечивает совместимость ULID с UUID, который может стать его совместимой заменой.

Тестирование различных типов индексов на запись

подготавливаем таблицы:
-- bigserial
CREATE TABLE test_serial (
    id bigserial PRIMARY KEY,
    created_at timestamp DEFAULT current_timestamp
);

-- uuid v4
CREATE TABLE test_uuid (
    id uuid PRIMARY KEY DEFAULT uuid_generate_v4(),
    created_at timestamp DEFAULT current_timestamp
);

-- ulid
CREATE TABLE test_ulid (
    id uuid PRIMARY KEY DEFAULT generate_ulid(),
    created_at timestamp DEFAULT current_timestamp
);

-- uuid
CREATE TABLE test_sequential_uuid_timestamp (
    id uuid PRIMARY KEY DEFAULT uuid_time_nextval(interval_length := 60, interval_count := 65536),
    created_at timestamp DEFAULT current_timestamp
);
и скрипт pgbench:
BEGIN;
  INSERT INTO :TEST_TABLE (created_at) values (current_timestamp);
END;

Результаты по количеству транзакций оказались предсказуемые:

Мы видим постепенную деградацию производительности неравномерного индекса. Происходит это из-за того, что с каждым новым значением в индексе растёт активный dataset (количество блоков, которые участвуют в операциях INSERT). В итоге нам начинает не хватать buffer pool для того, чтобы держать активный dataset, и у нас возрастает общий IOPS за счет чтения, пока всё не упрётся в физические ограничения.

При этом поражает, насколько больше неравномерный uuid генерирует WAL:

Падение скорости генерации WAL связано с тем, что нам приходиться больше читать
Падение скорости генерации WAL связано с тем, что нам приходиться больше читать

При этом в случае с UUID мы видим, как активно используется диск на чтение. Это связано с тем, что перед тем, как изменить страницу с индексом (одна запись – одна страница), её надо предварительно поднять в буфер. Тогда как в случае с равномерным индексом страница индекса, в которую надо произвести запись – уже находится в буфере.

Графики по IOPS
равномерный индекс использует, в основном, диск на запись
равномерный индекс использует, в основном, диск на запись
неравномерный индекс использует диск на запись и существенное чтение
неравномерный индекс использует диск на запись и существенное чтение

Итак, мы показали, что основная проблема при обновлении неравномерного индекса – это IOPS.

При неравномерных данных каждый новый INSERT генерирует чтение и запись в разные страницы индекса
При неравномерных данных каждый новый INSERT генерирует чтение и запись в разные страницы индекса

Бонус использования ULID

Хотел бы дополнить рассказ одним из бонусов использования зависимости ULID от времени в секционировании. Для примера воспользуемся модифицированной функцией generate_ulid:

модифицированная функция generate_ulid
CREATE OR REPLACE FUNCTION generate_ulid(at_in timestamptz default current_timestamp, entropy_in bool default true)
RETURNS TEXT
AS $$
DECLARE
  -- Crockford's Base32
  encoding   BYTEA = '0123456789ABCDEFGHJKMNPQRSTVWXYZ';
  timestamp  BYTEA = E'\\000\\000\\000\\000\\000\\000';
  output     TEXT = '';

  unix_time  BIGINT;
  ulid       BYTEA;
BEGIN
  -- 6 timestamp bytes
  unix_time = (EXTRACT(EPOCH FROM at_in) * 1000)::BIGINT;
  timestamp = SET_BYTE(timestamp, 0, (unix_time >> 40)::BIT(8)::INTEGER);
  timestamp = SET_BYTE(timestamp, 1, (unix_time >> 32)::BIT(8)::INTEGER);
  timestamp = SET_BYTE(timestamp, 2, (unix_time >> 24)::BIT(8)::INTEGER);
  timestamp = SET_BYTE(timestamp, 3, (unix_time >> 16)::BIT(8)::INTEGER);
  timestamp = SET_BYTE(timestamp, 4, (unix_time >> 8)::BIT(8)::INTEGER);
  timestamp = SET_BYTE(timestamp, 5, unix_time::BIT(8)::INTEGER);

  -- 10 entropy bytes
  ulid = timestamp || gen_random_bytes(10);

  -- Encode the timestamp
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 0) & 224) >> 5));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 0) & 31)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 1) & 248) >> 3));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 1) & 7) << 2) | ((GET_BYTE(ulid, 2) & 192) >> 6)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 2) & 62) >> 1));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 2) & 1) << 4) | ((GET_BYTE(ulid, 3) & 240) >> 4)));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 3) & 15) << 1) | ((GET_BYTE(ulid, 4) & 128) >> 7)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 4) & 124) >> 2));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 4) & 3) << 3) | ((GET_BYTE(ulid, 5) & 224) >> 5)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 5) & 31)));

if entropy_in then
  -- Encode the entropy
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 6) & 248) >> 3));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 6) & 7) << 2) | ((GET_BYTE(ulid, 7) & 192) >> 6)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 7) & 62) >> 1));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 7) & 1) << 4) | ((GET_BYTE(ulid, 8) & 240) >> 4)));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 8) & 15) << 1) | ((GET_BYTE(ulid, 9) & 128) >> 7)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 9) & 124) >> 2));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 9) & 3) << 3) | ((GET_BYTE(ulid, 10) & 224) >> 5)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 10) & 31)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 11) & 248) >> 3));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 11) & 7) << 2) | ((GET_BYTE(ulid, 12) & 192) >> 6)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 12) & 62) >> 1));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 12) & 1) << 4) | ((GET_BYTE(ulid, 13) & 240) >> 4)));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 13) & 15) << 1) | ((GET_BYTE(ulid, 14) & 128) >> 7)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 14) & 124) >> 2));
  output = output || CHR(GET_BYTE(encoding, ((GET_BYTE(ulid, 14) & 3) << 3) | ((GET_BYTE(ulid, 15) & 224) >> 5)));
  output = output || CHR(GET_BYTE(encoding, (GET_BYTE(ulid, 15) & 31)));
else
  output = output || '0000000000000000';
end if;

  RETURN output;
END
$$
LANGUAGE plpgsql
VOLATILE;

Допустим, нам необходимо секционирование большой таблицы по времени:

CREATE TABLE "table" (
  id text primary key not null default generate_ulid(now(), true),
  created_at timestamptz default current_timestamp,
  ...
) partition by range (id);

CREATE TABLE table_2021 partition of "table" for values
  from (generate_ulid('2021-01-01', false))
  to (generate_ulid('2022-01-01', false));

Благодаря тому, что функция generate_ulid() возвращает ULID, зависящий от времени, мы имеем право навесить constraint:

alter table table_2021 add constraint created_at_2021
  check (created_at >= '2021-01-01' and created_at < '2022-01-01');

Это позволит планеру при построении запроса выбирать правильную секцию, если в нашем запросе участвует время. Таким образом, мы создали псевдо-рандомный primary index по времени (в одной транзакции например можно сделать несколько записей в PK) :)

Научите ваш PostgreSQL правильно использовать данные

Эффективный индекс – строится на равномерных данных (об этом нам, помимо прочих, говорит документация).

Если вам нужен чистый рандом, попытайтесь сделать его равномерным. Это несложно.

Если в вашем случаем невозможно избавиться от неравномерных данных, постарайтесь сделать так, чтобы данные, которые могут вам потребоваться одновременно, лежали физически рядом. Например, данные о конкретных user_id, скорее всего, должны находиться как можно ближе друг к другу. Даже если на одну heap-страницу при с?анировании инде?са в среднем попадет две строч?и, это может уменьшить IOPS в два раза.

Помните, что вы всегда можете перестроить таблицу – с помощью CLUSTER (в монопольном доступе) или pg_repack (несовместимо с логической репликацией).

Знайте свои данные и успехов вам с индексами в борьбе с тормозами в вашей любимой базе данных, живите ровно!

UPD

Генерация большого количества WAL в случае с UUID связана с поведением FPW (full_page_write). Дело в том, что грязная страница в буфере пишется с FPW только один раз. Последующее изменения грязной страницы, находящейся в буфере, занимает небольшой размер в WAL. Так как в случае с UUID вытеснение из буфера происходит чаще, поэтому и запись FPW происходит значительно чаще.