Обработка запросов в семействе продуктов IBM DB2

Питер Гесснер, Гай Лохман, Берндхард Шайфер и Юн Ванг
Перевод: Сергей Кузнецов

Оригинал: Peter Gassner, Guy M. Lohman, K. Bernhard Schiefer, Yun Wang. Query Optimization in the IBM DB2 Family. IEEE Bulletin of the Technical Committee on Data Engineering, Vol. 16, # 4, December 1993. Текст доступен здесь.

Содержание

1. Введение

2. Оптимизация производственного уровня

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

4. Стратегии плана доступа

4.1 Одиночная таблица

4.2 Соединения

5. Перечисление соединений

6. Моделирование стоимости выполнения плана

6.1 Оценка стоимости

6.2 Статистика и показатели фильтрации

7. Развитые возможности

7.1 Методы, позволяющие избегать дорогостоящих операций

7.2 Моделирование развитых возможностей менеджера данных

7.3 Другие аспекты оптимизации

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

8. Заключение

Благодарности

Литература

Аннотация

В этой статье рассматриваются ключевые методы оптимизации запросов, требуемые в коммерческих оптимизаторах промышленного уровня и используемые, например, в семействе продуктов управления реляционными базами данных DB2. В настоящее время в это семейство входят DB2/2, DB2/6000 и DB2 для MVS1.

1. Введение

Оптимизация запроса является частью процесса компиляции запроса, в котором оператор манипулирования данными, представленный на выскоуровневом, непроцедурном языке, таком как SQL, транслируется в более детальную, процедурную последовательность операций, называемую планом. Оптимизаторы запросов обычно выбирают план путем моделирования оценочной стоимости выполнения многих возможных планов и выбора из них наименее дорогостоящего плана. После появления в 1970 г. реляционной модели IBM активно участвует в исследованиях оптимизации реляционных запросов, начиная с пионерской работы над проектом System R [SAC+79] и продолжив работами на прототипом распределенной реляционной СУБД System R* [DN82], [LDH+84] и прототипом расширяемой СУБД Starburst [Loh88a], [LFL88], [HP88], [HCL+90], [PHH92]. Внедрение этой технологии в лидирующие промышленные продукты документировано, прежде всего, в руководствах IBM, за несколькими исключениями [Mal90], [TMG93], [Moh93], [Wan92]. Без подобной документации в исследовательской литературе исследователи легко могут потерять из виду проблемы, стоящие перед разработчиками продуктов, которые просто не могут не принимать во внимание изобилие деталей языка SQL и должны строить оптимизаторы промышленного уровня для раpнообразных пользовательских приложений и конфигураций.

В статье приводится сводка некоторых «индустриальных» возможностей оптимизаторов в семействе продуктов IBM DB2, включая исходную DB2, работающую в среде ОС MVS [DB293b] [DB293a] [DB293d], и более современные клиент-серверные продукты DB2 для ОС AIX и OS/2: DB2/6000 and DB2/2 [DB293e] [DB293f]. Чтобы избежать путаницы, в этой статье "исходной" DB2 будет называться DB2 для MVS. Из-за ограниченного объема статьи в ней не обсуждаются аналогичные продукты для ОС VM/ESA и VM/ESA (SQL/DS, первая реляционная СУБД IBM [SQL93a] [SQL93b]) и ОС OS/400 (SQL/400). Все эти продукты происходят от прототипа System R, и в них используются многие достоинства этой работы: однократная оптимизация запросов во время компиляции для повторяющегося выполнения; использование детализированной модели для оценки стоимости выполнения возможных планов; широкий репертуар возможных путей доступа и методов соединений.

Однако каждый продукт подгонялся под свою среду, для чего часто требовались разные реализации, в особенности, разные стратегии выполнения. Оптимизатор запросов для DB2 для MVS, впервые появившийся в 1983 г., в основном был выполнен по образу оптимизатора System R, но был полностью переписан для обеспечения надежного управления ошибочными ситуациями и эффективности, а также полного покрытия SQL, корректной работы с неопределенными значениями и поддержки разных языков и наборов символов. DB2 для MVS, написанный на собственном языке разработки систем, продолжает совершенствоваться в лаборатории IBM Santa Teresa в Сан-Хосе, Калифорния. В декабре 1993 г. была выпущена третья версия продукта со значительно улучшенной производительностью и доступностью.

