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

Как показывает запрос Q24, в Q23 может быть устранена вложенность подзапроса с использованием NAAJ. Для представления NAAJ используется следующая нестандартная нотация: T1.x NA= T2.y, где T1 и T2 — левая и правая таблицы антисоединения с учетом наличия неопределенных значений соответственно.

Q24

SELECT T1.C FROM T1, T2 WHERE T1.x NA= T2.y AND T2.z > 10;

Поясним семантику NAAJ на примере Q24. NAAJ выполняется после вычисления всех предикатов фильтрации над правой таблицей. Поэтому, когда мы говорим о T2 в последующем объяснении, имеется в виду набор данных, полученный путем применения предиката T2.z > 10

к исходной таблице T2.

Если T2 не содержит строк, то вернуть все строки T1 и завершить работу.

Если любая строка T2 содержит неопределенные значения во всех столбцах, участвующих в условии NAAJ, то не возвращать никаких строк и завершить работу.

Если строка T1 содержит неопределенные значения во всех столбцах, участвующих в условии NAAJ, то не возвращать эту строку.

Для каждой строки T1, если условие NAAJ вычисляется в TRUE или UNKNOWN для какой-либо строки T2, то не возвращать эту строку T1; иначе вернуть эту строку T1.

Шаг 1 аналогичен соответствующему шагу обычного антиcоединения; т.е. если правая часть пуста, то возвращаются все строки левой части, включая те из них, которые содержат неопределенные значения в условии антисоединения. Отметим, что шаги 2 и 3 поглощаются шагом 4, но их явное наличие позволяет выполнить антисоединение более эффективно, если все столбцы соединения левой или правой строки содержат неопределенные значения. Шаг 4 существенно отличает NAAJ от обычного антисоединения. Тогда как в обычном антисоединении, если условие антисоединения вычисляется в UNKNOWN, то строка левой таблицы возвращается, в NAAJ она не возвращается. Далее будут представлены стратегии выполнения NAAJ. Для антисоединений с участием нескольких столбцов эти стратегии являются сложными, и мы проиллюстрируем их с использованием запроса Q25.

Q25

SELECT c1, c2, c3 FROM L WHERE (c1, c2, c3) <> ALL (SELECT c1, c2, c3 FROM R);

Аннотация

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

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

В этом разделе обсуждается вариант антисоединения, появившийся в 11g и называемый антисоединением с учетом наличия неопределенных значений (null-aware antijoin, NAAJ). В большинстве приложений достаточно часто используются подзапросы с <> ALL (т.е. NOT IN), так как разработчики приложений находят синтаксис подзапросов с <> ALL более интуитивно-понятным, чем синтаксис примерно эквивалентных конструкций с NOT EXISTS. Вложенность подзапросов с NOT EXISTS устраняется c использованием антисоединения. Семантика антисоединения прямо противоположна семантике внутреннего соединения, поскольку строка из левой таблицы становится кандидатом в результат только в том случае, когда она не соединяется ни с одной из строк правой таблицы. Мы называем эту операцию обычным антисоединением. Как правило, в коммерческих СУБД обычное антисоединение может использоваться для устранения вложенности подзапросов с <> ALL только в случаях, когда все столбцы в квантифицированном сравнении гарантированно не содержат неопределенных значений. Имеется другая стратегия, описанная в [9], в которой для учета возможности появления неопределенных значений используются дубликат таблицы и дополнительное антисоединение.

В SQL операция <> ALL может трактоваться как конъюнкция неравенств. Аналогично можно трактовать операции < ALL, <= ALL, > ALL и >= ALL. В стандарте SQL поддерживается троичная логика и, следовательно, любое реляционное сравнение с неопределенными значениями всегда вычисляется в UNKNOWN. Например, предикаты 7 = NULL, 7 <> NULL, NULL = NULL, NULL <> NULL вычисляются в UNKNOWN, и это логическое значение отличается от FALSE тем, что его отрицание тоже равняется UNKNOWN. Если итоговым результатом раздела WHERE является FALSE или UNKNOWN, то соответствующая строка отфильтровывается. Рассмотрим запрос Q23, содержащий подзапрос с >= ALL.

Q23

SELECT T1.C FROM T1 WHERE T1.x <> ALL (SELECT T2.y FROM T2 WHERE T2.z > 10);

Предположим, что подзапрос возвращает набор значений {7,11,NULL}, а в T1.x имеется следующий набор значений: {NULL,5,11}. Операция >= ALL может быть выражена как T1.x <> 7 AND T1.x <> 11 AND T1.x <> NULL. Это выражение вычисляется в UNKNOWN, так как T1.x <> NULL всегда вычисляется в UNKNOWN независимо от значения T1.x. Поэтому для этого набора значений Q23 вообще не вернет строк. Обычное антисоединение, если его использовать в этом случае, некорректно вернет {NULL,5}.

Для демонстрации повышения производительности за счет использования антисоединения с учетом наличия неопределенных значений проводилось две группы экспериментов. В экспериментах первой группы использовался запрос Q26, выдающий из заданного списка поставщиков имена поставщиков, у которых не было заказов в заданном месяце (в январе 1996 г.). В этой схеме L_SUPPKEY может содержать неопределенные значения, а S_SUPPKEY — нет.

Q26

SELECT s_name FROM supplier WHERE s_suppkey in (<supplier_list>) AND s_suppkey <> ALL (SELECT l_suppkey FROM lineitem WHERE l_shipdate >>= '1996-01-01' AND l_shipdate < '1996-02-01');

Без использования NAAJ вложенность подзапроса в Q26 устранить невозможно, а это приводит к коррелированному выполнению, когда мы должны выполнять подзапрос для каждой строки таблицы поставщиков. Такой запрос выполняется мучительно долго, поскольку для вычисления коррелированного предиката невозможно использовать индексное зондирование (index probe). Это связано с тем, что Oracle преобразует подзапрос с ALL в подзапрос с NOT EXISTS и использует коррелированный предикат, который эквивалентен предикату (l_suppkey IS NULL OR l_suppkey = r_suppkey). Единственным достоинством выполнения этого запроса без использования NAAJ является разделение таблицы lineitem по l_shipdate, позволяющее сократить объем сканирования до одного раздела. Рис. 10 иллюстрирует прирост производительности при возрастании числа поставщиков до 40. Преобразованный запрос выполняется с использованием антисоединения таблиц supplier и lineitem с учетом наличия неопределенных значений; антисоединие вычисляется на основе хэширования.

