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

VPS в России, Европе и США

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

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

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

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

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

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

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

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

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

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

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

1999 г

Обзор методов оптимизации запросов в реляционных системах

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

4.2 Сведение запросов с несколькими блоками к одноблочным запросам

Описанная в этом подразделе техника в некоторых случаях позволяет сжать SQL-запрос с несколькими блоками в одноблочный запрос.

4.2.1 Слияние представлений

Рассмотрим конъюнктивный запрос с SELECT ANY. Если одно или несколько отношений, к которым адресуется запрос, являются представлениями, но каждое из них определено через конъюнктивный запрос, то определения представлений могут быть просто "раскрыты" для получения одноблочного SQL-запроса. Например, если запрос выглядит как Q = Join (R, V), а представление V определено как V = Join (S, T), то запрос Q может быть раскрыт в Join (R, Join (S,T) ), и его можно свободно переупорядочить. Для выполнения такого шага может потребоваться некоторое переименование переменных в определении представления.

К сожалению, это простое раскрытие не работает, когда представления более сложны, чем SPJ-запросы. Если одно или несколько представлений содержат SELECT DISTINCT, преобразования, перемещающие или поднимающие DISTINCT, нужно производить очень осторожно, чтобы корректно сохранить число дубликатов [49]. В более общем случае, когда представление содержит операцию группировки, для раскрытия требуется возможность поднятия операции группировки и затем свободного переупорядочения не только соединений, но и операции группировки для достижения оптимальности. Например, нам задается запрос типа того, который показан на рис. 4(b), и мы стараемся понять, как преобразовать его к форме рис. 4(a), чтобы R1 и R2 можно было свободно переупорядочивать. Хотя в этом случае могут использоваться преобразования из подраздела 4.1.3, это только подчеркивает сложность проблемы [6].

4.2.2 Слияние вложенных подзапросов

Рассмотрим следующий пример запроса с вложенными подзапросами из [13], где Emp# и Dept# - ключи соответствующих отношений:

SELECT Emp.Name
FROM  Emp
WHERE  Emp.Dept# IN
                  SELECT Dept.Dept#  FROM Dept
                   WHERE Dept.Loc = 'Denver'
                    AND Emp.Emp# = Dept.Mgr

Если для ответа на запрос используется семантика последовательного просмотра кортежей, то внутренний запрос вычисляется один раз для каждого кортежа отношения Emp. Очевидная оптимизация применима в том случае, когда внутренний блок запроса не содержит переменных из внешнего блока запроса (отсутствует корреляция). В таких случаях внутренний запрос требуется вычислить только один раз. Если во внутреннем блоке присутствует переменная из внешнего блока, мы говорим, что блоки запроса коррелируют. Например, в приведенном выше запросе Emp.Emp# действует как корреляционная переменная. Ким [35] и в последствие другие исследователи [16, 13, 44] выявили методы устранения вложенности в SQL-запросе с корреляцией и "уплощения" его до запроса с одним блоком. Например, приведенный запрос со вложенностью приводится к

SELECT E.Name
FROM Emp.E, Dept D
WHERE E.Dept# = D.Dept#
AND D.Loc = 'Denver' AND E.Emp# = D.Mgr

Дайал [13] был первым, кто предложил алгебраическую трактовку устранения вложенности. Сложность проблемы зависит от структуры вложенности, т.е. от того, содержит ли вложенный запрос кванторы (например, ALL, EXISTS) и агрегаты. В простейшем случае, примером которого является приведенный выше пример, семантика перебора кортежей может моделироваться конструкцией Semijoin (Emp, Dept, Emp.Dept # = Dept.Dept#)2. Опираясь на этот подход, нетрудно заметить, почему может быть произведено слияние запроса, поскольку:

Semijoin ( Emp, Dept, Emp.Dept# = Dept.Dept# ) =
Project ( Join (Emp, Dept), Emp* )

Здесь предикатом соединения для Join (Emp, Dept) является Emp.Dept# = Dept.Dept#. Второй операнд операции Project3 означает, что должны быть оставлены все столбцы отношения Emp.

Проблема становится гораздо более сложной, когда во вложенном подзапросе присутствуют агрегаты, поскольку теперь для слияния блоков требуется вытягивание наверх агрегации без нарушения семантики запроса со вложенными подзапросами. Эту дополнительную сложность иллюстрирует приводимый ниже пример из [44]:

SELECT Dept.name
FROM Dept
WHERE Dept.num-of-machines >=
( SELECT COUNT (Emp.*) FROM Emp
   WHERE Dept.name = Emp.Dept_name )

Особенно сложно сохранить дубликаты и неопределенные отношения. Чтобы оценить эти тонкости, обратите внимание, что если для конкретного значения Dept.name (скажем, d) отсутствуют кортежи с совпадающим значением Emp.Dept_name, т.е. если значением предиката Dept.name = Emp.Dept_name является false для всех кортежей Emp, то кортеж отношения Dept со значением d войдет в результат запроса. Однако, если мы применим преобразование, использованное в первой части этого подраздела, то для dept d в результате запроса кортеж не появится, поскольку предикат соединения примет значение false. Поэтому при наличии агрегации мы должны сохранять все кортежи внутреннего блока запроса, используя левое внешнее соединение. В частности, приведенный запрос может быть корректно преобразован к виду

SELECT Dept.name 
FROM Dept LEFT OUTER JOIN Emp On (Dept.name = Emp.Dept_name)
GROUP BY Dept.name
HAVING Dept.num-of-machines < COUNT (Emp.*)

Так что для этого класса запросов единственный слитый блок запроса содержит внешние соединения. Если структура вложенности блоков линейна, то это подход применим, и преобразования производят один блок с линейной последовательностью соединений и внешних соединений. Оказывается, что последовательность соединений и внешних соединений такова, что мы можем использовать правило ассоциативности, описанное в подразделе 4.2.1, для вычисления сначала всех соединений, а затем всех внешних соединений из этой последовательности. Другой подход к устранению вложенных подзапросов состоит в преобразованию запроса к такому виду, в котором используются табличные выражения или представления (и конечно, это не одноблочный запрос). Это было направление работы Kim [35], которая впоследствии была усовершенствована в [44].


2 Semijoin (A,B,P) обозначает полусоединение A и B, сохраняющее атрибуты A; P - предикат полусоединения.

3 Я предполагаю, что эта операция не устраняет дубликаты.

Предыдущий раздел - Содержание - Следующий раздел

 

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 Тбит/с!

Новости мира 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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...