Цели оптимизации
Экономический принцип требует, чтобы процедуры оптимизации пытались либо максимизировать пропускную способность при заданном числе ресурсов, либо минимизоровать потребление ресурсов при данной пропускной способности. Оптимизация запросов направленая на минимизация времени отклика для заданного запроса и смеси типов запросов в данной системной среде. Эта общая цель допускает ряд различных операционных целевых функций. Время отклика является разумной целью только при предположении, что время пользователя является наиболее важным критическим ресурсом. В противном случае можно стремиться к непосредственной минимизации стоимости потребления технических ресурсов. К счастью, обе цели являются в большой степени взаимнодополнительными; при возникающие конфликты целей обычно разрешаются путем назначения ограничений на доступные технические ресурсы (например, на размер буферного пространства в основной памяти).
Чтобы допустить справедливое сравнение эффективности, функциональные возможности сравниваемых систем выполнения запросов должны быть сходными. Требование "реляционной полноты", придуманное Коддом [Codd 1972], (сравните с разд. 2.1) стало квазистандартом. Методы, обозреваемые в данной статье, представляются как вклады в реализацию запросов на реляционно полном языке с минимальной стоимостью выполнения или временем отклика. Запросы более высокого уровня сложности [Chandra and Harel 1982a] рассматриваются в разд. 6.1. Общая стоимость, подлежащая минимизации, складывается из следующих компонентов:
Стоимость коммуникаций: Стоимость передачи данных из места, в котором они хранятся, в места, где выполняются вычисления и представляются результаты. Эта стоимость состоит из стоимости коммуникационного канала, которая обычно связана с временем, в течение которого канал открыт, и стоимостью задержек в обработке, вызваемых передачей. Последний компонент, более важный для оптимизации запросов, часто полагается линейной функцией от объема передаваемых данных.
Стоимость доступа к вторичной памяти: Стоимость (или время) загрузки страниц данных из вторичной памяти в основную память.
На эту стоимость влияет выбираемых данных (главным образом, размер промежуточных результатов), кластеризация данных на физических страницах, размер доступного буферного пространства и скорость используемых устройств.
Стоимость хранения: Стоимость занятия вторичной памяти и буферов основной памяти. Стоимость хранения уместна только в том случае, когда память становится узким местом системы, и размер требуемой памяти может изменяться от запроса к запросу.
Стоимость вычислений: Стоимость (или время) использования ЦП.
На структуру алгоритмов оптимизации запросов влияют соотношения между этими компонентами стоимости. В территориально распределенной СУБД с относительно медленными коммуникационными каналами преобладает стоимость коммуникацонных задержек, а другие факторы существенны только для локальной подоптимизации. В централизованных системах доминирует время доступа к вторичной памяти, хотя для сложных запросов достаточно высокой может быть и стоимость ЦП [Gotlieb 1975]. В локально распределенных СУБД все факторы имеют близкие веса, что приводит к очень сложным оценочным функциям и процедурам оптимизации.
Поскольку эта статья в основном посвящена централизованным базам данных, стоимость коммуникаций не принимается во внимание, потому что в таких системах комуникационные требования не зависят от стратегии выполнения запросов. Для оптимизации одиночных запросов стоимость хранения также считается не первостепенно важной. Эти расходы учитываются только при одновременной оптмизации нескольких запросов.
Остаются стоимость доступа ко вторичной памяти (обычно измеряемая числом обращения к страницам) и стоимость использования ЦП (часто измеряемая числом сравнений, которые требуется произвести). В основе большинства методов, разработанных для сокращения этой стоимости, лежит ряд общих идей: (1) избегать дублирования усилий; (2) использовать стандартизованные компоненты; (3) заглядывать вперед, чтобы избегать лишних операций; (4) выбирать наиболее дешевые способы выполнения элементарных операций; (5) выстраивать их последовательность оптимальным образом.
Следующий простой пример показывает, что можно ожидать от оптимизации запросов.
Рассмотрим реляционную схему базы данных, описывающей служащих, предлагающих компьютерные лекции отделам географически распределенной организации:
employees (enr, ename, status, city) papers (enr, title, year) departments (dname, city, street address) courses (cnr, cname, abstract) lectures (cnr, dname, enr, daytime)
Ключевые атрибуты подчеркнуты; заданная комбинация значений ключевых атрибутов уникально идентифицирует элемент отношения. Предположим, что пользователя интересуют "названия отделов, расположенных в Нью-Йорке и предлагающих курсы по управлению базами данных".
Имеется много возможных стратегий разрешения этого запроса, три из которых сравниваются по отношению к следующим предположениям относительно реальных значений данных. Заметим, что детальные данные, используемые в приводимых ниже вычислениях, обычно недоступны оптимизатору запросов, а должны оцениваться.
Имеется 100 отделов, 5 из которых размещаются в Нью-Йорке. В физическом блоке может поместиться 5 записей об отделах или 50 значений dname.
Имеется 500 курсов, 20 из которых посвящены управлению базами данных. В физическом блоке помещается 10 записей.
Имеется 2000 лекций, три сотни из них - про управление базами данных, 100 проходят в отделах в Нью-Йорке и 20 (из трех отделов) удовлетворяют обоим условиям. В физический блок помещаются 10 записей.
Предположим также, что время сортировки составляет N * log(2)N, где N - размер файла в блоках, и что имеется буфер из одного блока для каждого отношения. Наконец, все отношения физически упорядочены по возрастанию значений ключа.
Первая представленная здесь стратегия следует прямому подходу трансляции выражения реляционного исчисления в операции алгебры [Codd 1972]. Вместе с каждым шагом стратегии приводится число обращений ко вторичной памяти, требующихся для чтения (r) и записи (w).
Стратегия 1
(r: 200000)
(w: 1)
итого: приблизительно 200000 обращений.
Исключительно высокая стоимость этой стратегии происходит из того факта, что она генерирует промежуточный результат, очень небольшая часть которого действительно существенна для дальнейшей обработки. Эффективность может быть существенно повышена путем рассмотрения только тех комбинаций элементов разных отношений, которые имеют одинаковые значения общих атрибутов. Путем использования существующих порядков сортировки, такие комбинации могут формироваться "слиянием" участвующих отношений. Эта операция называется "соединением".
Стратегия 2
(r: 50 + 200; w: 400)
(r + w: 400*1og(2)400)
(r: 400 + 20; w: 400 + 400)
(r: 800)
(w: 1)
Итого: Приблизительно 6000 обращений.
Стоимость ответа на запрос можно еще более сократить путем выполнения ограничений на основе значений как можно раньше и уменьшения за счет этого расходов на сортировку и слияние промежуточных результатов.
Стратегия 3
(r: 50 + 200)
(w: 2)
(r + w: 2)
(r: 2 + 20)
(w: 1)
Итого: 277 обращений
Таким образом, было достигнуто сокращение стоимости приблизительно в 700 раз.Для больших баз данных и более сложных запросов более совершенные методы могут привести к еще большим сокращениям.