Второй эксперимент проводился на реальной рабочей нагрузке — 241000 запросов, производимых Oracle Applications. Схема содержит около 14 000 таблиц, представляющих приложения кадровой службы (human resources), финансовые приложения (financial), приложения приема заявок (order entry), CRM, управления цепочкой поставок (supply chain) и т.д. Базы данных большинства приложений имеют сильно нормализованные схемы. Число таблиц в запросах варьируется между 1 и 159, в среднем — 8 таблиц на запрос.

Рис.10. Выполнение запроса без NAAJ и с NAAJ

Имелось 72 запроса с DISTINCT и подзапросами с <> ALL, пригодных для выполнения на основе NAAJ. Для 68 из них при использовании NAAJ затраченное процессорное время сократилось в среднем в 736730 раз! Один запрос выполнялся 350 секунд без использования NAAJ и 0,001 секунды — с использованием NAAJ. Время выполнения 4 запросов увеличилось в среднем в 100 раз, причем в наихудшем случае затраченное процессорное время увеличилось c 0,000001 секунды до 0,016 секунды.

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

Авторы хотели бы выразить признательность Тьерри Круанесу (Thierry Cruanes) за инфрастуктуру взаимодействий процесса QC с подчиненными процессами, Натану Фолкеру (Nathan Folkert) и Санкару Субраминьяну (Sankar Subramanian) за распараллеливание некоторого класса оконных функций с использованием этой инфраструктуры. Сьюзи Фэн (Susy Fan) заслуживает огромной благодарности за ее помощь при проведении экспериментов по оценке производительности.

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

Рассмотрим запрос Q8, являющийся упрощенным вариантом запроса 18 тестового набора TPC-H.

SELECT o_orderkey, c_custkey, SUM(l_quantity) FROM orders, lineitem L1, customers WHERE o_orderkey = l_orderkey AND c_custkey = o_custkey AND o_orderkey IN (SELECT l_orderkey FROM lineitem L2 GROUP BY l_orderkey HAVING SUM(l_quantity) > 30) GROUP BY o_orderkey, c_custkey;

Подзапрос Q8 подвергается преобразованию устранения вложенности, что приводит к порождению запроса Q9. К встроенному представлению (производной таблице) V2, появившемуся в в Q9 из-за устранения вложенности, не требуется применять полусоединение, так как здесь имеется эквисоединение, и столбцы соединения V2 обладают свойством уникальности, поскольку являются единственными столбцами группировки в V2.

SELECT o_orderkey, c_custkey, SUM(l_quantity) FROM orders, lineitem L1, customers, (SELECT l_orderkey FROM lineitem L2 GROUP BY l_orderkey HAVING SUM(l_quantity) > 30) V2 WHERE o_orderkey = V2.l_orderkey AND o_orderkey = L1.l_orderkey AND c_custkey = o_custkey GROUP BY o_orderkey, c_custkey;

Как показывает запрос Q10, с использованием перестановки группировки и соединения (т.е. размещения группировки, group-by placement) [5], [6], [8] можно получить еще одно представление V1, содержащее таблицу L1; в список выборки раздела SELECT представления V2 добавляется SUM(l_quantity), что не изменяет семантику Q9.

Q10

SELECT o_orderkey, c_custkey, SUM(V1.qty) FROM orders, customers, (SELECT l_orderkey, SUM(l_quantity) qty FROM lineitem L2 GROUP BY l_orderkey HAVING SUM(l_quantity) > 30) V2, (SELECT l_orderkey, SUM(l_quantity) qty FROM lineitem L1 GROUP BY l_orderkey) V1 WHERE o_orderkey = V2.l_orderkey AND o_orderkey = V1.l_orderkey AND c_custkey = o_custkey GROUP BY o_orderkey, c_custkey;

Как можно видеть, V1 и V2 — это разные экземпляры одного и того же представления, за исключением того, что предикаты фильтрации в V2 являются более ограничительными, чем в V1, из-за наличия в V2 раздела HAVING. Кроме того, эквисоединения V1 и V2 с таблицей orders производятся по столбцу o_orderkey, обладающему свойством уникальности, так как это единственный столбец группировки в этих представлениях; таким образом, эти два соединения являются фильтрующими соединениями. Следовательно, представление V1 можно исключить, а ссылки на V1 можно заменить ссылками на V2. Исключение фильтрующего представления из Q10 приводит к запросу Q11.

Q11

SELECT o_orderkey, c_custkey, SUM(V2.qty) FROM orders, customers, (SELECT o_orderkey, SUM(l_quantity) FROM lineitem GROUP BY l_orderkey HAVING SUM(l_quantity) > 30) V2 WHERE o_orderkey = V2.l_orderkey AND c_custkey = o_custkey GROUP BY o_orderkey, c_custkey;

Если бы представление V2 в запросе Q9 подвергалось слиянию, то могла бы быть приведена другая аргументация использования фильтрующего соединения с тем же результатом исключения таблицы lineitem

из внешнего запроса.

Если известно, что amount_sold положительно; например, в случае ограничения целостности базы данных типа RELY

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

В этом разделе мы обсудим метод преобразования, называемый исключением фильтрующей таблицы (filtering table elimination) и основанный на идее фильтрующих соединений. Фильтрующее соединение (filtering join) — это либо полусоединение, либо внутреннее эквисоединение, в котором один из столбцов соединения обладает свойством уникальности.

Здесь мы будем обозначать столбец, обладающий свойством уникальности, подчеркивая его имя, а для эквиполусоединения будем использовать нестандартную нотацию 0=. Пусть R — это некоторая таблица, а T1 и T2 — два экземпляра одной и той же базовой или производной таблицы T. В T1 и T2 либо имеется один и тот же набор предикатов фильтрации (если они вообще присутствуют), либо предикаты фильтрации T1 являются более ограничительными, чем предикаты фильтрации T2. В следующих случаях T2 и фильтрующее соединение могут быть исключены:

R.X = T1.Y and R.X = T2.Y ≡ R.X = T1.Y

R.X = T1.Y and R.X 0= T2.Y ≡ R.X = T1.Y

R.X 0= T1.Y and R.X 0= T2.Y ≡ R.X 0= T1.Y

