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

Цели и задачи дисциплины

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

Краткое содержание дисциплины

Компилятор запросов. Синтаксический анализ и деревья разбора. Грамматика для простого подмножества SQL. Препроцессор: разрешение представлений VIEW; семантический анализ (верификация имен отношений, верификация имен атрибутов и их квалификация, контроль типов). Алгебраические законы и планы запросов. Коммутативный и ассоциативный законы. Законы для операции выборки. Законы для операции проекции. Законы для соединения и прямого произведения. Преобразование дерева разбора в логический план запроса. Конверсия в реляционную алгебру. Удаление подзапросов из условий. Логическая оптимизация: продвижение операций выборки и проекции «вниз» по дереву запроса; замена сочетания выборки и прямого произведения на соединение. Пример, указывающий на целесообразность первоначального продвижения выборки вверх. Оценка стоимости операций. Оценка размеров промежуточных отношений. Оценка размеров проекции. Оценка размеров выборки. Оценка размеров соединения. Естественное соединение с несколькими атрибутами соединения. Соединение нескольких отношений. Оценка размеров для других операций. Использование статистик. Виды статистик (тотальные статистики и гистограммы). Гистограммы полные и частичные. Виды частичных гистограмм (с равной шириной интервалов, с равной высотой интервалов, с наиболее часто встречающимися значениями). Подходы к сбору статистик (периодичность сбора, малые выборки, инкрементный сбор, использование рудиментарных индексов). Физическая оптимизация. Общая схема работы оптимизатора физических планов. Подходы к перебору физических планов. Использование эвристик. Алгоритмы реализации операторов физической алгебры. Сканирование и сортировка. Стоимостная модель для физических операторов. Итераторная и потоковая модели для организации выполнения операторов физической алгебры. Однопроходные и многопроходные алгоритмы реализации операций над базой данных. Двухпроходные алгоритмы на базе сортировки и хеширования. Алгоритмы, базирующиеся на использовании индексов. Генерация физического плана запроса. Выбор методов для селекции. Выбор методов для соединения. Конвейеризация против материализации. Конвейеризация унарных операций. Конвейеризация бинарных операций. Нотация для физических планов запроса. Упорядочивание физических операций. Управление буферным пулом. Архитектура менеджера буферного пула. Стратегии вытеснения страниц. Связь между выбором физических операторов и управлением буферным пулом. Параллельные алгоритмы для реляционных операций. Распараллеливание покортежных операций. Распараллеливание полнотабличных операций. Производительность параллельных алгоритмов.

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать: