Использование техники полусоединений для оптимизации запросов с несколькими блоками
В предыдущем разделе я представил примеры того, как запросы, содержащие несколько блоков, могут быть свернуты к одному блоку. В этом разделе я обсуждаю дополнительный подход. Цель этого подхода состоит в использовании селективности предикатов за пределами одного блока. На концептуальном уровне подход напоминает идею использования полусоединения для распространения из узла A в удаленный узел B информации о подходящих значениях A, чтобы из B в A не посылались ненужные кортежи. В контексте запросов с несколькими блоками A и B находятся в разных блоках запроса, но являются частями одного и того же запроса, и поэтому не стоит вопрос о стоимости передачи данных. Информация, "получаемая от A", используется для сокращения объема вычислений в B, а также для гарантии того, что результаты, производимые в B, являются подходящими для A. Это техника требует введения новых табличных выражений и представлений. Например, рассмотрим следующий запрос из [56]:
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
Эта техника может быть использована в запросах с несколькими блоками, содержащими представления (включая рекурсивные представления) и вложенные подзапросы [42, 43, 56, 57]. В каждом случае целью является избежание избыточных вычислений в представлениях или вложенных подзапросах. Важно также осознавать соотношение стоимостей вычисления представлений (представления PartialResult в приведенном примере) и использования таких представлений для снижения стоимости вычислений.
Формальная связь описанных преобразований с полусоединениями была недавно представлена в [56] и может служить основой для интеграции этой стратегии с основанными на оценках оптимизаторами. Заметим, что вырожденное применение этой техники состоит в передаче между блоками предикатов, а не результатов представлений. Этот упрощенный метод используется в распределенных и неоднородных базах данных и получил обобщение в [36].
4 Хотя эта техника исторически является производной от Магических Множеств и побочной передачи информации, я нахожу связь с полусоединениями более интуитивной и менее таинственной.
- -
