Расширенная оптимизация подзапросов в Oracle

2010 г.

Расширенная оптимизация подзапросов в Oracle

Срикант Белламконда, Рафи Ахмед, Анжела Амор, Мохамед Зэйд

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

Оригинал: Enhanced Subquery Optimizations in Oracle / Srikanth Bellamkonda, Rafi Ahmed, Andrew Witkowski, Angela Amor, Mohamed Zait, Chun-Chieh Lin // Proceedings of the 35th international conference on Very large data base, 2009, pp. 1366 — 1377

Содержание

1. Введение

1.1. Преобразование запросов в Oracle
1.2. Устранение вложенности подзапросов
1.3. Оконные функции

2. Сращивание подзапросов

2.1. Сращивание подзапросов одинакового типа
2.2. Сращивание подзапросов разных типов
2.3. Сращивание и другие преобразования
2.4. Расширение возможностей выполнения запросов

3. Исключение представлений с группировкой

3.1. Исключение представлений

4. Удаление подзапросов с использованием оконных функций

4.1. Коррелированный поглощаемый подзапрос
4.2. Некоррелированный поглощаемый подзапрос
4.3. Поглощаемый подзапрос в разделе HAVING
4.4. Подзапросы, возвращающие мультимножества

5. Масштабируемое параллельное выполнение

6. Антисоединение с учетом наличия неопределенных значений

6.1. Алгоритм антисоединения с учетом наличия неопределенных значений
6.2. Стратегии выполнения NAAJ

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

7.1. Сращивание подзапросов
7.2. Исключение представлений с группировкой
7.3. Удаление подзапросов с использованием оконных функций
7.4. Масштабируемое выполнение оконных функций
7.5. Антисоединение с учетом наличия неопределенных значений

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

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

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

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

Аннотация

В статье описывается расширенная оптимизация подзапросов в реляционной СУБД Oracle. Рассматривается несколько методов – сращивание подзапросов (subquery coalescing), удаление подзапросов с использованием оконных функций (subquery removal using window functions) и устранение представлений для запросов с группировкой (group by view elimination). Эти методы распознают и устраняют избыточность в структурах запроса и преобразуют запросы к потенциально более оптимальным формам. В статье также обсуждаются новые методы параллельного выполнения, которые обладают универсальной применимостью и используются для улучшения масштабируемости запросов, подвергнутых некоторым из этих преобразований. Описывается новый вариант антисоединения для оптимизации подзапросов с квантором всеобщности, столбцы которых могут содержать неопределенное значение. Далее представляются результаты проверки производительности этих оптимизаций, которые показывают существенное уменьшение времени выполнения.

1. Введение

Современные реляционные СУБД выполняют сложные SQL-запросы, включающие вложенные подзапросы с функциями агрегации, представления с union/union all, distinct, group by и т.д. Такие запросы становятся все более и более важными в системах поддержки принятия решений (Decision-Support System, DSS) и оперативной аналитической обработки (On-Line Analytical Processing, OLAP). В качестве метода оптимизации таких запросов принято использовать преобразование запросов.

Подзапросы – это мощный компонент языка SQL, повышающий его уровень декларативности и выразительных возможностей. Стандарт SQL позволяет использовать подзапросы в разделах SELECT, FROM, WHERE и HAVING. Подзапросы широко используются в эталонных тестовых наборах поддержки принятия решений TPC-H [4] и TPC-DS [15]. Почти половина из 22 запросов в тестовом наборе TPC-H содержит подзапросы. Почти все подзапросы являются коррелированными, и многие из них содержат вызовы агрегатных функций. Поэтому эффективное выполнение сложных подзапросов является существенно важным для систем баз данных.

1.1. Преобразование запросов в Oracle

