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

2010 г.

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

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

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

Оригинал: 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

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

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

Здесь мы кратко остановимся на некоторых из преобразований, которые выполняются в Oracle на основе оценки стоимости.

2.2.1. Устранение вложенности подзапросов

В случае многотабличных подзапросов с EXISTS или ANY, как правило, не представляется возможным просто сливать подзапросы с содержащим их блоком запроса, так как возможен нежелательный эффект появления дубликатов строк, которых не было в результатах исходного запроса. Для многотабличных подзапросов с NOT EXISTS или ALL также не представляется возможным просто сливать подзапросы с содержащим их блоком запроса, так как соединение таблиц подзапроса следует выполнять до антисоединения с внешней таблицей. В этих случаях следует создавать встраиваемые представления, содержащие таблицы подзапросов. Для устранения вложенности коррелированных подзапросов, содержащих агрегаты, также требуется создание встраиваемых представлений с GROUP BY. Еще раз рассмотрим запрос Q1:

      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 departaments d, locations l
                                       WHERE d.loc_id = l.loc_id and
                                                      l.country_id = 'US');

Рассмотрим преобразованный запрос Q10, в котором вложенность первого подзапроса устранена за счет образования встроенного представления.

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

Непреобразованный запрос Q1 может лучше выполняться с использованием стратегии TIS, если внешний блок запроса значительно сокращает число кортежей таблицы employee, для которых требуется вычислить превышение средней зарплаты; кроме того, TIS может быть весьма эффективна, если на локальном столбце (т.е. на e2.dept_id) предиката корреляции имеется индекс. С другой стороны, преобразованный запрос позволяет рассматривать различные порядки и методы соединения, и для этого требуется выполнение операций агрегирования и группировки только один раз. Поэтому решение об устранении таких подзапросов должно основываться на оценке стоимости.

Преобразование, основанное на оценке стоимости, было введено в Oracle 10g. В версиях, предшествующих Oracle 10g, устранение вложенных подзапросов с образованием встраиваемых представлений основывалось на эвристиках. Немного упрощенный вариант этого эвристического правила можно сформулировать следующим образом: если во внешнем запросе имеются предикаты фильтрации и существуют индексы на локальных столбцах предиката корреляции подзапроса, то вложенность подзапроса устранять не следует.

В подразделе 4.1 мы приводим результаты производительности преобразований, основанных на оценке стоимости, в сравнении с результатами преобразований, основанных на эвристиках.

2.2.2. Слияние представлений c группировкой и устранением дубликатов

Слияние представлений с группировкой² (Group-by View Merging, group-by pull-up) позволяет слить представление, содержащее операцию GROUP BY (или DISTINCT), с его внешним блоком запроса. Это позволяет оптимизатору рассматривать дополнительные порядки соединения и пути доступа и откладывать вычисление агрегатов до тех пор, пока не будут выполнены соединения. Отложенное вычисление агрегатов может как повысить, так и понизить производительность в зависимости от характеристик данных, таких как сокращение набора данных, для которого выполнялось агрегирование. Рассмотрим запрос Q11, который получается путем слияния представления с GROUP BY в запросе Q10:

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

В непреобразованном запросе Q10 требуется, чтобы агрегация выполнялась на всей таблице employees. В преобразованнм запросе Q11 выполняются соединения двух таблиц employees и таблицы job_history, и применяется фильтрация вторым подзапросом до того, как выполняется агрегация. Если соединения и фильтры существенно уменьшают размер данных, которые агрегируются, то в результате может получиться улучшенный план выполнения. С другой стороны, ранняя агрегация уменьшает размер данных, которые обрабатываются операциями соединения, и агрегация в представлении с GROUP BY, возможно, должна будет выполняться на меньшем наборе данных. Эти соображения являются основанием того, почему решение должно быть основано на оценке стоимости. В запросах, выполняющих агрегацию последней, мы также учитываем возможность преобразования запроса для выполнения ранней агрегации (имеется в виду преобразование "размещение группировки" (group-by placement), которое мы описываем ниже).

2.2.3. Проталкивание предикатов соединения

В этом преобразовании (Join Predicate Pushdown) предикаты соединения проталкиваются внутрь представления. Проталкиваемые предикаты соединения, оказавшись внутри представления, действуют подобно корреляции, тем самым, делая доступными новые пути доступа. Проталкивание предикатов соединения позволяет соединять представление с внешними таблицами методом вложенных циклов на основе индексного доступа, недоступного обычным представлениям, которые могут соединяться только методами хэш-соединения или сортировки-слияния. Преобразование накладывает такой частичный порядок на соединяемые таблицы, что таблицы, к которым присоединяется представление (посредством проталкиваемых предикатов), должны предшествовать представлению, а представление должно соединяться методом вложенных циклов.

