Метод оптимизации, основанный на стоимости

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

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

Из множества возможных планов выполнения запроса оптимизатор в соответствии с критерием выбирает лучший план (рис. 7.3).

В качестве критерия оптимизации может выступать:

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

Рис.7.3. Построение плана выполнения запроса в методе оптимизации по стоимости

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

Стоимость плана выполнения запроса определяется на основании сведений о распределении данных в таблицах, к которым обращается команда, и связанных с ними кластеров и индексов. Эти сведения о распределении значений данных называются статистикой и хранятся в словаре-справочнике данных. Для таблицы статистика может включать в се-бя:

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

Для каждого индекса статистика может содержать такие данные, как:

• общее количество проиндексированных записей (оно может быть меньше, чем количество записей в таблице, т.к. null-значения не индексируются);
• минимальное и максимальное индексированные значения;
• количество различных индексированных значений.

Распределение значений в столбце может быть отражено с помощью гистограммы, которая также входит в статистику. Для этого всё множество значений столбца упорядочивается и разбивается на N интервалов. На рис. 7.4 приведено разбиение на N =10 интервалов множества значений некоторого столбца F. Для равномерного распределения это означает, что в первых 10% записей это поле имеет значение от 1 до 10, в следующих 10% записей – от 11 до 20 и т.д.

Рис.7.4. Примеры равномерного (а) и неравномерного (б) распределения значений

Гистограмма помогает оценить объём данных, удовлетворяющих усло-вию запроса. На рис. 7.4,б представлено неравномерное распределение дан-ных для некоторого столбца F. В словарь-справочник данных записываются полученные значения (1, 4, 4, 5, 6, 10, 11, 20, 35, 60, 100). При анализе запроса, например, с условием (F<=5) система сможет по этой гистограмме определить, что через индекс придётся выбрать не менее 30% записей таблицы.

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

Построение гистограммы бесполезно в следующих случаях:

• значения столбца распределены равномерно;
• столбец не используется в предикатах запросов;
• значения столбца уникальны и используются только в предикатах эквива-лентности.

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

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

Рассмотрим оптимизацию по синтаксису следующего запроса SQL:

Пример 7.2. Запрос, выбирающих всех сотрудников по фамилии 'Иванов' с зарплатой менее 40000 рублей:

SELECT *FROM EmpWHERE name LIKE 'Иванов%' AND salary

Пусть таблица Emp имеет следующее правило целостности и индексы:

• столбец tabNo определен как PRIMARY KEY, ему соответствует индекс PK_TABNO;
• существует индекс NAME_IND для столбца name;
• существует индекс SALARY_IND для столбца salary.

Возможны следующие пути доступа:

• полный просмотр таблицы (ранг 15);
• доступ по одиночному индексу NAME_IND. Этот путь становится доступным по условию name LIKE 'Иванов%' (ранг 9);
• доступ с помощью открытого интервала salary

Индекс PK_TABNO недоступен, т.к. в запросе нет условий на значение поля tabNo. Оптимизатор выберет доступ по индексу с рангом 9.

Теперь рассмотрим примеры оптимизации по стоимости.

Пример 7.3. Запрос, выбирающий сотрудников с номерами больше 7500:

SELECT * FROM EmpWHERE tabNo > 7500;

Статистика для столбца tabNo, в частности, включает значения HIGH_VALUE и LOW_VALUE (максимальное и минимальное значения). Если нет гистограммы, то оптимизатор предполагает, что значения равно-мерно распределены в интервале [LOW_VALUE, HIGH_VALUE], и может определить процент значений, попадающий в интервал до 7500. Доступ будет осуществляться по индексу, если этот процент невысок, например, не более 10, хотя конкретное пороговое значение зависит и от других параметров, например, количества записей в блоке памяти.

Пример 7.4. Запрос, выбирающий название отделов (name из таблицы De-part) и всех сотрудников с максимальной зарплатой в своём отделе (name, salary из таблицы Emp):

SELECT d.name, e.name, salaryFROM depart AS d, emp AS eWHERE d.depNo=e.depNo ANDe.salary=(SELECT max(salary) FROM emp AS p WHERE p.depNo=e.depNo);

Для таблиц есть индексы по первичным ключам (Depart.depNo и Emp.tabNo) и по внешнему ключу (Emp.depNo).

Этот запрос можно выполнить по разным планам, например:

1. Выбрать все записи из таблиц Emp и Depart, соединить их по условию d.depNo=e.depNo, затем для каждой полученной строки посчитать подзапрос (выбрать максимальную зарплату для данного отдела, обра-тившись к таблице Emp по индексу) и проверить второе условие.
2. Выбрать все записи из таблицы Emp, для каждой записи найти соответствие по условию d.depNo=e.depNo в таблице Depart через индекс по первичному ключу (на поле depNo), затем для каждой полученной строки посчитать подзапрос и проверить второе условие.
3. Выбрать все записи из таблицы Emp, каждую запись соединить по усло-вию d.depNo=e.depNo с таблицей Depart через индекс по первично-му ключу (на поле depNo). Предварительно посчитать подзапрос, добавив в него условие группировки по номерам отделов GROUP BY depNo. Затем для каждой строки соединения проверить второе условие.

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

