Внутристраничная очистка (HOT cleanup) – это оптимизация, благодаря которой старые версии строк могут эффективно удаляться из блоков таблиц. Освобождённое место используется под размещение новой версии строки. Освобождается только место, занимаемое версиями строк, вышедшими за горизонт базы данных (xmin horizon). В статье рассматривается алгоритм работы аналогичной оптимизации для индексов. Если горизонт удерживается, то ни внутристраничная очистка, ни вакуум не могут освободить место, и тогда новая версия строки вставляется в другой блок. Увидим на примере стандартного теста pgbench, как сильно может снижаться производительность при удержании горизонта базы данных (в случае когда есть сессия с долгим запросом или транзакцией) и разберемся в причинах снижения производительности.

Алгоритм быстрой очистки табличной страницы реализован в файле pruneheap.c (heap page pruning and HOT-chain management code) исходного кода PostgreSQL. При удалении строки в блоке (странице) таблицы удаляющая транзакция проставляет свой номер в заголовок строки в поле xmax и пытается найти место под новую версию строки в том же самом блоке, при этом признак фиксации не проставляется. При следующем обращении к строке другой процесс обычно сверяется со статусом транзакции в буфере XLOG Ctl (CLOG) и иногда — в буфере статуса мультитранзакций Shared MultiXact State. По результатам сверки в заголовке строки таблицы выставляются биты-подсказки о том, что транзакция, удалившая строку, была зафиксирована или отменена. При этом на строку могут ссылаться записи индексов, созданных на таблицу. Если доступ к строке таблицы был не через индекс, то индекс никак не обновляется, впрочем, как и все остальные индексы, созданные на таблицу.

Однако если процесс при доступе к строке использовал индекс (Index Scan), и этот процесс обнаруживает, что строка (или цепочка строк, на которую ссылается индексная запись) удалена и вышла за горизонт базы, то в индексной записи листового блока (leaf page) в lp_flags он установит бит-подсказку LP_DEAD (ее называют known dead, killed tuple). Очистка реализована в файле indexam.c исходного кода PostgreSQL и описана так: If we scanned a whole HOT chain and found only dead tuples, tell index AM to kill its entry for that TID.

LP_DEAD устанавливается в записи того индекса, через который был получен доступ к строке.

LP_DEAD устанавливается независимо от того, была ли строка (или цепочка строк, на которую ссылается индексная запись) удалена ранее или этим же процессом.

Вставку этого бита-подсказки называют внутристраничной очисткой в индексах. Бит можно посмотреть в столбце dead, выдаваемый функцией bt_page_items ('имя_индекса',номер_блока).

Пример создания цепочки версий строк и очистки индексных записей

Создадим таблицу, вставим строки и удалим часть строк:

create extension if not exists pageinspect;
drop table t;
create table t (id int primary key, c text) with (autovacuum_enabled = off);
insert into t SELECT i, 'some text ' || i from generate_series(1, 10000) as i;
delete from t where id between 100 and 9000;
analyze t;
CREATE EXTENSION
DROP TABLE
CREATE TABLE
INSERT 0 10000
DELETE 8901
ANALYZE
В таблице 68 блоков, в индексе 30 блоков:
select pg_table_size('t')/8192 table_size, pg_relation_size('t_pkey')/8192 index_size;
 table_size | index_size
------------+------------
         68 |         30
(1 row)

В листовых блоках индекса, записи которого ссылаются на удалённые строки, индексные записи пока не имеют признака удалённых (dead = f):

select itemoffset, ctid, itemlen, dead, left(data,8) data from bt_page_items('t_pkey',20) limit 3;
 itemoffset |  ctid    | itemlen | dead | data
------------+----------+---------+------+-----------
          1 | (44,1)   |      16 |      | 2b 1b 00
          2 | (42,151) |      16 | f    | bd 19 00
          3 | (41,152) |      16 | f    | be 19 00

Первая запись в блоке индекса (itemoffset=1) не хранит ссылку на строку таблицы, она хранит High Key. В столбце ctid – ссылка на строку в блоке таблицы в формате (номер блока, номер указателя на строку).

Выполним индексное сканирование таблицы. Быстрая очистка индексов происходит только при индексном сканировании, именно поэтому в таблице удаляли часть строк, а в следующем запросе часть строк выбирается — это необходимо для того, чтобы планировщик выбрал Index Scan. Чтобы убедиться, что выбрано индексное сканирование, и чтобы на экран не выводилось много строк, используется команда explain:

explain (analyze, settings, buffers, costs off) select * from t where id between 1 and 9000;

                   QUERY PLAN
