Правда ли, что изменения ключей индекса выполняются «по месту»?

Автор: Paul Randal, Do changes to index keys really do in-place updates?

Сегодня утром в Twitter развернулась интересная дискуссия (её начал мой хороший друг Erin Stellato) о «встроенных» обновлениях (in‑place updates) записей индекса, когда значение ключа меняется, но запись остаётся на той же странице. Разные источники, включая книгу SQL Server 2008 Internals (стр. 361 — этот фрагмент я не писал и не рецензировал :-) ), описывают процесс — увы, неверно. Там говорится, что запись останется ровно в той же позиции на странице и изменятся лишь байты, хранящие ключ.

Это не так. Настоящие in‑place‑обновления значений ключей индекса не выполняются, начиная с версии 2005. Давайте нырнём в кроличью нору…

Вот простой пример:

CREATE DATABASE KeyUpdateTest;
GO
USE KeyUpdateTest;
GO
ALTER DATABASE KeyUpdateTest SET RECOVERY SIMPLE;
ALTER DATABASE KeyUpdateTest SET AUTO_CREATE_STATISTICS OFF;
ALTER DATABASE KeyUpdateTest SET AUTO_UPDATE_STATISTICS OFF;
GO
CREATE TABLE test (c1 INT, c2 VARCHAR (2000));
GO
CREATE CLUSTERED INDEX test_cl ON test (c1);
GO
CHECKPOINT;
GO
INSERT INTO test VALUES (1, REPLICATE ('Paul', 500));
GO
CHECKPOINT;
GO

Теперь посмотрим на саму страницу (хранимую процедуру, которую я использую ниже, можно взять из моей старой заметки Inside The Storage Engine: sp_AllocationMetadata – putting undocumented system catalog views to work):

EXEC sp_allocationMetadata 'test';
GO

Object Name Index ID Alloc Unit ID     Alloc Unit Type First Page Root Page First IAM Page
———– ——– —————– ————— ———- ——— ————–
test        1        72057594039762944 IN_ROW_DATA     (1:144)    (1:144)   (1:145)

DBCC TRACEON (3604);
GO
DBCC PAGE (keyupdatetest, 1, 144, 2);
GO

Memory Dump @0x0000000016A6A000