В Oracle выполняется множество преобразований запросов – устранение вложенности подзапросов (subquery unnesting), слияние представлений с группировкой и удалением дубликатов (group-by and distinct view merging), исключение общих подвыражений (common sub-expression elimination), проталкивание предикатов соединений (join predicate pushdown), факторизация соединений (join factorization), преобразование теоретико-множественных операций пересечения и вычитания в (анти)соединение (conversion of set operators intersect and minus into (anti)join), раскрытие OR (OR expansion), преобразование типа "звезда" (star transformation), размещение операций группировки и удаления дубликатов (group-by and distinct placement) и т.д. Преобразования запросов могут быть основаны на эвристиках или оценке стоимости. При применении преобразований, основанных на оценке стоимости, для генерации оптимального плана комбинируются логические преобразования и физическая оптимизация.

В Oracle 10g появились общая инфраструктура (framework) [8] преобразований запросов на основе оценки стоимости и несколько стратегий поиска в пространстве состояний. При выполнении преобразований, основанных на оценке стоимости, запрос копируется, преобразуется, и с использованием существующего стоимостного физического оптимизатора вычисляется его стоимость. Этот процесс повторяется несколько раз с применением новых наборов преобразований; и в конце концов выбирается одно или несколько преобразований, которые применяются к исходному запросу, если это приводит к оптимальной стоимости. Инфраструктура преобразований на основе оценки стоимости обеспечивает механизм для исследования пространства состояний, образуемого при применении одного или нескольких преобразований, что позволяет Oracle эффективным образом выбирать оптимальное преобразование. Инфрастуктура преобразований на основе оценки стоимости позволяет справляться со сложностями, возникающими при наличии в запросе пользователя нескольких блоков запроса и взаимной зависимости преобразований. Наличие общей инфрастуктуры преобразований на основе оценки стоимости позволяет расширять обширный репертуар методов преобразования запросов Oracle новыми преобразованиями. В этой статье представлены новые методы преобразования – сращивание подзапросов (subquery coalescing), удаление подзапросов (subquery removal) и устранение фильтрующего соединения (filtering join elimination).

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

Устранение вложенности подзапросов [1], [2], [8], [9] – это важное преобразование запросов, поддерживаемое во многих системах баз данных. Если вложенность коррелированного подзапроса не устраняется, он вычисляется несколько раз с использованием семантики покортежной итерации (tuple iteration semantics). Это похоже на соединение методом вложенных циклов, и, следовательно, при этом не могут быть учитываться эффективные пути доступа, методы соединений и порядки соединений.

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

Устранение вложенности нескалярных подзапросов часто приводит к полу- или антисоединениям. В Oracle для выполнения полу- или антисоединения могут использоваться индексный поиск, хеширование и сортировка со слиянием. Исполнительный механизм Oracle кэширует результаты полу- и антисоединений для кортежей левой таблицы, так что можно избежать нескольких вычислений результатов подзапроса, если в столбцах соединения левой таблицы имеется большое число дубликатов. В Oracle устраняется вложенность подзапросов, входящих в квантифицированное (с квантором существования или всеобщности) сравнение с операцией сравнения, отличной от равенства (например, > ANY, < ALL и т.д.) c использованием соединения методом сортировки со слиянием по предикату сравнения при отсутствии соответствующих индексов.

Вложенность подзапросов, являющихся операндами операций сравнения с квантором всеобщности (например, <> ALL), со столбцами, в которых допускаются неопределенные значения, не может быть устранена с использованием обычного антисоединения. Для устранения вложенности таких подзапросов в Oracle используется вариант антисоединения, называемый антисоединением с учетом наличия неопределенных значений (null-aware antijoin).

1.3. Оконные функции

В стандарте SQL 2003 [11] SQL расширяется оконными функциями¹, которые не только обеспечивают простые и изящные выразительные средства для формулировки аналитических запросов, но также могут способствовать эффективной оптимизации и выполнению запросов, позволяя избежать многочисленных самосоединений (self-join) и наличия нескольких блоков запроса. Оконные функции широко используются в ряде аналитических приложений. В Oracle оконные функции поддерживаются начиная с версии Oracle 8i. Синтаксис оконных функций выглядит следующим образом:

  Window_Function ([arguments]) OVER (
     [PARTITION BY pk₁ [,pk₂ , ...]]
[ORDER BY ok₁ [,ok₂ , ...][WINDOW clause]])

