Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

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

В расширяемых системах поведение компонента перебора соединений может адаптироваться к конкретному запросу, ограничивая "кустистость" деревьев соединений или разрешая/запрещая вычисление декартовых произведений . Однако довольно сложно заранее определить воздействие такой настройки на качество и стоимость поиска.

2.1.2 Внешние и обычные соединения

Одностороннее внешнее соединение - это несимметричная операция языка SQL, которая сохраняет все кортежи одного из отношений-операндов. Симметричное внешнее соединение сохраняет кортежи обоих отношений-операндов. Например, (R LOJ S), где LOJ обозначает левое внешнее соединение R и S, сохраняет все кортежи R. В результирующем отношении этой операции, кроме кортежей, получаемых при естественном соединении, содержатся все кортежи R, которые не удалось соединить с S (заполненные неопределенными значениями для всех атрибутов S). В отличие от естественных соединений последовательность внешних и обычных соединений нельзя произвольно изменять. Однако если имеются предикат обычного соединения между R и S и предикат внешнего соединения между S и T, то действует следующее тождество:
Join (R, S LOJ T) = Join (R,S) LOJ T

Если продолжать применять это правило ассоциативности, мы получим эквивалентное выражение, в котором вычисление "блока обычных соединений" предшествует "блоку внешних соединений". Впоследствии обычные соединения могут произвольно переупорядочиваться. Как и другие преобразования, это тождество следует применять на основе оценок. Тождества, приведенные в [1], определяют класс запросов, в которых можно изменять порядок обычных и внешних соединений.

2.1.3 Группировки и соединения

При традиционном выполнении SPJ-запроса с группировкой вычисление SPJ-компонента запроса предшествует группировке. Набор преобразований, описываемых в этом подразделе, делает возможным выполнять операцию группировки до соединения. Эти преобразования применимы к запросам с SELECT DISTINCT, так что это специальный случай группировки. Выполнение операции GROUP BY потенциально может привести к значительному сокращению числа кортежей, поскольку для каждого раздела отношения, выделяемого операцией группировки, она генерирует только один кортеж. Поэтому в некоторых случаях при выполнении сначала группировки стоимость соединения может быть существенно уменьшена. Более того, при наличии подходящего индекса операция группирования может быть выполнена недорого. Для случая, когда операцию группирования можно выполнить после соединения, существуют двойники таких преобразований.

В этом подразделе кратко обсудим конкретные случаи, в которых применимы преобразования, вызывающие выполнение группировки до соединения. Рассмотрим дерево запроса на рис. 4(a). Пусть R1 и R2 соединяются по внешнему ключу, столбцы агрегирования G все взяты из R1, а в состав набора столбцов группировки входит внешний ключ R1. Для такого запроса рассмотрим соответствующее дерево операций на рис. 4(b), где G1 = G. В этом дереве завершающее соединение может только сократить набор потенциальных разделов R1, созданных G1, но не может повлиять на разделы и на агрегаты, вычисляемые G1 на этих разделах, поскольку каждый кортеж R1 соединяется не более чем с одним кортежем R2. Следовательно, можно переместить группировку вниз, как показано на рис. 4(b), и сохранить эквивалентность для произвольных агрегатных функций без побочного эффекта. На рис. 4(c) иллюстрируется пример, где преобразование вводит группировку, и представляется класс полезных примеров, где операция группировки выполняется поэтапно. Например, предположим, что в запросе, дерево операций которого показано на рис. 4(a), агрегатные функции вычисляются только на столбцах R1. В этих случаях введенный оператор группировки G1 разделяет отношение по столбцам R1 и вычисляет агрегатные функции на этих разделах. Однако на рис. 4(a) могут потребоваться истинные разделы, чтобы объединить несколько разделов, образованных G1, в один раздел (отображение много-к-одному). Это обеспечивает оператор группирования G. Такое поэтапное вычисление может быть полезным для уменьшения стоимости соединения по причине сокращения объема данных операцией группировки G1. Для возможности такой поэтапной агрегации требуется, чтобы агрегатные функции обладали тем свойством, что Agg (S U S") можно вычислить на основе AGG (S) и AGG(S"). Например, чтобы вычислить общий объем продаж для всех продуктов каждого отделения, мы можем использовать преобразование с рис. 4(c) для выполнения ранней агрегации и получения общего объема продаж для каждого продукта. Затем нам потребуется еще одна группировка, чтобы сложить объемы продаж всех продуктов, относящихся к одному отделению.