Предположим, что первым выполняется нефильтрующее соединение, если таковое имеется. В таком случае фильтрующее соединение сохраняет все результирующие строки R, поскольку фильтрующее соединение может только отфильтровать строки R в отличие от внутреннего соединения, которое может как отфильтровать, так и продублировать строки. В фильтрующем соединении таблица T2 оказывается избыточной, и поэтому она может быть удалена. Хотя этот метод очень похож на сращивание конъюнктивных подзапросов с EXISTS, далее мы представим другое его применение.

В этом эксперименте использовался запрос Q8, представляющий собой упрощенный вариант запроса 18 из TPC-H. Метод исключения представлений с группировкой, описанный в подразделе 3.1, позволяет исключить представление с группировкой, устраняя излишние ссылки на таблицу lineitem, что в результате приводит к запросу Q11. Значение константы в предикате раздела HAVING изменялось в пределах от 30 до 300, так что подзапрос возвращал от 2000 до 34000000 строк (это показано на оси X). На рис. 6 представлены результаты эксперимента.

Рис.6. TPC-H Q18, исключение представления

Преобразование к Q11 может представлять проблему для оптимизатора, поскольку предикат раздела HAVING задан на агрегате, и оптимизатору сложно оценить мощность отфильтрованного множества. Если эта оценка будет заниженной, то оптимизатор может выбрать для выполнения соединения метод вложенных циклов, а не метод хеширования, что приведет к снижению производительности.

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

Эксперименты по производительности проводились на схеме 30G TPC-H. Использовалась машина под управлением OC Linux с 8 двухъядерными процессорами (400 MHz) и 32 GB оперативной памяти. Машина была соединена с общим хранилищем данных под управлением Oracle Automated Storage Manager. Пропускная способность системы ввода-вывода общего хранилища данных была несколько ограничена по сравнению с мощностью процессоров, и это показано в экспериментах по распараллеливанию. Для параллельного выполнения всех запросов использовались все процессоры (если при описании эксперимента явно не оговорено иное).

Коррелированный поглощаемый подзапрос

Рассмотрим запрос Q14, являющийся упрощенным вариантом запроса 2 тестового набора TPC-H. Во внешнем запросе имеются дополнительная таблица PARTS и фильтрующий ее предикат. Подзапрос коррелирует с таблицей PARTS и поглощается внешним запросом.

Q14

SELECT s_name, n_name, p_partkey FROM parts P, supplier, partsupp, nation, region WHERE p_partkey = ps_partkey AND s_suppkey = ps_suppkey AND s_nationkey = n_nationkey AND n_regionkey = r_regionkey AND p_size=36 AND r_name = 'ASIA' AND ps_supplycost IN (SELECT MIN (ps_supplycost) FROM partsupp, supplier, nation, region WHERE P.p_partkey = ps_partkey AND s_suppkey = ps_suppkey AND s_nationkey = n_nationkey AND n_regionkey = r_regionkey AND r_name = 'ASIA');

С использованием метода удаления подзапросов запрос Q14 преобразуется в Q15:

Q15

SELECT s_name, n_name, p_partkey FROM (SELECT ps_supplycost, MIN (ps_supplycost) OVER (PARTITION BY ps_partkey) AS min_ps, s_name, n_name, p_partkey FROM parts, supplier, partsupp, nation, region WHERE p_partkey = ps_partkey AND s_suppkey = ps_suppkey AND s_nationkey = n_nationkey AND n_regionkey = r_regionkey AND p_size=36 AND r_name = 'ASIA') V WHERE V.ps_supplycost = V.min_ps;

Дубликаты строк, если они появляются в Q15 после соединения таблиц PARTSUPP и PARTS, на результат не влияют, так как агрегатной функцией является MIN. Если бы агрегатной функцией была бы не MIN/MAX, или если соединение с дополнительной таблицей (в нашем случае PARTS) не являлось бы соединением без потерь, то вычисление оконной функции должно было бы производиться внутри представления, которое затем уже соединялось бы с дополнительной таблицей. Именно так обстоит дело с запросом 17 из TPC-H, для которого удаление подзапроса приводит к Q16.

Q16

