Преобразование запросов, основанное на стоимости

Рафи Ахмед, Эллисон Ли, Эндрю Витковски, Динеш Дас, Хонг Су, Мохамед Зэйд, Тьерри Крюейнс

Перевод Леонида Борчука
Под ред. Сергея Кузнецова

Оригинал: Cost-Based Query Transformation in Oracle / Rafi Ahmed, Allison Lee, Andrew Witkowski, Dinesh Das, Hong Su, Mohamed Zait, Thierry Cruanes // Proceedings of the 32nd international conference on Very large data base, 2006, pp. 1026 — 1036

Содержание

Аннотация

1. Введение

2. Преобразования в Oracle

2.1. Эвристические преобразования

2.2. Преобразования, основанные на оценке стоимости

3. Инфраструктура преобразований, основанных на оценке стоимости

3.1. Основные компоненты

3.2. Методы поиска в пространстве состояний

3.3. Взаимодействие преобразований

3.4. Производительность оптимизации

4. Исследование производительности

4.1. Преобразование, основанное на оценке стоимости

4.2. Устранение вложенности и проталкивание предикатов соединения

4.3. Преобразование "размещение группировки"

4.4. Время оптимизации

5. Родственные работы

6. Заключение

7. Благодарности

8. Список литературы

Аннотация

В статье описано преобразование запросов в СУБД Oracle, основанное на стоимости, которое является новым этапом оптимизации запросов. Рассматривается набор эвристических и стоимостных преобразований, выполняемых Oracle. Представлена инфраструктура (framework) для преобразований запросов, основанных на стоимости, показаны необходимость такой инфраструктуры, возможное взаимодействие между несколькими преобразованиями и эффективный алгоритм перечисления пространства поиска трансформаций, основанных на стоимости. Описан практический способ объединения преобразований, основанных на стоимости, с традиционным физическим оптимизатором. Выделены некоторые проблемы преобразований, основанных на стоимости. Наши результаты показывают, что некоторые преобразования, если их выполнять на основе стоимости, ведут к значительному улучшению времени выполнения.

1. Введение

Современные СУБД выполняют сложные SQL-запросы, включающие вложенные подзапросы с функциями агрегации, UNION/UNION ALL, DISTINCT, представления с группировкой и т.д. Такие запросы становятся все более значимыми в системах поддержки принятия решений (DSS) и интерактивной аналитической обработки (OLAP). Для оптимизации таких запросов была предложена перезапись запроса в виде эвристического преобразования. Однако существует много возможных вариантов преобразования даже для простых SQL-выражений в зависимости от того, как и какие преобразования применяются. Дополнительные сложности создает взаимодействие двух или более преобразований друг с другом.

В традиционных СУБД оптимизация запросов, как правило, состоит из двух этапов обработки: этапов логической и физической оптимизации. На этапе логической оптимизации заданный запрос переписывается (обычно на основе эвристик или правил) в эквивалентную, но потенциально более декларативную или оптимальную форму. Традиционный физический оптимизатор работает в рамках одного блока запроса, который оперирует множеством базовых таблиц с применением ограничения, проекции и соединения. На этапе физической оптимизации выбираются методы доступа, последовательность соединений и методы соединений для генерации эффективного плана выполнения запроса.

Преобразования запроса реализуются либо как система перезаписи [16], управляемая эвристическими правилами, либо как расширения генератора планов внутри физического оптимизатора [2, 6, 19]. Первый подход универсален, но не масштабируется на сложные коммерческие системы, а второй легко применим только для нескольких избранных преобразований. В этой работе аргументированно обсуждается новый подход с методическим обеспечением расчета стоимости преобразований без необходимости модификации физического оптимизатора.

Некоторые эвристические правила являются неотъемлемой частью преобразований, которые применяются на этапе логической оптимизации. В разд. 2 мы перечисляем несколько преобразований, которые применяются в Oracle на основе эвристических правил. Однако остается большой класс преобразований, которые не подчиняются полностью эвристическим правилам и могут приводить к неоптимальным планам выполнения, если решение по использованию таких преобразований не основывалось на оценке затрат.

Мы обосновываем эти проблемы несколькими примерами разд. 2. Рассмотрим здесь только один простой запрос, который получает информацию о сотрудниках (employees) и должностях (job), занимаемых ими позднее 1998, для сотрудников, имеющих зарплату выше средней в своих департаментах (departments), которые расположены (locations) в США.

 
      Q1
      SELECT e1.employee_name, j.job_title
      FROM employees e1, job_history j
      WHERE e1.emp_id = j.emp_id and
                     j.start_date > '19980101' and
                    e1.salary > (SELECT AVG (e2.salary)
                                       FROM employees e2
                                       WHERE e2.dept_id = e1.dept_id) and
                    e1_dept_id IN  (SELECT dept_id
                                             FROM departments d, locations l
                                             WHERE d.loc_id = l.loc_id and
                                              l.country_id = 'US');

В этом запросе можно устранить вложенность обоих подзапросов за счет введения встраиваемых (inline) представлений (производных таблиц), и впоследствии оба представления могут быть слиты. Это дает нам многочисленные альтернативы преобразования этого запроса — устранение вложенности (нуля или более) подзапросов и последующее слияние (нуля или более) представлений. Интересно, что, как мы увидим в разд. 2, могут иметься и другие преобразования, которые могли бы стать применимыми к этому запросу. Нет ясного эвристического правила для определения того, какое из преобразований ведет к лучшему плану выполнения, т.к. здесь играет роль множество факторов (например, соотношение размеров участвующих таблиц, селективность предикатов, существование индексов на локальных столбцах предикатов корреляции и т.д.).

Содержание Вперёд