Рис. 4. Группировка и соединение.

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

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

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

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

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

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

Рассмотрим следующий пример запроса с вложенными подзапросами , где 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# действует как корреляционная переменная. Ким [2] и впоследствии другие исследователи выявили методы устранения вложенности в SQL-запросе с корреляцией и "уплощения" его до запроса с одним блоком. Например, приведенный запрос со вложенностью приводится к

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

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

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

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

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

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, для вычисления сначала всех соединений, а затем всех внешних соединений из этой последовательности.

2.3 Использование техники полусоединений для оптимизации запросов с несколькими блоками

В предыдущем разделе были представлены примеры того, как запросы, содержащие несколько блоков, могут быть свернуты к одному блоку. В этом разделе обсудим дополнительный подход. Цель этого подхода состоит в использовании селективности предикатов за пределами одного блока. На концептуальном уровне подход напоминает идею использования полусоединения для распространения из узла A в удаленный узел B информации о подходящих значениях A, чтобы из B в A не посылались ненужные кортежи. В контексте запросов с несколькими блоками A и B находятся в разных блоках запроса, но являются частями одного и того же запроса, и поэтому не стоит вопрос о стоимости передачи данных. Информация, "получаемая от A", используется для сокращения объема вычислений в B, а также для гарантии того, что результаты, производимые в B, являются подходящими для A.

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

CREATE VIEW depAvgSal AS (
SELECT E.did, Avg (E.Sal) AS avgsal
FROM EMP E
GROUP BY E.did )
SELECT E.eid, E.sal
FROM EMP E, Dept D, DepAvgSal V
WHERE E.did = D.did AND E.did = V.did AND E.age < 30
AND D.budget > 100k AND E.sal > V.avgsal

Метод распознает, что мы можем создать множество подходящих E.did, выполняя соединение E и D в приведенном выше запросе и выполняя проекцию результата на E.did (с устранением дубликатов). Это множество можно передать представлению DepAvgSal для ограничения его вычисления. Это достигается с помощью следующих трех соединений:

CREATE VIEW PartialResult AS
( SELECT E.eid, E.sal, E.did
FROM Emp E, Dept D
WHERE E.did = D.did AND E.age < 30 AND D.budget > 100k)
CREATE VIEW Filter AS
( SELECT DISTINCT P.did FROM PartialResult P )
CREATE VIEW LimitedAvgSal AS
( SELECT E.did, Avg (E.Sal) AS avgsal
FROM Emp E, Filter F
WHERE E.did = F.did GROUP BY E.did )

В приводимом ниже переформулированном запросе эти представления используются для ограничения вычислений.

SELECT P.eid, P.sal
FROM PartialResult P, LimitedDepAvgSal V
WHERE P.did = V.did AND P.sal > V.avgsal

Эта техника может быть использована в запросах с несколькими блоками, содержащими представления (включая рекурсивные представления) и вложенные подзапросы. В каждом случае целью является избежание избыточных вычислений в представлениях или вложенных подзапросах. Важно также осознавать соотношение стоимостей вычисления представлений (представления PartialResult в приведенном примере) и использования таких представлений для снижения стоимости вычислений.

3. Статистики и оценка стоимости

Для заданного запроса имеется много логических эквивалентных выражений и для каждого из выражений имеется много способов его реализации с помощью операций. Даже если игнорировать вычислительную сложность перебора пространства возможностей, остается вопрос принятия решения о том, какое дерево операций потребляет меньше всего ресурсов. В число ресурсов могут входить время центрального процессора, стоимость ввода/вывода, пропускная способность коммуникаций или комбинация всего этого. Поэтому фундаментальную значимость имеет способность точно и эффективно оценивать стоимость данного дерева операций (полного или частичного). Оценка стоимости должна быть точной, потому что оптимизация хороша ровно настолько, насколько хороша оценка стоимости. Оценка стоимости должна быть эффективной, поскольку она входит в самый внутренний цикл оптимизации запросов и много раз вызывается. Основы подхода оценок берут свое начало от System R.
1. Собирать статистические сводки по поводу хранимых данных.
2. Для данной операции на основе статистической информации о входных потоках операции данных определять:
a) статистическую информацию о выходном потоке данных;
b) оценочную стоимость выполнения операции.

Характеристики

Список файлов домашнего задания