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

Как уже отмечалось, запросы, являющиеся предписаниями по обработке данных, интерпретируются (или компилируются, т. е. переводятся) машиной данных СУБД в машинные коды и выполняются. При этом, однако, декларативный характер языка SQL («что сделать») приводит к неоднозначности в определении конкретной схемы и конкретного порядка обработки данных (наличию нескольких вариантов «как сделать»). Под оптимизацией запросов понимается такой способ обработки запросов, когда по начальному представлению запроса вырабатывается процедурный план его выполнения, наиболее оптимальный при существующих в базе данных управляющих структурах. Оптимизация осуществляется в соответствии с критериями, заложенными в оптимизатор процессора запросов СУБД.

 

В общей схеме обработки запроса выделяют:

• лексический и синтаксический разбор запроса;

• логическую оптимизацию;

• семантическую оптимизацию;

• построение процедурных планов выполнения запросов и выбор оптимального;

• непосредственное выполнение запроса.

Лексический и синтаксический разбор запроса формируют внутреннее представление запроса, содержащее вместо имен таблиц, полей и связей базы данных их истинные внутренние идентификаторы и указатели, находящиеся в системном каталоге базы данных.

Логическая оптимизация запроса может включать различные эквивалентные преобразования, «улучшающие» представление запроса. Такие преобразования можно разбить на три группы:

• преобразования предикатов сравнения;

• преобразования порядка реляционных операций (соединения, объединения, выборки);

• приведение запросов с подчиненными запросами к запросам на соединение (JOIN).

Преобразования предикатов сравнения, улучшающие в целях оптимизации представление запроса, в свою очередь, разделяются на:

• приведение предикатов сравнения к каноническому виду;

• приведение логического условия сравнения к каноническому виду.

Каноническим называется такой вид предикатов сравнения, который содержит сравнение простых выражений. Можно выделить три типа таких сравнений:

Имя поля Операция сравнения Константное арифметическое выражение;

• Имя поля Операция сравнения Арифметическое выражение;

Арифметическое выражение Операция сравнения Константное арифметическое выражение.

В первом типе под «Константным арифметическим выражением» понимается такое выражение, которое содержит константы и так называемые объемлющие переменные, в любой момент имеющие одинаковое значение в отношении всех

где МРОТ  — объемлющая переменная, определяющая величи­ну минимального размера оплаты труда.

На этом примере легко понять суть последующей оптимизируемости канонических представлений. Правая часть такого сравнения одинакова для всех просматриваемых записей-кортежей и определяется (вычисляется) один раз для всех — razgovorodele.ru. В исходном выражении помимо собственно операции сравнения необходимо при выборке каждого кортежа производить арифметические вычисления, что существенно увеличивает количество операций при выполнении соответствующего запроса.

Во втором типе под «Арифметическим выражением» понимается такое выражение, в котором может присутствовать имя поля другой таблицы, полностью раскрыты скобки, произведено приведение и упорядочение членов. Примером приведения предиката сравнения ко второму оптимизируемому каноническому виду является следующее выражение (сотрудники, оклад которых с учетом вычетов по болезни больше величины минимальной оплаты труда):

где КолДней — переменная, равная количеству рабочих дней в данном месяце.

Примером приведения предиката сравнения к третьему оптимизируемому каноническому виду является следующее выражение (сотрудники, чей оклад после вычета подоходного налога с учетом льгот на иждивенцев в десять раз превышает величину минимальной оплаты труда):

где ИЖД — имя поля той же таблицы «Сотрудники», с данными по количеству иждивенцев для конкретного сотрудника; названия таблицы «Сотрудники» для краткости опущены.

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

Преобразования порядка реляционных операций также направлены на сокращение возможного количества операций при обработке запросов. Одними из наиболее частых реляционных операций в запросах являются операции соединения (JOIN) и операции ограничения (WHERE restriction). В этом отношении общим правилом оптимизирующего преобразования запросов будет замена последовательности операции соединения с последующими ограничениями на предварительные ограничения с последующим соединением:

где А и В имена таблиц.

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

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

Каноническим представлением запроса по данным из n таблиц называется запрос, содержащий n–1 предикат соединения и не содержащий предикатов с подчиненными запросами. Если вернуться к примеру подчиненного запроса с предикатом In, то его эквивалентным оптимизируемым выражением будет следующее:

Логическая оптимизация запросов не учитывает семантики конкретной базы данных, проявляемой в ограничениях целостности на значения полей таблиц и связей между ними. В результате ядро СУБД всякий раз при выполнении логически оптимизированного запроса еще и проверяет ограничения целостности. Часть записей-кортежей, сформированных по результатам операций запроса, при этом может быть отвергнута именно по ограничениям целостности. Семантическая оптимизация запросов основывается на слиянии внутреннего представления запроса и ограничений целостности конкретной базы данных до непосредственного выполнения запроса и призвана за счет совместной проверки ограничений целостности и условий запроса сократить количество выполняемых операций.