SELECT SUM(V.avg_extprice)/7 AS avg_yearly FROM parts, (SELECT (CASE WHEN l_quantity < (1.2 * AVG (l_quantity) OVER (PARTITION BY (l_pertkey)) THEN l_extprice ELSE NULL END) avg_extprice, l_partkey FROM lineitem) V WHERE p_partkey = V.l_partkey AND V.avg_extprice IS NOT NULL AND p_brand = 'Brand#23' AND p_container = 'Med Box';

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

Распараллеливание оконных функций в Oracle было усовершенствовано для достижения более масштабируемого выполнения запросов. Обычно в Oracle оконные функции распараллеливаются путем распределения данных по нескольким процессам с использованием хеширования или в соответствии с диапазонами значений ключей PBY. Аналогичное распараллеливание применяется для раздела SQL MODEL [7]. При вычислении оконной функции каждый процесс работает над полученном им разделом независимо от других процессов. Например, таким образом распараллеливается оконная функция, введенная в запрос Q16 при удалении подзапроса. Параллельный план выполнения для Q16 показан на рис. 2.

Рис.2. Типичное распараллеливание оконной функции

Производяшие данные подчиненные процессы P1, ...PN распределяют на основе значения хеш-функции от l_partkey результат соединения таблиц parts и lineitem по потребляющим данные подчиненным процессам C1, ...CN, которые выполняют оконную сортировку (window sort). Каждый потребляющий данные подчиненный процесс вычисляет оконную функцию AVG над получаемыми им разделами (определяемыми значениями ключа l_partkey раздела PBY). Отметим, что масштабируемость такого обычного распараллеливания оконных функций определяется числом элементов в наборе ключей PBY. Для оконных функций с небольшим числом ключей PBY (например, region, gender), а также вовсе без ключей PBY масштабируемость ограничена или полностью отсутствует. Масштабируемость таких оконных функций стала критически важной для получения существенной пользы от описанного в разд. 4 преобразования удаления подзапросов с использованием оконных функций. С этой целью был разработан новый метод параллельного выполнения, который мы кратко опишем.

Рассмотрим преобразованный запрос Q20 (подраздел 4.3), в котором имеется оконная функция SUM(SUM(ps_supplycost * ps_availqty) OVER () gt_value без ключей PBY. Она является оконной функцией общего итога (grand-total, GT) для генерации отчетов, поскольку вычисляется на всем наборе данных и возвращает для каждой строки общий итог. GT-функции по своей природе не являются распараллеливаемыми, поскольку у них отсутствуют ключи PBY, по которым обработку данных можно разделить между подчиненными процессами. Если GT-функция не распараллеливается, то это снижает общую выгоду от применения преобразования устранения подзапросов. Типичный параллельный план выполнения оконных GT-функций представлен на рис. 3.

Рис.3. Не слишком параллельный план для GT-функций

Очевидно, что параллельный план, показанный на рис. 3, не очень хорошо масштабируется, так как вычисление оконной GT-функции выполняется процессом-координатром запроса (Query Coordinator, QC). Подчиненные процессы C1, ...CN посылают результат операции группировки процессу QC, который в одиночку вычисляет GT-функцию, используя выполнение с «буферизацией окна». Как упоминалось в подразделе 1.3, Oracle в этом случае выбирает стратегию «буферизации окна», поскольку для вычисления оконной GT-функции требуется всего лишь буферизовать строки. Оконный агрегат вычисляется постепенно, по мере буферизации строк. К моменту исчерпанию входного потока, когда все входные строки окажутся буферизированными, мы полностью вычислим значение оконной функции общего итога. После этого буферизированные строки выводятся вместе со значением общего итога.

В новой схеме распараллеливания оконных GT-функций основная часть вычислений GT-функции проталкивается в подчиненные процессы, а не выполняется QC. Для завершения вычисления GT-функции требуется небольшой дополнительный шаг координации между подчиненными процессами и QC. При использовании такой модели вычисление GT-функций становится сильно масштабируемым. Новый план параллельного выполнения оконных GT-функций показан на рис. 4.

Рис.4. Параллельное выполнение GT-функций

Теперь обработка буфера окна проталкивается в подчиненные процессы C1, ...CN. Каждый из них вычисляет локальный итог и сообщает его процессу-координатору запроса. QC консолидирует результаты, полученные от подчиненных процессов, и сообщает значение общего итога обратно подчиненным процессам. После этого подчиненные процессы выводят буферизированные строки совместно со значением общего итога. При использовании этого параллельного плана подчиненные процессы параллельно выполняют основную часть обработки строк. Сериализация частичных результатов (или их консолидация в QC) не приведет к заметным накладным расходам, поскольку число значений, обрабатываемых QC, будет небольшим (максимум 1000), что определяется уровнем параллелизма (числом процессов, параллельно работающих над выполнением одной задачи).

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

Подчиненные процессы C1, ..., CN локально вычисляют оконные агрегаты для генерации отчетов для каждого раздела и передают в QC массив локальных оконных агрегатов и соответствующие значения ключей PBY. QC завершает вычисление агрегатов для генерации отчетов для каждого раздела и передает результаты (итоговые оконные агрегаты и значения ключей PBY) обратно подчиненным процессам. Для получения результатов подчиненные процессы выполняют соединение локальных данных с данными, полученными от QC. Поскольку как локальные данные подчиненных процессов, так и данные, получаемые от QC, являются упорядоченными по значениям ключей PBY, это соединение похоже на соединение сортировкой со слиянием. Результаты экспериментов, демонстрирующие масштабируемость оконных функций, представлены в разд. 7.

Масштабируемое выполнение оконных функций

Для иллюстрации эффекта от распараллеливания оконных функций без раздела PBY использовался следующий запрос к таблице lineitem:

SELECT SUM(l_extprice) OVER () W FROM lineitem;

Запрос выполнялся с применением и без применения усовершествованных методов распараллеливания, описанных в разд. 5, и степень параллелизма (degree of parallelism, DOP) изменялась от 2 до 16. На рис. 9 представлены результаты этого эксперимента.

Рис.9. Распараллеливание оконной функции без PBY

Заметим, что даже если оконная функция не распараллеливается, сканирование таблицы по-прежнему выполняется параллельно. Сканирующие подчиненные процессы посылают свои данные координатору запроса, который затем вычисляет оконную функцию. Вследствие этого, при степени параллелизма, равной 2, производительность преобразованного запроса возрастает немного меньше, чем в 2 раза. Рис. 9 также показывает, что при DOP > 8 система не масштабируется линейно при дальнейшем росте DOP из-за ограниченной пропускной способности нашей совместно используемой дисковой системы.

Некоррелированный поглощаемый подзапрос

Рассмотрим запрос Q17, являющийся упрощенной версией запроса 15 тестового набора TPC-H. В Q17 имеется агрегатный подзапрос, в котором отсутствует корреляция с внешним запросом, и в подзапросе используется общее с внешним запросом представление (производная таблица) с группировкой V.

Q17

WITH V AS (SELECT l_suppkey, SUM(l_extprice) revenue FROM lineitem WHERE l_shipdate >= '1996-01-01' GROUP BY l_suppkey)

SELECT s_suppkey, s_name, V.revenue FROM supplier, V WHERE s_suppkey = V.l_suppkey AND V.revenue = (SELECT MAX(V.revenue) FROM V);

Этот запрос может быть преобразован в запрос Q18, в котором вводится оконная функция и удаляется подзапрос.

Q18

SELECT s_suppkey, s_name, V.revenue FROM supplier, (SELECT l_suppkey, SUM(l_extprice) revenue, MAX(SUM(l_extprice)) OVER () gt_rev FROM lineitem WHERE l_shipdate >= '1996-01-01' GROUP BY l_suppkey) V WHERE s_suppkey = V.l_suppkey AND V.revenue = V.gt_rev;

В этом примере для удаления подзапроса вводится оконная функция общего итога MAX (специфицируемая с использованием пустого раздела OVER( ) ) на агрегате SUM(l_extprice). Потребность в наличии в оконной функции раздела PBY отсутствует, так как в подзапросе из Q17 отсутствует корреляция, и его требуется применять ко всему множеству строк. Мы используем новый метод распараллеливания оконных функций общего итога, описываемый в разд. 5, так что преобразованный запрос Q18 может быть выполнен эффективным и масштабируемым образом.

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

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

Window_Function ([arguments]) OVER ( [PARTITION BY pk1 [,pk2 , ...]] [ORDER BY ok1 [,ok2 , ...][WINDOW clause]])

Оконные функции вычисляются внутри разделов (partition), определяемых ключами pk1, pk2 и т.д. раздела PARTITION BY (PBY), над данными, упорядоченными внутри каждого раздела по значениями ключей ok1, ok2 и т.д. раздела 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), можно вычислить эти функции при обработке входных данных.

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

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

для каждой строки включает в себя все строки раздела, к которому она относится, то эта функция является оконной функцией для генерации отчетов. В этой статье мы иногда называем эти функции агрегатами для генерации отчетов (reporting aggregate).

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

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’

Подзапросы, возвращающие мультимножества

Чтобы можно было удалить подзапроса с использованием оконных функций, этот подзапрос не обязательно должен содержать агрегатные функции и возвращать множество из одной строки. Рассмотрим запрос Q21, в котором подзапрос производит мультимножество строкй и участвует в квантифицированном предикате с квантором ALL.

Q21

SELECT ps_partkey, s_name, SUM(ps_supplycost * ps_availqty) AS value FROM partsupp, supplier, nation WHERE ps_suppkey = s_suppkey AND s_nationkey = n_nationkey AND n_name = 'GERMANY' GROUP BY s_name, ps_partkey HAVING SUM(ps_supplycost * ps_availqty) > ALL (SELECT ps_supplycost * ps_availqty * 0,01 FROM partsupp, supplier, nation WHERE n_name = 'GERMANY' AND ps_suppkey = s_suppkey AND s_nationkey = n_nationkey);

Этот запрос преобразуется в запрос Q22:

Q22

SELECT ps_partkey, s_name, VALUE FROM (SELECT ps_partkey, s_name SUM(ps_supplycost * ps_availqty) as VALUE, MAX(MAX(ps_supplycost * ps_availqty)) OVER () VAL_pkey FROM partsupp, supplier, nation WHERE n_name = 'GERMANY' AND ps_suppkey = s_suppkey AND s_nationkey = n_nationkey GROUP BY s_name, ps_partkey) V WHERE V.value > V.Val_pkey * 0,01;

Если бы в предикате подзапроса использовалось квантифицированное сравнение "> ANY", то оконная функция имела бы вид MIN(MIN(ps_supplycost * ps_availqty)) OVER (). Используя несколько оконных функций, можно аналогичным образом справиться с предикатами "= ALL" и "= ANY".

Поглощаемый подзапрос в разделе HAVING

Техника удаления подзапросов также может применяться и при наличии во внешнем запросе группировки. Например, рассмотрим запрос Q19, являющийся упрощенным вариантом запроса 11 из тестового набора TPC-H. Подзапрос в Q19 является некоррелированным и поглощаемым внешним запросом. Фактически, в подзапросе и внешнем запросе имеется один и тот же набор таблиц и предикатов.

Q19

SELECT ps_partkey, SUM(ps_supplycost * ps_availqty) AS value FROM partsupp, supplier, nation WHERE ps_suppkey = s_suppkey AND s_nationkey = n_nationkey AND n_name = 'FRANCE' GROUP BY ps_partkey HAVING SUM(ps_supplycost * ps_availqty) > (SELECT SUM(ps_supplycost * ps_availqty) * 0.0001 FROM partsupp, supplier, nation WHERE ps_suppkey = s_suppkey AND s_nationkey = n_nationkey AND n_name = 'FRANCE');

Q19 может быть преобразован в Q20. Как и в Q17, введенная оконная функция является функцией общего итога без ключей PBY, так как в подзапросе в Q19 отсутствует корреляция.

Q20

SELECT V.ps_partkey, V.value FROM (SELECT ps_partkey, SUM(ps_supplycost * ps_availqty) AS value, SUM(SUM(ps_supplycost * ps_availqty) OVER () gt_value FROM partsupp, supplier, nation WHERE ps_suppkey = s_suppkey AND s_nationkey = n_nationkey AND n_name = 'FRANCE' GROUP BY ps_partkey) V WHERE V.value > V.gt_value * 0,0001;

Преобразование запросов в 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).

Расширение возможностей выполнения запросов

В запросе Q7 предикат раздела HAVING отфильтровывает группы, имеющие, по крайней мере, одну запись с датой прихода (receipt date), большей даты завершения (commit date). Неудовлетворение этого и других предикатов, таких как MIN(l_receiptdate) > '18-FEB-2001', COUNT(*) <= 10, SUM(amount_sold) < 2000, немедленно делает группу неприемлемой (т.е. исключают ее из кандидатов в результирующий набор данных), и такие предикаты могут быть вытолкнуты в раздел GROUP BY для ускорения процесса агрегирования этой группы. Это приводит к эффективному выполнению. Например, в Q7 входная запись с l_receiptdate > l_commitdate делает равным единице значение агрегата SUM для соответствующей группы, исключая, таким образом, группу из списка кандидатов. Аналогично, если в качестве предиката используется SUM(amount_sold) < 2000, и в базе данных имеется ограничение, указывающее, что значение amount_sold должно быть положительным, то группа исключается из списка кандидатов, как только значение SUM для нее превысит 2000. Раздел GROUP BY в подобных случаях позволяет не производить агрегацию для групп, исключенных из списка кандидатов.

Использование таких предикатов также приносит пользу при выполнении параллельной группировки, снижая трафик передачи данных. В Oracle применяется метод параллельного проталкивания группировки (group-by pushdown, GPD) на основе оценки стоимости, который проталкивает выполнение группировки в процессы, производящие данные (подчиненные процессы-производители, producer slave), с целью сокращения коммуникационных расходов и повышения уровня масштабируемости группировки. Процессы, производящие данные, распределяет локально агрегированные данные между другими процессами (подчиненными процессами-потребители, consumer slave) на основе хеширования или диапазонов значений ключей группировки. Затем подчиненные процессы-потребители завершают выполнение группировки и производят результаты. План параллельного выполнения запроса Q7 с GPD представлен на рис. 1. Сокращение трафика достигается, если подчиненные процессы-производители P1, ..., PN во время выполнения группировки отфильтровывают группы, основываясь на предикатах раздела HAVING.

Рис.1. Проталкивание в параллельной группировке

Аналогичным образом, предикаты, удовлетворение которых приводит к немедленному включению групп в список кандидатов в результирующий набор данных, также могут быть вытолкнуты в обработку группировки. Обработку агрегации групп, не входящих в результирующий набор, можно пропустить, как только найдется группа, являющаяся кандидатом. Примеры таких предикатов: MIN(l_receiptdate) < '18-FEB-2001', COUNT(*) > 10, SUM(amount_sold) > 2000, если известно, что amount_sold положительно.

Расширенная оптимизация подзапросов в 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], [2], [3], [4], [9]. В нашей системе поддерживаются почти все эти разновидности методов устранения вложенности с примененем как эвристических, так и основанных на оценке стоимости стратегий. В ранней работе, посвященной преобразованиям запросов [2], предлагается метод вытягивания агрегатов и группировки в позицию дерева операций, предшествующую соединению. Похожий алгоритм применялся в ранних версиях Oracle (8.1 и 9i). Преобразование инициировалось эвристиками на фазе преобразования запроса. В Oracle 11g для размещения операций группировки и удаления дубликатов, а также их коммутирования с соединениями [5] [6] используется инфраструктура, основанная на оценке стоимости [8]. Некоторые методы удаления подзапросов с использованием оконных функций опубликованы в [13]. Неформальные ссылки, содержащиеся в [12], наводят на мысль, что метод устранения подзапросов с группировкой обсуждался где-то еще. Мы показываем, каким образом подобный метод может быть включен в оптимизатор Oracle. Работы, посвященные сращиванию подзапросов, антисоединению с учетом наличия неопределенных значений и масштабируемому вычислению оконных функций, в опубликованной литературе не обсуждались.

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