Третий план от второго отличается предварительным вычислением подзапроса. Это позволит один раз построить агрегированные значения (по количеству отделов). А во втором запросе агрегированные значения будут строиться для каждого сотрудника. Т.е. чем больше сотрудников в одном отделе, тем больше выигрыш по времени в третьем запросе.

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

Настройка приложений

Цель настройки приложений – повышение эффективности работы с БД. В настройку приложений входит:

• создание индексов;
• настройка команд SQL;
• выбор метода оптимизации SQL-запросов;
• использование средств сбора статистики.

Первый пункт мы уже обсуждали (см. разделы 4.5.2).

Настройка команд SQL, которые используются в приложениях к БД, – это один из основных способов повышения производительности системы. Эта настройка должна производиться каждым разработчиком программного обеспечения.

Для оптимизации приложений необходимо иметь представление о порядке и механизмах реализации запросов в СУБД. Основные информационные потоки между пользователями, оперативной памятью и базой данных приведены на рис. 7.5. В ОП для каждого сеанса связи с БД выделяется специальная область – курсор, куда помещается результат выполнения последнего (текущего) запроса пользователя.

Рис.7.5. Информационные потоки в БД

Приведем основные рекомендации по написанию запросов, удобных для оптимизатора и эффективных при выполнении.

1. Если запрос содержит несколько условий, то они должны располагаться в порядке уменьшения селективности.

Например, для получения списка сотрудниц второго отдела при условии, что во втором отделе сотрудников около 5% от общего числа сотрудников, а женщин на предприятии – примерно половина, запрос должен выглядеть так:

SELECT * FROM empWHERE depNo=2 AND sex='ж';

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

Например, список пациентов по отделениям №№1,2:

SELECT * FROM patients p, depart dWHERE d.id IN (1,2) AND p.depNo=d.id;

1. Если запрос содержит условие с неопределённой лидирующей частью типа (field LIKE '%…') или (field LIKE '_…'), то необходимо дополнять это условие так, чтобы система могла воспользоваться индексом по полю field (если он существует).

Например, список всех хирургов:

SELECT * FROM doctorsWHERE special>'A' AND special like '%хирург%';

Здесь условие special>'A' не исключает из поиска ни одной записи таблицы, но позволяет системе проводить этот поиск по индексу, который занимает гораздо меньше памяти, чем сама таблица.

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

Например, запрос на выборку названия отделения №3:

SELECT name FROM departWHERE id*1=3;

id – это первичный ключ, по нему есть индекс. Но при доступе через индекс потребуется минимум два обращения к диску. Включение индексированного поля в выражение (id*1 вместо id) подавляет использо-вание индекса.

1. Следует использовать UNION ALL вместо UNION, если в объединяемых отношениях отсутствуют одинаковые записи (или наличие одинаковых записей некритично). Дело в том, что UNION вычисляется путем сортировки, которая может занять много времени, а UNION ALL сортировки не требует.
2. Следует использовать IN вместо EXISTS, если EXISTS не оптимизируется. Например, список сотрудников, у которых есть дети:

SELECT * FROM empWHERE empNo in (SELECT empNo FROM children);

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

SELECT DISTINCT e.* FROM Emp AS е, Children AS сWHERE с.empNo=e.empNo;

1. Если оптимизатор плохо оптимизирует операцию "или" (OR), то можно заменять её операцией UNION при наличии индексов. Убедиться в "плохой оптимизации" можно так: выполнить запрос по условию (field=X) и запрос с условием ((field=X) OR (field=Y)) на большой таблице. Если второй запрос выполняется намного дольше, чем первый, то OR не оптимизируется. Например, список "Пациенты палат №3 и пациенты, больные гриппом" в отсутствие индексов можно сформулировать так:

SELECT * FROM PatientsWHERE room=3 OR diagnose LIKE 'грипп%';

а если индексы есть, то таким:

SELECT * FROM PatientsWHERE room=3UNION ALLSELECT * FROM PatientsWHERE diagnose LIKE 'грипп%';

1. Условие "не равно" ('<>') также подавляет использование индекса. Поэтому, если значения индексированного столбца распределены неравномерно, следует заменять его комбинацией условий '<' OR '>' и, с учетом предыдущего правила, реализовывать это с помощью UNION.

Например, список сотрудников всех отделов (10% от общего числа), кроме сотрудников центрального офиса (отдел №3) будет выглядеть так:

SELECT * FROM EmpWHERE deptNo3;

1. 9. Некоторые оптимизаторы будут использовать индексное сканирование, если запрос содержит раздел ORDER BY с указанием индексированного столбца. Для выполнения следующего запроса будет использован индекс на столбце tabNo, даже если этот столбец не используется в условиях раздела WHERE:

SELECT * FROM empWHERE depNo

1. Условие <выражение1> op <выражение2>, где op – операция, также не позволяют использовать индекс. Из выражений надо по возможности вынести в левую часть поле, по которому есть индекс. Например, условие (salary*0.87>30000) лучше записать так: salary>30000/0.87.

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

Многие СУБД позволяют просмотреть план выполнения запроса средствами администрирования. Так можно убедиться в том, что система использует поостренные индексы для выполнения запросов.

	"Сложная система, спроектированная наспех, никогда не работа-ет, и исправить её, чтобы заставить работать, невозможно".
	Законы Мерфи. 16-й закон системантики