Доказательство того, что записи не всегда физически хранятся в порядке ключа индекса

Автор: Paul Randal, Inside the Storage Engine: Proof that records are not always physically stored in index key order

Я упоминал это в публикации «Анатомия страницы» — существует распространённое заблуждение, будто записи в индексе ВСЕГДА хранятся в том же физическом порядке, что и логический порядок, определяемый ключом индекса. Вот доказательство того, что это неверно (и заодно небольшое знакомство с другими стилями дампа для DBCC PAGE).

Я создам таблицу с кластерным индексом по целочисленному столбцу и для простоты удержу таблицу в пределах одной страницы:

USE [master];
GO
IF DATABASEPROPERTY (N'rowordertest', 'Version') > 0 DROP DATABASE [rowordertest];
GO
CREATE DATABASE [rowordertest];
GO
USE [rowordertest];
GO
CREATE TABLE [t1] ([c1] INT, [c2] VARCHAR (10));
CREATE CLUSTERED INDEX [t1c1] ON [t1] ([c1]);
GO

Теперь вставлю в таблицу несколько строк, со значениями c1 от 2 до 5, намеренно не вставляя c1 = 1:

INSERT INTO [t1] VALUES (2, REPLICATE ('b', 10));
INSERT INTO [t1] VALUES (3, REPLICATE ('c', 10));
INSERT INTO [t1] VALUES (4, REPLICATE ('d', 10));
INSERT INTO [t1] VALUES (5, REPLICATE ('e', 10));
GO

Теперь, используя DBCC IND, видим, что страница данных — это (1:143), а дамп этой страницы через DBCC PAGE даёт следующее (я опускаю вывод заголовка):

DBCC IND ('rowordertest', 't1', 1);
GO
DBCC TRACEON (3604);
GO
DBCC PAGE ('rowordertest', 1, 143, 3);
GO

Slot 0 Offset 0x60 Length 27
Record Type = PRIMARY_RECORD         Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Memory Dump @0x5BA3C060
00000000:   30000800 02000000 0300f802 0011001b  0...............
00000010:   00626262 62626262 626262             .bbbbbbbbbb
UNIQUIFIER = [NULL]
Slot 0 Column 1 Offset 0x4 Length 4
c1 = 2
Slot 0 Column 2 Offset 0x11 Length 10
c2 = bbbbbbbbbb
(skip slots 2 and 3 for brevity)
Slot 3 Offset 0xb1 Length 27
Record Type = PRIMARY_RECORD         Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Memory Dump @0x5BA3C0B1
00000000:   30000800 05000000 0300f802 0011001b  0...............
00000010:   00656565 65656565 656565             .eeeeeeeeee
UNIQUIFIER = [NULL]
Slot 3 Column 1 Offset 0x4 Length 4
c1 = 5
Slot 3 Column 2 Offset 0x11 Length 10
c2 = eeeeeeeeee

DBCC PAGE со стилем дампа 3 всегда выводит записи на странице в их логическом порядке (потому что именно так упорядочен массив слотов). Обратите внимание: запись с c1 = 2 хранится по смещению 0x60 на странице, а последняя запись на странице с c1 = 5 — по смещению 0xb1. Теперь вставим запись с c1 = 1. Она станет первой логической записью в индексе, но приведёт ли это к перестановке записей на странице, чтобы они все были сохранены в логическом порядке?

INSERT INTO [t1] VALUES (1, REPLICATE ('a', 10));
GO
DBCC PAGE ('rowordertest', 1, 143, 3);
GO

Slot 0 Offset 0xcc Length 27
Record Type = PRIMARY_RECORD         Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Memory Dump @0x61FCC0CC
00000000:   30000800 01000000 0300f802 0011001b  0...............
00000010:   00616161 61616161 616161             .aaaaaaaaaa
UNIQUIFIER = [NULL]
Slot 0 Column 1 Offset 0x4 Length 4
c1 = 1
Slot 0 Column 2 Offset 0x11 Length 10
c2 = aaaaaaaaaa
Slot 1 Offset 0x60 Length 27
Record Type = PRIMARY_RECORD         Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
(snip)

Ответ — нет. Хотя запись с c1 = 1 и выводится первой в DBCC PAGE, посмотрите на её смещение внутри страницы — 0xCC — это явно последняя запись на странице, и физический порядок хранения отличается от логического порядка, определённого ключом индекса. Дополнительное подтверждение можно получить, посмотрев сырой шестнадцатеричный дамп страницы с помощью стиля дампа 2 в DBCC PAGE:

DBCC PAGE ('rowordertest', 1, 143, 2);
GO

(snip)
6204C000:   01010400 00400001 00000000 00000800  .....@..........
6204C010:   00000000 00000500 44000000 0f1fe700  ........D.......
6204C020:   8f000000 01000000 13000000 60000000  ............`...
6204C030:   16000000 00000000 00000000 00000000  ................
6204C040:   01000000 00000000 00000000 00000000  ................
6204C050:   00000000 00000000 00000000 00000000  ................
6204C060:   30000800 02000000 0300f802 0011001b  0...............
6204C070:   00626262 62626262 62626230 00080003  .bbbbbbbbbb0....
6204C080:   00000003 00f80200 11001b00 63636363  ............cccc
6204C090:   63636363 63633000 08000400 00000300  cccccc0.........
6204C0A0:   f8020011 001b0064 64646464 64646464  .......ddddddddd
6204C0B0:   64300008 00050000 000300f8 02001100  d0..............
6204C0C0:   1b006565 65656565 65656565 30000800  ..eeeeeeeeee0...
6204C0D0:   01000000 0300f802 0011001b 00616161  .............aaa
6204C0E0:   61616161 61616100 00000000 00000000  aaaaaaa.........
6204C0F0:   00000000 00000000 00000000 00000000  ................
(snip)

DBCC PAGE ('rowordertest', 1, 143, 1);
GO

(snip)
OFFSET TABLE:
Row - Offset
4 (0x4) - 177 (0xb1)
3 (0x3) - 150 (0x96)
2 (0x2) - 123 (0x7b)
1 (0x1) - 96 (0x60)
0 (0x0) - 204 (0xcc)
(snip)

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