Лекции и практики (1). Курс лекций и материалы для практических занятий

• Название: Курс лекций и материалы для практических занятий
• Дата: 17.03.2023
• Размер: 1.01 Mb.
• Имя файла: Лекции и практики (1).docx
• Тип: Курс лекций; #996812
• страница: 38 из 75

Лекция 12.Методы оптимизации.

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

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

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

Таблица 8.1. Ранги путей доступа для СУБД Oracle9

Ранг	Пути доступа
1	Одна строка по ROWID*
2	Одна строка по кластерному соединению
3	Одна строка по хеш-кластеру с уникальным или первичным ключом
4	Одна строка по уникальному или первичному ключу
5	Кластерное соединение
6	Ключ хеш-кластера
7	Ключ индексного кластера
8	Составной индекс
9	Индекс по одиночному столбцу (по условию равенства)
10	Индексный поиск по закрытому интервалу
11	Индексный поиск по открытому интервалу
12	Сортировка-объединение
13	MAX и MIN по индексированному столбцу
14	ORDER BY по индексированному столбцу
15	Полный просмотр таблицы

* ROWID (идентификатор строки, КБД) – значение, которое может быть однозначно преоб- разовано в физический адрес записи.

Ранг пути доступа определяется на основании знаний о последовательно-сти реализации этого пути. Например, самый быстрый способ доступа – это чтение по КБД: если он известен, то это одно физическое чтение. А поиск кон- кретного значения через индекс (ранг 9) обычно занимает меньше времени, чем поиск в закрытом интервале значений (ранг 10).

Метод оптимизации по синтаксису учитывает ранги путей доступа. Если для какой-либо таблицы существует более одного пути доступа, то выбирается тот путь, чей ранг выше, т.к. при прочих равных условиях он выполняется быстрее, чем путь с более низким рангом (рис. 8.2).

Рис. 8.2. Построение плана выполнения запроса в методе оптимизации по синтаксису
План выполнения запроса в методе оптимизации по синтаксису формиру- ется из выбранных путей доступа с максимальными рангами.

Оптимизации по синтаксису может приводить к построению неоптималь- ных планов выполнения запроса. Например, для запроса:

select * from emp

where depno>3;

система при оптимизации по синтаксису всегда выберет доступ к таблице empчерез индекс по полю depno. Но если из таблицы по условию (depno>3) выби- рается больше 25% записей, то эффективнее будет прочитать таблицу методом последовательного чтения (FULL), чем читать записи в порядке, определённом индексом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F. Для равномерного распределения это означает, что в первых 10% записей это поле имеет значение от 1 до 10, в следующих 10% записей – от 11 до 20 и т.д.




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

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

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

• 
  столбец не используется в предикатах запросов;
  
• 
  значения столбца уникальны и используются только в предикатах эквива- лентности;
  
• 
  значения столбца распределены равномерно. При равномерном распределе- нии оценку селективности условия можно провести без построения гисто- граммы. Например, для условия (field>limit) по формуле:
  

(high_value – limit) / (high_value – low_value)

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

таблиц для анализа и периодическое обновление статистики данных.

3. 
   Другие возможности управления оптимизацией
   

В качестве дополнения к основным методам оптимизации в некоторых СУБД (например, Oracle, SQL Server и др.) существуют возможности задания подсказок оптимизатору (hints). Подсказки являются указаниями оптимизатору, какие пути доступа к данным следует использовать. Подсказки касаются ис- пользования индексов (INDEX), последовательного чтения (FULL), порядка и методов соединения таблиц и проч.

Подсказки не входят в стандарт, поэтому в разных системах они описы- ваются по-разному. Например, в Oracle подсказки указываются в качестве ком- ментария, который располагается сразу за именем команды (чаще всего – SELECT) и начинается со знака '+', который следует сразу за знаком коммента- рия без пробела:

select --+ INDEX (emp ind_salary)

* from emp

where depno IN (2, 3, 6) AND salary > 75000; select /*+FULL */ depno, ename, salary

from emp

order by depno;

(-- – комментарий до конца строки; /* */ – многострочный комментарий).

В первом запросе указывается подсказка для использования индекса ind_salaryдля таблицы emp (по полю salary). Во втором указывается последовательное чтение (FULL) для подавления использования индекса по полю depno.

Для СУБД SQL Server порядок указания подсказок иной:

select *

from authors with (INDEX(aunmind)); select *

from depart d, emp e, children c

where d.depno = e.depno AND e.tabno = c.tabno OPTION (FORCE ORDER);

В первом запросе указывается подсказка для использования индекса aunmindдля таблицы authors. Во втором закрепляется последовательность соединения таблиц: они будут соединяться в той же последовательности, в которой указаны в части FROM.

В СУБД Oracle11g есть ещё одно дополнительное средство настройки оп- тимизатора: возможность формировать т.н. «базу управления запросами» (SQL management base, SMB) [10]. В этой базе для каждого представляющего интерес запроса можно накапливать историю планов его выполнения, а из неё форми- ровать основную линию (baseline) планов. В основную линию включаются только те планы, которые администратор назначает удовлетворительно произ- водительными.

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

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

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

SELECT *

FROM Emp

WHERE name LIKE 'Иванов%' AND salary<40000;

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

• 
  столбец tabNo определен как PRIMARY KEY, ему соответствует индекс
  

PK_TABNO;

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

SALARY_IND (ранг 11).

Индекс PK_TABNO недоступен, т.к. в запросе нет условий на значение поля

tabNo. Оптимизатор выберет доступ по индексу с рангом 9.

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

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

SELECT *

FROM Emp

WHERE tabNo > 7500;

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

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

SELECT d.name, e.name, salary FROM depart AS d, emp AS e WHERE d.depNo=e.depNo AND

e.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. Затем для каждой строки соединения проверить второе условие.
   

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

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

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