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

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

^*Кузнецов С.Д. Введение в СУБД. // СУБД. — № 4. — 1995. — С. 98.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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