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

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

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

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

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

В оптимизаторах DB2 используется много методов минимизации дорогостоящих операций.

Если много предикатов соединяются предикатами AND, то вычисление первого из этих предикатов, которое наиболее вероятно приведет к FALSE, обеспечит наилучшую производительность. Когда в DB2 для MVS вычисляются предикаты на таблице или индексе, эти предикаты разделяются на «классы», или типы. Предикаты, относящиеся к типам, которые более вероятно выдадут FALSE, вычисляются первыми. Первыми вычисляются предикаты сравнения на равенство (этот тип включает и предикат IS NULL), затем вычисляются предикаты проверки вхождения в диапазон, затем – прочие предикаты, и последними вычисляются предикаты с подзапросами. Внутри данного класса предикатов предикаты вычисляются в порядке их появления в списке SELECT. Как показывает опыт заказчиков, лучше предоставить пользователю возможность контроля над порядком вычисления предикатов внутри класса, поскольку вычислениям показателя фильтрации не всегда можно доверять.

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

Все сортировки, требуемые для GROUP BY и ORDER BY, если это возможно, комбинируются в одну сортировку путем переупорядочения столбцов GROUP BY. Для удовлетворения SELECT DISTINCT на надмножестве множества столбцов S может использоваться уникальный индекс на S, даже если этот индекс не используется в запросе, поскольку уникальный индекс определяет ключ на S и гарантирует, что в таблицу никогда не попадут дубликаты S. Аналогично, столбцы GROUP BY могут быть свободно переупорядочены в соответствии с порядком столбцов индекса, что обеспечивает требуемый порядок для GROUP BY, сохраняя сортировку.

Иногда знания об операции могут использоваться для ее более эффективного выполнения. Например, во всех продуктах DB2 вычисление подзапросов с EXISTS завершается немедленно после обнаружения первой требуемой строки. Кроме того, для выполнения запросов с агрегацией без GROUP BY можно использовать специальные индексы для завершения обработки немедленно после нахождения требуемой строки. Например, для выполнения запроса

SELECT MAX(ORDER_NUMBER)
FROM SALES

требуется выбрать всего лишь одну первую строку в порядке убывания индекса на ORDER_NUMBER.

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

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