0000000016A6A000:   01010400 00c20001 00000000 00000800 †…..Â……….
0000000016A6A010:   00000000 00000100 1c000000 bd174108 †…………½.A.
0000000016A6A020:   90000000 01000000 1d000000 8a000000 †…………Š…
0000000016A6A030:   12000000 00000000 00000000 239dbd4a †…………#.½J
0000000016A6A040:   00000000 00000000 00000000 00000000 †…………….
0000000016A6A050:   00000000 00000000 00000000 00000000 †…………….
0000000016A6A060:   30000800 01000000 03000002 001100e1 †0…………..á
0000000016A6A070:   07506175 6c506175 6c506175 6c506175 †.PaulPaulPaulPau
0000000016A6A080:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000016A6A090:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000016A6A0A0:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000016A6A0B0:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
<snip>
0000000016A6A820:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000016A6A830:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000016A6A840:   6c000021 21212121 21212121 21212121 †l..!!!!!!!!!!!!!
0000000016A6A850:   21212121 21212121 21212121 21212121 †!!!!!!!!!!!!!!!!
<snip>
0000000016A6BFE0:   21212121 21212121 21212121 21212121 †!!!!!!!!!!!!!!!!
0000000016A6BFF0:   21212121 21212121 21212121 21216000 †!!!!!!!!!!!!!!`.

OFFSET TABLE:

Row – Offset
0 (0x0) – 96 (0x60)

Теперь обновлю строку:

UPDATE test SET c1 = 2 WHERE c1 = 1;
GO

И посмотрим на записи в журнале (в выводе ниже я убрал «чужие» записи, появившиеся до моей транзакции):

SELECT [Current LSN], [Operation], [Context],
 [Log Record Length], [Page ID], [Slot ID]
FROM fn_dblog (NULL, NULL);
GO

Current LSN             Operation           Context               Log Record Length Page ID        Slot ID
————————— ——————- ——————— —————– ————– ———–
0000001d:00000096:0011  LOP_BEGIN_XACT      LCX_NULL              112               NULL           NULL
0000001d:00000096:0012  LOP_DELETE_ROWS     LCX_MARK_AS_GHOST     2116              0001:00000090  0
0000001d:00000096:0013  LOP_MODIFY_HEADER   LCX_PFS               76                0001:00000001  0
0000001d:00000096:0014  LOP_SET_BITS        LCX_PFS               56                0001:00000001  0
0000001d:00000096:0015  LOP_INSERT_ROWS     LCX_CLUSTERED         2120              0001:00000090  1
0000001d:00000096:0016  LOP_COMMIT_XACT     LCX_NULL              52                NULL           NULL
0000001d:000000a2:0001  LOP_EXPUNGE_ROWS    LCX_CLUSTERED         64                0001:00000090  0
0000001d:000000a2:0002  LOP_SET_BITS        LCX_PFS               56                0001:00000001  0
0000001d:000000a2:0003  LOP_MODIFY_HEADER   LCX_PFS               76                0001:00000001  0

Строка удалена и затем вставлена. Посмотрите на длины записей в журнале! И на номера слотов. Новая строка попала в слот 1 (запись LOP_INSERT_ROWS), а слот 0 помечен как «фантомный» (LOP_DELETE_ROWS). Потом запускается очистка фантомов (LOP_EXPUNGE_ROWS), которая удаляет старый слот 0, массив слотов сдвигается, и новая запись снова становится слотом 0. Подробно об очистке фантомов — в моей статье Подробно об очистке фантомных строк.

Но находится ли запись в том же физическом месте на странице? Нет — создана совершенно новая запись.

DBCC PAGE (keyupdatetest, 1, 144, 2);
GO

Memory Dump @0x0000000013CAC000

0000000013CAC000:   01010400 00800001 00000000 00000800 †…………….
0000000013CAC010:   00000000 00000100 1c000000 bd172210 †…………½.".
0000000013CAC020:   90000000 01000000 1d000000 a2000000 †…………¢…
0000000013CAC030:   01000000 76020000 00000000 239dbd4a †….v…….#.½J
0000000013CAC040:   01000000 00000000 00000000 00000000 †…………….
0000000013CAC050:   00000000 00000000 00000000 00000000 †…………….
0000000013CAC060:   3c000800 01000000 03000002 001100e1 †<…………..á
0000000013CAC070:   07506175 6c506175 6c506175 6c506175 †.PaulPaulPaulPau
0000000013CAC080:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000013CAC090:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
<snip>
0000000013CAC820:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000013CAC830:   6c506175 6c506175 6c506175 6c506175 †lPaulPaulPaulPau
0000000013CAC840:   6c300008 00020000 00030000 02001100 †l0…………..
0000000013CAC850:   e1075061 756c5061 756c5061 756c5061 †á.PaulPaulPaulPa
0000000013CAC860:   756c5061 756c5061 756c5061 756c5061 †ulPaulPaulPaulPa
<snip>
0000000013CADFE0:   21212121 21212121 21212121 21212121 †!!!!!!!!!!!!!!!!
0000000013CADFF0:   21212121 21212121 21212121 41084108 †!!!!!!!!!!!!A.A.

OFFSET TABLE:

Row – Offset
0 (0x0) – 2113 (0x841)

Обратите внимание, где закончилась исходная запись (смещение 0x830 от начала страницы). В первом дампе всё после этого — пустое пространство. Во втором дампе новая запись начинается именно там. И посмотрите на массив слотов (в DBCC PAGE он называется offset table). В первом дампе исходная запись начиналась по смещению 0x60, во втором — по смещению 0x841. Несмотря на запуск очистки фантомов, запись НЕ вернулась на исходное место.

Очевидно, in‑place‑обновления не было — вся запись создана заново целиком.

В этом случае запись снова оказалась физическим слотом 0, но это «крайность»: на странице всего один слот. Если повторить эксперимент с двумя строками (например, c1=1 и c1=2), а затем обновить c1 у первой строки до 3, вы увидите, что новая запись сначала окажется физическим слотом 2, а после очистки фантомов станет слотом 1. Но и здесь — удаление и полная повторная вставка.

Теперь покажу случай, когда строка вынуждена перейти на другую страницу — уж точно не in‑place‑обновление!

CREATE DATABASE KeyUpdateTest;
GO
USE KeyUpdateTest;
GO
ALTER DATABASE KeyUpdateTest SET RECOVERY SIMPLE;
ALTER DATABASE KeyUpdateTest SET AUTO_CREATE_STATISTICS OFF;
ALTER DATABASE KeyUpdateTest SET AUTO_UPDATE_STATISTICS OFF;
GO
CREATE TABLE test (c1 INT, c2 VARCHAR (4000));
GO
CREATE CLUSTERED INDEX test_cl ON test (c1);
GO
CHECKPOINT;
GO
INSERT INTO test VALUES (1, REPLICATE ('Paul', 1000));
GO
INSERT INTO test VALUES (2, REPLICATE ('Erin', 1000));
GO
CHECKPOINT;
GO

Я заполнил страницу двумя строками.

DBCC PAGE (keyupdatetest, 1, 144, 2);
GO
<snip>
Metadata: ObjectId = 2105058535      m_prevPage = (0:0)                   m_nextPage = (0:0)
pminlen = 8                          m_slotCnt = 2                        m_freeCnt = 58
m_freeData = 8130                    m_reservedCnt = 0                    m_lsn = (29:150:2)
<snip>
0000000016A6BFA0:   696e4572 696e4572 696e4572 696e4572 †inErinErinErinEr
0000000016A6BFB0:   696e4572 696e4572 696e4572 696e4572 †inErinErinErinEr
0000000016A6BFC0:   696e0000 21212121 21212121 21212121 †in..!!!!!!!!!!!!
0000000016A6BFD0:   21212121 21212121 21212121 21212121 †!!!!!!!!!!!!!!!!
0000000016A6BFE0:   21212121 21212121 21212121 21212121 †!!!!!!!!!!!!!!!!
0000000016A6BFF0:   21212121 21212121 21212121 11106000 †!!!!!!!!!!!!..`.