В качестве дополнительной оптимизации после проталкивания предикатов соединения может удаляться операция GROUP BY, если в запросе имеются эквисоединения для всех элементов раздела GROUP BY, и все эти предикаты соединения пригодны для проталкивания. Это возможно, потому что корреляция по условию равенства действует как группировка по значениям соответствующих столбцов. Похожая оптимизация возможна и для представлений с операцией DISTINCT, как показано в запросе Q13.

Рассмотрим следующий запрос, возвращающий информацию о сотрудниках и их истории работы (job history) для сотрудников (employees), которые работают в отделениях (departaments), расположенных в Великобритании (U.K.) или США (U.S.):

      Q12
      SELECT e1.employee_name, j.job_title,
             e2.employee_name as mgr_name
      FROM employees e1, job_history j,
           employees e2,
           (SELECT DISTINCT dept_id
            FROM departments d, locations l
            WHERE d.loc_id = l.loc_id and
                  l.county_id IN ('U.K.','U.S.')) V
      WHERE e1.emp_id = j.emp_id and
            j.start_date > '19980101' and
            e1.mgr_id = e2.emp_id and
            e1.dept_id = V.dept_id;

Запрос Q12 преобразуется на основе проталкивания предиката соединения в запрос Q13. Это преобразование позволяет нам удалить из представления дорогостоящую операцию DISTINCT. Внутреннее (inner) соединение преобразуется в полусоединение (semi) (этого не видно по запросу), которое налагает частичный порядок соединения, когда e1 должно предшествовать V.

      Q13
      SELECT e1.employee_name, j.job_title,
             e2.employee_name as mgr_name
      FROM employees e1, job_history j,
           employees e2,
           (SELECT dept_id
            FROM departments d, locations l
            WHERE d.loc_id = l.loc_id and
                  l.county_id IN ('U.K.','U.S.') and
                  e1.dept_id = d.dept_id) V
      WHERE e1.emp_id = j.emp_id and
            j.start_date > '19980101' and
            e1.mgr_id = e2.emp_id;

В Q13 для соединения представления V может быть использован метод вложенных циклов; это может быть достаточно эффективно, если на d.dept_id имеется индекс, и количество кортежей внешнего запроса сравнительно мало. Тем не менее, для определения того, какой из запросов Q12 и Q13 даст более оптимальный план выполнения, требуется решение, основанное на оценке стоимости.

В Oracle проталкивание предикатов соединения может применяться как к сливаемым (например, с DISTINCT и GROUP BY), так и к несливаемым³ (например, с объединением или анти-/полу-/внешним соединением) представлениям.

2.2.4. Размещение группировки

Преобразование "проталкивание группировки" [1], [24] (Group-By Pushdown) проталкивает операцию GROUP BY внутрь последовательности соединений запроса, приводя, тем самым, к раннему выполнению операции GROUP BY. Раннее выполнение GROUP BY может привести к значительному сокращению числа строк, к которым применяется несколько операций GROUP BY, а также количества строк, используемых позднее в соединениях; следовательно, может улучшиться общая производительность запроса.

Размещение группировки (Group-By Placement) также может позволить вытянуть операцию GROUP BY за пределы последовательности соединений, что мы называем слиянием представления с группировкой. Запрос с GROUP BY может подвергаться различным видам преобразований размещения группировки в зависимости от его графа соединения и таблиц, на которые существуют ссылки в агрегатных функциях. В Oracle преобразование "размещение группировки" ("проталкивание группировки") порождает одно или несколько представлений с группировкой.

Сначала оптимизатор Oracle выполняет слияние представлений с группировками ("вытягивание группировки", Group-By Pullup), за которым далее следует преобразование "проталкивание группировки", не затрагивающее те запросы, которые подверглись слиянию представлений с группировками. Общее преобразование "размещение группировки" будет доступно в следующей версии Oracle.

2.2.5. Факторизация соединений

