Как оптимизировать подзапросы SQL? Это так глубоко написано!

задняя часть SQL

Это 13-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.

подзапросОптимизация (подзапросов) всегда была одной из трудностей в оптимизации SQL-запросов. Базовая реализация коррелированных подзапросов похожа на Nested-Loop, но эта реализация часто невыносимо неэффективна. Когда объем данных немного больше, его необходимо обработать в оптимизаторе.разъединение(Decoorelation или Unnesting), перепишите его как более эффективный оператор, такой как Semi-Join.

Предшественники подытожили полный набор методологии, которая теоретически может диссоциировать любой запрос. В этой статье объединены несколько классических работ по SQL Server и HyPer, чтобы объяснить эту теоретическую систему отделения от мелкого к более глубокому. Используемые ими методы аналогичны с небольшими отличиями, а основные идеи выяснены.

Введение в подзапросы

Подзапрос представляет собой синтаксис, определенный в стандарте SQL, который может появиться практически в любом месте SQL, включая выбор, от, где и т. Д.

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

SELECT c_count, count(*) AS custdist
FROM (
         SELECT c_custkey, count(o_orderkey) AS c_count
         FROM CUSTOMER
                  LEFT OUTER JOIN ORDERS ON c_custkey = o_custkey
             AND o_comment NOT LIKE '%pending%deposits%'
         GROUP BY c_custkey
     ) c_orders
GROUP BY c_count
ORDER BY custdist DESC, c_count DESC;

Независимая колонка подпроса за пределами объема, если не указано иное, следующие подзапросы относятся к связанным подзапросам.

Коррелированные подзапросы уникальны тем, что сами по себе неполны:Его закрытие содержит некоторые параметры, предоставленные внешним запросом. Очевидно, что запрос может быть выполнен только в том случае, если известны эти параметры, поэтому мы не можем рассматривать его как некоррелированный подзапрос.

По формируемым данным подзапросы можно разделить на следующие типы:

Скаляр (скалярнозначный)Подзапрос: выведите результирующую таблицу только с одной строкой и одним столбцом, и это скалярное значение будет ее результатом. Если результат пустой (0 строк), выведите NULL. Обратите внимание, однако, что более 1 строки результатов не допускается и будет генерировать исключение во время выполнения.

标量子查询可以出现在任意包含标量的地方，例如 SELECT、WHERE 等子句里。 Ниже приведен пример:

SELECT c_custkey
FROM CUSTOMER
WHERE 1000000 < (
    SELECT SUM(o_totalprice)
    FROM ORDERS
    WHERE o_custkey = c_custkey
)

Запрос 1: скалярный подзапрос, появляющийся в предложении WHERE, со связанными параметрами, отмеченными красным

SELECT o_orderkey, (
    SELECT c_name
    FROM CUSTOMER
    WHERE c_custkey = o_custkey
) AS c_name FROM ORDERS

Запрос 2: скалярный подзапрос, появляющийся в предложении SELECT

Экзистенциальный тестПодзапрос: подзапрос, который конкретно ссылается на EXISTS и возвращает логическое значение. Если он появляется в WHERE, это знакомое полусоединение. Конечно, он может появиться везде, где можно разместить логическое значение.

SELECT c_custkey
FROM CUSTOMER
WHERE c_nationkey = 86 AND EXISTS(
        SELECT * FROM ORDERS
        WHERE o_custkey = c_custkey
    )

Запрос 3: пример полусоединения

Количественное сравнениеПодзапрос: особенно запрос IN, SOME, ANY возвращает логическое значение, часто используемые формы:x = SOME(Q)(эквивалентноx IN Q)или X <> ALL(Q)(эквивалентноx NOT IN Q). Точно так же он может появиться везде, где можно разместить логическое значение.

SELECT c_name
FROM CUSTOMER
WHERE c_nationkey <> ALL (SELECT s_nationkey FROM SUPPLIER)

Запрос 4: неассоциативный подзапрос для сравнения наборов

первоначальный план выполнения

Мы, например, запрос 1, интуитивно чувствуем, почему переход к связанному подзапросу ассоциации очень необходим.

Ниже приведен исходный план запроса (дерево отношений) запроса 1 без разрыва ассоциации. В отличии от других планов запросов, мы специально рисуем дерево выражений (Expression Tree), хорошо видно, что подзапрос на самом деле висит под условным выражением Filter.

​