В DB2.* сканирование таблицы может производиться как в прямом, так и в обратном направлении (смена направления изменяется при достижении начала или конца таблицы). Этот метод называется двунаправленным (boustrophedonic) сканированием. (Истоки этого термина восходят к сельскому хозяйству. Крестьянин, вспахивающий поле, начинает с единственной борозды. По достижению края поля он разворачивается и начинает вспахивать новую борозду, параллельную начальной.) Это позволяет при следующем сканировании использовать страницы, уже находящиеся в буфере, а не замещать эти страницы в соответствии с алгоритмом LRU менеджера буферного пула. В DB2/* также выполняется агрегация или вставка в кучу сортировки с удержанием страницы в буферном пуле.

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

В DB2 для MVS имеются два типа упреждающего чтения страниц, минимизирующего время ввода-вывода при последовательном (или почти последовательном) доступе: последовательное упреждающее чтение и последовательное упреждающее чтение со скачками (skip sequential prefetch). Оптимизатор может воспользоваться последовательным упреждающим чтением при сканировании таблицы, временной таблицы или кластеризованного индекса. При любом сканировании таблицы будет использоваться последовательное упреждающее чтение, если только таблица пространства (для сегментированной таблицы) не показывает, что в таблице содержится очень мало страниц данных, или если в запросе содержится раздел OPTIMIZE FOR N ROWS с небольшим значением N. Последовательное упреждающее чтение со скачками основано на специальных возможностях ввода-вывода MVS для асинхронного чтения списка страниц, которые упорядочены, но не обязательно смежны. Такой список страниц появляется, например, при чтении страниц на основе упорядоченного списка RID’ов. Обычно для этих разновидностей ввода-вывода имеются разные оценочные формулы.

Менеджер данных в DB2 для MVS может также распознавать фактический последовательный доступ во время выполнения и обеспечивать обнаруживаемое упреждающее чтение. Оптимизатор пытает моделировать такие ситуации всегда, когда это возможно. Например, в тех случаях, когда внешний источник ввода соединения методом вложенных циклов полностью упорядочен, упреждающее чтение, вероятно, будет обнаружено во время выполнения для сканирования индекса и, возможно, страниц данных внутренней таблицы. Наконец, в DB2 для MVS пользователь может выбирать размер страницы в 32К или 4К при создании таблицы. Размер страницы влияет на характеристики ввода-вывода, и это моделируется в оптимизаторе.

В DB2 для MVS имеется возможность сжимать или шифровать данные на уровне строки. Стоимость распаковки или дешифрации моделируется оптимизатором.

В DB2 для MVS также можно оптимизировать запрос для использования параллелизма ввода-вывода. Эта возможность является новой для DB2 Version 3. Поскольку это очень сложное и новое средство, оно не рассматривается в этой статье.

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

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

Оптимизаторы DB2 должны иметь дело с блокировками и транзакционной семантикой, требуемой пользователем (уровнем изоляции). Если для пользователя требуется уровень изоляции «стабильности курсора», то блокировки, установленные на индексах, могут быть сняты до осуществления доступа к соответствующим страницам данных. Поскольку другой пользователь в промежутке может поменять соответствующие страницы данных, оптимизатору требуется повторно применять любой предикат, уже примененный к индексу.

Как часть плана, оптимизатор выбирает тип блокировки и гранулярность блокирования для каждой таблицы, к которой требуется доступ. Выбор уровня блокирования представляет собой интересный компромисс: более крупное гранулирование блокировок существенно сокращает стоимость получения и снятия блокировки, но в то же время снижает уровень параллелизма при доступе к таблицам.

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

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

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

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

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

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

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

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

Продукты DB2 являются результатом многолетней работы специализированной и новаторской группы разработчиков. Авторы глубоко признательны группе оптимизации DB2 для MVS в лаборатории Санта-Тереза и, в особенности, главного архитектора Юна Ванга (Yun Wang). Тим Малкемус (Tim Malkemus) являлся главным разработчиком и лидером группы оптимизации при разработке OS/2 Extended Edition Database Manager в лаборатории Остина, Техас. Группы в Almaden Research Center, T.J. Watson Research Center и Santa

Teresa Laboratory помогают в разработке будущих версий DB2/*. Авторы хотели бы выразить благодарность Чейтену Бару (Chaitan Baru), Полу Беду (Paul Bird ), Хешелу Хэррису (Hershel Harris), Ричарду Хеджесу (Richard Hedges), Глену Лафлину (Glenn Laughlin), Брюсу Линдсею (Bruce Lindsay), Тиму Малкемусу (Tim Malkemus), Джону Макферсону (John McPherson), Роджеру Миллеру (Roger Miller), Хамиду Пирамешу (Hamid Pirahesh), Шейле Ричардсон (Sheila Richardson), Пат Селинджер (Pat Selinger) и Сурендре Верма (Surendra Verma) за конструктивное рецензирование первых вариантов этой статьи.

Литература

[CHH+91] J. Cheng, D.Haderle, R.Hedges, B. Iyer, T.Messinger, C.Mohan, and Y.Wang. An efficient hybrid join algorithm: A db2 prototype. In Proceedings of the Seventh IEEE International Conference on Data Engineering, Kobe, Japan, April 1991. Also available as IBM Research Report RJ7884, San Jose, CA, October 1990.

[DB293a] DB2. Capacity Planning for DB2 Applications (GG24-3512). IBM Corp., 1993.

[DB293b] DB2. DB2 V2.3 Nondistributed Performance Topics (GG24-3823). IBM Corp., 1993.

[DB293c] DB2. DB2 V3 Administration Guide (SC26-4888), Chapter 7: Performance Monitoring and Tuning. IBM Corp., 1993.

[DB293d] DB2. Design Guidelines for High Performance (GG24-3383). IBM Corp., 1993.

[DB293e] DB2/2. DB2/2 1.1.0 Guide ( S62G-3663 ). IBM Corp., 1993.

[DB293f] DB2/2. DB2/6000 1.1.0 Administration Guide ( S609-1571 ). IBM Corp., 1993.

[DN82] D.Daniels and P.Ng. Query Compilation in R*. IEEE Database Engineering, 5(3):15–18, September 1982.

[HCL+90] L.M. Haas,W. Chang, G.M. Lohman, J.McPherson, P.F.Wilms, G. Lapis, B. Lindsay, H. Pirahesh, M. Carey, and E. Shekita. Starburst Mid-Flight: As the Dust Clears. IEEE Transactions on Knowledge and Data Engineering, pages 143–160, March 1990. Also available as IBM Research Report RJ7278, San Jose, CA, Jan. 1990.

[HP88] Waqar Hasan and Hamid Pirahesh. Query Rewrite Optimization in Starburst. Research Report RJ6367, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120, August 1988.

[LDH+84] G.M. Lohman, D. Daniels, L. Haas, R. Kistler, and P. Selinger. Optmization of Nested Queries in a Distributed Relational Database. In Proceedings of the Tenth International Conference on Very Large Databases (VLDB), Singapore, pages 218–229, August 1984. Also available as IBM Research Report RJ4260, San Jose, CA, April 1984.

[LFL88] M. Lee, J.C. Freytag, and G.M. Lohman. Implementing an Interpreter for Functional Rules in a Query Optimizer. In Proceedings of the Fourteenth International Conference on Very Large Databases (VLDB), Los Angeles, CA, pages 218–229, August 1988. Also available as IBM Research Report RJ6125, San Jose, CA, March 1988.

[LLPS91] G.M. Lohman, B. Lindsay, H. Pirahesh, and K.B. Schiefer. Extensions to Starburst: Objects, Types, Functions, and Rules. Communications of the ACM, 34(10):94–109, Oct. 1991. Also available as IBM Research Report RJ8190, San Jose, CA, June 1991.

[Loh88a] G.M. Lohman. Grammar-Like Functional Rules for Representing Query Optimization Alternatives. In Proceedings of ACM SIGMOD 1988 International Conference on Management of Data, Chicago, IL, pages 18–27. ACM SIGMOD, May 1988. Also available as IBM Research Report RJ5992, San Jose, CA, December 1987.

[Loh88b] G.M. Lohman. Heuristic Method for Joining Relational Database Tables. IBMTechnical Disclosure Bulletin, 30(9):8–10, Feb. 1988.

[Mal90] Tim Malkemus. The database manager optimizer. In Dick Conklin, editor, OS/2 Notebook: The Best of the IBM Personal Systems Developer. Microsoft Press, 1990. Available from IBMas G362-0003, ISBN 1-55615-316-3.

[MHWC90] C. Mohan, D. Haderle, Y. Wang, and J. Cheng. Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. In Proceedings of the International Conference on Extending Data Base Technology, Venice, Italy, pages 29–43, March 1990. An expanded version of this paper is available as IBM Research Report RJ7341, San Jose, CA, March 1990.

[Moh93] C.Mohan. IBM’s Relational DBMS Products: Features and Technologies. In Proceedings of ACM SIGMOD 1993 International Conference on Management of Data, Washington, DC, pages 445–448, May 1993.

[OL90] K. Ono and G.M. Lohman. Measuring the Complexity of Join Enumeration in Query Optimization. In Proceedings of the Sixteenth International Conference on Very Large Databases (VLDB), Brisbane, Australia, August 1990.

[PHH92] Hamid Pirahesh, Joseph M. Hellerstein, and Waqar Hasan. Extensible/Rule Based Query Rewrite Optimization in Starburst. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 39–48, San Diego, June 1992.

[SAC+79] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and T.G. Price. Access Path Selection in a Relational Database Management System. In Proceedings of ACM SIGMOD 1979 International Conference on Management of Data, pages 23–34, May 1979. Есть перевод на русский язык: П. Селинджер, М. Астрахан, Д. Чемберлин, Р. Лури, Т. Прайс. Выбор пути доступа в реляционной системе управления базами данных.

[SQL93a] SQL/DS. SQL/DS 3.4 General Information (GH09-8074). IBM Corp., 1993.

[SQL93b] SQL/DS. SQL/DS Performance Tuning Handbook (SH09-8111). IBM Corp., 1993.

[SSar] K.B. Schiefer and Arun Swami. On the Estimation of Join Result Sizes. In Extending Data Base Technology, March 1994 (to appear). An expanded version of this paper is available as IBM Research Report RJ9569, San Jose, CA, November 1993.

[TMG93] Bruce Tate, Tim Malkemus, and Terry Gray. Comprehensive Database Performance for OS/2 2.0 ES. Von Norstrand Reinhold, 1993. Available from IBM as G362-0012, ISBN 0-442-01325-6.

[TO91] Annie Tsang and Manfred Olschanowsky. A Study of Database 2 Customer Queries. Technical Report TR 03.413, Santa Teresa Laboratory, Bailey Road, San Jose, CA, April 1991.

[Wan92] Yun Wang. Experience from a Real Life Query Optimizer (foils only). In Proceedings of ACM SIGMOD 1992 International Conference on Management of Data, San Diego, CA, page 286, May 1992.

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