MATTHIAS JARKE
Graduate School of Business Administration,
New York University, New York, New York 10006
JURGEN KOCH
Fachbereich Informatik, Johann Wolfgang
Goethe-Universitdt, 6000 Frankfurt 1, West Germany
Оптимизация запросов в системах баз данных
(Query Optimization in Database System)
Источник: CitForum.RU, 2005, http://www.citforum.ru/database/articles/query_optimization/
Перевод - Сергей Кузнецов
Оригинал: http://www-i5.informatik.rwth-aachen.de/lehrstuhl/lehre/IDB05/download/Literature/QO.pdf
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
© 1984 ACM 0360-0300/84/0600-0111
Computing Surveys, Vol. 16, No. 2, June 1984
Предисловие переводчика
С моей точки зрения, оптимизация запросов является наиболее важным и интересным направлением исследований и разработок во всей области баз данных. Важность этого направления определяется тем, что от развитости компонента оптимизации запросов критически зависит общая производительность любой SQL-ориентированной СУБД (я ограничиваюсь этим классом систем, потому что, во-первых, они полностью довлеют на современном рынке СУБД, и, во-вторых, методы оптимизации наиболее развиты именно для SQL-запросов). Я считаю это направление наиболее интересным, потому что при решении задач оптимизации приходится использовать самые разнообразные подходы и методы из различных областей вычислительной науки и математики: методы оптимизации программ, применяемые в компиляторах языков программирования, математическую логику, математическую статистику, методы искусственного интеллекта, распознавания образов и т.д.
На протяжении последних тридцати лет эти факторы привлекают к данному направлению внимание сотен исследователей, опубликовавших тысячи статей, многие из которых доступны и/или интересны только профессионалам. Но некоторое знакомство с методами оптимизации запросов полезно гораздо более широкой аудитории: проектировщикам и администраторам систем баз данных, разработчикам приложений баз данных и даже пользователям этих приложений. Такое знакомство обеспечивают обзоры методов оптимизации. До сих пор русскоязычным читателям были доступны моя обзорная статья и перевод более современной обзорной статьи Сураджита Чаудхари.
Мне кажется, что для полноты картины очень полезно познакомится с еще более ранней статьей Ярке и Коха, перевод которой мы и предлагаем вашему вниманию. Перечитывая эту статью, я обнаружил в ней достоинства, которыми, к сожалению, не обладают более поздние обзоры: последовательность и систематичность. Авторы пытаются (и преуспевают в этом) представить последовательную картину процесса оптимизации запроса. В свое время меня раздражало то, что они ведут свое изложение не прямо в контексте языка SQL, а используют более абстрактное представление запросов на языке реляционного исчисления. Однако сейчас мне понятно, что этот подход позволил авторам отвлечься от не слишком существенных технических трудностей оптимизации, специфичных для языка SQL, и сосредоточиться на более фундаментальных методах оптимизации.
Для справедливости следует заметить, что в 1984 г. было гораздо проще написать фундаментальный обзор методов оптимизации, чем в настоящее время. За прошедшие 20 лет было разработано множество методов, существенной части которых нельзя отказать в фудаментальности. Поэтому в наше время очень трудно выбрать стиль изложения, позволяющий описать текущее состояние данного направления исследований в такой же последовательной и логичной манере, что я Ярке и Коха. Тем более рекомендую прочитать русский вариант этой замечательной статьи, которая лично на меня оказала очень серьезное влияние.
Содержание
Эффективные методы обработки непредвиденных запросов являются решающей предпосылкой успеха обобщенных систем управления базами данных. Предлагалось множество подходов к совершенствованию эффективности алгоритмов вычисления запросов: основанные на логике и семантические преобразования, быстрые реализации основных операций, комбинаторные и эвристические алгоритмы генерации возможных путей доступа и выбора между ними.
Эти методы представляются в каркасе общей процедуры вычисления запроса использованием для представления запросов реляционного исчисления. Кроме того, затрагиваются аспекты нестандартной оптимизации запросов, такие как вычисление запросов более высокого уровня, оптимизация запросов в распределенных базах данных и использование машин баз данных. Однако основное внимание уделяется оптимизации запросов в централизованных системах баз данных.
ВВЕДЕНИЕ
Системы управления базами данных (СУБД) стали стандартным инструментом экранирования пользователя компьютера от деталей управления вторичной памятью. СУБД разрабатываются для повышения производительности труда прикладных программистов и облегчения доступа к данным неискушенных в комьютерах конечных пользователей.
Имеются две основные области исследований систем баз данных. Одна из них - это анализ моделей данных, на которые может отображаться реальный мир и на основе которых могут строиться интерейсы для различных типов пользователей. Такие концептуальные модели включают иерерхическую, сетевую, реляционную модели, а также ряд моделей, ориентированных на семантику, которые обозревались в большом числе книг и обзоров [Brodie et al. 1984].
Вторая область интересов затрагивает безопасную и эффективную реализацию СУБД. Комьютеризоаванные данные становятся центральным ресурсом большинства организаций. Это должно учитываться в каждой реализации, предназначенной для производственного использования, путем гаранирования безопасности данных в случаях параллельного доступа [Bernstein and Goodman 1981c], восстановления [Verhofstad 1978] и реорганизации [Sockut and Goldberg 1979]. Одно из основных критических замечаний ко многим ранним СУБД относилось к отсутствию эффективности при обработке предлагаемых ими мощных операций, в особенности, доступа к данным на основе их содержимого через запросы. Оптимизация запросов предназначена для решения этой проблемы путем интеграции большого числа методов и стратегий, простирающихся от логических преобразований запросов до оптимизации путей доступа и хранения данных на уровне файловых систем.
Традиционно в каждом из этих подходов использовался отдельный язык. Вероятно, это является одной из причин, по которым до сих пор не представлен исчерпывающий обзор методов оптимизации запросов. Целью этой статьи является представление методов оптимизации запросов в общем каркасе реляционного исчисления. Показано, что реляционной исчисление технически эквивалентно представлению реляционной алгебры [Codd 1972; Klug 1982a] и поддается расширениям для реализации сетевых СУБД [Dayal and Goodman 1982]. Более того, многие популярные языки запросов, такие как SQL [Astrahan and Chamberlin 1975] и QUEL [Stonebraker et al. 1976], легко отображаются в реляционное исчисление.
Для экономии места в этой статье мы прежде всего сосредотачиваемся на проблеме оптимизации запросов в централизованной СУБД. Оптимизация централизованных запросов важна не только во многих базах данных на мейнфреймах - а в последнее время и в микропроцессорных СУБД - но также является подпроблемой оптимизации запросов в распределенных системах. Сама оптимизация распределенных запросов [Bayer et al. 1984; Sacco and Yao 1982; Ullman 1982] затрагивается только кратко, а следующих двух близких областей мы вообще не касаемся:
Пользовательская оптимизация. Общая стоимость информационной системы составляется из стоимости СУБД и стоимости усилий пользователей для работы с системой. Граница между этими двумя областями состоит из функциональных возможностей и удобства использования языка запросов [Vassiliou and Jarke 1984], и наиболее важной характеристикой является время отклика системы. Если предположить, язык запросов обладает заданными функциональными возможностями, а минимизация времени отклика является целью системы выполнения запросов, то оптимизация запросов может считаться отдельно трактуемой подпроблемой пользовательской оптимизации.
Структуры файлов. Алгоритм оптимизации запросов должен производить выбор между множеством путей доступа для выполнения запроса. Внутренние детали реализации таких путей доступа и вывод соответствующих оценочных форму (см., например, Teorey and Fry [1982]) находятся за пределами этой статьи.
Статья состоит из шести разделов, расположенных в соответствии с подходом "сверху-вниз". В разд. 1 мы представляем глобальный каркас для оптимизации запросов. В разд. 2 мы сравниваем четыре метода представления запросов с точки зрения их пригодности для оптимизации. В разд. 3 мы используем один из этих методов, реляционное исчисление, для представления преобразований, основанных на логике, включая развивающиеся методы семантической оптимизации.
После преобразования запрос должен быть отображен в последовательность операций, возвращающих требуемые данные. В разд. 4 мы анализируем реализацию таких операций в низкоуровневой системе хранения данных и путей доступа. В разд. 5 мы представляем оптимизационные процедуры для интеграции этих операций в глобально оптимальный план доступа.
Для ряда проблем оптимизации запросов требуется трактовка по причине более высокой сложности запросов или некоторых характеристик используемой апаратуры. Обзор трех таких проблемных областей - запросы более высокого уровня, распределенные запросы и запросы с использованием машин баз данных - приводится в разд. 6.
1. ПРОБЛЕМА ОПТИМИЗАЦИИ ЗАПРОСОВ
Точная оптимизация процедур вычисления запросов является, вообще говоря, вычислительно трудной, и еще больше мешает отсутствие точной статистической информации о базе данных. В алгоритмах вычисления запросов приходится в большой степени полагаться на эвристики. Тем не менее, в статье будет использоваться термин "оптимизация запросов" для обозначения стратегий, направленных на повышение эффективности процедур вычисления запросов. В этом разделе мы формулируем цели оптимизации запросов и представляем общую процедуру, разработанную для структуризации процесса поиска решения.
1.1 Запросы
Запрос - это языковое выражение, которое описывающее данные, подлежащие выборке из базы данных. В конетексте оптимизации запросов часто предполагается, что запросы выражаются в манере, основанной на содержании, (в большинстве случаев ориентированной на множества, что дает оптимизатору достаточную возможность выбора между возможными процедурами вычисления.
Запросы используются в нескольких окружениях. Наиболее очевидно приложение, в котором поступают непосредственные запросы конечного пользователя, нуждающегося в информации о структуре или содержимом базы данных. Если потребности пользователей ограничены набором стандартных запросов, они могут оптимизироваться вручную путем программирования соответствующих процедур поиска и ограничения пользовательского ввода форматом меню. Однако, если требуется задавать непредвиденные запросы с использованием языка запросов общего назначения, становится необходимой система автоматической оптимизации запросов.
Второе применение запросов происходит в транзакциях, которые изменяют хранимые данные на основе их текущих значений (например, "повысить зарплату всем доцентам на 10%"). Наконец, выражения, подобные запросам, могут использоваться внутри СУБД, например, для проверки прав доступа [Griffiths and Wade 1976], поддержки ограничений целостности [Stonebraker 1975] и корректной синхронизации параллельного доступа [Reimer 1983].
1.2 Цели оптимизации
Экономический принцип требует, чтобы процедуры оптимизации пытались либо максимизировать пропускную способность при заданном числе ресурсов, либо минимизоровать потребление ресурсов при данной пропускной способности. Оптимизация запросов направленая на минимизация времени отклика для заданного запроса и смеси типов запросов в данной системной среде. Эта общая цель допускает ряд различных операционных целевых функций. Время отклика является разумной целью только при предположении, что время пользователя является наиболее важным критическим ресурсом. В противном случае можно стремиться к непосредственной минимизации стоимости потребления технических ресурсов. К счастью, обе цели являются в большой степени взаимнодополнительными; при возникающие конфликты целей обычно разрешаются путем назначения ограничений на доступные технические ресурсы (например, на размер буферного пространства в основной памяти).
Чтобы допустить справедливое сравнение эффективности, функциональные возможности сравниваемых систем выполнения запросов должны быть сходными. Требование "реляционной полноты", придуманное Коддом [Codd 1972], (сравните с разд. 2.1) стало квазистандартом. Методы, обозреваемые в данной статье, представляются как вклады в реализацию запросов на реляционно полном языке с минимальной стоимостью выполнения или временем отклика. Запросы более высокого уровня сложности [Chandra and Harel 1982a] рассматриваются в разд. 6.1. Общая стоимость, подлежащая минимизации, складывается из следующих компонентов:
Стоимость коммуникаций: Стоимость передачи данных из места, в котором они хранятся, в места, где выполняются вычисления и представляются результаты. Эта стоимость состоит из стоимости коммуникационного канала, которая обычно связана с временем, в течение которого канал открыт, и стоимостью задержек в обработке, вызваемых передачей. Последний компонент, более важный для оптимизации запросов, часто полагается линейной функцией от объема передаваемых данных.
Стоимость доступа к вторичной памяти: Стоимость (или время) загрузки страниц данных из вторичной памяти в основную память. На эту стоимость влияет выбираемых данных (главным образом, размер промежуточных результатов), кластеризация данных на физических страницах, размер доступного буферного пространства и скорость используемых устройств.
Стоимость хранения: Стоимость занятия вторичной памяти и буферов основной памяти. Стоимость хранения уместна только в том случае, когда память становится узким местом системы, и размер требуемой памяти может изменяться от запроса к запросу.
Стоимость вычислений: Стоимость (или время) использования ЦП.
На структуру алгоритмов оптимизации запросов влияют соотношения между этими компонентами стоимости. В территориально распределенной СУБД с относительно медленными коммуникационными каналами преобладает стоимость коммуникацонных задержек, а другие факторы существенны только для локальной подоптимизации. В централизованных системах доминирует время доступа к вторичной памяти, хотя для сложных запросов достаточно высокой может быть и стоимость ЦП [Gotlieb 1975]. В локально распределенных СУБД все факторы имеют близкие веса, что приводит к очень сложным оценочным функциям и процедурам оптимизации.
Поскольку эта статья в основном посвящена централизованным базам данных, стоимость коммуникаций не принимается во внимание, потому что в таких системах комуникационные требования не зависят от стратегии выполнения запросов. Для оптимизации одиночных запросов стоимость хранения также считается не первостепенно важной. Эти расходы учитываются только при одновременной оптмизации нескольких запросов.
===========***********==============
От редакции OM/RE: полностью статья находится на сайте CitForum.RU, по адресу: http://www.citforum.ru/database/articles/query_optimization/
| 
