Оптимизация запросов в системах баз данных


         

Цели оптимизации - часть 3


Следующий простой пример показывает, что можно ожидать от оптимизации запросов.

Рассмотрим реляционную схему базы данных, описывающей служащих, предлагающих компьютерные лекции отделам географически распределенной организации:

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

  • Сформировать декартово произведение отношений "courses", "lectures" и "departments"



    Содержание  Назад  Вперед