Анализ стоимости планов доступа
Выбор физических планов доступа определяется эвристическими правилами или основывается на стоимостной модели структур хранения и операций доступа [Merrett 1977]. В этом разделе обозреваются стоимостные модели и их интеграция в процедуры оптимизации.
Хотя несколько исследователей анализируют требования к рабочей памяти [Kim 1982; Lang et al. 1977; Sacco and Schkolnick 1982] или затраты ЦП [Gotlieb 1975; Selinger et al. 1979], большинство стоимостных моделей основывается на числе обращений к вторичной памяти. Для данной операции на эту величину влияет размер операндов, используемые структуры доступа и размер буферов основной памяти.
В начале вычисления операндами являются существующие структуры данных известного размера, такие как отношения и индексы. Однако на более поздних стадиях большинство операндов является результатами предшествующих операций, и стоимостная модель должна оценивать их размер с использованием информации об исходных структурах данных и селективности операций, уже выполненных над ними. Хотя ведется много работ, пока отсутствуют общепринятые формулы для оценки размера промежуточных результатов. Отчасти это является следствием недостаточного понимания допустимого соотношения объема используемой информации и точностью результата.
Вообще говоря, чем более органичительными являются предположения о данных, тем меньше требуется параметров для вычисления размера результатов операций. Например, в [Demolombe 1980] описывается рекурсивная процедура оценки размера результата вычисления безкванторного выражения исчисления, для которой должны быть известны пять типов параметров, если доступны достаточно детальные статистические данные о базе данных. Однако при более ограничительных предположениях требуются только три из из них. В оценках размеров, приведенных в [Selinger et al. 1979], используется только информация, уже существующая в базе данных, но делается много предположений о данных и запросе [Astrahan et al. 1980]. В другой предельной точке Яо [Yao 1979] предполагает (неявно), что известны детальные данные о селективности; ничего не говорится о том, каким образом эти данные получаются. (Однако см. [Yao 1977b] на предмет модели стоимости доступа.)
В последние годы исследователи осознают потребность в тщательной формулировке и критическом анализе всех используемых предположений о характеристиках баз данных для генерации формально обоснованной системы параметров, которая позволяет
В таких методах состояние базы данных во время выполнения представляется как случайный процесс, генерующий элементы отношения из декартова произведения доменов атрибутов под управлением некоторым распределением вероятности (которое обычно предполагается равномерным), а также общими правилами (например, функциональными зависимостями) схемы базы данных [Gelenbe and Gardy 1982; Richard 1981]. Из этих предположений выводятся параметры, значения которых должны быть известны для вычисления размера любого промежуточного результата сложных операций. Например, в [Richard 1981] демонстрируется, что достаточно знать размер всех проектов в базе данных, если распределения значений атрибутов являются равномерными и независимыми (даже если атрибуты определены на одном и том же домене).
В [Christodoulakis 1981, 1983 и Montgomery et al. 1983] приводится критический анализ таких предположений и показывается, что они ведут к предубеждению против структур прямого доступа в планах выборки. Однако пока не опубликованы какие-либо формулы с более общими предположениями и без чрезмерных требований данных.
Окончательной мерой стоимости является число обращений к вторичной памяти, а не размеры промежуточных результатов. В большом числе исследований оценивалась взаимосвязь между этит величинами [Cardenas 1975; Chan and Niamir 1982; Cheung 1982b; Luk 1983; Whang et al. 1983; Yao 1977a; Yu et al. 1978]. По существу, она зависит от используемых физических структур хранения и пропорции элементов, к которым происходит обращение.
Предположим сначала, что требуется доступ ко всем элементам операнда размером N. Тогда оптимальным числом обращений к вторичной памяти будет N/B, где B - коэффициент блокирования операнда.
Этого можно достичь, только если элементы хранятся плотно, и с самого начала известно, на каких физических записях они располагаются. В качестве контрпримера, для так называемого "сегментного сканирования" в System R требуется доступ к надмножеству требуемых страниц, чтобы найти все элементы отношения [Selinger et al. 1979]. Если требуется читать элементы в некотором предопределенном порядке, они должны храниться не только плотно, но также и отсортированными в данном порядке.
Если используется прямой доступ к подмножеству элементов, то число обращений к вторичной памяти, требуемых для выборки n из N элементов будет зависеть от кластеризации элементов в физических блоках. В большинстве упоминавшихся выше моделей предполагается случайное размещение записей по блокам, что в некотором смысле соответствует худшему случаю [Christodoulakis 1981]. Оптимальная кластеризация может сократить число страниц, к которым требуется совершить обращение, до n/B.
В заключение заметим, что традиционные предположения о распределениях атрибутов и размещении элементов ведут к завышению стоимости, и поэтому оценки стоимости препятствуют использованию структур прямого доступа. С другой стороны, для более совершенные методов требуется больше статистической информации о базе данных. Вопрос о том, как сохранять такую информацию, к сегодняшнему дню еще не решен полностью.