При фактическом выполнении исполнитель плана запроса (исполнитель) вызывает исполнителя выражения (оценщика), когда он выполняется для фильтра; поскольку это условное выражение содержит скалярный подзапрос, оценщик вызовет исполнителя для вычисления результата скалярного подзапроса. -запрос .

Этот чередующийся вызов Executor-Evaluator-Executor очень неэффективен! Учитывая, что через Фильтр могут проходить миллионы строк данных, если для каждой строки данных выполняется подзапрос, общее время выполнения запроса явно неприемлемо.

Применить оператор

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

Для этого перед началом диссоциации введем оператор Apply:

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

Значение Apply определяется выражением набора в правой половине рисунка ниже: Для каждой части данных rr во внешнем отношении RR вычислить внутреннее отношение E(r)E(r) и вывести результат их соединения ( Джойн) r⊗E (r)r⊗E(r). Результатом Apply является объединение всех этих результатов (объединение, упомянутое в этой статье, относится к объединению в соответствии с семантикой Bag, то есть UNION ALL).

​

Apply — это имя SQL Server, которое в статье HyPer называется Correlated Join. Они полностью эквивалентны. Учитывая, что статья о SQL Server была опубликована ранее и имеет более широкое значение, в этой статье используется ее название.

Согласно другому режиму подключения (⊗⊗), есть 4 формы применения:

  • Cross ApplyA×A×: это самая основная форма поведения, которое мы только что описали;
  • Left Outer ApplyALOJALOJ: Создать r∘{NULLs}r∘{NULLs}, даже если E(r)E(r) пусто.
  • Semi ApplyA∃A∃: вернуть rr, если E(r)E(r) не пусто, иначе отбросить;
  • Anti-Semi ApplyA∄A∄: если E(r)E(r) пусто, вернуть rr, иначе отбросить;

Давайте перепишем предыдущий пример с только что определенным нами оператором Apply: извлеките подзапрос из Expression. Результат выглядит следующим образом:

​

В приведенном выше примере мы можем быть уверены, что Scalar AGG подзапросесть и толькоСтрока результатов, поэтому ее можно напрямую преобразовать в Apply. Но в некоторых случаях нельзя быть уверенным, что подзапрос вернет 0 или 1 строку результатов (например, представьте себе запрос 2, если c_custkey не уникален), чтобы обеспечить семантику SQL, добавьте оператор Max1RowMax1Row справа от Apply:

