Оптимизатор запросов. Часть первая. Статья из серии статей о СУБД.
ВСТУПЛЕНИЕ.
Данный цикл статей посвящен рассмотрению устройства системы управления базами данных (СУБД). Хотя данное пособие не ставит целью ознакомить читателя с какой-то конкретной СУБД, опираться мы будем, в основном, на СУБД MS SQL. Для того, чтобы процесс обучения был понятен, я постараюсь вводить термины и определения постепенно, по мере углубления в материал.
Введение
Работа оптимизатора запроса является ключевой для обработки данных. Знание того, как оптимизатор выстраивает свою стратегию, отлично помогает при построении запросов.
Для лучшего понимания статьи, необходимо понимать, что такое индексы (кластерные, некластерные), понимание языка манипулирования данными (DML T-SQL). Знать из чего состоит запрос, а именно: Условие; Соединения; Выражения в запросе; Вложенные запросы.
Что такое оптимизатор.
Когда выбираются данные из базы, движок СУБД пытается наилучшим (наиболее быстрым, менее затратным) образом использовать ресурсы. Эту работу выполняет оптимизатор запросов. Задача оптимизатора – это рассмотрение наилучшей стратегии обработки данных. В качестве результата, оптимизатор выдает «План выполнения запроса». При выборе стратегии оптимизатор учитывает очень много факторов – это индексы, условия в запросе (подробно рассмотрим далее) и, так называемую, статистику или, как ее еще называют, статистические данные, содержащую такую информацию как диаграмма состояния таблиц.
Работа оптимизатора.
Работа оптимизатора состоит из нескольких этапов:
- Синтаксический разбор запроса. На этом этапе запрос проверяется правильность написания запроса. Если запрос написан правильно, то строится дерево, на основании текста запроса. Затем проверяется наличие объектов, к которым обращается запрос. После этого, строится окончательное дерево с идентификаторами объектов.
- Компиляция запроса. Дерево компилируется и передается на следующий этап.
- Оптимизация запроса. Оптимизатор анализирует входящее дерево. Ищет аргументы поиска и критерии соединения. Затем решает, какие индексы использовать, какой будет порядок соединения таблиц. И выбирает наилучшую стратегию.
- Исполнение запроса. Сохранение плана запроса и его исполнение
Этапы работы оптимизатора
- Анализ запроса
- Выбор индексов
- Выбор порядка выполнения операций соединения
- Выбор метода выполнения операций соединения
1. Анализ запроса. Это первый этап, на котором определяются:
- Аргументы поиска.
- Операторы OR (ИЛИ).
- Критерии соединения.
Запомните эту последовательность. Разбор происходит именно в такой последовательности. Наиболее значимым для нас, будет Аргумент поиска.
Что такое аргумент поиска? – Это та часть запроса, которая используется в условии и ограничивает конечную выборку данных. Аргументами поиска являются: условие отбора на равенство, операции больше/меньше, операции вхождения в множество. Основным назначением аргументов поиска является возможность использования индексов для ускорения выборки данных.
Например: Год рождения = 1980 - равенство
Годовой доход >= 1 000 000 рублей, - операции Больше равно
Год рождения = 1980 И Рост >= 175см – Логическое умножение и операции Больше равно
Место рождения В (Москва, Воронеж) – вхождение в множество
Что не входит в аргументы поиска? – Операции неравенства, операции отрицания и выражения в левой части условия.
Пример: Год рождения НЕ РАВНО 1980 - неравенство
Место рождения НЕ В (Москва, Нью-Йорк, Воронеж) – оператор отрицания
Годовой доход * 10 >= 1 000 000 – выражение в левой части
Кстати, во многих случаях достаточно произвести небольшие манипуляции с запросом и результат может ускориться в разы. Вернувшись к нашему примеру, если мы переделаем условие: Годовой доход * 10 >= 1 000 000 на Годовой доход >= 100 000, то есть заменим выражение в левой части на простую выборку, то получим аргумент, который может использовать индекс. Так происходит потому, что выражения рассчитываются после выборки и потом на них накладывается условие. Тоже самое и с отрицанием: сначала необходимо выбрать данные и только потом, сравнивая с условием, откинуть ненужное. Поэтому там, где нет аргументов поиска, происходит сканирование таблицы (описано далее). Если же в условии стоит равенство, то его можно отобрать по индексу (если он установлен). Запомните это правило. Если есть возможность – используйте равенство.
Операторы OR - логически складывает условия и может, но не обязательно, создать еще одну выборку.
Критерии соединения – это, фактически, выбор порядка выполнения операций соединения и выбор метода выполнения операций соединения, которые и будут рассмотрены далее.
2.Выбор индексов. Это второй этап работы оптимизатора. На этом этапе оптимизатор ищет наличие индекса/ов, используя аргументы поиска, и решает - использовать индекс или нет. Выбор решения зависит от селективности выражения и статистических данных. Селективность – это отношение количества выбираемых строк, к общему количеству строк в таблице.
Для углубления в тему, давайте рассмотрим селективность выражения с индексированным столбцом, а затем «Статистические данные».
2.1.Селективность выражения с индексированным столбцом.
Когда оптимизатор строит план по выполнению запроса, он рассматривает возможность использования индексов. На его решение влияет не только то, есть индекс у поля/полей выборки, но также и целесообразность использования индекса. Если оптимизатор решил, что индекс лучше не использовать, то он просто сканирует страницы. Сканирование – это последовательное считывание страниц, в которых содержатся данные, и отбор нужных записей. В отличии от сканирования, доступ по индексу читает или записывает данные, используя индекс. Как правило, доступ по индексу работает быстрее, чем простое сканирование, разумеется, при условии хорошей селективности выражения.
Доступ по индексу бывает двух типов: Доступ по кластерному индексу и доступ по некластерному индексу. При доступе по кластерному индексу, система сканирует индекс и переходит к записи, которая хранится в листьях дерева индекса. При доступе по некластерному индексу могут возникнуть две ситуации: когда в таблице есть кластерный индекс и когда в таблице нет кластерного индекса. В случае, когда в таблице нет кластерного индекса, то обход начинается с некластерного индекса и заканчивается переходом к записи по идентификатору строки, хранящимся в листе дерева. Когда же есть кластерный индекс, то после прохода по некластерному индексу, оптимизатор сканирует кластерный индекс и переходит непосредственно к записи. Здесь важно понять: когда некластерный индекс заставляет прыгать туда-сюда – от индекса к данным, да еще и двумя разными способами, то проход по кластерному индексу всегда заканчивается данными.
2.2.Статистические данные. Существуют статистические данные индекса и статистические данные столбца. Давайте рассмотрим их подробней.
2.2.1.Статистические данные индекса создаются при создании индекса. Помимо создания дерева индекса, система создает гистограмму. В этой гистограмме отображается количество точных совпадений строк для каждого интервала, среднее количество строк с разными значениями в каждом интервале, плотность значений и много еще различной информации. Эти данные позволяют искать наиболее оптимальное решение для оптимизатора.
2.2.2.Статистические данные столбца. Система может создавать статистику для столбца, точно также, как она создает статистику для индекса. Это бывает, когда столбец используется в условии WHERE (ГДЕ). Такая статистика может помочь при выборке по составному условию. Например, когда одно поле индексировано, а второе не имеет индекса, но имеет статистику. Тогда при выборке можно использовать помимо индекса еще и статистику поля.
По мере изменения данных столбца, статистические данные индекса устаревают. Устаревшие статистические данные могут в значительной мере отрицательно влиять на производительность запроса. Поэтому статистику необходимо обновлять. Неправильная статистика приводит к неправильным расчетам оптимизатора, а это влияет на выбор стратегии. Помните об этом.
3. Выбор порядка выполнения операций соединения. Некоторые считают, что порядок соединения таблиц будет таким же, как он описан в запросе. Если честно, то это никак не влияет на то, в каком порядке таблицы будут соединяться. Оптимизатор принимает решение на основе многих факторов. Это и количество строк в выборке каждой таблицы, и степень сложности выборки строк, и плотность данных в станицах и т.д. Некоторые СУБД позволяют использовать подсказки для оптимизатора (hints), в которых можно приказать оптимизатору соединять таблицы в определенном порядке. Но это тема не для данной статьи.
4. Выбор метода выполнения операций соединения. Соединения таблиц может выполняться следующими методами:
4.1. Вложенный цикл (nested loops)
4.2. Соединение слиянием (merge connection)
4.3. Соединение хешированием (hash connection)
Вложенный цикл. Использование вложенного цикла основано на полном переборе строк таблиц. То есть, выбирая строку одной таблицы, перебираются все строки соединяемой таблицы. Можно заметить, что если таблицы не проиндексированы, то выборка будет очень накладной. Если в одной таблице N строк, а в соединяемой K строк, то результат прохода = N * K, то есть первая таблица будет сканирована один раз, а соединяемая столько раз, сколько строк в первой таблице. При полном переборе строки сначала сравниваются и, если они соответствуют условию соединения, попадают в результирующий набор
Соединение слиянием. Соединение слиянием подразумевает, что строки соединяемых таблиц предварительно физически упорядочены по полю соединения. Происходит сканирование двух таблиц и сопоставление строк по одинаковым значениям в полях соединения. Единственной проблемой при соединении слиянием может быть случаи, когда строки в таблицах не отсортированы. Иногда, при рассмотрении запроса, бывали случаи, когда простая сортировка полей соединения давала прирост производительности. (Правда, для этого нужно, все таки, глянуть на план выполнения запроса. А потом принимать решение). Соединение слиянием гораздо эффективнее вложенного цикла.
Соединение хешированием.
Метод соединения хешированием обычно применяется при отсутствии индексов для столбцов соединения. В случае использования этого метода обе соединяемые таблицы рассматриваются как два потока ввода: компонуемый ввод и контрольный ввод. (В качестве компонуемого ввода обычно используется наименьшая таблица.) Процесс работает следующим образом:
1. Значение соединяемого столбца из строки компонуемого ввода сохраняется в определенном сегменте хеша в зависимости от числа, возвращаемого алгоритмом хеширования.
2. После обработки всех строк из компонуемого ввода начинается обработка строк из контрольного ввода.
3. Каждое значение соединяемого столбца строки из контрольного ввода обрабатывается с использованием того же самого алгоритма хеширования.
4. Соответствующие строки извлекаются из каждого сегмента хеша и затем используются для создания результирующего набора.
Это соединение используется для неиндексируемых столбцов. Поэтому, если вы видите в плане запроса данный вид соединения, то это может служить определенной подсказкой для создания индексов.
Вот, собственно, и заканчивается первая часть описания работы оптимизатора. Во второй части будут более подробно рассмотрены создания планов запроса и их анализ.
