Индексирование. Виды индексов.

Индекс – структура данных определённого вида, которая предназначена для ускорения поиска записи файла данных.

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

Файл данных, для которого существует индекс, называется индексированным, а поле индексированного файла значения, которого используется в индексе наз. индексным полем.

Индекс можно создать как по одному полю, так и по нескольким полям, причем не обязательно относящихсяк первичному ключу.

Основное преимущество использования индекса это значительное ускорения выборки данных. С использованием индекса возможно выполнения последовательного доступа к данным отсортированным по ключу индекса.

Недостатки использования индекса: Замедления обновления файла данных, так как при добавлении новой записи файл данных формируется обновлением индекса, а индекс представляет собой упорядоченный последовательный файл и обновляется медленно.

Индексом можно классифицировать следующим образом:

1. По виду полей данных

– первичный

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

2. По числу использованных полей записей данных

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

- не составной индекс – ключ индекса состоит только из одного поля

3. по числу ссылокна данные:

- плотный индекс, число индексных записей равно числу записей данных. 1 индексссылается на 1 запись

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

4. По числу уровней индекса

- одноуровневый – индекс, который ссылается на сами данные

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

Работа с индексами.

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

Создания индекса не предусмотрено созданием стандарта языка SQL. ОднакоподдерживаютсяследующиеоператорыCreateindex [UNIQUE] indexnameONtablename (column [ASCLDESC])

Указанные в операторе столбцы составляют ключ в индексе, должны быть перечислены в возрастающем или убывающем порядке. Индексы могут создаваться только для таблиц, а не для представления. Если в операторе указано ключевое слово UNIQUE уникальное значения ключа индекса будет поддерживаться автоматически система. Требования уникальности значении обязательно для первичных ключей. Для каждого из ключевых столбцов должен быть указан порядок сортировки значений по возрастанию и по убыванию. Если сортировка не задана, то по умолчанию по возрастающей.
44. Оптимизация запросов в реляционных СУБД.

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

Обработка запроса, поступившего в систему и представленного на некотором языке запросов, состоит из этапов или фаз. На первой фазе запрос, представленный на языке запросов, подвергается лексическому и синтаксическому анализу. При этом вырабатывается его внутреннее представление, отражающее структуру запроса и содержащее информацию, которая характеризует объекты базы данных, упомянутые в запросе (отношения, поля и константы). На второй фазе запрос в своем внутреннем представлении подвергается логической оптимизации. При этом могут применяться различные преобразования, "улучшающие" начальное представление запроса. Среди этих преобразований могут быть эквивалентные преобразования, после проведения, которых получается внутреннее представление, семантически эквивалентное начальному (например, приведение запроса к некоторой канонической форме). Преобразования могут быть и семантическими, когда получаемое представление не является семантически эквивалентным начальному, но гарантируется, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в базе данных. Третий этап обработки запроса состоит в выборе на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов выполнения данного запроса в соответствии с его внутреннем представлением, полученным на второй фазе. Основой является информация о существующих путях доступа к данным. Единственный путь доступа, который возможен в любом случае, – это последовательное чтение (FULL). На этом же этапе для каждого плана оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется либо доступная оптимизатору статистическая информация о состоянии базы данных, либо информация о механизмах реализации различных путей доступа. Из полученных альтернативных планов выбирается наиболее оптимальный с точки зрения некоторого (заранее выбранного или заданного) критерия. На четвертом этапе по внутреннему представлению наиболее оптимального плана выполнения запроса формируется процедурное представление плана. Выполняемое представление плана может быть программой в машинных кодах, если, как в случае System R, система ориентирована на компиляцию запросов в машинные коды, или быть машинно-независимым, но более удобным для интерпретации, если, как в случае INGRES, система ориентирована на интерпретацию запросов. на последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с выполняемым планом запроса. Существуют два принципиально разных подхода к оптимизации запросов. Если оптимизатор основывается только на информации о механизмах реализации путей доступа, то метод оптимизации основан на синтаксисе (на правилах, RULE). Если же помимо этого используется статистическая информация о распределении данных, то это метод оптимизации, основанный на стоимости (на издержках, COST). Рассмотрим эти подходы подробнее.

Методы оптимизации запросов

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

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

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

Критерии оптимизации: 1.Наилучшая общая производительность системы. 2. Минимальное время реакции – время, необходимое для обработки и выдачи первой строки. 3.Минимальные затраты времени на обработку всех строк, к которым обращается данная команда.

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

В Oracle статистика собирается командой ANALYZE, которая имеет два вида – для точного расчёта статистики и для её оценки:

ANALYZE {table | index} <имя> compute statistics;

ANALYZE {table | index} <имя> estimate statistics on <число> {percent | rows};

Если таблица (индекс) небольшая (несколько тысяч строк), то следует рассчитывать статистику, например:

ANALYZE table EMP compute statistics;

Если таблица (индекс) большая, то статистику можно оценить, например:

ANALYZE table EMP estimate statistics on 2000 rows; -- по 2000 строк

ANALYZE index IND_EMP estimate statistics on 20 percent; -- по 20 процентам

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