Оконные функции вычисляются внутри разделов (partition), определяемых ключами pk₁, pk₂ и т.д. раздела PARTITION BY (PBY), над данными, упорядоченными внутри каждого раздела по значениями ключей ok₁, ok₂ и т.д. раздела ORDER BY (OBY). В разделе WINDOW определяется окно (window) (начальная и конечная точки) для каждой строки. В качестве оконных функций могут использоваться агрегатные функции SQL (SUM, MIN, COUNT и т.д.), функции ранжирования (RANK, ROW_NUMBER и т.д.) или ссылочные функции (LAG, LEAD, FIRST_VALUE и т.д.). Детали синтаксиса и семантики оконных функций описаны в стандарте ANSI SQL [10] [11].

Оконные функции в блоке запроса вычисляются после разделов WHERE, GROUP BY и HAVING. Oracle вычисляет оконную функцию, сортируя данные по ключам разделов PBY и OBY и выполняя, если это требуется, проходы по отсортированным данным. Мы называем такой способ выполнения методом сортировки окна (window sort). Очевидно, что, если оконная функция не содержит ключей PBY и OBY, сортировка не требуется. В этом случае Oracle буферизирует данные, требуемые для вычисления оконной функции, и такой способ выполнения называется методом буферизации окна (window buffer).

Оценочный оптимизатор Oracle устраняет сортировку при оконных вычислениях, если выбирается план, производящий данные в порядке ключей PBY и OBY. В этом случае выполнение производится на основе буферизации окна, когда Oracle просто буферизирует данные и производит несколько проходов по ним для вычисления оконной функции. Однако если данные поступают упорядоченными, то для вычисления оконных функций типа RANK, ROW_NUMBER, кумулятивных (cumulative)(нарастающих) оконных агрегатов можно избежать и буферизации. Сохраняя некоторую информацию о контексте (значения оконной функции и ключей PBY), можно вычислить эти функции при обработке входных данных.

1.3.1. Оконные функции для генерации отчетов

Оптимизация подзапросов, представленная в этой статье, используется для класса оконных функций, называемых оконными функциями для генерации отчетов (Reporting Window Functions). Это такие оконные функции, которые, в силу своей спецификации, возвращают для каждой строки агрегированное значение всех строк соответствующего раздела (как он определяется ключами PBY). Если оконная функция не содержит разделов OBY и WINDOW, или если окно для каждой строки включает в себя все строки раздела, к которому она относится, то эта функция является оконной функцией для генерации отчетов. В этой статье мы иногда называем эти функции агрегатами для генерации отчетов (reporting aggregate).

Оконные функции для генерации отчетов полезны в сравнительном анализе, где они обеспечивают возможность сравнить значение строки на некотором уровне детализации со значением на более общем уровне детализации. Например, чтобы вычислить для некоторого тикера (кода акции) отношение каждодневного объема биржевых торгов к общему объему, для каждой строки (на уровне одного дня) требуется получить агрегированную сумму за все дни. Оконная функция, которая выдает агрегированную сумму для всех строк, и ее результирующие данные выглядели бы примерно таким образом :

Q1
SELECT tiker, day, volume,
  SUM(volume) OVER (PARTITION BY ticker) 
    AS "Reporting SUM"
FROM stocks;

Таблица 1. Пример оконной функции для генерации отчетов SUM

Если в агрегате для генерации отчетов отсутствуют ключи PBY, то выдаваемое им значение является общим итогом по всем строкам, так как имеется только один неявный раздел. Мы называем такие агрегаты для генерации отчетов функциями общего итога (grand-total, GT). Наши преобразования запросов в некоторых случаях вставляют в запрос GT-функции.

¹ В документации Oracle упоминаются в разделе ‘analytic functions’

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