------------------------------------------------------------------
 Index Scan using t_pkey on t (actual time=0.023..1.667 rows=99 loops=1)
   Index Cond: ((id >= 1) AND (id <= 9000))
   Buffers: shared hit=109 dirtied=17
 Planning:
   Buffers: shared hit=15 dirtied=2
 Planning Time: 0.147 ms
 Execution Time: 1.822 ms
(7 rows)

Серверный процесс с помощью индекса обратился к блокам таблицы. В таблице 68 блоков, а команда обратилась к 109+17 блоков. В 109 блоков входят блоки индекса, которые использовались для поиска строк таблицы. Очистив строки в блоках таблицы, серверный процесс вернулся в листовые блоки индекса и пометил индексные записи как мёртвые (проставил бит dead), то есть, выполнил очистку записей в листовых блоках индекса:

select itemoffset, ctid, itemlen, dead, left(data,8) data from bt_page_items('t_pkey',20) limit 3;
 itemoffset |   ctid   | itemlen | dead |   data
------------+----------+---------+------+----------
          1 | (44,1)   |      16 |      | 2b 1b 00
          2 | (41,151) |      16 | t    | bd 19 00
          3 | (41,152) |      16 | t    | be 19 00
(3 rows)

В столбце dead значение 't' указывает на то, что запись в индексе помечена как ведущая на мертвую (удалённую) версию строки таблицы и по этой ссылке переходить не нужно, ее нужно игнорировать.

При Bitmap Index Scan и Seq Scan (неиндексном доступе) бит-подсказка не устанавливается. Помеченная таким флагом строка будет удалена позже, при выполнении команды, которая вносит изменения в блок индекса, например, UPDATE.

Возврат в блок и установка в нем флага добавляет накладные расходы и увеличивает время выполнения команды (Execution Time: 1.822 ms), но делается однократно. Последующие запросы смогут игнорировать индексную запись и не будут обращаться к блоку таблицы, на которую ведёт ссылка мёртвой индексной записи.

Выполним запрос повторно:

explain (analyze, settings, buffers, costs off) select * from t where id between 1 and 9000;

                               QUERY PLAN
-------------------------------------------------------------
 Index Scan using t_pkey on t (actual time=0.012..0.203 rows=99 loops=1)
   Index Cond: ((id >= 1) AND (id <= 9000))
   Buffers: shared hit=27
 Planning:
   Buffers: shared hit=3
 Planning Time: 0.085 ms
 Execution Time: 0.356 ms
(7 rows)

В этот раз (и последующие) команда прочла 27 блоков вместо 109. Время выполнения команды уменьшилось с 1.822 мс до 0.356 мс, абсолютные значения выглядят незначительными, однако под нагрузкой и при большем числе строк разница уже будет существенной.

Проверим это теперь стандартным тестом pgbench.

Влияние внутристраничной очистки на производительность

Для теста возьмем самую маленькую таблицу pgbench_branches, в которой всего одна строка. Создадим тестовые таблицы pgbench и отключим автовакуум, чтобы он не очистил блоки внезапно. При работе теста автовакуум не оказывает влияние на показатели, так как не может очищать версии строк, не вышедшие за горизонт базы данных.

pgbench -i
psql -c "alter table pgbench_branches set (autovacuum_enabled=off)"

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

begin;
select pg_current_xact_id();

В первом терминале запустим стандартный тест:

pgbench -T 100000 -P 30
progress: 30.0 s, 510.9 tps, lat 1.954 ms stddev 1.278, 0 failed
progress: 60.0 s, 374.2 tps, lat 2.670 ms stddev 1.959, 0 failed
progress: 90.0 s, 308.6 tps, lat 3.238 ms stddev 1.583, 0 failed
progress: 120.0 s, 255.5 tps, lat 3.911 ms stddev 1.989, 0 failed
progress: 150.0 s, 211.3 tps, lat 4.730 ms stddev 2.706, 0 failed
progress: 180.0 s, 163.9 tps, lat 6.098 ms stddev 4.372, 0 failed
progress: 210.0 s, 130.1 tps, lat 7.684 ms stddev 5.986, 0 failed
progress: 240.0 s, 102.7 tps, lat 9.735 ms stddev 7.363, 0 failed
progress: 270.0 s, 70.9 tps, lat 14.094 ms stddev 9.706, 0 failed
progress: 300.0 s, 62.4 tps, lat 16.018 ms stddev 9.223, 0 failed

Из-за удержания горизонта старые версии строк, создаваемые командами UPDATE (которые отправляет на выполнение pgbench), не смогут очищаться ни быстрой внутристраничной очисткой, ни автовакуумом. Версии строк начнут накапливаться в блоках.