[1] W. Kim, «On Optimizing an SQL-Like Nested Query», ACM TODS, September 1982.

[2] U. Dayal, «Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates, and Quantifiers», Proceedings of the 13th VLDB Conference, Brighton, U.K., 1987.

[3] M. Muralikrishna, «Improved Unnesting Algorithms for Join Aggregate SQL Queries», Proceedings of the 18th

VLDB Conference, Vancouver, Canada, 1992.

[4] H. Pirahesh, J.M. Hellerstein, and W. Hasan, «Extensible Rule Based Query Rewrite Optimizations in Starburst», Proc. of ACM SIGMOD, San Diego, USA, 1992.

[5] S. Chaudhuri and K. Shim, «Including Group-By in Query Optimization», Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.

[6] W.P.Yan and A.P.Larson, «Eager Aggregation and Lazy Aggregation», Proceedings of the 21th VLDB Conference, Zurich, Switzerland, 1995.

[7] A. Witkowski, et al, «Spreadsheets in RDBMS for OLAP», Proc. of ACM SIGMOD, San Diego, USA, 2003.

[8] R. Ahmed, et al, «Cost-Based Query Transformation in Oracle», Proceedings of the 32th VLDB Conference, Seoul, S. Korea, 2006.

[9] M. Elhemali, C. Galindo-Legaria, et al, «Execution Strategies for SQL Subqueries», Proc. of ACM SIGMOD, Beijing, China, 2007.

