Классика баз данных - статьи

       

Трансформация запросов


Запрос можно часто представить на SQL в разных эквивалентных формах. Эти возможные формы существуют по причине избыточности SQL, эквивалентности с некоторыми ограничениями подзапросов и соединений, а также логического вывода, который может быть произведен из предикатов раздела WHERE. С момента появления семейства продуктов DB2 в них использовалась оценочная оптимизация для выбора оптимального плана запроса, независимо от того, как он изначально формулировался прикладным программистом (например, невзирая на то, в каком порядке таблицы перечисляются в списке раздела FROM). Однако в них производилось только небольшое число семантических преобразований. Обеспечивались руководства пользователя по написанию SQL-запросов. Некоторые преобразования было более трудно описать, поскольку было невозможно показать, что они всегда приносят пользу.

Как в DB2 для MVS, так и в DB2/* удалялись столбцы раздела SELECT подзапроса с EXIST, чтобы (ненужные) столбцы раздела SELECT не оказывали какого-либо влияния на определение пути доступа (см. разд. 4.1) или эффективности времени выполнения. В обоих оптимизаторах в запрос подставлялись представления везде, где это было возможно, и как можно раньше вычислялись предикаты и убирались неиспользуемые столбцы. Кроме того, в DB2 для MVS предикаты из оператора SELECT выталкиваются в представление, которое должно материализовываться во временной таблице; материализация производится в основной памяти, если размер таблицы не превышает размера доступного буфера. В DB2/* предикат IN со списком литеральных значений преобразуется в последовательность предикатов, соединенных через OR, чтобы сделать возможным использование стратегии доступа к таблице «Index-ORing» (см. разд. 4.1). В DB2/* также на стадии компиляции вычисляются некоторые выражения, содержащие скалярные функции с аргументами-константами, чтобы избежать их вычисления во время выполнения запроса.

Во всех продуктах DB2 выполняются некоторые логические преобразования. Например, во всех случаях, когда это возможно, устаняются предикаты с NOT.
Аналогично, предикат LIKE анализируется на предмет возможности выделения пары граничных значений (определяющих диапазон) для сокращения числа строк, для которых должен проверяться шаблон целиком. В DB2/* также используется закон Де Моргана для получения КНФ, поскольку это упрощает вычисление предиката оптимизатором.

В DB2 для MVS генерируется транзитивное замыкание предикатов сравнения на равенство как для предикатов над одной таблицей, так и для предикатов соединения, чтобы обеспечить как можно более раннюю фильтрацию строк и более выявить последовательности соединений с большим потенциалом. Например, если пользователь задал условие T1.C1 = T2.C2 AND T2.C2 = 5, DB2 сгенерирут выведенный предикат T1.C1 = 5, чтобы как можно быстрее сократить число строк T1. Аналогично, появление предикатов соединения T1.C1 = T2.C2 AND T2.C2 = T3.C3 побудит DB2 к генерации предиката T1.C1 = T3.C3, без которого перечислитель соединений отложил бы рассмотрение возможности содинений между T1 и T3. При наличии в соединении числа таблиц, большего предустановленной константы, транзитивное замыкание предиката соединения не производится, чтобы сохранить приемелимый размер пространства поиска стратегии динамического программирования перечисления соединений.

Преобразования подзапросов в соединения часто разительно повышают эффективность, но являются достаточно сложными (об этом свидельствует ряд статей, содержащих описания ошибочных преобразований). В DB2 для MVS применяется очень осторожный подход к преобразованиям запросов. Например, преобразование подзапроса в соединение выполняется только в том случае, когда в подзапросе имеется только одна таблица, и если у этой таблицы имеется уникальный индекс, полностью соответствующий предикату сравнения на равенство; в этом случае преобразование всегда дает приемущество. В DB2 для MVS применяются другие методы повышения эффективности подзапросов, такие как кэширование результатов подзапросов с корреляцией.

В DB2/* имеется несколько другой набор методов трансформации.


В DB2/* используются наименьшее и наибольшее значения подзапроса без корреляции для обеспечения условий старта и остановки (см. разд. 4.1) для внешнего блока запроса. Кроме того, в DB2/* специальным образом обрабатываются квантифицированные подзапросы (ALL, EXISTS). Например, SELECT C1 FROM T WHERE C1 > ALL ( SELECT C2 FROM T2 )

будет выполняться так, как если бы он был написан как SELECT C1 FROM T WHERE C1 > ( SELECT MAX(C2) FROM T2 )

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

В DB2/* с использованием Starburst будет иметься полностью отдельный шаг компиляции, посвященный перезаписи запросов и основанный на технологии Starburst перезаписи на основе правил [PHH92]. Это добавит в DB2/* много дополнительных преобразований, для подробного описания которых потребовалось бы слишком много места.


Содержание раздела