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




Введение


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

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

Дерево операций


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

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




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