Оптимизация запросов.

Ответ на запрос, написанный на языке МД (SQL, QBR и т.д.), иногда требует достаточно много времени. Время исполнения запросов может быть в достаточной степени сокращено, если процессор ЯЗ перефразирует запрос перед его исполнением. Такой процесс называется оптимизацией, этот перефразированный запрос не обязательно является оптимальным из всех возможных способов его реализации.

Оптимизация запросов равносильна оптимизации выражений РА и РИ. Особенно важное значение имеет исследование выражений, которое включает соединение или декартово произведение с последующими операциями селекции и проекции.

Непосредственное выполнение операций требует достаточно много времени.

Пример: R(A B), S(C D). Выполнить

(n) (m)

операций.

– количество операций уменьшается сортировкой.

В:

С:

Декартово произведение RS R(AB) S(CD)

Надо организовать просмотр файла Ф_R, реализовать отношение R, и для каждой записи Z_R, соответствующей кортежу t, надо просматривать весь файл Ф_S. При этом строится конкатенация записи Z_R с каждой записью Z_S.

Соединение .

Общие стратегии оптимизации:

1. Выполнить операции селекции по возможности раньше.

2. Целесообразно предварительно, перед выполнением операции соединения (или декартова произведения с последующей селекцией), сделать сортировку или индексирование файла.

Если сделать индексы по В и С, то время вычисления RS будет линейно зависимо от обоих отношений. При сортировке R по В и S по С, надо просматривать каждый файл один раз для поиска записей, удовлетворяющих условию B<C.

В: 5, 10, 15 fix B и С: 1, 3, 4, 15, 20

двигаться по С

3. Искать общие подвыражения в выражении. Если результат общего подвыражения представляет собой небольшие отношения, который можно прочитать из внешней памяти за значительно меньшее время, чем требуется для его вычисления, целесообразно один раз вычислить это подвыражение.

Пример:

4. Собирать в каскады проекции и селекции. Последовательность таких операций, каждая из которых требует только одного операнда, может выполняться одновременно, за один просмотр файла.

5. Комбинировать операции проекции с последующими или предшествующими двуместными операциями.

Нет необходимости устраивать просмотр файла только для исключения определенных полей.

6. Комбинировать некоторые селекции с предшествующим декартовым произведением, и выполнять вместо них соединение.

Рассмотренные операции оптимизации предусматривают преобразование выражений РА. В связи с этим рассмотрим ряд алгебраических законов, которые применяются к операторам РА.

Будем предполагать, что процессор ЯЗ начинает обработку с построения дерева разбора для выражения РА.

Пример:

Сам язык запросов произвольный, если запрос написан в виде выражения РИ, то он переводится в выражение РА.

Напомним, что выражения РА, операндами которых являются переменные отношения есть отображения кортежей отношения на единственное отношение, которое получается после подстановки каждого кортежа вместо отношений и вычисления выражения.

Два выражения и называются эквивалентными, что записывается , если они представляют собой одни и те же отображения.