Советы по созданию индексов

Четвертая нормальная форма

1НФ запрещает таблицам иметь неатомарные, или многозначные, атрибуты. Однако существует множество ситуаций моделирования, требующих многозначных атрибутов. Например, в групповой системе медицинского страхования необходимо отслеживать нескольких людей, находящихся на иждевении каждого работника. Преподаватель может быть занят в нескольких комиссиях и отвечает за преподавание нескольких предметов. Как можно смоделировать такие ситуации в РБД, запрещающей многозначные атрибуты? Рассмотрим несколько вариантов.

Таблица Факультет с минимальным числом записей

Имя преподавателя	Комиссия	Курс
Иванов	Зачетная	ИМ101
Иванов	Стипендиальная	ИМ102
Иванов	Стипендиальная	ИМ103

Таблица Факультет с минимальным числом записей с пустыми значениями

Имя преподавателя	Комиссия	Курс
Иванов	Зачетная	ИМ101
Иванов	Стипендиальная	ИМ102
Иванов		ИМ103

Таблица Факультет со строками без повторов

Имя преподавателя	Комиссия	Курс
Иванов	Зачетная
Иванов	Стипендиальная
Иванов		ИМ101
Иванов		ИМ102
Иванов		ИМ103

Каждое решение имеет недостатки. Все они требуют лишнего места из-за необходимости вводить избыточные данные. Те, где есть пустые строки, нарушают категорную целостность, так как все атрибуты составляют ключ таблицы. Наконец, не очевидно, что атрибуты Комиссия и Предмет не зависят друг от друга Нельзя ли из первого варианта сделать вывод, что зачетная комиссия каким-то образом зависит от предмета ИМ101? Эти кажущиеся связи между независимыми атрибутами можно исключить, потребовав, чтобы каждое значение атрибута сочеталось с каждым значением другого атрибута как минимум в одной строке

Таблица Факультет с многозначной зависимостью

Имя преподавателя	Комиссия	Курс
Иванов	Зачетная	ИМ101
Иванов	Стипендиальная	ИМ101
Иванов	Зачетная	ИМ102
Иванов	Стипендиальная	ИМ102
Иванов	Зачетная	ИМ103
Иванов	Стипендиальная	ИМ103

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

Таблица имеет 4НФ, если она имеет 3НФ и не содержит МЗЗ. Решить проблему можно, поместив каждый многозначный атрибут в свою собственную таблицу вместе с ключом, от которого атрибут зависит.

Таблица ФакультетКомиссия		Таблица ФакультетПредмет
Имя преподавателя	Комиссия		Имя преподавателя	Предмет
Иванов	Зачетная		Иванов	ИМ101
Иванов	Стипендиальная		Иванов	ИМ102
			Иванов	ИМ103

Теперь ключом каждой из этих таблиц являются оба атрибута таблицы.

Лекция 9

Индексирование баз данных

Индекс (англ. index) — объект базы данных, создаваемый с целью повышения производительности выполнения запросов.

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

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

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

Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск - например, балансированного дерева.

Некоторые СУБД расширяют возможности индексов введением возможности создания индексов по выражениям. Например, индекс может быть создан по выражению upper(last_name) и соответственно будет хранить ссылки, ключём к которым будет значение поля last_name в верхнем регистре.

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

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

Принцип работы индексов

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

Рассмотрим для примера следующий запрос.

SELECT *

FROM TABLE_NAME

WHERE NAME = 'SMITH';

Как показано на рис. 1, для ускорения поиска значений 'SMITH' в таблице используется индекс, построенный по значениям столбца NAME (фамилия). После того, как для фамилии места соответствующих записей в таблице определены, данные могут быть извлечены очень быстро. В индексе данные упорядочены по алфавиту — здесь, например, это касается фамилий.

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

Существует два типа индексов: кластерные и некластерные. У каждой таблицы может быть только один кластерный индекс и множество некластерных.

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

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