В таблице pgbench_branches одна строка, и в каждой транзакции будет создаваться новая версия этой строки. В блоке может поместиться 226 версий строк, и как только место будет исчерпано, вставки новых версий строк пойдут уже в другой блок. Строка обновляется командой: UPDATE pgbench_branches SET bbalance = bbalance + :delta WHERE bid = :bid;

select lp, t_ctid, (t_infomask2 & 16384)!=0 hhu, (t_infomask2 & 32768)!=0 hot from heap_page_items(get_raw_page('pgbench_branches', 0));
 lp  | t_ctid  | hhu | hot 
-----+---------+-----+-----
   1 | (0,2)   | t   | f
   2 | (0,3)   | t   | t
...
 224 | (0,225) | t   | t
 226 | (1,1)   | f   | t
(4 rows)

В каждом блоке будет цепочка версий, и на первую добавленную в блок версию строки в индексе будет указывать отдельная ссылка. Для остальных версий строк индексные записи отсутствуют благодаря оптимизации HOT update. Индекс создан на столбец bid, а обновляется столбец bbalance. В примере и на изображении для простоты показаны цепочки версий одной строки, но в реальности в одном блоке таблицы может быть несколько цепочек версий разных строк.

begin transaction isolation level repeatable read;
EXPLAIN (analyze, timing off, buffers) select bbalance from pgbench_branches WHERE bid = 1;
select pg_table_size('pgbench_branches')/8192 table_size, pg_relation_size('pgbench_branches_pkey')/8192 index_size;
select blkno, type, live_items, dead_items, avg_item_size, free_size  from bt_multi_page_stats('pgbench_branches_pkey',1,-1);
select itemoffset, ctid, itemlen, dead, left(data,2) data from bt_page_items('pgbench_branches_pkey',1) limit 5;
rollback;
BEGIN
              QUERY PLAN
-----------------------------------------
 Index Scan using pgbench_branches_pkey on pgbench_branches  (cost=0.15..8.17 rows=1 width=4) (actual rows=1 loops=1)
   Index Cond: (bid = 1)
   Buffers: shared hit=374
 Planning Time: 0.052 ms
 Execution Time: 5.053 ms
(5 rows)
 table_size | index_size
------------+------------
        377 |          2
(1 row)
 blkno | type | live_items | dead_items | avg_item_size | free_size 
-------+------+------------+------------+---------------+-----------
     1 | l    |        373 |          0 |            16 |       688
(1 row)
 itemoffset | ctid  | itemlen |  dead | data  
------------+-------+---------+-------+-----
          1 | (0,1) |      16 | f     | 01
          2 | (1,1) |      16 | f     | 01
          3 | (2,1) |      16 | f     | 01
          4 | (3,1) |      16 | f     | 01
          5 | (4,1) |      16 | f     | 01
(5 rows)

Почему в первой строке нет HighKey? Дело в том, что дерево индекса состоит из одного блока, который является и корневым и листовым правым. В правых блоках индекса отсутствует HighKey. Через 600 секунд работы теста таблица разрослась до 377 блоков, и это при том, что в таблице всего одна строка. Это пример раздувания (bloat) таблицы. В индексе 373 записи, и при каждом обращении к таблице сканируется Buffers: shared hit=374 буферов.

progress: 600.0 s, 48.7 tps, lat 20.530 ms stddev 8.386, 0 failed
progress: 630.0 s, 42.0 tps, lat 23.821 ms stddev 10.743, 0 failed
progress: 660.0 s, 47.6 tps, lat 21.026 ms stddev 12.074, 0 failed
progress: 690.0 s, 45.1 tps, lat 22.165 ms stddev 11.254, 0 failed
progress: 720.0 s, 43.7 tps, lat 22.905 ms stddev 10.442, 0 failed

Снижение tps довольно существенное — больше, чем в 10 раз за полчаса.

На 900 секунде теста начнется дедупликация в блоке индекса:

begin transaction isolation level repeatable read;
select pg_table_size('pgbench_branches')/8192 table_size, pg_relation_size('pgbench_branches_pkey')/8192 index_size;
select blkno, type, live_items, dead_items, avg_item_size, free_size  from bt_multi_page_stats('pgbench_branches_pkey',1,-1);
select itemoffset, ctid, itemlen, dead, left(data,2) data, left(tids::text,11) tids from bt_page_items('pgbench_branches_pkey',1) limit 5;
rollback;
 table_size | index_size
------------+------------
        421 |          2