Max1Row(E)=⎧⎩⎨⎪⎪Null,E,ошибка,если |E|=0 если |Y|=1иначе Max1 Row(E)={Null,if |E|=0E,если |E|=1error ,в противном случае

Теоретически мыМожет преобразовывать все подзапросы в операторы Apply.Общий метод выглядит следующим образом:

  1. Если подзапрос появится в экспрессии оператора, мы извлекаем подзапрос под оператором (оставляя переменную результата подзапроса) для формирования оператора Alojaloj. Если существует более одного подзапроса, будет производиться несколько аложалов. Добавьте оператор Max1Rowmax1row при необходимости.
  2. Затем примените некоторые другие правила, чтобы преобразовать ALOJALOJ в A×A×, A∃A∃, A∄A∄. Например, результат подзапроса XX в приведенном выше примере используется в качестве условия фильтра Filter, значения NULL будут отфильтрованы, поэтому его можно безопасно преобразовать в A×A×.

В следующем примере условное выражение фильтра содержит два подзапроса, Q1Q1 и Q2Q2. После преобразования соответственно генерируются соответствующие операторы Apply. Среди них Q2Q2 не может определить, что будет сгенерирована только одна запись, поэтому также добавляется оператор Max1RowMax1Row.

​

Основные правила ликвидации

Первый набор правил — это самые основные правила.Значок ⊗⊗ в уравнении указывает на то, что он не ограничивает тип подключения, который может быть любым из {×,LOJ,∃,∄}{×,LOJ,∃,∄ }.

​

Эти два правила очень очевидны, переведены большими белыми словами: Если правая часть Apply не содержит параметров слева, то это эквивалентно прямому соединению.

Вот пример применения правила (2) к запросу 3:

​

Отключение проекта и фильтра

Второй набор правил описывает, как работать с Project и Filter в подзапросах, идею можно описать одним предложением:Нажмите Apply как можно больше и поднимите операторы ниже Apply..

​​

Обратите внимание, что эти правила касаются только случая перекрестного применения. Остальные 3 варианта Apply теоретически могут быть преобразованы в Cross Apply, но пока нам нужно знать только этот факт.

Вы спросите: обычно мы максимально опускаем Filter и Project, почему здесь наоборот? Суть в следующем: Filter и Project изначально содержали выражения со связанными переменными, но после того, как они были упомянуты выше, Apply,Связанные переменные становятся обычными переменными!Это именно то, что мы хотим.

Мы увидим огромные преимущества этого позже:Применить при нажатии вниз, первый набор правил может быть применен непосредственно к Применить стал Присоединиться, что завершает оптимизационный процесс разъединения подзапросов.

Ниже приведен пример применения правила (3) к запросу 2. После применения правила (1) процесс диссоциации завершается.

​

Диссоциация агрегата

Третий набор правил описывает, как обрабатывать агрегаты в подзапросах (т. е. группировать по). Как и в предыдущей группе, наша руководящая идеология остается:Нажмите Apply как можно больше и поднимите операторы ниже Apply..

Следующие уравнения, GA, FGA, F представляют собой полимеризацию с группировкой Group By (Group Agg), где AA представляет пакет столбца, столбец FF представляет агрегатные функции; G1FGF1 представляет собой пакет с полимеризуемым (Scalar Agg).

​

Этот набор правил не такой простой и понятный, как раньше, давайте посмотрим на пример, чтобы прочувствовать его. Вот результат применения правила (9) к запросу 1:

​

Правило (9) превращает ScalarAgg в GroupAgg, нажимая кнопку Apply, гдеСтолбец группировки — это клавиша R, вот первичный ключ c_custkey CUSTOMER.

Если у R нет первичного или уникального ключа, мы теоретически можем сгенерировать его во время сканирования.

Почему он эквивалентен до и после преобразования? Перед преобразованием мы делаем вычисление агрегации ScalarAgg для каждой строки R, а затем объединяем результаты агрегирования; после преобразования мы сначала подготавливаем все данные к агрегированию (это называется augment), а затем используем GroupAgg делает все агрегаты сразу.

Это также объясняет, почему мы используем ALOJALOJ вместо исходного A×A×: в исходном ScalarAgg, даже если ввод является пустым набором, он выведет NULL. Если мы используем ALOJALOJ здесь, мы получаем такое же поведение (*); наоборот, если мы используем A×A×, возникает проблема — клиенты без соответствующих ЗАКАЗОВ исчезают в результате!

Правило (8) касается GroupAgg, и причина та же, за исключением того, что исходный столбец группировки должен быть сохранен.

Подробности в преобразовании ScalarAgg*

Внимательные читатели могут заметить, что агрегатная функция, сгенерированная в правой части правила (9), представляет собой F'F' с одинарной кавычкой, что означает, что она может несколько отличаться от исходной агрегатной функции FF. Как это будет по-другому? Эта тема более глубокая, и учащиеся, не заинтересованные в ней, могут ее пропустить.

首先我们思考下，GroupAgg 以及 ALOJALOJ 的行为真的和变换前一模一样吗？ вообще-то нет.举个反例：

SELECT c_custkey, (
    SELECT COUNT(*)
    FROM ORDERS
    WHERE o_custkey = c_custkey
) AS count_orders
FROM CUSTOMER

Представьте: у клиента Эрика нет заказов, тогда этот запрос должен вернуть['Eric', 0]ряд. Однако, когда мы применяем правило (9) для преобразования, мы получаем['Eric', 1]Значение , результат неверный!

Почему это так? После преобразования мы сначала подготавливаем промежуточные данные (аугмент) с помощью LeftOuterJoin, а затем используем GroupAgg для агрегации. LeftOuterJoin генерирует['Eric', NULL, NULL, ...]Строка ; в следующем GroupAgg, агрегатная функцияCOUNT(*)Предположим, что группа Эрика имеет 1 строку данных, поэтому выведите['Eric', 1].

Вот более сложный пример с аналогичной проблемой:

SELECT c_custkey
FROM CUSTOMER
WHERE 200000 < (
    SELECT MAX(IF_NULL(o_totalprice, 42)) -- o_totalprice may be NULL
    FROM ORDERS
    WHERE o_custkey = c_custkey
)

Таким образом, корень проблемы таков: F(∅)≠F({NULL})F(∅)≠F({NULL}), такая агрегатная функция FF имеет эту проблему.

Преобразованный GroupAgg не может отличить, являются ли данные NULL, которые он видит, сгенерированы OuterJoin или существуют в исходном, иногда эти два случая дают разные результаты в ScalarAgg перед преобразованием.

К счастью, агрегатные функции F(col)F(col), определенные в стандарте SQL, все в порядке - все они удовлетворяют F(∅)=F({NULL})F(∅)=F({NULL}) , мы только нужно немного преобразить ФФ, чтобы решить эту проблему.

  • Например, один, установитеCOUNT(*)Замените его на Count ненулевого столбца (например, первичного ключа), например:COUNT(o_orderkey);
  • Например 2, нам нужно положитьMIN(IF_NULL(o_totalprice, 42))Сделайте это в два шага: определите промежуточные переменныеX, сначала вычислите с помощью ProjectX = IF_NULL(o_totalprice, 42), а затем на агрегатную функциюMIN(X)Просто сделайте диссоциацию.

Отключение операций над множествами

Последний набор правил оптимизации используется для обработки с помощью Union (соответствуетUNION ALL), вычесть (соответствуетEXCEPT ALL) и подзапрос оператора Inner Join. Опять же, наша руководящая идеология:Нажмите Apply как можно больше и поднимите операторы ниже Apply..

В следующем уравнении ×× представляет перекрестное соединение, а ⋈R.key⋈R.key представляет естественное соединение в соответствии с ключом RR: r∘e1∘e2r∘e1∘e2 . Как и прежде, мы предполагаем, что RR имеет первичный ключ или уникальный ключ, если нет, мы можем добавить его во время сканирования.

​​

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

На самом деле, этот набор правил редко пригодится. Как упоминалось в [2], сложно даже написать осмысленный подзапрос с Union All в рамках схемы TPC-H.

разное

Есть несколько моментов, которые я считаю важными, они перечислены ниже в форме часто задаваемых вопросов.

► Можно ли разъединить любой коррелированный подзапрос?

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

Метод доказательства упоминается в [1], [3]. Взяв в качестве примера [1], идея примерно такова:

  1. Для любого дерева отношения запроса сначала извлеките связанный подзапрос из выражения и используйте оператор Apply для его представления;
  2. Шаг за шагом удаляйте неосновные реляционные операторы.Во-первых, удаляйте объединение и вычитание посредством эквивалентного преобразования;
  3. Дальнейшее сокращение набора операторов, удаление OuterJoin, ALOJALOJ, A∃A∃, A∄A∄;
  4. Наконец, все A×A× удаляются, а оставшееся дерево отношений содержит только некоторые базовые операторы отношения, то есть диссоциация завершается.

С другой стороны, большинство подзапросов, используемых пользователями в реальном мире, относительно просты, и правила, описанные в этой статье, могут охватывать 99% сценариев. Хотя теоретически можно обработать любой подзапрос, на практике ни одна известная СУБД не реализует все эти правила преобразования.

► Каковы сходства и различия между практиками HyPer и SQL Server?

Теория Hyper охватывает больше связанной сцены. Например, различные операторы JOIN и другие операторы [3] дают соответствующие эквивалентные правила преобразования (в качестве примера на следующем рисунке показано преобразование внешнего соединения). В [1] только доказывается, что эти ситуации могут быть защищены защищаемой ситуацией (фактически подразумевается, что она должна не обрабатываться).

​

Еще одна деталь в том, что в HyPer тоже есть такое правило:

​

Среди них D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1), что указывает на результат Distinct Project для T1T1 (т.н.Magic Set). Довольно неясно смотреть на уравнение напрямую, но его легко понять, взглянув на следующий пример:

​

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

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

► Должны ли эти правила преобразования, упомянутые в этой статье, использоваться в RBO или CBO? Другими словами, обязательно ли план выполнения после диссоциации лучше, чем до диссоциации?

Ответ: не обязательно.

Интуитивно понятно, что если количество данных в левой части «Применить» относительно невелико (например, есть только 1 данные), лучше напрямую ввести их в расчеты в правой части «Применить». В другом случае справа есть подходящий индекс, и в этом случае стоимость многократного применения не является неприемлемой.

Так что правильнее заложить эти правила в оптимизатор СВО, а оптимизатор подбирает оптимальный план по смете. Даже, в некоторых случаях, мы будем применять эти уравнения справа налево, делая «дополнительные соотношения».

Это то же самое, что и использование HashJoin или NestedLoopJoin. По сути, NestedLoopJoin — это частный случай Apply. Нередко NestedLoopJoin оказывается более эффективным, чем HashJoin, если существует подходящий индекс.

Категории