Индексы физически могут быть реализованы различными структурами. Наиболее частоупотребимы B+ деревья и хэши.

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

Если используется составной индекс, то поиск по всем атрибутам, входящим в индекс, начиная со второго, будет медленным. Допустим, определен индекс index1(id1, id2), в этом случае поиск значений, удовлетворяющих условию id2=1, будет медленным (не исключено, что оптимизатор вообще не будет использовать этот индекс для обработки данного условия и будет принято решение о полном сканировании данных), а поиск значений, удовлетворяющих условию id1=1 and id2=1, будет быстрым.

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

Неявные индексы — это индексы, создаваемые автоматически сервером базы данных при создании объектов. Например, автоматически создаются индексы для ключей и ограничений типа уникальности. Зачем создаются такие индексы? Пользователь добавляет в базу данных информацию о новом товаре. Код товара является ключом таблицы, и это значит, что код товара должен быть уникальным. Чтобы быстро проверить уникальность вводимого пользователем кода среди сотен или тысяч записей, коды товаров должны быть индексированы. Поэтому при создании ключа или задании условий уникальности автоматически создается соответствующий индекс.

Еще один тип индекса — так называемый двоичный масочный (bitmap). В индексе этого типа двоичная маска формируется на основе набора значений, допустимых для столбца индексируемой таблицы, с учетом их действительных значений, уже внесенных в таблицу. Бит устанавливается в 1, если соответствующее значение из набора допустимых совпадает со значением в данной строке таблицы. В противном случае би­ту присваивается значение 0. Если набор допустимых значений в столбце невелик, то такой масочный ин­декс оказывается значительно более компактным и обрабатывается быстрее, чем традиционный древовид­ный индекс. В табл. приведены примеры двоичных масок для таблицы автомобилей Car. Ключом для индекса является столбец цвета изделия.

Цвет автомобиля Маска

Красный 00010010001000100001

Зеленый 10000001010001001010

Серебристый 00100000100010010000

Белый 00001000000000000100

Черный 01000100000100000000

В таблице, которую мы использовали для примера, имеется 20 строк. В маске каждый бит соответству­ет одной записи и устанавливается в 1, если значение столбца Color (цвет автомобиля) совпадает со значе­нием параметра для этой маски. Таким образом, в строках 4, 7, 11, 15 и 20 автомобили имеют красный цвет, а в строках 2, 6 и 12 — черный. Для определенных типов данных ключевого столбца масочный ин­декс оказывается значительно более эффективным, чем традиционный древовидный.

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

Оптимизатор SQL использует различные типы доступа к данным при обработке запросов, и индексирование существенно влияет на выбор оптимизатора.

Приведем некоторые способы доступа к данным на примере выборки select id, name from xtable where id=10:

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

· Атрибут id индексирован; тип индекса - . Тогда применяется индексное сканирование; полное сканирование может быть выбрано только в случае, если объем данных, удовлетворяющих данному условию, является большим (эта информация анализируется статистическим оптимизатором) и сравним с количеством записей в таблице. Индексное сканирование применяется лишь тогда, когда размер индексированных атрибутов меньше размера кортежа и все необходимые для обработки запроса данные могут быть получены из индекса; в остальных случаях может быть применено полное сканирование.

· Атрибут id входит в составной индекс, и является первым (лидирующим) атрибутом индекса, при этом тип индекса - . Аналогично предыдущему примеру, применяется индексное сканирование.

· Атрибут id входит в составной индекс, он не первый атрибут индекса; тип индекса - . Индексное сканирование применяется лишь тогда, когда размер индексированных атрибутов меньше размера кортежа и все необходимые для обработки запроса данные могут быть получены из индекса; в остальных случаях применяется полное сканирование.

· Атрибут id индексирован; тип индекса - хеш. Здесь применяется индексное сканирование для поиска на =; если бы условие было id <=10, то применение хеш-индекса для такого поиска не эффективно.

· Атрибут id индексирован; тип индекса - bitmap. Здесь применяется индексное сканирование для поиска на =; если бы условие было id <=10, то применение bitmap-индекса для такого поиска не эффективно.