Клиент-серверные продукты DB2 происходят от OS/2 Extended Edition DatabaseManager, который был написан на языке Си в подразделении IBM Entry Systems Division в Остине, Техас. В нем использовался некоторый исходный код (в основном, в менеджере данных) и концепции (ранняя версия Query Graph Model [PHH92] и оценочный вариант жадного алгоритма [Loh88b]) из прототипа Starburst по состоянию на то время. Продукт был впервые выпущен в 1988 г. как OS/2 Extended Edition 1.0 Database Manager и несколько раз совершенствовался. В 1992 г. разработка и поддержка продуктов баз данных для OS/2 была перемещена в лабораторию IBM в Торонто, Канада, которая в мае 1993 г. выпустила 32-разрядную версию DBM, названную DB2/2 для OS/2 2.x. В Остине началось и в Торонто продолжилась работа по портированию этого продукта на AIX, что привело к выпуску в ноябре 1993 г. DB2/6000. IBM планирует расширять клиент-серверные продукты DB2 за счет использования значительных частей прототипа Starburst (компилятора SQL, включая его технологии основанной на правилах перезаписи запросов [PHH92] и оптимизации [Loh88a] [LFL88]), добавления нескольких важных объектно-ориентированных расширений (совместная работа Института технологии баз данных (Database Technology Institute) в лаборатории Santa Teresa и проекта Sturburst), поддержки параллельного выполнения запросов (совместная работа лаборатории Торонто и IBM T.J. Watson Research Center in Hawthorne, NY) и портирования на платформы не IBM, включая рабочие станции и серверы Hewlett-Packard HP 9000 с ОС HP/UX. Поскольку в DB2/2 и DB2/6000 используется общий базовый код, в статье используется название DB2/*, когда между этими продуктами нет разницы. Имеется в виду третья версия DB2 для MVS и первая версия DB2/*.

2. Оптимизация производственного уровня

«Черт прячется в деталях.»
Х. Росс Перо

Оптимизаторы в продуктах должны иметь дело со многими аспектами оптимизации запросов, редко рассматриваемыми в исследовательских прототипах.

Прежде всего, они должны, конечно, оптимизировать весь язык SQL. Это включает поддержку предикатов со сложными комбинациями AND, OR и NOT; предикаты IN и LIKE; предикаты IS NULL и NOT NULL; разделы UNION, INTERSECT и EXCEPT; вложенные подзапросы (и даже выражения, содержащие несколько вложенных подзапросов!); корреляцию (ссылки из подзапросов на значения, обеспечиваемые в другом блоке SELECT...FROM...WHERE... того же запроса) и много других конструкций, так или иначе влияющих на оптимизатор.

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

В третьих, оптимизаторы в продуктах должны иметь дело с такими «будничными» деталями, как поддержка наборов символов национальных языков (у которых часто имеются разные порядки сортировки), обеспечением корректных ответов на разных уровнях изоляции (в особенности, на уровне стабильности курсора), корректной обработкой неопределенных значений (где должен находиться NULL в порядке сортировки? учитываются ли неопределенные значения в агрегатных функциях? применяется ли трехзначная логика? и т.д.), а также с аспектами реализации используемого менеджера данных, которые должны специфицироваться в плане и точно моделироваться в оценочной модели. Соответствующие примеры приводятся по ходу статьи, и в разд. 7.2 последний из затронутых вопросов обсуждается более подробно.

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

Последнее и, возможно, наиболее важное требование к оптимизаторам в продуктах состоит в том, что они должны быть чувствительными к изменениям требований клиентов, не воздействуя на существующие приложения. DB2 для MVS – это зрелый продукт с тысячами лицензий на многопользовательских системах, многие из которых поддерживают тысячи пользователей. Приложения, выполняющиеся на DB2 для MVS, часто являются «хлебом и маслом» обработки информации в компаниях Fortune 500. При каждом новом выпуске продукта заказчики ожидают только улучшений (без деградации эффективности какого бы то ни было плана). В DB2 для MVS имеется тенденция к реализации стратегий оптимизации, которые в большинстве случаев принимают подходящий путь доступа, а не рискуют применить менее понятные пути доступа, которые труднее точно моделировать. Грубо говоря, применяется правило «99-1», означающее, что свойство, которое, как ожидается, положительно скажется на 99% запросов, но может привести к деградации 1% запросов, не включается в продукт.

В высоко конкурентном мире рабочих станций DB2/* пользователи требуют большей функциональности, в частности, объектно-ориентированных возможностей, таких как определяемые пользователями типы и функции, бинарные большие объекты (BLOB), ограничения, триггеры и параллельное выполнение. Кроме возможностей «индустриального уровня», заказчики ожидают от DB2/* быстрого появления новых возможностей, согласующихся с промышленными стандартами, такими как недавно опубликованный стандарт ANSI SQL92 и развивающийся стандарт ANSI SQL3. Поэтому в DB2/* активно внедряются новые функциональные возможности, и прилагаются все усилия к сохранению лидирующей производительности.

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

Запрос можно часто представить на 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/* много дополнительных преобразований, для подробного описания которых потребовалось бы слишком много места.

Содержание Вперёд