Стоимость доступа к данным и использования индексов

Автор: Charlie Caro, Borland Interbase R&D
Перевод: Кузьменко Дмитрий
Оригинальный текст
 
Предисловие переводчика. Нижеприведенный текст является ответом на письмо, в котором приводились данные Database Statistics, и задавался вопрос – что лучше для такой БД: размер страницы 1К или размер страницы 2К? Именно из исходного письма взяты цифры 818, 204, 70000 и т. п. Безусловно для вашей БД эти цифры будут совершенно другими, однако это письмо поможет понять, как посчитать стоимость выборки данных в зависимости от размера кэша, размера страницы БД, уровня индекса и т. п. Если же вы не поняли, что такое Уровень индекса или страницы указателей, вам стоит почитать литературу по B-деревьям, например, "Тиори, Фрай. Проектирование баз данных.".
Даже если вы увеличили размер страницы, а индекс имеет глубину = 4 (параметр Index depth в статистике по БД), можно ожидать улучшения производительности при случайных выборках записей.

Предположим, что кэш сервера составляет 75 страниц.

Можно также упростить себе задачу, дополнительно предположив что страницы уровней 2 и 3 будут постоянно находиться в кэше.

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

Уровень 1 индекса является основным фактором:
  • Для страниц размером 1К, уровень 1 стоит (1 - 75/818) или приблизительно 0.9 операций ввода/вывода.
  • Для страниц размером 2К, уровень 1 стоит (1 - 75/204) или приблизительно 0.6 операций ввода/вывода.

В среднем, работа с индексом будет стоить 1.9 операций ввода/вывода для страниц 1К, и 1.6 операций ввода/вывода для страниц 2К..

Дополнительным фактором является стоимость выборки страницы указателей (Pointer Page – PP), которые ссылаются на страницы данных таблицы (Data Pages – DP).

В общем, выборка по индексу осуществляется так (Lx – уровень страницы индекса):
Индекс(L3)->Индекс(L2)->Индекс(L1)->Индекс(L0)->PP->DP

Для размера страниц 1К, если таблица имеет 70000 страниц, то для нее нужно около 280 страниц указателей. В этом случае стоимость выборки указателей (1 - 75/280) или 0.7.

Для размера страниц 2К, та-же таблица будет иметь 35000 страниц, и соответственно 70 страниц указателей. Стоимость выборки (1 - 75/70) или 0.

Таким образом общая стоимость выборки случайной записи:
Индекс(L3)->Индекс(L2)->Индекс(L1)->Индекс(L0)->PP->DP
1kb 0 + 0 + 0.9 + 1 + 0.7 + 1 = 3.6 I/O's
2kb 0 + 0 + 0.6 + 1 + 0 + 1 = 2.6 I/O's

Получается, что для такой таблицы стоимость выборки меньше при размере страницы БД 2К, чем при 1К.
 
(с) 1997 Epsylon Technologies

Подпишитесь на новости Firebird в России

Подписаться