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

Питер ГесснерСоломон Гесснер (нем.Salomon Gessner, 1 апреля 1730, Цюрих — 2 марта 1788, там же) — швейцарский поэт, художник и график. Один из крупнейших мастеров европейского Рококо. Писал на немецком языке., Гай Лохман, Берндхард Шайфер и Юн Ванг
Перевод: Сергей КузнецовКузнецов (Кузнецова)— одна из самых распространённых русских фамилий. В «Списке общерусских фамилий», занимает 3 место. Самым распространённым сочетанием фамилии имени и отчества в России в XX веке считался Кузнецов Николай Иванович

ОригиналОригинал(от лат. originalis - первоначальный) — первоначальный, подлинный.: 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. В настоящее время в это семействоСемейство (лат.familia, мн. ч. familiae)— один из основных рангов иерархической классификации в биологической систематике. входят 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 в Остине, Техас. В нем использовался некоторый исходный код (в основном, в менеджере данных) и концепцииКонцепция, или концепт, (от лат.conceptio— понимание, система)— определённый способ понимания (трактовки, восприятия) какого-либо предмета, явления или процесса; основная точка зрения на предмет; руководящая идея для их систематического освещения. (ранняя версия 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. В Остине началось и в ТоронтоТоронто (англ.Toronto [trnto])— крупнейший город Канады, административный центр провинции Онтарио. Население— 2 503 281 жителей (2006), вместе с городами Миссиссога, Брэмптон, Маркем и другими образует агломерацию Большой Торонто с населением 5715 тыс. жителей. продолжилась работа по портированию этого продукта на 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.

Последнее и, возможно«Возможно» (фр.Peut-tre)— фильм режиссёра Седрика Клапиша 1999 года., наиболее важное требование к оптимизаторам в продуктах состоит в том, что они должны быть чувствительными к изменениям требований клиентов, не воздействуя на существующие приложения. 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) или эффективности времени выполнения. В обоих оптимизаторах в запрос подставлялись представления везде, где это было возможно, и как можно раньше вычислялись предикатПредикат (лат.praedicatum— заявленное, упомянутое, сказанное)— любое математическое высказывание, в котором есть, по меньшей мере, одна переменная. Предикат является основным объектом изучения логики первого порядка.ы и убирались неиспользуемые столбцы. Кроме того, в DB2 для MVS предикаты из оператора SELECT выталкиваются в представление, которое должно материализовываться во временной таблицБогуслав Таблиц (словацк. Bohuslav Tablic (Tablicz); 6 сентября 1769, Ческе Брезово, Словакия — 21 января 1832, Костолне Моравце, Словакия) — чешско-словацкий писатель, священник, деятель возрождения словаков-лютеран, подобно тому как Бернолак является деятелем возрождения словаков-католиков. Таблиц учредил в Пресбурге «Общество чешско-словацкой литературы и языка» с целью издавать на понятном народу чешском языке простонародные и школьные книги. Учреждение этого общества было причиной если не процветания словацкой литературы, то появления в пресбургском лицее кафедры словацкого языка, для чего общество собрало большой капитал. Занять кафедру приглашен был Юрай Палкович. Общество скоро распалось, но кафедра продолжала существовать. Молодёжь имела возможность слушать историю своего народа на родном языке. В 1812 г. Таблиц был одним из основателей нового «Литературного общества Горных Городов» (Bergstdte), задававшегося прежней целью; результатом было открытие кафедры словацкого языка и в Банской Штьявнице. Это общество также скоро распалось. Таблиц писал очень много и по различным специальностям. Первое место занимают его «Poesie» (Вацов, 1806-1812). К ним приложены биографии известных словацких деятелей. Его «Sloventi verovci» (Вацов, 1805-1809) — отрывки из произведений древних словацких писателей, в то время почти уже позабытых. Перу Таблица принадлежит также много книг для народа, изданных двумя упомянутыми обществами.е; материализацияМатериализация— в оккультизме, парапсихологиии спиритуализме— проявление в присутствии медиума посторонней живой материи разной степени консистенции и уровня организованности, способной (если верить сторонникам реальности феномена) принимать формы лиц, конечностей, человеческих фигур, как полных, так и недооформленных. Принято считать, что фигуры и лица людей на спиритических сеансах материализуются на основе так называемой «эктоплазмы», источником которой служит организм медиума, хотя в парапсихологической и спиритуалистской литературе встречаются также сообщения об аппортах(результатах телепортации)— необъяснимых возникновениях в наблюдаемых замкнутых пространствах (иногда— на глазах у присутствующих) неодушевлённых объектов (драгоценностей, цветов ит.д.), а также животных, птиц, насекомых. производится в основной памяти, если размер таблицы не превышает размера доступного буфера. В DB2/* предикат IN со списком литеральных значений преобразуется в последовательность предикатов, соединенных через OR, чтобы сделать возможным использование стратегии доступа к таблице «Index-ORing» (см. разд. 4.1). В DB2/* также на стадии компиляции вычисляются некоторые выражения, содержащие скалярные функции с аргументами-константами, чтобы избежать их вычисления во время выполнения запроса.

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

В DB2 для MVS генерируется транзитивное замыкание предикатов сравнения на равенство как для предикатов над одной таблицей, так и для предикатов соединения, чтобы обеспечить как можно более раннюю фильтрацию строк и более выявить последовательности соединений с большим потенциалом. Например, если пользовательПользователь— лицо или организация, которое использует действующую систему для выполнения конкретной функции. задал условие T1.C1 = T2.C2 AND T2.C2 = 5, DB2 сгенерирут выведенный предикат T1.C1 = 5, чтобы как можно быстрее«Быстрее пули» (англ.Faster) — фильм-боевик режиссера Джорджа Тиллмана мл. Мировая премьера назначена на 4 ноября 2010 года (в России — 2 декабря). сократить число строк 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/* много дополнительных преобразований, для подробного описания которых потребовалось бы слишком много места.

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