OFFSET TABLE:

Row – Offset
1 (0x1) – 4113 (0x1011)
0 (0x0) – 96 (0x60)

Теперь обновлю первую строку, чтобы c1 = 3 — моя строка «уедет» от Erin :-)

UPDATE test SET c1 = 3 WHERE c1 = 1;
GO

И посмотрим журнал:

SELECT [Current LSN], [Operation], [Context],
 [Log Record Length], [Page ID], [Slot ID]
FROM fn_dblog (NULL, NULL);
GO

Current LSN             Operation           Context                Log Record Length Page ID        Slot ID
————————— ——————- ———————- —————– ————– ———–
0000001d:000000a3:0015  LOP_BEGIN_XACT      LCX_NULL               136               NULL           NULL
0000001d:000000a3:0016  LOP_MODIFY_ROW      LCX_PFS                80                0001:00000001  0
0000001d:000000a3:0017  LOP_MODIFY_ROW      LCX_IAM                88                0001:00000091  0
0000001d:000000a3:0018  LOP_HOBT_DELTA      LCX_NULL               64                NULL           NULL
0000001d:000000a3:0019  LOP_FORMAT_PAGE     LCX_INDEX_INTERIOR     84                0001:00000092  -1
0000001d:000000a3:001a  LOP_INSERT_ROWS     LCX_INDEX_INTERIOR     84                0001:00000092  0
0000001d:000000a3:001b  LOP_ROOT_CHANGE     LCX_CLUSTERED          96                0001:00000082  52
0000001d:000000a3:001c  LOP_COMMIT_XACT     LCX_NULL               52                NULL           NULL
0000001d:000000a3:001d  LOP_BEGIN_XACT      LCX_NULL               120               NULL           NULL
0000001d:000000a3:001e  LOP_MODIFY_ROW      LCX_PFS                80                0001:00000001  0
0000001d:000000a3:001f  LOP_MODIFY_ROW      LCX_IAM                88                0001:00000091  0
0000001d:000000a3:0020  LOP_HOBT_DELTA      LCX_NULL               64                NULL           NULL
0000001d:000000a3:0021  LOP_FORMAT_PAGE     LCX_HEAP               84                0001:00000093  -1
0000001d:000000a3:0022  LOP_INSERT_ROWS     LCX_CLUSTERED          4092              0001:00000093  0
0000001d:000000a3:0023  LOP_DELETE_SPLIT    LCX_CLUSTERED          60                0001:00000090  1
0000001d:000000a3:0024  LOP_MODIFY_HEADER   LCX_HEAP               84                0001:00000090  0
0000001d:000000a3:0025  LOP_INSERT_ROWS     LCX_INDEX_INTERIOR     88                0001:00000092  1
0000001d:000000a3:0026  LOP_COMMIT_XACT     LCX_NULL               52                NULL           NULL
0000001d:000000a3:0027  LOP_INSERT_ROWS     LCX_CLUSTERED          4120              0001:00000093  1
0000001d:000000a3:0028  LOP_COMMIT_XACT     LCX_NULL               52                NULL           NULL