[10] A. Eisenberg, K. Kulkarni, et al, «SQL: 2003 Has Been Published», SIGMOD Record, March 2004.

[11] F. Zemke, «Rank, Moving and reporting functions for OLAP», 99/01/22 proposal for ANSI-NCITS.

[12] C. Zuzarte, et al, «Method for Aggregation Subquery Join Elimination»,

[13] C. Zuzarte, H. Pirahesh, et al, «WinMagic: Subquery Elimination Using Window Aggregation», Proc. of ACM SIGMOD, San Diego, USA, 2003.

[14] TPC Benchmark H (Decision Support), Standart Specification Rev 2.8,

[15] TPC-DS Specification Draft , Rev 32, http://tpc.org/tpcds/spec/tpcds32.pdf

Для части работ, описанных в этой статье, рассматривается вопрос о выдаче патентов США.

Сращивание и другие преобразования

В [8] мы обсуждали, как различные преобразования взаимодействуют друг с другом, и как инфраструктура преобразований, основанных на оценке стоимости, управляет возможными взаимодействиями. Сращивание подзапросов не является исключением, так как срощенный подзапрос стать предметом других преобразований. Подзапрос из Q5 может быть подвергнут преобразованию устранения вложенности, что приведет к запросу Q6, который содержит встроенное представление (производную таблицу) V:

SELECT s_name FROM supplier, lineitem L1, (SELECT LX.rowid xrowid FROM lineitem L2, lineitem LX WHERE L2.l_orderkey = LX.l_orderkey AND L2.l_suppkey <> LX.l_suppkey GROUP BY LX.rowid HAVING SUM(CASE WHEN L2.l_receiptdate >

L2.l_commitdate THEN 1 ELSE 0 END) = 0) V WHERE s_suppkey = L1.l_suppkey AND L1.rowid = V.xrowid;

После слияния представления из Q6 получается запрос Q7, в котором таблица LX оказывается избыточной, так как в слитом блоке запроса LX и L1 соединяются по столбцу rowid, обладающему свойством уникальности. Поэтому LX

удаляется, а все ссылки на нее заменяются ссылками на L1.

SELECT s_name FROM supplier S, lineitem L1, lineitem L2 WHERE s_suppkey = L1.l_suppkey AND L1.l_orderkey = L2.l_orderkey GROUP BY L1.rowid, S.rowid, S.s_name HAVING SUM(CASE WHEN L2.l_receiptdate > L2.l_commitdate THEN 1 ELSE 0 END) = 0);

Здесь мы имеем уже, как минимум, четыре альтернативных формулировки запроса. В большинстве случаев неясно, какая из четырех альтернатив является оптимальным выбором. Для поддержки принятия решения может быть использована инфраструктура преобразований Oracle, основанных на оценке стоимости, которая обсуждалась в подразделе 1.1.

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

Сращивание подзапросов (subquaery coalescing) — это метод, при применении которого при определенных условиях два подзапроса могут быть срощены в один подзапрос, что позволяет вместо выполнения нескольких операций сканирования таблиц и соединения ограничиться единственным сканированием таблицы и единственным соединением. Хотя сращивание подзапросов определяется как бинарная операция, она может последовательно применяться к любому числу подзапросов. Сращивание подзапросов оказывается возможным, поскольку подзапрос действует как предикат фильтрации таблиц внешнего запроса.

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

Говорят, что блок запроса X включает другой блок запроса Y, если результат Y является подмножеством (не обязательно собственным) результата X. X называется включающим (container) блоком запроса, а Y — включаемым (contained) блоком запроса. Другими словами, X и Y отвечают свойству включения (containment), если Y содержит некоторые конъюнктивные предикаты фильтрации P, и X и Y становятся эквивалентными, если P не влияют на обоснование их эквивалентности.

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

В настоящее время в Oracle выполняются различные типы сращивания подзапросов, когда два подзапроса с [NOT] EXISTS предстают в конъюнкции или дизъюнкции. Поскольку подзапросы с ANY и ALL могут быть преобразованы в подзапросы c EXISTS и NOT EXISTS соответственно, мы не обсуждаем здесь сращивание подзапросов с ANY/ALL. В тривиальном случае наличия двух подзапросов, которые являются эквивалентными и имеют один и тот же тип (например, либо EXISTS, либо NOT EXISTS), сращивание подзапросов заключается в удалении одного из них. Если у эквивалентных подзапросов имеются разные типы, то сращивание приводит к удалению обоих подзапроса и их замене предикатом FALSE/TRUE в зависимости от того, соединены ли эти подзапросы конъюнкцией или дизъюнкцией.

Рассмотрим наш запрос Q4, являющийся упрощенной версией запроса 21 из TPC-H. По сравнению с Q4 исходный запрос 21 из TPC-H содержит две дополнительные таблицы orders и nation и предикаты селекции, ограничивающие данные заданной страной (nation). В схеме представлены 25 стран, данные которых распределены равномерно. Сращивание подзапросов, описанное в подразделе 2.2, преобразует Q4 в Q5. На рис. 5 показано время выполнения преобразованного (Q5) и непреобразованного (Q4) вариантов запроса как функция от количества стран. В среднем повышение производительности составило 27%.

Рис.5. TPC-H Q21, сращивание подзапросов

Сращивание подзапросов одинакового типа

Если два конъюнктивных подзапроса с EXISTS или два дизъюнктивных подзапроса с NOT EXISTS

отвечают свойству включения, то они могут быть срощены в один подзапрос путем сохранения включаемого подзапроса и удаления включающего подзапроса. Для случая дизъюнктивных подзапросов с EXISTS или конъюнктивных подзапросов с NOT EXISTS сращивание может быть выполнено путем сохранения включающего подзапроса и удаления включаемого подзапроса.

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

Рассмотрим запрос Q2 с двумя дизъюнктивными подзапросами с EXISTS; подзапросы содержат один и тот же коррелированный предикат, но разные конъюнктивные предикаты фильтрации:

SELECT o_orderpriority, COUNT(*) FROM orders WHERE o_orderdate >= '1993-07-01' AND EXISTS (SELECT * FROM lineitem WHERE l_orderkey = o_orderkey AND l_returnflag = 'R') OR EXISTS (SELECT * FROM lineitem WHERE l_orderkey = o_orderkey AND l_receipt_date > l_commitdate) GROUP BY o_orderpriority;

Сращивание подзапросов объединяет два подзапроса с EXISTS в один подзапрос с EXISTS

с дизъюнкцией предикатов фильтрации, что приводит к получению запроса Q3.

SELECT o_orderpriority, COUNT(*) FROM orders WHERE o_orderdate >= '1993-07-01' AND EXISTS (SELECT * FROM lineitem WHERE l_orderkey = o_orderkey AND (l_returnflag = 'R' OR l_receipt_date > l_commitdate)) GROUP BY o_orderpriority;

Сращивание подзапросов разных типов

Для сращивание двух конъюнктивных подзапросов, удовлетворяющих свойству включения и имеющих разные типы, требуется применение другого метода. Рассмотрим запрос Q4, который является несколько упрощенным вариантом запроса 21 из TPC-H.

SELECT s_name FROM supplier, lineitem L1 WHERE s_suppkey = l_suppkey AND EXISTS (SELECT * FROM lineitem L2 WHERE l_orderkey = L1.l_orderkey AND l_suppkey <> L1.l_suppkey) AND NOT EXISTS (SELECT * FROM lineitem L3 WHERE l_orderkey = L1.l_orderkey AND l_suppkey <> L1.l_suppkey AND l_receiptdate > l_commitdate);

Два подзапроса в Q4 отличаются только своими типами и тем, что в подзапросе с NOT EXISTS имеется дополнительный предикат фильтрации l_receipt_date > l_commitdate. Сращивание подзапросов приводит к запросу Q5 с единственным подзапросом с EXISTS, в результате чего устраняется один экземпляр таблицы lineitem.

SELECT s_name FROM supplier, lineitem L1 WHERE s_suppkey = l_suppkey AND EXISTS (SELECT 1 FROM lineitem L2 WHERE l_orderkey = L1.l_orderkey AND l_suppkey <> L1.l_suppkey) HAVING SUM(CASE WHEN l_receiptdate > l_commitdate THEN 1 ELSE 0 END) = 0);

Агрегатная функция раздела HAVING возвращает общее количество строк, удовлетворяющих предикату подзапроса. Раздел HAVING, включенный в срощенный подзапрос, является новым предикатом фильтрации, который проверяет, удовлетворяет ли какая-либо строка предикату подзапроса, тем самым имитируя поведение удаленного подзапроса с NOT EXISTS.

Для каждого набора корреляционных значений подзапросы в Q4 могут находиться в одном из трех состояний:

Если подзапрос EXISTS не возвращает строк (т.е. вычисляется в FALSE), то результатом конъюнкции двух подзапросов является FALSE. В Q5 раздел HAVING применяется к пустому множеству, и срощенный подзапрос с EXISTS также вычисляется в FALSE.

Если подзапрос с EXISTS

возвращает несколько строк (т.е. вычисляется в TRUE), и подзапрос NOT EXISTS тоже возвращает несколько строк (т.е. вычисляется в FALSE), то результатом конъюнкции двух подзапросов является FALSE. В Q5 раздел HAVING применяется к непустому множеству строк, для которых l_receiptdate > l_commitdate, и потому вычисляется в FALSE; таким образом, срощенный подзапрос вычисляется в FALSE.

Если подзапрос с EXISTS

возвращает несколько строк, а подзапрос с NOT EXISTS не возвращает строк из-за дополнительных предикатов фильтрации, то результатом конъюнкции двух подзапросов является TRUE. В Q5 раздел HAVING

применяется к непустому множеству строк, для которых неверно, что l_receiptdate > l_commitdate, и потому вычисляется в TRUE; таким образом, срощенный подзапрос вычисляется в TRUE.

Приведенное обсуждение обосновывает эквивалентность запросов Q4 и Q5. В том случае, когда подзапрос с NOT EXISTS является включающим запросом, а конъюнктивный подзапрос с EXISTS – включаемым запросом, сращивание состоит в удалении обоих подзапросов и замене их предикатом FALSE. Условия, при наличии которых подзапрос с EXISTS возвращает несколько строк (т.е. вычисляется в TRUE), гарантируют, что подзапрос с NOT EXISTS

