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

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

2. Введение

Реляционные языки запросов обеспечивают высокоуровневый "декларативный" интерфейс для доступа к данным, хранимым в реляционных базах данных. Со временем появился язык SQL [41] как стандарт реляционных языков запросов. Двумя ключевыми подкомпонентами компонента вычисления запросов в SQL-ориентированной системе баз данных являются оптимизатор запросов и подсистема выполнения запросов.

Подсистема выполнения запросов реализует набор физических операций. На вход каждой операции поступают один или несколько потоков данных, и на выходе формируется поток данных. Примерами физических операций являются сортировка (внешняя), последовательное сканирование, индексное сканирование, соединение методом вложенных циклов и соединение сортировкой и слиянием. Я называю эти операции физическими, поскольку они не обязательно связаны один к одному с реляционными операциями. Проще всего представлять физические операции как куски кода, которые используются в качестве строительных блоков для обеспечения возможности выполнения SQL-запросов. Абстрактным представлением такого выполнения является дерево физических операций, пример которого показан на рис. 1. Дуги в дереве операций представляют потоки данных между операциями. Мы используем термины "дерево физических операций" и "план выполнения" (или просто план) в одном и том же смысле. Подсистема выполнения отвечает за выполнение плана, что приводит к формированию ответов на запросы. Следовательно, возможности подсистемы выполнения запросов определяют структуру допустимых деревьев операций. В [21] читатель может найти обзор методов вычисления запросов.

Рис. 1. Дерево операций

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

• Алгебраическое представление данного запроса может быть преобразовано во многие другие логически эквивалентные алгебраические представления; например,
  Join (Join (A,B),C) = Join (Join (B,C),A)
• Для данного алгебраического представления может существовать много деревьев операций, реализующих алгебраическое выражение; например, в системе баз данных обычно поддерживается несколько алгоритмов соединения.

Кроме того, пропускная способность, или время ответа системы при выполнении этих планов может весьма различаться. Поэтому здравый выбор плана выполнения, производимый оптимизатором имеет критическое значение. Таким образом, к оптимизации запросов можно относиться как к сложной поисковой проблеме. Для того, чтобы смочь решить эту проблему, нам требуется обеспечить:

• Пространство планов (пространство поиска).
• Метод оценки стоимости, чтобы можно было оценить каждый план в каждом пространстве поиска. Интуитивно, это оценка ресурсов, требуемых для выполнения плана.
• Алгоритм перебора, который может осуществлять поиск в пространстве планов выполнения.

Желаемым оптимизатором является такой, в котором

(1) пространство поиска включает планы с низкой стоимостью;
(2) метод оценок является точным;
(3) алгоритм перебора эффективен.

Каждая из этих трех задача нетрививальна, и из-за этого построение хорошего оптимизатора является громадной работой.

Мы начинаем с обсуждения подхода к оптимизации в System R, поскольку это был необыкновенно элегантный подход, который питал многие последующие работы в области оптимизации. В разделе 4 мы обсудим, что представляет собой пространство поиска, анализируемое оптимизатором. В этом разделе представлены алгебраические преобразования, включаемые в пространство поиска. Раздел 5 посвящается проблеме оценки стоимости. В разделе 6 мы обсуждаем тему перебора пространства поиска. Это завершает обсуждение базовых основ оптимизации. В разделе 7 мы обсудим некоторые современные разработки в области оптимизации запросов.

Предыдущий раздел - Содержание - Следующий раздел