Это действительно любопытно. Что происходит (для ясности опущу некоторые детали):

• 0000001d:000000a3:0016: страница (1:146) выделяется под новый корень кластерного индекса;
• 0000001d:000000a3:0019: она минимально форматируется (только заголовок; хотя заголовок — 96 байт, в конце остаётся 12 байт пустоты);
• 0000001d:000000a3:001a: в корневую страницу вставляется индексная запись, указывающая на (1:144);
• 0000001d:000000a3:001b: в метаданных корень индекса меняется с (1:144) на (1:146);
• 0000001d:000000a3:001e: страница (1:147) выделяется как вторая листовая страница данных кластерного индекса;
• 0000001d:000000a3:0022: происходит расщепление страницы (1:144), строка Erin переносится в слот 0 страницы (1:147);
• 0000001d:000000a3:0023: строка Erin удаляется со страницы (1:144) — без «фантомов»;
• 0000001d:000000a3:0025: в корень вставляется указатель на (1:147);
• 0000001d:000000a3:0027: обновлённая строка Paul вставляется как слот 1 на странице (1:147).

Как видите, это максимально далеко от in‑place‑обновления. Страница (1:144) остаётся с одной «фантомной» записью (Paul — строка Erin не «фантом», потому что была перемещена из‑за сплита). При следующем обращении к странице очистка призраков удалит её и страница будет деаллоцирована.

Итак, in‑place‑обновления значений ключей не происходят, даже если на первый взгляд кажется иначе. Вы можете поэкспериментировать и увидеть то же самое в некластерных индексах.

Ещё одно заблуждение — в копилку!

PS Некоторые из вас могут помнить времена, когда такие in‑place‑обновления действительно были. Это было до версии 2005, когда задачами обслуживания индексов занимался Storage Engine (конкретно моя прежняя команда Access Methods), меняя структуры кластерных и некластерных индексов при изменении ключей. Целая россыпь функций в версии 2005 привела к тому, что эту работу передали процессору запросов (Query Processor), и прежние изящные «шорткаты» стали невозможны.