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

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

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

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

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

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

---

⁴ Хотя эта техника исторически является производной от Магических Множеств и побочной передачи информации, я нахожу связь с полусоединениями более интуитивной и менее таинственной.

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