также вернет несколько строк (т.е. будет вычислен в FALSE). В том случае, когда подзапрос с NOT EXISTS не возвращает строк, подзапрос с EXISTS также не вернет строк. Следовательно, результатом конъюнкции двух подзапросов всегда будет FALSE.

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

Стратегии выполнения NAAJ

В соответствии с семантикой NAAJ строка левой части может соединяться с несколькими строками правой части (соответствовать нескольким строкам). Например, строка левой части, которая содержит неопределенное значение в одном из соединяемых столбцов, будет соответствовать строкам правой части, которые содержат любое значение в соответствующем столбце. В этом случае условие NAAJ вычисляется в UNKNOWN, и, следовательно, строка не возвращается. Пусть, например, левая таблица L из запроса Q25 содержит строку (null, 3, null). Предположим, что правая таблица R содержит две строки: R = {(1, 3, 1), (2, 3, 2)}. Хотя в R отсутствует строка (null, 3, null), нашей строке из L соответствуют обе строки R, поскольку столбец c2 в обеих строках содержит значение 3. Поэтому строка (null, 3, null) не возвращается.

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

После этого выполняются шаги 1 и 2, описанные в подразделе 6.1, для раннего завершения выполнения соединения, возвращающего все строки или не возвращающего ни одной строки. В случае, когда эти шаги не срабатывают, для каждой строки левой части мы ищем соответствующую строку в правой части (если на шаге 3 алгоритма, приведенного в подразделе 6.1, эта строка не исключается). Если на любом из следующих трех шагов, описываемых ниже, соответствие обнаруживается, то строка левой части отбрасывается, как и в обычном антисоединении.

Поиск в отсортированной структуре данных или хеш-таблице для правой части на предмет наличия точного соответствия.

Поиск других возможных соответствий с использованием собранной информации о неопределенных значениях. Например, предположим, что имеются три столбца соединения c1, c2 и с3, но в правой части неопределенные значения имеются только в столбцах c1 и c2. Если поступающая на обработку строка левой части содержит значения (1,2,3), то в структуре доступа к правой части ищутся строки (1,null,3), (null, 2, 3) и (null, null, 3).

Оптимизация ключа из одного столбца:

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

Этот метод позволяет заменять подзапросы оконными функциями[11], сокращая, тем самым, число сканирований таблицы и соединений, что способствует повышению производительности запроса. Некоторые из обсуждаемых методов удаления подзапросов были внедрены в Oracle 9i, некоторые были опубликованы в литературе [13]. В упрощенной форме рассматриваемый метод удаляет поглощаемые (subsumed) агрегированные подзапросы c использованием оконных функций.

Говорят, что внешний блок запроса поглощает (subsume) некоторый подзапрос, если он содержит все таблицы и предикаты, встречающиеся в этом подзапросе. Внешний блок запроса может содержать дополнительные таблицы и предикаты. Очевидно, что свойство поглощения (subsumption) отличается от свойства включения (containment), обсуждавшегося в разд. 2. Кроме того, в этом методе используются свойство соединения без потерь (lossless) и алгебраические агрегаты (например, SUM, MIN, MAX, COUNT, AVG и т.д.).

Q12 является примером запроса с поглощаемым агрегатным подзапросом, для которого применимо преобразование удаления подзапроса. T1 и T2 могут быть базовыми или производными таблицами, а также могут представлять собой соединение нескольких таблиц. Агрегат AGG подзапроса участвует в операции реляционного сравнения (relop) со столбцом T2.z внешнего запроса; корреляция в подзапросе происходит по столбцу T1.y.

Q12

SELECT T1.x FROM T1, T2 WHERE T1.y = T2.y and T2.z relop (SELECT AGG(T2.w) FROM T2 WHERE T2.y = T1.y);

Если предположить, что соединение T1 и T2 является соединением без потерь, в котором T2.y — это внешний ключ, ссылающийся на первичный ключ T1.y, то подзапрос может быть удален путем за счет введения оконной функции, в которой ключом раздела PARTITION BY служит столбец корреляции. Это демонстрируется в запросе Q13.

Q13

SELECT V.x FROM (SELECT T1.x, T2.z, AGG(T2.w) OVER (PARTITION BY T2.y) AS win_agg FROM T1, T2 WHERE T1.y = T2.y) V WHERE V.z relop win_agg;

Чтобы иметь возможность удалить подзапрос с использованием оконной функции, соединение между T1 и T2 не обязательно должно быть соединением без потерь. Однако наличие этого свойства приводит к преобразованиям, позволяющим оптимизатору использовать большее число перестановок соединений.

С использованием метода удаления подзапросов могут быть преобразованы различные варианты запросов вида Q12, в частности, варианты с некоррелированным подзапросом, с наличием дополнительных таблиц и предикатов, с отсутствием агрегатов, с наличием группировки в подзапросе и внешнем запросе. Примеры таких преобразований приводятся в последующих подразделах.

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

Для иллюстрации этого вида оптимизации выполнялись запросы 2, 11, 15 и 17 из тестового набора TPC-H. На рис. 7 представлено время выполнения оптимизированных (qN.opt) и неоптимизированных запросов. Преобразованные запросы Q15 и Q16 (аналоги запросов 2 и 17 из TPC-H) продемонстрировали резкое повышение производительности. Для запроса 2 из TPC-H время выполнения сократилось в 24 раза за счет того, что путем оконного преобразования было устранено нескольких операций сканирования и соединения таблиц.

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

На рис. 8 иллюстрируется эффект от удаления некореллированного подзапроса путем оконного преобразования в запросе 15 из TPC-H как функция от числа месяцев, сканируемых в таблице lineitem. Оптимизационный переход от Q17 (исходный запрос) к Q18 (преобразованный запрос) разъясняется в подразделе 4.2. Как показывает рис. 8, в результате этого преобразования время выполнения сократилось в 8,4 раза.

Рис.8. TPC-H Q15, удаление некореллированного подзапроса

Заметим, что удаление подзапросов с использованием оконных функций оказывает очень эффективное воздействие на время выполнения запросов TPC-H. В среднем производительность запросов q2, q11, q15 и q17 повысилась в 10 раз.

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

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

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

Устранение вложенности нескалярных подзапросов часто приводит к полу- или антисоединениям. В Oracle для выполнения полу-

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

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

Современные реляционные СУБД выполняют сложные

это мощный компонент языка SQL,