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
Назад Содержание Вперёд
В Oracle выполняется множество преобразований запросов, некоторые из них основываются на оценке затрат, а другие — на эвристиках. В этом подразделе мы обсудим несколько преобразований обеих категорий и выясним, почему для некоторых преобразований требуются решения на основе оценки стоимости, а для других — нет. Следует отметить, что это только подмножество преобразований, выполняемых в Oracle.
Большинство наших обсуждений сосредоточено на деревьях запросов, которые отличаются от алгебраических деревьев операций тем, что дерево запроса позволяет сохранить всю декларативность языка SQL. Дерево запроса превращается в дерево операций после физической оптимизации.
Традиционные преобразования на основе эвристик выполняются с целью раннего выполнения операций селекции и проекции, удаления избыточных операций, минимизации числа блоков запроса.
Минимизация числа блоков запроса путем слияния их с другими блоками запроса снимает ограничения с множества перестановок операций соединения, которые могут быть сгенерированы, позволяя, таким образом, переупорядочивать большее число таблиц [16]. Традиционный реляционный оптимизатор генерирует только "левоглубинное" (left-deep) (линейное) дерево выполнения; таким образом, можно утверждать, что он никогда не сможет сгенерировать план, эквивалентный плану с "кустистым" (bushy) деревом, генерируемым в случае отсутствия преобразований. Несмотря на это, считается, что значительную часть деревьев соединений с низкой стоимостью обработки можно найти в пространстве левоглубинных деревьев [5].
Как правило, минимизация количества блоков запроса оказывается хорошей эвристикой до тех пор, пока не требуется применение, дублирование или изменение расположения операций DISTINCT или GROUP BY. В Oracle многие преобразования руководствуются эвристиками, которые мы называем
императивными правилами, так как они всегда приводят к применению преобразований, если они допустимы. Здесь мы кратко описываем некоторые из этих преобразований.
Устранение вложенности подзапросов (Subquery Unnesting) — важное преобразование, которое обычно реализовывается коммерческими СУБД. Подзапрос с неустраненной вложенностью вычисляется несколько раз с использованием семантики кортежной итерации (tuple iteration semantics, TIS), что подобно выполнению соединения методом вложенных циклов, и, следовательно, при этом не может быть учтено множество эффективных путей доступа и последовательностей соединения.
Оптимизатор Oracle может устранить вложенность почти всех типов подзапросов за исключением подзапросов, в которых имеется корреляция не с предком, в которых корреляция проявляется в дизъюнкции, а также некоторых подзапросов с квантором ALL и составным условием с корреляцией, включающим имена столбцов, в которых допускаются неопределенные значения. Существует две основных категории методов устранения вложенности: первая категория включает методы, основанные на порождении встраиваемых представлений (inline view), вторая — методы, основанные на слиянии подзапроса с его внешним запросом. В Oracle методы первой категории применяются на основе оценки стоимости, тогда как методы второй категории используются императивным образом.
Рассмотрим следующий запрос, возвращающий информацию об отделах для отделов (departments), сотрудники (employees) которых получают высокую зарплату:
Q2
SELECT d.dept_name, d.budget
FROM departaments d
WHERE EXISTS (SELECT 1
FROM employees e
WHERE d.dept_id = e.dept_id
AND e.salary > 200000);
Этот запрос преобразуется в следующий эквивалентный запрос:1
Q3
SELECT d.dept_name, d.budget
FROM departaments d, employees e
WHERE d.dept_id S= e.dept_id
AND e.salary > 200000;
Преобразование, сливающее подзапрос с внешним запросом, в общем случае позволяет использовать дополнительные способы и последовательности выполнения операций соединения. В рассматриваемом примере Oracle может использовать для полусоединения (semijoin) методы вложенных циклов, хеширования или сортировки со слиянием. Реализация в Oracle антисоединения (antijoin) и полусоединения обладает свойством "остановись-на-первом-совпадении" (stop-at-the-first-match). Механизм выполнения Oracle кэширует результаты анти- и полусоединения для кортежей левой таблицы; это кэширование может быть весьма полезно, если в соединяемых столбцах левой таблицы имеется большое число дубликатов.
Полусоединение, как и антисоединение, и левое внешнее соединение (left outerjoin) является некоммутативным соединением и навязывает частичный порядок соединения таблиц, то есть в рассматриваемом примере в последовательности соединения таблица departaments должна предшествовать таблице employees. Но мы можем преобразовать это полусоединение во внутреннее (inner) соединение, применяя к выбранным строкам employees операцию сортировки с удалением дубликатов и смягчая ограничение частичного порядка соединений [22]. Это позволяет оптимизатору допускать возможность обоих порядков соединения — (d semijoin e) и (distinct(e) join d).
Вложенность подзапросов с ALL, в столбцах условий которых не допускаются неопределенные значения, и подзапросов с NOT EXISTS, как правило, может устраняться с использованием антисоединения. В следующей версии Oracle будет иметься еще один вариант антисоединения — антисоединение с учетом возможности появления неопределенных значений (null-aware antijoin), для которого будут допустимы столбцы с неопределенными значениями в связывающих условиях подзапросов с ALL.
Метод устранения соединения (Join Elimination) удаляет таблицу из запроса, если имеются такие ограничения на столбцы соединения этой таблицы, что устранение соединения не влияет на результаты запроса. Рассмотрим следующие два запроса Q4 и Q5, которые выбирают некоторую информацию о сотрудниках (employees):
Q4
SELECT e.name, e.salary
FROM employees e, departaments d
WHERE e.dept_id = d.dept_id;
Так как dept_id в таблице employees является внешним ключом, ссылающимся на первичный ключ таблицы departaments, соединение с departaments из Q4 можно устранить.
В запросе Q5 столбец соединения в правой таблице внешнего соединений уникален. Так как внешнее соединение содержит все кортежи левой таблицы, а эквисоединение (equi-join) с уникальными столбцами не порождает дубликаты, таблицу departaments можно исключить.
Q5
SELECT e.name, e.salary
FROM employees e left outer join
departaments d on e.dept_id = d.dept_id;
Применение преобразования устранения соединений к Q4 и Q5 приводит к порождению запроса Q6. Если в Q4 e.dept_id может содержать неопределенные значения, в раздел WHERE Q6 должен быть добавлен предикат e.dept_id is not null.
Q6
SELECT e.name, e.salary
FROM employees e;
Очевидно, что устранение избыточного соединения улучшит производительность запроса, и поэтому устранение соединений всегда выполняется Oracle, если это допустимо.
При перемещении предикатов фильтрации (Filter Predicate Move Around) дешевые предикаты сдвигаются в блоки запросов представления для выполнения более ранней фильтрации. Преобразование перемещения предикатов фильтрации выполняется на основе императивных эвристик, поскольку оно может сделать доступными новые пути доступа и уменьшить размер данных, обрабатываемых позднее более дорогостоящими операциями, такими как соединения и группировки.
Предикаты фильтрации могут вытягиваться наверх (pull up), перемещаться в сторону (move across) и проталкиваться вниз (push down) на любой уровень. Интересным расширением [9] является наша возможность проталкивания предикатов фильтрации сквозь раздел PARTITION BY оконных функций стандарта ANSI и разделенное внешнее соединение ANSI, а также сквозь подраздел DIMENSION BY раздела SQL MODEL [25], [26]. Еще одной техникой, уникальной для нашей системы, является проталкивание предикатов сквозь агрегат оконной функции перед вычислением агрегатов [26]. Сейчас она применяется только внутри раздела SQL MODEL, но в следующей версии будет обобщена на оконнные функции, присутствующие в списке SELECT блока запроса. Пусть, например, имеется таблица accounts (act-id, time, balance), в которой в динамике по времени регистрируются текущие остатки на счетах. Рассмотрим встраиваемое представление, рассчитывающее скользящий средний остаток, и внешний запрос, выбирающий его за 12 месяцев для счета'ORCL':
Q7
SELECT acct-id, time, ravg
FROM (SELECT acct-id, time,
AVG(balance) over (PBY acct-id OBY time
RANGE BEETWEN UNBOUNDED PROCEEDING
AND CURRENT ROW) ravg
FROM accounts)
WHERE acct-id='ORCL' AND time <= 12;
В этом запросе предикаты над acct-id и time можно протолкнуть внутрь представления.
Q8
SELECT acct-id, time, ravg
FROM (SELECT acct-id, time,
AVG(balance) over (PBY acct-id OBY time
RANGE BEETWEN UNBOUNDED PROCEEDING
AND CURRENT ROW) ravg
FROM accounts
WHERE acct-id='ORCL' AND time <= 12);
Проталкивание предикатов сквозь PARTITION BY (PBY) можно выполнять всегда. Для проталкивания сквозь ORDER BY (OPBY) требуется анализ [26] затрагиваемого диапазона оконной функции.
Упрощение группировки (Group Pruning) — еще одно императивное преобразование, которое удаляет из представлений группы, не требующиеся во внешних блоках запроса. Например, рассмотрим запрос Q9:
Q9
SELECT sum_sal, country_id, state_id, city_id
FROM (SELECT SUM (e.salary) sum_sal,
l.country_id, l_state_id, l.city_id
FROM employees e, departaments d
locations l
WHERE e.dept_id = d.dept_id and
d.location_id = l.location_id
GROUP BY ROLLUP (counrty_id, state_id,
city_id))
WHERE city_id = 'San Francisco';
В приведенном выше запросе внешний предикат на city_id фильтрует группы (country_id) и (country_id, state_id). Преобразование может быть выполнено на основе как предикатов на столбцах раздела GROUP BY, так и функций группировки. Это преобразование выполняется после перемещения упрощающих предикатов фильтрации в непосредственную близость к запросу с GROUP BY.
1 Заметим, что здесь мы используем нестандартную нотацию полусоединения (semijoin) T1.C S= T2.C, где T1 и T2 — левая и правая таблица полусоединения соответственно.
Назад Содержание Вперёд
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
Виртуальные VPS серверы в РФ и ЕС
