Автор: Paul Randal, On index key size, index depth, and performance
В моём информационном бюллетене Insider я обсуждал, как фрагментация индекса часто учитывается при проектировании индексов, а глубина индекса — часто нет. В бюллетене я сказал, что сделаю более подробную статью в блоге с данными, и вот она.
Ветвление и глубина индекса
Глубина индекса определяется показателем ветвления индекса (fanout). Из бюллетеня:
Ветвление индекса измеряет, для страницы на уровне x в индексе, на сколько страниц она ссылается на уровне ниже (ближе к листовому уровню). Чем выше ветвление, тем меньше уровней в индексе.
Размер ключа индекса влияет на размер структуры, необходимой для ссылки на него. В частности, ключ индекса поднимается во все записи (и все уровни) индекса, поскольку он используется для навигации по индексу от корневой страницы вниз до листового уровня.
Чем больше размер ключа индекса, тем меньше записей индекса может поместиться на странице индекса и, следовательно, тем ниже показатель ветвления. Чем ниже ветвление, тем больше уровней требуется в индексе, в зависимости от количества страниц на листовом уровне.
Например, если показатель ветвления в индексе равен 10, это означает, что каждая страница индекса может содержать 10 записей индекса, ссылаясь на 10 страниц на уровне ниже в индексе. Если индекс имеет 10 000 страниц на листовом уровне, должно быть 1 000 страниц на уровне выше, затем 100 страниц, затем 10 страниц и, наконец, корневая страница. Это всего 5 уровней.
Для тех же данных, если показатель ветвления индекса изменён на 100, а индекс имеет 10 000 страниц на листовом уровне, следующему уровню нужно 100 страниц, а затем идёт корневая страница. Это всего лишь три уровня.
Я хочу измерить, есть ли заметная разница в производительности в зависимости от показателя ветвления и, следовательно, глубины индекса, при изменении размера его ключа, для операций выборки одной строки. На сканированиях заметного эффекта не будет, поскольку это включает только один обход индекса, чтобы найти начальную точку сканирования (хорошо, для сканирований это немного сложнее, если какие-либо из листовых страниц индекса изменяются, пока сканирование позиционировано на них, но это здесь не имеет значения).
Описание теста
Тест, который я собираюсь использовать:
- Создать таблицу с 2 миллионами записей, каждая запись достаточно велика, чтобы на каждой странице данных помещалась только одна запись (я собирался сделать десять миллионов строк, но это заняло бы слишком много времени).
- Удалить любой существующий кластерный индекс.
- Создать новый кластерный индекс с размером ключа от 8 до 900 байт (создание индекса после заполнения таблицы гарантирует самое плотное использование пространства).
- Убедиться, что весь индекс находится в памяти (очистить статистику ожиданий и убедиться, что во время следующего шага нет чтений страниц с диска).
- Замерить, сколько времени занимает поиск одной строки для всех 2 миллионов строк (выполнить 5 тестов и усреднить время).
Вот код моего теста:
USE [master];
GO
IF DATABASEPROPERTYEX (N'IndexDepthTest', N'Version') != 0
BEGIN
ALTER DATABASE [IndexDepthTest] SET SINGLE_USERWITH ROLLBACK IMMEDIATE;
DROP DATABASE [IndexDepthTest];
END
GO
CREATE DATABASE [IndexDepthTest] ON PRIMARY (
NAME = N'IndexDepthTest_data',
FILENAME = N'T:\IDT\IndexDepthTest_data.mdf',
SIZE = 32768MB,
FILEGROWTH = 256MB)
LOG ON (
NAME = N'IndexDepthTest_log',
FILENAME = N'N:\IDT\IndexDepthTest_log.ldf',
SIZE = 2048MB,
FILEGROWTH = 256MB);
GO
ALTER DATABASE [IndexDepthTest] SET RECOVERY SIMPLE;
GO
SET NOCOUNT ON;
GO
USE [IndexDepthTest];
GO
CREATE TABLE [DepthTest] (
[c1] BIGINT IDENTITY,
[c2] CHAR (8) DEFAULT 'c2', -- to allow 16-byte key
[c3] CHAR (92) DEFAULT 'c3', -- to allow 100-byte key
[c4] CHAR (300) DEFAULT 'c4', -- to allow 400-byte key
[c5] CHAR (500) DEFAULT 'c5', -- to allow 900-byte key
[c6] CHAR (4000) DEFAULT 'c6'); -- to force one row per leaf page
INSERT INTO [DepthTest] DEFAULT VALUES;
GO 2000000
-- Run one of the following sets of DROP/CREATE statements
-- No existing clustered index to drop
CREATE CLUSTERED INDEX [8ByteKey] ON [DepthTest] ([c1]);
GO
DROP INDEX [8ByteKey] ON [DepthTest];
GO
CREATE CLUSTERED INDEX [16ByteKey] ON [DepthTest] ([c1], [c2]);
GO
DROP INDEX [16ByteKey] ON [DepthTest];
GO
CREATE CLUSTERED INDEX [100ByteKey] ON [DepthTest] ([c1], [c3]);
GO
DROP INDEX [100ByteKey] ON [DepthTest];
GO
CREATE CLUSTERED INDEX [400ByteKey] ON [DepthTest] ([c1], [c3], [c4]);
GO
DROP INDEX [400ByteKey] ON [DepthTest];
GO
CREATE CLUSTERED INDEX [900ByteKey] ON [DepthTest] ([c1], [c3], [c4], [c5]);
GO
SELECT
[index_depth],
[index_level],
[page_count],
[record_count]
FROM sys.dm_db_index_physical_stats (
DB_ID (N'IndexDepthTest'),
OBJECT_ID (N'DepthTest'),
1,
0,
'DETAILED');
GO
DECLARE @c INT = 0;
WHILE (@c != 5)
BEGIN
DECLARE @t DATETIME = GETDATE ();
DECLARE @a BIGINT = 0;
DECLARE @b BIGINT;
WHILE (@a != 2000000)
BEGIN
SELECT @b = [c1] FROM [DepthTest] WHERE [c1] = @a;
SELECT @a = @a + 1;
END;
SELECT GETDATE () - @t;
SELECT @c = @c + 1;
END;
GO
Мой тестовый сервер — Dell R720 с 16 физическими ядрами (Intel E5-2670 @ 2,60 ГГц), 64 ГБ памяти, SSD Fusion-io/SanDisk на 640 ГБ для хранения, и я запускаю тест на SQL Server 2012.
Тест разработан как для того, чтобы убедиться, что индекс обходится до самого листового уровня (и к листовой записи нужно обратиться, чтобы проверить существование выбираемого значения и извлечь его), так и для того, чтобы убедиться, что все страницы индекса находятся в памяти.
Я пройдусь по шагам для 8-байтового кластерного ключа, а затем представлю данные для всех тестов.
Потребовалось несколько минут, чтобы выполнить 2 миллиона вставок, а затем создать первый кластерный индекс. Результаты вызова DMV были:
index_depth index_level page_count record_count
----------- ----------- -------------------- --------------------
4 0 2000000 2000000
4 1 4214 2000000
4 2 16 4214
4 3 1 16Итак, при размере ключа индекса 8 байт индексу требуется 4214 страниц на уровне 1 структуры индекса, чтобы хранить ссылки на все 2 миллиона листовых страниц. Это означает, что значение показателя ветвления равно 2000000 / 4214, что составляет примерно 474.
Времена для 2 миллионов выборок для 8-байтового кластерного ключа составили 21,983 с, 21,94 с, 21,973 с, 21,967 с, 21,963 с, со средним значением 21,9652 с и средним на выборку 10,98 микросекунды.
Результаты тестов
Выполнение теста для каждого из моих тестовых размеров ключа дало следующие результаты:
| Размер ключа | Глубина индекса | Общее количество страниц | Показатель ветвления |
Среднее время выборок | Примерное время на выборку |
|---|---|---|---|---|---|
| 8 | 4 | 2004231 | 474 | 21,9652 с | 10,9826 мкс |
| 16 | 4 | 2006980 | 288 | 21,8122 с | 10,9061 мкс |
| 100 | 5 | 2028182 | 72 | 22,9522 с | 11,4976 мкс |
| 400 | 6 | 2111124 | 19 | 23,7482 с | 11,8741 мкс |
| 900 | 8 | 2285728 | 8 | 25,5732 с | 12,7866 мкс |
Результаты ясно показывают, что существует штраф за производительность при поиске по индексу, когда индекс имеет больше уровней. На каждом уровне индекса во время поиска выполняется двоичный поиск, чтобы найти нужную запись индекса для навигации вниз к следующему уровню ниже в индексе, и этот двоичный поиск занимает время CPU.
Для каждого дополнительного уровня в индексе, согласно моим результатам, требуется примерно 0,4–0,5 микросекунды дополнительного времени, и это чистое время CPU, поскольку во время тестов не было чтений страниц.
Возможно, вы задаётесь вопросом, почему время на выборку для индекса с 16-байтовым ключом меньше, чем для индекса с 8-байтовым ключом, хотя они имеют одинаковую глубину 4 в моём тесте. Это связано с алгоритмом двоичного поиска. В среднем количество сравнений, необходимых для двоичного поиска по x элементам, равно log(x) по основанию 2. Для 8-байтового индекса показатель ветвления (то есть количество записей на странице для двоичного поиска) равен 474, что даёт среднее количество сравнений 8,9. Для 16-байтового индекса показатель ветвления равен 288, что даёт среднее количество сравнений 8,2. Это небольшое снижение объясняет небольшое снижение времени теста — это чуть-чуть эффективнее для меньшего показателя ветвления при той же глубине индекса. Я не собираюсь утверждать, что это означает, будто вы лучше с GUID-ключом кластеризации, чем с bigint — это совсем другое обсуждение с гораздо большим количеством факторов, чем просто производительность одиночных выборок :-)
Резюме
Мои результаты показывают, что глубина индекса имеет значение. Она определяется количеством строк в индексе и размером ключа индекса. Вы не можете контролировать количество строк, но вы можете контролировать размер ключа индекса. Где это возможно, чем меньше вы сможете удержать размер ключа индекса, тем меньше будет глубина индекса для того же количества записей и тем быстрее будет обход индекса от корневой страницы до листового уровня.
Хотя мы говорим всего лишь о долях микросекунды, для рабочих нагрузок с огромным количеством операций выборки одной строки это всё накапливается, и особенно на старых, более медленных процессорах, где разница будет более выраженной, чем в моих тестах. И эти результаты также опровергают аргумент, который гласит: «глубина индекса не имеет значения, потому что всё равно всё в памяти».
Суть — это ещё одна причина держать ваши ключи индексов как можно более узкими.
Комментариев нет:
Отправить комментарий