Факторизация соединений (Join Factorization) применяется для запросов с UNION/UNION ALL, где ветви UNION ALL содержат общие соединяемые таблицы. Эти соединяемые таблицы вытягиваются во внешний блок, и блок запроса с UNION ALL превращается в представление, с которым соединяются вытянутые таблицы. Такая факторизация предотвращает многократный доступ к общим таблицам. С использованием факторизации соединений запрос Q14 может быть преобразован в запрос Q15.

      Q14
      SELECT e.first_name, e.last_name, job_id,
             d.departament_name, l.city
      FROM employees e, departaments d,
           locations l
      WHERE e.dept_id = d.dept_id and
            d.location_id = l.location_id
      UNION ALL
      SELECT e.first_name, e.last_name, j.job_id,
             d.departament_name, l.city
      FROM employees e, job_history j,
           departaments d, locations l
      WHERE e.emp_id = j.emp_id and
            j.dept_id = d.dept_id and
            d.location_id = l.location_id;

 
      Q15
      SELECT V.first_name, V.last_name, V.job_id,
             d.departament_name, l.city
      FROM departaments d, locations l,
           (SELECT e.first_name, e.last_name
                   e.job_id, e.dept_id
            FROM employees e
            UNION ALL
            SELECT e.first_name, e.last_name
                   j.job_id, j.dept_id
            FROM employees e, job_history j
            WHERE e.emp_id = j.emp_id) V
      WHERE d.dept_id = V.dept_id and
            d.location_id = l.location_id;

Интересно, что имеется множество случаев, когда общие таблицы можно факторизовать, но соответствующие предикаты соединения вытянуть невозможно. В таких случаях предикаты соединения можно оставить внутри представления с UNION ALL, которое затем соединяется на основе техники, описанной в п. 2.2.3 "проталкивание предикатов соединения". Это преобразование будет доступно в следующей версии Oracle.

2.2.6. Вытягивание предиката

Преобразование "вытягивание предиката" (Predicate Pullup) фильтрации вытягивает дорогостоящие предикаты фильтрации из представления в запрос, содержащий это представление. В настоящее время предикат считается дорогостоящим, если он содержит процедурные функции SQL, определяемые пользователем операции или подзапросы. Преобразование "вытягивание предиката" в настоящее время принимается во внимание, только если в запросе, содержащем представление, указан предикат rownum⁴, и в представлении имеется блокирующая операция.

Рассмотрим следующий запрос, содержащий представление с двумя дорогостоящими предикатами:

  
      Q16
      SELECT *
      FROM (SELECT document_id
            FROM product_docs
            WHERE containts(summary,'optimizer',1) > 0
                  AND containts(full_text,'execution',2) > 0
            ORDER BY create_date) V
      WHERE rownum <= 20;

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

  
      Q17
      SELECT *
      FROM (SELECT document_id, value(r) as vr
            FROM product_docs
            WHERE containts(full_text,'execution',2) > 0
            ORDER BY create_date) V
      WHERE containts(summary,'optimizer',1) > 0
            AND rownum <= 20;

Выполнение поздней проверки дорогостоящих предикатов на значительно сокращенном наборе данных может, в некоторых случаях, улучшить производительность запроса. Если предикаты отфильтровывают очень мало строк, то мы можем избежать выполнения дорогостоящего предиката на полном наборе данных. Сокращение объема данных происходит из-за наличия предиката rownum в запросе, содержащем представление. Это преобразование действует противоположным образом по отношению к распространенному методу оптимизации проталкивания в представление предиката фильтрации. Поэтому в Oracle решение о вытягивании предикатов принимается на основе оценки стоимости.

2.2.7. Преобразование операций над множествами в соединения

Операции над множествами MINUS и INTERSECT преобразуются в антисоединение и внутреннее/полусоединение соответственно, что позволяет, тем самым, использовать различные методы и порядки соединений. Однако в семантике операций над множествами и соединений существуют различия: и в INTERSECT, и в MINUS значения null считаются совпадающими, тогда как в соединениях и антисоединениях – нет. Кроме того, MINUS и INTERSECT — операции над множествами и, следовательно, возвращают результирующий набор без дубликатов. Должно быть принято решение, основанное на оценке стоимости, относительно того, следует ли удалять дубликаты во входных или выходных данных соединений; эта проблема аналогична размещению операции DISTINCT (Distinct Placement).

2.2.8. Внесение дизъюнкции в объединение

Если предикаты фильтрации или соединения появляются в дизъюнкции, запрос может быть развернут в запрос с UNION ALL, в котором каждая ветвь содержит один из предикатов дизъюнкции. В отсутствие такого преобразования дизъюнктивный предикат применяется в качестве заключительного фильтра (post-filter) результата, который может быть декартовым произведением.

² Заметим, что SELECT DISTINCT — это частный случай операции группировки.

³ В некоторых случаях anti-/semi-/outer-соединяемые представления могут, на самом деле, сливаться, особенно, если они содержат единственную таблицу.

⁴ Rownum — это конструкция Oracle, позволяющая пользователям указать максимальное количество кортежей, которые должны выдаваться запросом.

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