(1 row)
 blkno | type | live_items | dead_items | avg_item_size | free_size 
-------+------+------------+------------+---------------+-----------
     1 | l    |         12 |          0 |           220 |      5460
(1 row)
 itemoffset |   ctid    | itemlen |  dead | data | tids
------------+-----------+---------+-------+------+------------
          1 | (16,8414) |    1352 | f     | 01   | {"(0,1)","(
          2 | (16,8377) |    1128 | f     | 01   | {"(222,1)",
          3 | (407,1)   |      16 | f     | 01   |
          4 | (408,1)   |      16 | f     | 01   | 
          5 | (409,1)   |      16 | f     | 01   | 
(5 rows)

Две первые записи хранят массив ссылок (tids) на вставленные первыми в блок версии строк в цепочке версий в каждом блоке таблицы. У первых двух записей длина itemlen=1352 и 1128. Значение live_items уменьшилось с 373 до 12, при этом в блоке индекса хранится 409 ссылок на версии строк таблицы. Почему число записей (live_items) в блоке индекса уменьшилось? Потому, что дедупликация выполняется, когда в блоке нет места. Сначала в блоке накапливались записи размером 16 байт, каждая из которых хранила ссылку на версию строки в блоке таблицы. Как только места стало не хватать, была выполнена дедупликация: записи индекса были помещены в 2 записи. Новые записи вставляются недедуплицированными. Как только в блоке снова не станет места, дедупликация выполнится снова.

Индекс состоит из двух блоков (16 Кб): одного листового блока (он же корневой блок) и блока метаданных:

select pg_table_size('pgbench_branches')/8192 table_size, pg_relation_size('pgbench_branches_pkey')/8192 index_size;
 table_size | index_size
------------+------------
        713 |          2
(1 row)

Можно подождать еще какое-то время, в первом терминале (с работающим тестом pgbench) показатель tps будет постепенно снижаться.

Завершим в первом терминале тест pgbench комбинацией клавиш Ctrl+C. Во втором терминале завершим транзакцию, удерживающую горизонт базы:

postgres=# begin;
BEGIN
postgres=*# select pg_current_xact_id();
 pg_current_xact_id 
--------------------
           16375547
(1 row)
postgres=*# rollback;

Выполним команду:

explain (analyze, timing off, buffers) select bbalance from pgbench_branches where bid = 1;

                    QUERY PLAN
-----------------------------------------------------------
 Index Scan using pgbench_branches_pkey on pgbench_branches  (cost=0.15..8.17 rows=1 width=4) (actual rows=1 loops=1)
   Index Cond: (bid = 1)
   Buffers: shared hit=711 dirtied=522
 Planning Time: 0.077 ms
 Execution Time: 8.349 ms
(5 rows)

Это первый запрос к таблице после того, как перестал удерживаться горизонт. Все версии строк, кроме последней, вышли за горизонт, и их можно очищать. В начале теста мы отключили автовакуум, чтобы он не успел это сделать раньше этой команды. При обращении к таблице способом Index Scan серверный процесс просканирует цепочку до актуальной версии строки, выполнит быструю очистку блоков таблицы и одновременно внутристраничную очистку индекса. На это указывает строка плана Buffers: shared hit=711 dirtied=522. 

Выполнение запроса заняло 8.349 ms. Примерно такой и была длительность выполнения запроса к таблице pgbench_branches в процессе выполнения теста. Индекс состоит из одного блока, и его очистка не оказывала влияние на длительность команды UPDATE.

Что снижает tps стандартного теста pgbench, когда горизонт удерживается? Этот показатель снижают две команды UPDATE на таблицы pgbench_branches и pgbench_tellers. Каждый раз команда UPDATE pgbench_branches обращалась ко всем блокам таблицы. Команда UPDATE pgbench_tellers обращалась к примерно 1/10 блоков таблицы, но в индексе было большое число блоков. Так что вклад обеих команд в снижение tps примерно равнозначен.

В таблице pgbench_accounts — 10 000 строк. В одной транзакции теста (число которых показывает tps) обновляется по одной строке каждой таблицы: pgbench_accounts, pgbench_tellers, pgbench_branches. В таблице pgbench_accounts длинные цепочки создаваться не успевают, и цепочки версий ограничены преимущественно одним блоком. Это происходит из-за того, что вероятность для команды UPDATE попасть в одну и ту же строку – 1/10000. В pg_bench_branches строка одна, и поэтому она обновляется в каждой транзакции. Команды теста (SELECT и UPDATE), обращающиеся к таблице pgbench_accounts, в первые часы работы теста влияния на tps не оказывают.

Повторное выполнение запросов к таблице pgbench_branches будет уже моментальным:

EXPLAIN (analyze, timing off, buffers) select bbalance from pgbench_branches WHERE bid = 1;
                      QUERY PLAN
------------------------------------------------------------------
 Index Scan using pgbench_branches_pkey on pgbench_branches  (cost=0.15..8.17 rows=1 width=4) (actual rows=1 loops=1)
   Index Cond: (bid = 1)
   Buffers: shared hit=2
 Planning Time: 0.037 ms
 Execution Time: 0.024 ms
(5 rows)

Выполним запросы:

select pg_table_size('pgbench_branches')/8192 table_size, pg_relation_size('pgbench_branches_pkey')/8192 index_size;
select blkno, type, live_items, dead_items, avg_item_size, free_size  from bt_multi_page_stats('pgbench_branches_pkey',1,-1);
select itemoffset, ctid, itemlen, dead, left(data,2) data, left(tids::text,11) tids from bt_page_items('pgbench_branches_pkey',1) limit 5;
 table_size | index_size
------------+------------
        713 |          2
(1 row)
 blkno | type | live_items | dead_items | avg_item_size | free_size 
-------+------+------------+------------+---------------+-----------
     1 | l    |          1 |         22 |           196 |      3536
(1 row)
 itemoffset |   ctid    | itemlen |  dead | data | tids
------------+-----------+---------+-------+------+-----------
          1 | (16,8414) |    1352 |  t    | 01   | {"(0,1)","(
          2 | (16,8414) |    1352 |  t    | 01   | {"(222,1)",
          3 | (16,8414) |    1352 |  t    | 01   | {"(444,1)",
          4 | (16,8414) |    1352 |  t    | 01   | {"(666,1)",
          5 | (16,8414) |    1352 |  t    | 01   | {"(888,1)",
(5 rows)

Запустим снова тест, и если горизонт базы не удерживать, tps снижаться не будут:

pgbench -n -T 100000 -P 10
pgbench (17.0 (Ubuntu 17.0-1.pgdg22.04+1))
progress: 10.0 s, 618.5 tps, lat 1.613 ms stddev 1.571, 0 failed
progress: 20.0 s, 593.4 tps, lat 1.682 ms stddev 1.482, 0 failed
progress: 30.0 s, 617.6 tps, lat 1.616 ms stddev 1.084, 0 failed
progress: 40.0 s, 650.2 tps, lat 1.535 ms stddev 0.176, 0 failed

Видно, что tps увеличился с 43.7 до 650.

Из-за чего возникает снижение tps при удержании горизонта? Причина в том, что ни в таблице, ни в индексе не работает быстрая внутристраничная очистка (HOT prune/cleanup). Из-за частого (со скоростью tps) обновления строки создается очень длинная цепочка версий, которая располагается в большом числе блоков. Из-за этого при каждом обращении к строке сканируются все её версии, они разбиты на цепочки hhu (heap hot update, бит в заголовке строки таблицы) в блоках. Если горизонт не удерживается, внутристраничная очистка блока таблицы эффективно освобождает место под новые строки. Если же горизонт удерживается настолько долго, что update не находит места в блоке, то будет строиться новая цепочка hhu в других блоках (в примере в блок помещается 226 версий строки, при tps = 226 это секунда).

Как только горизонт сдвинется, тут же сработает очистка в индексе. Если горизонт долго удерживался и резко сдвинется, очистка выглядит как проседание tps — в это время однократно происходит очистка и потом увеличение tps. Число записей в индексе будет равно числу блоков таблицы. Благодаря дедупликации число записей будет очень большим, а индекс будет довольно долго состоять из одного листового (корневого) блока и блока метаданных. В дальнейшем размер индекса увеличится, но увеличение индекса на tps не повлияет. С дедупликациями tps выше, чем без него, и кривая изменения tps выглядит несколько иначе.

Резюме

Мы описали алгоритм и показали примеры работы внутристраничной очистки индекса. Удержание горизонта долгим запросом, транзакцией или запросами на реплике с обратной связью не позволяет удалять старые версии строк ни вакууму, ни быстрой очистке, и это может существенно увеличить время выполнения команд помимо раздувания таблиц и индексов. Стандартный тест pgbench позволяет наблюдать за снижением производительности выполнения команд теста, и в рамках данной статьи мы рассмотрели механизм снижения производительности вследствие появления длинных цепочек версий строк таблиц и отсутствия внутристраничной очистки блоков таблиц и индексов. Снижению производительности подвержены таблицы, в которых часто обновляется небольшое число строк.