· Атрибут id является ключом хеш-кластера. В этом случае применяется алгоритм хеширования при поиске блока данных для чтения. При хорошем алгоритме и правильном размере кластера поиск может быть осуществлен за одно чтение; при ошибках в выборе алгоритма и блока кластера это может составить до нескольких тысяч операций чтения блоков.

· Атрибут id является ключом индексного кластера. Здесь применяется индексное сканирование, почти аналогично случаю с индексом .

· Таблица кластеризована, id не является ни кластерным ключом, ни лидирующим в составном индексе . В этой ситуации для кластера применяется полное сканирование.

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

Советы по созданию индексов

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

Здесь наилучшей рекомендацией будет метод проб и ошибок. Точно также, как перед использованием базы данных ее нужно протестировать, прежде, чем использовать индексы, протестируйте их. Во время такого тестирования должны быть опробованы различные комбинации индексов, работа без индексов, простые и составные индексы. Для эффективного использования индексов требуется хорошее понимание структуры и связей базы данных, требований запросов и транзакций, да и самих данных.

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

Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмём такой запрос SQL: SELECT first_name FROM people WHERE last_name = 'Франкенштейн';. Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полный скан таблицы», в плане может отображаться словом «NATURAL»). При использовании индекса СУБД просто проходит по двоичному дереву, пока не найдёт запись "Франкенштейн". Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.

Теперь возьмём такой запрос: SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';. Этот запрос должен нам найти всех клиентов, у которых е-мейл заканчивается на "@yahoo.com", однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по бинарному дереву.

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

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

Для OLAP приложений можно добавлять столько индексов, сколько потребуется, т.к. OLAP приложения работают только на чтение из БД.

Индекс создается путем указания имен столбцов, которые нужно в него включить. СУБД выбирает индекс по следующему принципу: один из столбцов, указанных в операторе SELECT, должен быть первым столбцом индекса. В противном случае индекс просто не будет использоваться.

Например, если в базе данных индекс построен на основании двух столбцов Zip_Code (Почтовый индекс) и State (Штат) (причем столбцы перечислены именно в таком порядке) и в базу данных делается запрос на записи о штатах, то указанный индекс использоваться не будет. И чтобы ответить на запрос, СУБД придется найти другой способ выборки строк. Вполне возможно, что придется прибегнуть к сканированию таблицы, что сразу же отрицательно скажется на производительности системы в целом.

Но если в операторе SELECT будет указан только столбец Zip_Code, то СУБД воспользуется индексом, несмотря на то, что в нем тоже определен столбец State. СУБД проигнорирует этот компонент индекса и будет работать без него. В то же время приложение получит существенную выгоду от использования индекса.

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

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

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

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

Если столбец в таблице не содержит по крайней мере 95% уникальных значений, тогда очень вероятно, что Оптимизатор Запроса не будет использовать некластерный индекс, основанный на этом столбце. Поэтому не стоит добавлять некластерные индексы к столбцам, которые не имеют хотя бы 95% уникальных записей. Например, столбец с "Да" или "Нет" не имеет 95% уникальных записей.

Следует избегать создания индексов для таблиц с ключами очень большой длины, поскольку скорость работы с такими таблицами заметно падает из-за больших объемов ввода/вывода

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

SELECT *

FROM ИМЯ_ТАБЛИЦЫ

WHERE GENDER = 'ЖЕН';

Этот запрос вызывает непрерывный поток обращений от таблицы к индексу и наоборот. Из-за того, что условием WHERE GENDER = 'ЖЕН' (или МУЖ) возвращается большой объем данных, серверу базы данных придется постоянно читать сначала данные из индекса, затем соответствующую строку из таблицы и т. д. В данном случае гораздо более эффективным было бы простое сканирование всех данных таблицы, поскольку значительная ее часть все равно должна быть прочитана.

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

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

Не следует использовать индексы для небольших таблиц.

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

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