Обработка запросов в семействе продуктов 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. Текст доступен здесь.

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

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

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

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

В оптимизаторах DB2 имеются два базовых пути доступа: через индекс и через сканирование таблицы. При доступе через сканирование таблицы просто проверяется каждая ее строка с возможным применением предикатов. Оптимизатор должен тщательно разделять и моделировать как «SARGable»-предикаты (SARG происходит от Search ARGument), так и «остаточные» предикаты. SARGable-предикаты применяются, когда страница закрепляется за буфером, чтобы избежать нетребуемых расходов ЦП на копирование строки. Предикаты, включающие вложенный подзапрос (еще один блок запроса SELECT FROM WHERE), который зависит от некоторого значения в сканируемой таблице (коррелирует с ним), должны заново вычисляться для каждого такого значения. Чтобы избежать потенциального самоблокирования, когда дополнительные страницы считываются в буфер для подзапроса, в DB2 откладывается применение таких «остаточных» предикатов до того времени, когда строка будет скопирована из буфера.

В DB2/* записи каждой таблицы хранятся отдельно от записей любой другой таблицы. В DB2/2 Version 1 все они помещаются в один файл, в то время как в DB2/6000 Version 1 они расщепляются на разделы, называемые сегментами. Это ограничение ослабляется в DB2 для MVS, но обычно клиенты считают более эффективным размещение каждой таблицы в своем собственном физическом пространстве.

В DB2 и DB2/* индексы поддерживаются за счет многостолбцовых B+-деревьев и используются для упорядочения, группирования схожих значений, обеспечения уникальности, обеспечения альтернативы доступа к базовой таблицы (доступ только к индексу) и прямого доступа к только тем строкам, которые удовлетворяют некоторым предикатам. В оптимизаторах DB2 используются разнообразные и очень сложные стратегии индексного доступа.

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

Простые предикаты, включающие простое сравнение столбца со значением ил выражением (например, DEPTNO = 'K55'), являются кандидатами в старт/стоповые условия, равно как и предикаты соединения, «проталкиваемые» (pushed down) на внутреннюю таблицу соединения с вложенными циклами (см. следующий подраздел), и даже подзапрос, возвращающий единственное значение (например, EMP.SALARY= (SELECT MAX(SALARY) FROMEMP)).

Более сложные предикаты, такие как BETWEEN (пара предикатов диапазона), LIKE (пара предикатов диапазона может быть извлечена, если первым символом шаблона LIKE не является метасимвол) и предикат IS NULL также могут использоваться как старт/стопные условия. Может использоваться даже предикат IN <list> либо путем стортировки <list> и успешного использования каждого значения в качестве старт/стопного ключа (в DB2 для MVS), либо использования объединения идентификаторов строк (в DB2/*), описываемого ниже.

Для поддержания эффективности индексных операций наличие выражений и даже преобразований типа на индексном столбце обычно препятствуют использованию этого столбца как условия старта или остановки. Однако в DB2/* типы данных в сравнении не обязаны быть идентичными; они должны лишь удовлетворять требованиям совместимости ANSI между строками и символами.

Оказывается поразительно сложно определить, когда предикаты могут использоваться как старт/стопные условия, и когда их можно применить и как SARG’и. Ключи индекса формируются путем конкатенации значений столбцов из любого числа столбцов индекса, но старт/стопные условия сократят сканирование индекса, только если старшие по порядку (лидирующие, или префиксные) столбцы ограничиваются предикатами. Например, индекс на столбцах X и Y не может получить удачное старт/стопное условие при наличии предиката на Y, если не имеется предиката и на X.

Предикат может всегда применяться как старт/стопный ключ, только если операцией сравнения в предикате является «=». Если имеется предикат на столбце «=», «≥» или «≤», то предикаты на последующих столбцах являются кандидатами на старт/стопные условия. Однако после первого предиката со сравнением на неравенство последующие столбцы индекса не являются полезными и могут быть применены как SARG’и. Например, предположим, что имеется единственный индекс на столбцах X, Y и Z. Для предикатов X = 5, Y ≥ 7, Z ≥ 'B' в DB2 был бы построен стартовый ключ 5||7, стоповый ключ 5, и предикат на Z применялся бы как SARG. В DB2/* с использованием Stardurst будет построен ключ 5||7||'B', и предикат на Z будет применен и как SARG, потому что сканирование индекса, начинающееся с этого значения ключа, может включать такие значения, как 5||8||'A', не удовлетворяющие предикату на Z. Если бы предикат на Y ≥ 7 был строгим неравенством, в DB2/* Version 1 сканирование начиналось бы с 5||7, и предикаты на Y и Z применялись бы как SARG’и.

Поскольку столбцы индекса могут в индивидуальном порядке объявляться как упорядоченные по возрастанию или по убыванию, для столбцов индекса с упорядочением по убыванию старт/стопные условия должны перевертываться; например, если столбец Z упорядочивается по убыванию, то Z > 'B' является его стоповым условием. Наконец, когда уникальный индекс является «полностью уточненным» (т.е. со всеми его столбцами связаны предикаты сравнения по равенству), все оптимизаторы DB2 понимают, что может быть выбрана, самое большее, одна строка, так что менеджер данных может пользоваться ускоренным доступом, и могут быть предприняты другие средства эффективной обработки.

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

SELECT MIN(SALARY) FROM EMP,

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

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

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

ZIPCODE BETWEEN 90100 AND 90199 OR
ZIPCODE BETWEEN 91234 AND 91247,

и имеется индекс на столбце ZIPCODE, в DB2 будет рассматриваться план, в котором к этому индексу доступ производится дважды: один раз со старт/стопными ключами (90100,90199) и другой – с (91234,91247). Затем списки кортежей будут объединены с удалением дубликатов. Иногда это называют «index Oring».

В DB2/* на основе Starburst эта обработка списков RID будет расширена включением пересечения («ANDing») списков RID’ов, что позволит избежать чтения страниц данных при наличии индексов на всех используемых в запросе столбцах. Например, для запроса

SELECT C1, C2
FROM T
WHERE C1 = 10 AND C2 = 47

будут сохранены RID’ы от сканирования индекса по C1 со стартовым ключом 10 и стоповым ключом 10, и пересечены с RID’ами от другого индексного сканирования по C2 со стартовым и стоповым ключом 47. Поскольку все столбцы, на которые имеются ссылки в запросе, доступны через индексы, не требуются чтения страниц данных.

В DB2 для MVS в настоящее время выполняется как Oring, так и ANDing с многими индексами в сложных комбинациях предикатов с AND и OR с использованием методов, представленных в [MHWC90]. Один и тот же индекс может использоваться много раз. Например, если для таблицы T имеется единственный индекс I на столбцах C1 и C2, то для запроса

SELECT C1,C2
FROM T
WHERE C1 = 10 AND (C2 = 32 OR C2 = 97)

в DB2 для MVS индекс I мог бы использоваться дважды, один раз со стартовым и стоповым ключом 10||32, а другой раз – 10||97. Поддерживается любой уровень вложенности AND/OR, и может использоваться любое число индексов с учетом возможных ограничений по памяти. Для обработки нескольких индексов оптимизатор производит очень подробный анализ для определения наилучшего порядка обработки, минимизирующего как использование памяти (число RID’ов), так и число обращений к таблице. Во время выполнения этот план может быть изменен или остановлен, как это описывается в разд. 7.4.

Одной из опасностей использования индекса в операторе UPDATE является то, что обновленные строки могут быть помещены далее текущей позиции индексного скана и обновлены еще раз, если выбирается инекс на обновляемом столбце. Например, следующий оператор мог бы привести к бесконечному увеличению зарплаты, если бы для сканирования EMP использовался индекс на SALARY:

UPDATE EMP
SET SALARY = SALARY * 1.1

Эта семантическая аномалия была любовно названа «проблемой Хеллоуин» покойным Мортоном Астраханом (Morton Astrahan), посольку Пат Селинджер (Pat Selinger) обнаружила ее в Хеллоуин. Эта проблема возникает только из-за того, что доступ к строкам и их обновления конвейеризуются, что обычно бывает полезно, и ее можно избежать путем сбора всех RID’ов строк, подлежащих обновлению, до начала их обновления.

4.2 Соединения

Соединение таблиц является одной из наиболее критичных операций по отношению к оптимизации, поскольку она широко распространена, для ее выполнения требуется много ресурсов, и она имеет много разновидностей. И в DB2/*, и в DB2 для MVS поддерживаются алгоритмы соединения вложенных циклов и сортировки со слиянием с обычной реализацией. Соединения через вложенные циклы и сортировку со слиянием с годами стали сочетаться совместно, поскольку в обоих методах берется внешнее значение предиката соединения и «проталкивается вниз» так, как будто внутренняя таблица ограничивается предикатом на одной таблице.

Основная разница состоит в том, что в случае соединения слиянием оба входных источника должны быть упорядочены (через индекс или путем явной сортировки), и внутренний ввод должен производиться из одной упорядоченной таблицы (базовой или временной), чтобы использовать идентификатор строки (RID) как механизм позиционирования для возврата на более раннюю позицию внутренней таблицы, если во внешней таблице встречается дубликат. Для соединения методом вложенных циклов оптимизаторы DB2 рассматривают возможность сортировки внешней таблицы по столбцами предиката соединения, а в DB2/* даже рассматривается возможность сортировки таблицы перед соединением для позднейшей обработки разделов GROUP BY, ORDER BY или DISTINCT.

В оптимизаторе DB2 для MVS также поддерживается гибридный метод соединения [CHH+91], смесь двух упомянутых методов. Лучше всего его можно охарактеризовать как соединение через вложенные циклы с упорядоченной внешней таблицей и пакетной обработкой RID для внутренней таблицы. Гибридное соединение часто оказывается полезным, когда на внутренней таблице имеются только некластеризованные индексы, и в результате содержится немного строк. Подобно соединению путем слияния, в гибридном соединении обычно требуются, чтобы строки внутреннего и внешнего источников ввода были упорядочены. Подобно соединению через вложенные циклы, не требуется помещать внутреннюю таблицу во временную таблицу, но обеспечивается эффективный доступ к страницам данных внутренней таблицы, поскольку сначала сортируется список RID’ов, а чтение каких-либо страниц данных откладывается до конца соединения. Этот метод эффективно комбинируется с другими методами обработки RID’ов, такими как индексный ANDing.

Если выполняется соединение методом вложенных циклов с использованием индексного сканирования для внутренней таблицы, и внешняя таблица упорядочена в соответствии с предикатом соединения, оптимизатор DB2 для MVS применяет «индексную предысторию» («index look-aside»). При этом запоминается позиция в корневой странице, посещенная в последний раз в индексе внутренней таблицы, что позволяет не обходить нелистовые страницы индекса. В оптимизаторе DB2 для MVS это поведение моделируется везде, где возможно.

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

Применяя стратегии доступа и соединений, описанные в предыдущем разделе, оптимизаторы DB2 рассматривают возможные последовательности соединений, производя поиск хорошего плана в одной и той же восходящей манере, но с использованием разных алгоритмов.

В DB2 для MVS для перечисления различных порядков соединения используется динамическое программирование. Базовые алгоритмы детально описаны в [SAC+79]. Как правило, две таблицы не будут соединяться, если для них отсутствует предикат соединения. Однако применяются специальные эвристики для попыток распознавания случаев, в которых может оказаться выгодным декартово произведение. Все таблицы, для которых гарантированно будет произведена одна строка по причине наличия полностью уточненного уникального индекса, фиксируются в начале порядка соединений. Эта ситуация без потерь, она полностью безопасна и сокращает время оптимизации. В DB2 для MVS также используется тот факт, что эти «однострочные» таблицы не влияют на упорядоченность результирующего набора.

По мере возрастания числа таблиц, участвующих в соединении, требования динамического программирования по времени и памяти могут стать чрезмерными на небольших PC с OS/2. В результате в DB2/* используется «жадный» алгоритм [Loh88a], который очень эффективен, поскольку никогда не меняет курс. Поскольку жадный алгоритм всегда занимается наиболее дешевыми соединениями, оптимизатор может кэшировать результат соединения во временной таблице и использовать ее как внутреннюю таблицу более позднего соединения. Тем самым, в DB2/* допускаются составные внутренние источники данных (планы «густых деревьев» (bushy tree)). Как и при использовании DB2 для MVS, на возможные соединения указывают предикаты соединения. Декартово произведение берется только при отсутствии предикатов соединения.

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

Перебор большего числа комбинаций соединений может позволить оптимизатору найти более эффективный план, но может привести к повышению стоимости выполнения самого процесса оптимизации [OL90]. Чтобы избегать потенциальных декартовых произведений, в DB2/* с использованием Starburst любой предикат, ссылающийся на более чем одну таблицу, будет считаться действующим, как предикат соединения. Например, предикат вида X.1 + Y.2 > Z.4 может использоваться для соединения таблиц X, Y и Z. Кроме того, будут ликвидированы зависящие от реализации ограничения на число таблиц, ссылки на которые содержатся в запросе; единственным ограничением будет объем памяти, доступной для хранения фрагментов плана в течение оптимизации.

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

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

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

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

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

Более сложно надежно оценить стоимость ввода-вывода. Должны делаться предположения о доступности пула буферов и кластеризации данных. Как правило, в DB2 для MVS предполагается, что для каждой конкретной таблицы доступен очень малый процент пула буферов. Однако, если имеется высокий уровень локальности ссылок (как во внутреннем индексе, возможно, во внутренней таблице соединения вложенными циклами или индексе внутренней таблицы при гибридном соединении), принимается более либеральное предположение о том, останется ли страница данных или индексная страница в основной памяти в течение выполнения запроса.

В DB2 для MVS индексные деревья имеют 3 или 4 уровня. Моделирование процентов удачи буферного пула для этих уровней является очень важным для клиентов, производящих оперативную обработку транзакций над большими (более 10M строк) таблицами. На ввод-вывод страниц данных влияют особенности запроса, размер пула буферов и степень кластеризации данных с общими значениями в страницах данных. В формулах для доступа к данным через отсортированный список RID’ов учитываются размер таблицы, степень кластеризации индекса и селективность предикатов на индексе.

В DB2 для MVS пользователю разрешается задавать на любом запросе раздел OPTIMIZE FOR N ROWS, чтобы указать, что по курсору будут прочитаны только N строк до его закрытия [DB293c]. В этом случае DB2 для MVS разделяет общую стоимость на затраты, ассоциируемые с открытием курсора, и затраты на каждое чтение строки. Выбирается план, который будет меньше всего стоить для открытия и N чтений, и этот план может существенно отличаться от плана, оптимального при отсутствии такого раздела.

Если выбирается план «N строк», то DB2 для MVS может отключить упреждающее чтение (обсуждаемое в разд. 7.2), если устанавливается, что для возврата N строк потребуется всего несколько страниц данных. Упреждающее чтение может привести к чтению 64 индексных страниц и 64 страниц данных при выборке всего одной строки. Это составляет около 0.5 Мб данных, которые потребуется прочитать с диска и поместить в буферный пул, и большая часть которых не требуется. Такая дополнительная работа будет стоить заказчику десятки тысяч долларов в год за счет расходов на ввод-вывод, память и ЦП. По причине неизбежной неточности в показателях фильтрации и статистики для случая OPTIMIZE FOR 1 ROWS был написан специальный код для выбора плана, в котором, по возможности, избегается сортировка (данных или RID’ов), независимо от того, будет ли запрос, по оценке оптимизатора, выдавать ровно одну строку.

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

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

В DB2 для MVS также вычисляется статистика неравномерного распределения для каждого столбца, являющегося первым столбцом индекса. Сохраняются десять старших значений и относительная частота их появления, что является очень важным для точного вычисления селективности предикатов. В DB2/* с использованием Starburst также будет иметься возможность сбора статистики о неравномерном распределении. Эта статистика будет собираться для всех столбцов таблицы, и у пользователя будет иметься возможность указывать число значений, которые нужно собирать; более тонкая гранулярность обеспечивает лучшие показатели фильтрации, но их сбор обходится дороже.

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

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

В DB2 для MVS статистика может обновляться пользователем с использованием операторов SQL UPDATE. Возможность обновлять статистику вручную является очень полезной, особенно в модельных производственных приложениях над тестовыми базами данных. В DB2/* с использованием Starburst также будет поддерживаться эта возможность.

В DB2 для MVS и в DB2/* используются одни и те же основные формулы для оценки показателя фильтрации [DB293c]. Значения по умолчанию, используемые в выражениях, переменных основного языка и параметрах, настроены в соответствии с паттернами использования типичных заказчиков и, по существу, одни и те же во всех продуктах.

Во всех продуктах используются классические формулы для составных предикатов, в которых предполагается независимость конъюнктов, и поэтому их показатели фильтрации перемножаются [SAC+79]. Иногда точная оценка показателей фильтрации затрудняется наличием корреляции предикатов. Для уменьшения этой в проблемы в DB2 для MVS, как правило, для вычисления размера результата используется наиболее селективный предикат на каком либо заданном столбце.

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

C1 > :hv1
   OR (C1= :hv1 AND C2 >= :hv2)
   OR (C1= :hv1 AND C2 = :hv2 AND C3 >= hv3)

(где :hv1, :hv2 и :hv3 – переменные основной программы) анализировать трудно, поскольку они часто используются для позиционирования курсора на индексе при выполнении операции открытия курсора, или после COMMIT, ROLLBACK WORK, или другого прерывания пакетной обработки (заметим, что COMMIT WITH HOLD не решает эту проблему полностью, поскольку для курсора по-прежнему требуется начальное открытие, а удержание курсора не работает при использовании логики рестарта). В DB2 для MVS используются специальные формулы для попытки оценить эффект корреляции между AND-предикатами, обнаруживаемыми в OR-предикатах.

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

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