Фэй Хань

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

Подзапрос — это запрос внутри другого SQL-запроса. Общий подзапрос встроен в предложение FROM, например:

SELECT ID FROM (SELECT * FROM SRC) AS T

Подвыражения в предложениях FROM могут очень хорошо обрабатываться обычными оптимизаторами SQL. Но когда дело доходит до подзапросов в предложении WHERE или списках SELECT, оптимизация становится очень сложной, потому что подзапросы могут быть где угодно в выражении, например. в пунктах CASE...WHEN....

Подзапросы, не вошедшие в предложение FROM, классифицируются как «коррелированные подзапросы» и «некоррелированные подзапросы». Коррелированный подзапрос относится к подзапросу со столбцами из внешних ссылок, например:

SELECT * FROM SRC WHERE
EXISTS(SELECT * FROM TMP WHERE TMP.id = SRC.id)

Некоррелированные подзапросы могут быть предварительно обработаны на этапе планирования и переписаны в константу. Поэтому эта статья в основном посвящена оптимизации коррелированных подзапросов.

Вообще говоря, существуют следующие три типа подзапросов:

  • Скалярный подзапрос, например (SELECT...) + (SELECT...)
  • Количественное сравнение, например T.a = ANY(SELECT...)
  • Экзистенциальный тест, такой как NOT EXISTS(SELECT...), T.a IN (SELECT...)

Для простых подзапросов, таких как Existential Test, обычной практикой является переписывание их в SemiJoin. Но в литературе почти не исследуется общий алгоритм и какие подзапросы нужны для устранения корреляции. Для тех подзапросов, корреляцию которых нельзя удалить, обычной практикой в ​​базах данных является выполнение во вложенном цикле, что называется коррелированным выполнением.

TiDB наследует стратегию подзапросов в SQL Server [1]. Он вводит оператор Apply для использования алгебраического представления для подзапросов, что называется нормализацией, а затем удаляет корреляцию на основе информации о стоимости.

Оператор Apply

Причина, по которой подзапросы трудно оптимизировать, заключается в том, что подзапрос нельзя представить в виде логического оператора, такого как Projection или Join, что затрудняет поиск общего алгоритма преобразования подзапроса. Итак, прежде всего нужно ввести логическую операцию, которая может представлять подзапросы: оператор Apply, который также называется d-Join[2]. Семантика оператора Apply такова:

где E представляет собой параметризованный подзапрос. При каждом выполнении оператор Apply получает запись r из отношения R и отправляет r в E в качестве параметра для ⊗ операции r и E(r). ⊗ различается в зависимости от типа запроса, обычно это SemiJoin ∃.

Для следующего оператора SQL:

SELECT * FROM SRC WHERE
EXISTS(SELECT * FROM TMP WHERE TMP.id = SRC.id)

представление оператора Apply выглядит следующим образом:

Поскольку оператор над Apply равен Selection, формально это:

Для подзапроса EXISTS в списке SELECT и данных, которые не могут пройти через уравнение SRC.id=TMP.id, вывод должен быть ложным. Поэтому следует использовать OuterJoin:

Проекция C предназначена для преобразования NULL в false. Но более распространена следующая практика: если вывод оператора Apply напрямую используется предикатом запроса, он преобразуется в SemiJoin.

Удаление корреляции

Введение оператора Apply позволяет нам удалить корреляцию подзапросов. Два примера в предыдущем разделе можно преобразовать в:

и

Другие правила удаления корреляции можно формально представить как:

На основании приведенных выше правил корреляция между всеми подзапросами SQL может быть удалена (3). Но правила (5), (6) и (7) используются редко, потому что стоимость запроса увеличивается в результате правил об общем выражении. В качестве примера возьмем следующую инструкцию SQL:

SELECT C_CUSTKEY
FROM CUSTOMER WHERE 1000000 <
(SELECT SUM(O_TOTALPRICE)
FROM ORDER WHERE O_CUSTKEY = C_CUSTKEY)

Два «CUSTKEY» являются первичными ключами. Когда оператор преобразуется в Apply, он представляется как:

Из-за первичных ключей по правилу (9) его можно преобразовать в следующее:

Примечание:

  1. Если в ORDERS нет первичных ключей, следует добавить оператор ππ для выделения уникального ключа.
  2. Обратите внимание на разницу между правилом (8) и правилом (9). Для функции агрегации G1FGF1 без столбца агрегации, когда входное значение равно NULL, выходным значением должно быть значение по умолчанию функции агрегации F. Следовательно, следует использовать LeftOuterJoin, и запись NULL должна быть выходной, когда правая таблица имеет значение NULL. В этом случае, исходя из правила (2), Apply можно полностью удалить. Оператор может быть преобразован в оператор SQL с соединением:

Кроме того, на основе упрощения OuterJoin оператор может быть упрощен до:

Теоретически вышеперечисленные 9 правил решили проблему удаления корреляции. Но является ли удаление корреляции лучшим решением для всех сценариев? Ответ - нет. Если результаты оператора SQL малы, а подзапрос может использовать индекс, лучшим решением будет использование коррелированного выполнения. Оператор Apply можно оптимизировать до Segment Apply, который предназначен для сортировки данных внешней таблицы в соответствии с коррелированным ключом. В этом случае ключи, находящиеся в одной группе, не нужно будет выполнять несколько раз. Конечно, это сильно связано с количеством уникальных значений (NDV) коррелированных ключей во внешней таблице. Следовательно, решение об использовании удаления корреляции также зависит от статистики. Когда дело доходит до этого момента, обычный оптимизатор уже не применим. Только оптимизатор со стилем Volcano или Cascade может учитывать как правила логической эквивалентности, так и оптимизацию на основе затрат. Таким образом, идеальное решение для подзапроса зависит от отличной структуры оптимизатора.

Агрегация и подзапрос

В предыдущем разделе окончательный оператор не был полностью оптимизирован. Функцию агрегирования выше OuterJoin и InnerJoin можно сдвинуть вниз[4]. Если OutJoin не может быть упрощено, формальное представление правила выталкивания вниз:

πC выше Join предназначен для преобразования NULL в значение по умолчанию, когда функция агрегирования принимает пустые значения. Стоит отметить, что приведенная выше формула может применяться только при выполнении следующих трех условий:

  • Все столбцы, связанные с R в предикате p, находятся в столбце Group by.
  • Ключ отношения S находится в столбце Group by.
  • Агрегации в функции GG используют только столбцы в R.

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

использованная литература

[1] К. Галиндо-Легариа и М. Джоши. «Ортогональная оптимизация подзапросов и агрегация». В: Proc. конференции ACM SIGMOD. по управлению данными (2001 г.), стр. 571–581.

[2] Д. Майер, К. Ван и Л. Шапиро. Алгебраическое разделение вложенных объектных запросов. Тех. представитель КСЭ-99–013. Орегонский институт последипломного образования, 1999 г.

[3] К. А. Галиндо-Легариа. Параметризованные запросы и вложенные эквиваленты. Тех. представитель МСР-ТР-2000–31. Майкрософт, 2001.

[4] В. Ян и П.-А. Ларсон. «Нетерпеливое агрегирование и ленивое агрегирование». В: Proc. Междунар. конф. по очень большим базам данных (VLDB) (1995), стр. 345–357.

Первоначально опубликовано на www.pingcap.com7 декабря 2016 г.