Введение в базы данных

Лекция 8

План лекции

Оптимизация запросов:

• Стадии оптимизации запросов
• Преобразование (перезапись) запросов
• Детали исполнения запросов
• Правила составления запросов
• Оценка хранения и распределения данных

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

Написать запрос так, чтобы выполнить наименьшее число простых операций (чтений блоков и страниц).

Средства оптимизации

В РСУБД оптимизацию можно проводить:

• Преобразуя выражения реляционной алгебры
• Используя знания о механизмах выполнения простых операций
• Проводя оценку путей доступа к данным

Оптимизация средствами СУБД

Большинство техник оптимизации запросов автоматизированы.

​

Планировщик запроса

Сравнивает до сотен различных стратегий выполнения запроса.

​

• Преобразование выражение в реляционной алгебре
• Выбор структуры запроса
• Выбор методов исполнения
• Оценка размера и распределения

Чем пользуется планировщик

• Статистика хранения и выполнения запросов (pg_stat_*)
• Динамика изменения статистики

Стадии оптимизации запроса

Стадии оптимизации запроса

1. Перезапись запроса
2. Выбор метода исполнения
3. Выбор структуры запроса
4. Оценка размера и распределения

Перезапись запроса

Преобразование запроса во внутреннюю форму (реляционную алгебру).

Избегая синтаксического сахара и других различных вариантов написания одного и того же запроса, понять, что и как нужно выбрать.

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

​

Выбор метода исполнения

• Преобразование запроса
• Порядок выполнения операций
• Порядок соединений

Выбор структуры исполнения

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

Оценка трудоемкости (EXPLAIN) и свойств операции (как меняются свойства выборки после операции).

Оценка плана

• Модель стоимости
• Стоимость операции
• Размер операндов
• Размер результата
• Оценка размера и распределения
• Статистика по данным
• Статистика предыдущих запросов

Перезапись запроса

Минимизация запроса

Повторное применение фильтрации заменяется одинарным:

​

Повторное применение проекции заменяется внешней:

​

Фильтрация осуществляется до проекции:

​

Дистрибутивность операций

Фильтрация:

Дистрибутивность операций

Проекция:

Обработка условий

Примеры:

Преобразование предикатов

Конъюнктивная нормальная форма:

Слева на право, до первой лжи

Дизъюнктивная нормальная форма:

Слева на право, до первой истины

Семантическая оптимизация

Применение знания об ограничениях:

Не эквивалентные запросы, но тот же результат

Выбор метода исполнения

Цепь (или сеть) операций

• Аргументы операции
• Базовые таблицы
• Результаты других операций
• Результат операций
• Аргумент другой операции
• Окончательный результат

Типы операций

• Контейнеры
• Загружают аргументы
• Сохраняют результаты
• Преобразователи
• Просматривают аргументы в процессе работы

Курсоры

Выдают записи последовательно.

• open() – открыть курсор
• fetch() – следующая строка
• reset() – начать с начала
• close() – закрыть курсор

Фильтрация

• Преобразователь
• Выкидывает ненужные строки
• Трудоемкость
• O(n), где n – размер входа
• Свойства
• Может уменьшать количество строк

Проекция

• Преобразователь
• Выкидывает ненужные атрибуты
• Сравнивает соседние элементы
• Трудоемкость
• O(n), где n – размер входа
• Свойства
• Вход должен быть упорядочен
• Сохраняет порядок

Сортировка

• Контейнер
• Сортировка в памяти
• Внешняя сортировка
• Трудоемкость
• O(nlogn), где n – размер входа
• Свойства
• Выход упорядочен
• Время исполнения зависит от объема

Просмотр таблиц

• Преобразователь и контейнер
• Полный проход по таблице
• Внешняя сортировка
• Трудоемкость
• O(n), где n – размер входа
• Методы исполнения
• Полный просмотр
• Индексы

Объединение

• Преобразователь
• Слияние входов
• Трудоемкость
• O(n), где n – размер входа
• Свойства
• Упорядоченные входы
• Упорядоченный результат

Пересечение

• Преобразователь
• Слияние входов
• Трудоемкость
• O(n), где n – размер входа
• Свойства
• Упорядоченные входы
• Упорядоченный результат

Вложенный перебор

• Преобразователь
• Перебор левого входа
• Перебор правого входа
• Трудоемкость
• O(l·r), где l, r – размеры входов
• Свойства
• Сохраняет упорядоченность

Поиск по индексу

• Преобразователь
• Перебор левого входа
• Доступ к правому входу по индексу
• Трудоемкость
• O(max(l·logr,n)), где l, r – размеры входов, n – выхода
• Свойства
• Сохраняет упорядоченность

Поиск по хэшу

• Преобразователь
• Захэшировать правый вход
• Перебор левого входа
• Доступ по хэшу к правому ходу
• Трудоемкость
• O(max(l+r,n)), где l, r – размеры входов, n – выхода

Итог двух этапов: реальные стратегии

Зная:

• n (количество записей в таблице) из метаданных
• стоимость переписанных операций

можно оценить сложность запроса целиком + предположить занимаемую память.

EXPLAIN

​

Выбор структуры исполнения

Планирование операций

• Унарные:
• Фильтрация – первый приоритет
• Проекция – второй приоритет
• Над множествами не влияют (можно распараллелить)
• Соединения:
• Порядок важен
• Желательно сокращение результата

Порядок соединений

Динамическое программирование на подмножествах.

Можно найти лучший вариант соединения отношений не вычисляя одно и то же несколько раз.

Оценка хранения и распределения данных

Размер и распределение

• Оценка размера
• Какого размера результат
• Поместится ли он в памяти
• Оценка распределения
• Позволяет оценить размер результатов соединения

Типы распределений

• Распределение отношения
• Строки
• Страницы
• Распределение атрибутов
• Значения
• Размер
• Диапазон
• Распределение
• Распределение индексов
• Листы, узлы, высота дерева
• Уникальные значения, корзины

Упрощающие предположения

• Равномерность распределения: равное количество кортежей с равными значениями
• Независимость атрибутов: распределения атрибутов независимы
• Равномерность запросов: запросы ко всем значениям равновероятны
• Равномерность заполнения: страницы содержат равное число кортежей
• Случайность расположения: кортежи распределены по страницам случайным

Оцениваемые значения

• Мат. ожидание числа чтений страниц
• Запрос с одним атрибутом
• Все запросы с одним атрибутом
• Запрос с несколькими атрибутами
• Мат. ожидание количества различных значений в результате фильтрации

Оценка операций

Входные данные:

• Базовые отношения: статистика
• Результаты операций: распределение аргументов + свойства операции

Как СУБД выбирает стратегию

• Доступная память
• Размеры соединяемых отношений
• Доступные индексы
• Нужно ли сортировать
• Распределение данных
• Параллельность выполнения подзапросов

Как пользователь советует СУБД

Подсказки:

SELECT /*+ full(t) */ t.name FROM tbl1 t WHERE ...�SELECT /*+ index(t ind_date) */ t.name FROM tbl1 t WHERE ...�

​

​