Logo Host-telecom.com — профессиональный хостинг в Европе! Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Мощные сервера

VPS с гибкой конфигурацией: за 1€

Мощные выделенные сервера: от 25€

Собственный Дата-Центр
Поддержка 24/7

хостинг Украина Виртуальный хостинг для сайта от $4,87

Регистрация домена от $2 в год

Партнерская программа – $20 за клиента

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

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

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

4. Удаление подзапросов 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, в частности, варианты с некоррелированным подзапросом, с наличием дополнительных таблиц и предикатов, с отсутствием агрегатов, с наличием группировки в подзапросе и внешнем запросе. Примеры таких преобразований приводятся в последующих подразделах.

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

Рассмотрим запрос 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';
4.2. Некоррелированный поглощаемый подзапрос

Рассмотрим запрос 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 может быть выполнен эффективным и масштабируемым образом.

4.3. Поглощаемый подзапрос в разделе 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;

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

Чтобы можно было удалить подзапроса с использованием оконных функций, этот подзапрос не обязательно должен содержать агрегатные функции и возвращать множество из одной строки. Рассмотрим запрос 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".

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

Распараллеливание оконных функций в 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.

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

ATLEX Выделенные серверы: в Европе / в России.

Виртуальные серверы: в Европе / в России.

Партнерская программа

Ваш сайт в 8 раз быстрее конкурентов. Хостинг от $2.95

VPS: SSD, KVM, бесплатные бэкапы и администрирование

Все необходимое для вашего сайта и лучшая техподдержка 24/7

хостинг сайтов ГиперХост — хостинг сайтов который Вы искали.

Виртуальный хостинг, Аренда VPS серверов, рация доменных имен, SSL сертификаты

💰 Самые низкие цены на домены

🔒 Отличный хостинг на SSD c бесплатными SSL

💻 Огромнейший выбор dedicated выделенных серверов

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...