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


         

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


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

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

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"

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