Для примера предположим, что в таблице «Сотрудники» по полю «Оклад» наложено ограничение целостности, заключающееся в том, что оклад не может быть меньшим величины минимального размера оплаты труда МРОТ, равного, скажем, 84 руб. Предположим также, что нужно сформировать список сотрудников, чей оклад меньше 50 руб. Соответствующий запрос имеет вид:

Без семантической оптимизации данный запрос будет выполняться следующим образом — будет последовательно извлекаться каждая запись в таблице «Сотрудники» и проверяться на выполнение условия отбора. Результатом выполнения запроса будет пустое множество записей. С учетом внутренней семантической оптимизации в ответ на запрос без последовательного перебора всех записей сразу будет выдано пустое множество записей.

После логической и семантической оптимизации строится процедурный план выполнения запросов. Процедурным планом запроса называется детализированный порядок выполнения операций доступа к базе данных физического уровня. Уже упоминавшаяся многовариантность способов выполнения SQL-инструкций соответственно приводит к набору альтернативных процедурных планов выполнения запросов, среди которых оптимизатор запросов ядра СУБД должен выбрать оптимальный в соответствии с определенными критериями.

Общепринятым критерием оптимальности процедурных планов является минимизация стоимости выполнения запросов. При этом под стоимостью выполнения запроса понимаются вычислительные ресурсы (ресурсы процессора и ресурсы дисковой и оперативной памяти), необходимые для выполнения запросов.

Для иллюстрации вариантности процедурных планов рассмотрим запрос по выборке записей из таблицы «Сотрудники» по возрасту не старше 30 лет и с должностным окладом более 100руб.:

Если по полям «Дата_Рожд» и «Оклад» таблицы «Сотрудники» существуют индексы, то возможны три варианта плана выполнения запроса:

1) последовательно без учета индексации просматривать (сканировать) записи таблицы «Сотрудники» и отбирать записи при выполнении требуемых условий;

2) сканировать индекс поля «Дата_Рожд» с условием вы­борки «>=#01/01/68#», выбирать соответствующие записи из таблицы «Сотрудники» и среди них отбирать те, которые удовлетворяют условию по полю «Оклад»;

3) сканировать индекс поля «Оклад» с условием выборки «>100 руб.», выбирать соответствующие записи из таблицы «Сотрудники» и среди них отбирать те, которые удовлетворяют условию по полю «Дата_Рожд».

Стоимость каждого варианта в конечном счете определяется главным образом количеством пересылаемых страниц (блоков) из файла данных в буферы оперативной памяти ввиду того, что, как уже отмечалось, время операций доступа к конкретным записям в оперативной памяти на несколько порядков меньше времени процессов обмена между внешней и оперативной памятью, и тем самым основные затраты приходятся именно на эту операцию.

Если количество записей в таблице «Сотрудники» невелико и все они умещаются в одной странице (в одном блоке) файла базы данных, то наименее затратным будет первый вариант. Если записи таблицы «Сотрудники» распределены по множеству страниц, менее затратными являются 2-й и 3-й варианты. При этом различия между ними будут определяться так называемой селективностью значений по полям «Дата_Рожд» и «Оклад».

Селективность определяется главным образом характером статистического распределения значений по соответствующим полям. Исходя из мощности (количества записей), вида (равномерное, нормальное) и параметров распределения (среднее значение, максимальное и минимальное значение) можно получить приблизительные оценки количества страниц (блоков) файла базы данных, пересылка которых потребуется в оперативную память в ходе выполнения запроса. Так, если по приведенному примеру имеются некоторые априорные или апостериорные данные о том, что распределение значений по возрасту сотрудников является нормальным со средним значением 27 лет, а распределение величин должностных окладов является равномерным в интервале от 50 руб. до 500 руб., то, очевидно, наименее затратным будет 2-й вариант процедурного плана выполнения запроса, так как потребует меньшего количества пересылок страниц файла базы данных.

Стратегии оптимизатора по оценкам стоимости выполнения запросов могут быть упрощенными (когда статистические распределения любых полей являются по умолчанию равномерными) либо более сложными. В сложных стратегиях при ведении базы данных (добавление, удаление, изменение записей) осуществляется мониторинг за параметрами апостериорных статистических распределений значений по полям базы данных (отслеживается минимальное, максимальное, среднее значение и другие параметры) — razgovorodele.ru. В этом случае оценки стоимости процедурных планов выполнения запросов являются более точными, и тем самым повышается эффективность оптимизации запросов и в целом эффективность обработки данных.