Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

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

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

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

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

2010 г.

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

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

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

Оригинал: Cost-Based Query Transformation in Oracle / Rafi Ahmed, Allison Lee, Andrew Witkowski, Dinesh Das, Hong Su, Mohamed Zait, Thierry Cruanes // Proceedings of the 32nd international conference on Very large data base, 2006, pp. 1026 — 1036

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

2. Преобразования в Oracle

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

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

2.1. Эвристические преобразования

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

Минимизация числа блоков запроса путем слияния их с другими блоками запроса снимает ограничения с множества перестановок операций соединения, которые могут быть сгенерированы, позволяя, таким образом, переупорядочивать большее число таблиц [16]. Традиционный реляционный оптимизатор генерирует только "левоглубинное" (left-deep) (линейное) дерево выполнения; таким образом, можно утверждать, что он никогда не сможет сгенерировать план, эквивалентный плану с "кустистым" (bushy) деревом, генерируемым в случае отсутствия преобразований. Несмотря на это, считается, что значительную часть деревьев соединений с низкой стоимостью обработки можно найти в пространстве левоглубинных деревьев [5].

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

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

Устранение вложенности подзапросов (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.

2.1.2. Устранение соединений

Метод устранения соединения (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, если это допустимо.

2.1.3. Перемещение предикатов фильтрации

При перемещении предикатов фильтрации (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] затрагиваемого диапазона оконной функции.

2.1.4. Упрощение группировки

Упрощение группировки (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 в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные 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 This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...