Таблицы могут иметь большое количество строк. А, так как строки не упорядочены, то поиск по указанному значению может потребовать значительного времени. Использование индексов позволяет ускорить процесс чтения требуемых записей. INDEX - это упорядоченный список определенных столбцов или групп столбцов в таблице. Когда создается индекс по одному или нескольким полям, то сервер БД формирует соответствующий упорядоченный список. Таблица, конечно же, должна уже быть создана и должна содержать имена индексируемых столбцов.
CREATE INDEX
Добавление индекса снижает производительность запросов, связанных с добавлением, изменением или удалением данных, поскольку каждый раз при выполнении транзакции данные индекса также обновляются, что требует выполнения от сервера дополнительной работы. Однако выполение запросов SELECT по индексируемым полям существенно перевешивают эти недостатки. Не следует создавать индексы по каждому столбцу таблицы, не определив, какие запросы будут выполняться.
Индекс может быть уникальным unique index , что не позволяет иметь в таблице дублированных записей с одинаковыми значениями индексируемых полей.
ПРИМЕЧАНИЕ: при создании уникального индекса транзакция будет отклонена, если уже имеются идентичные значения в записях таблицы по индексируемым полям. Для уникального индекса таблицы с несколькими полями комбинация значений должна быть единственной, но каждое из значений поля может и не быть уникальным.
Ограничения "primary key" и unique index обеспечивают уникальность значений полей таблицы, в которой они определены. По умолчанию primary key создает кластерный индекс на столбце, а "unique index" - некластерный. Другим отличием является то, что "primary key" не может иметь нулевых записей, т.е. поле NOT NULL, в то время как "unique index" допускает только одну нулевую запись (NULL). Таблица может иметь только один первичный ключ, но несколько "unique index".
Удаление индекса не воздействует на содержание полей. Синтаксис оператора удаления индекса drop index:
DROP INDEX
В разных СУБД имеются существенные различия по использованию оператора alter index . Так например MySQL не поддерживает данный оператор, в Interbase можно использовать данный оператор для отключения и повторного включения индекса, в результате чего будет выполнена переиндексация данных.
В СУБД PostgresSQL индекс можно переименовать с использованием оператора alter index . Синтаксис переменования индекса:
Переименование индекса в СУБД PostgresSQL ALTER INDEX index_name RENAME TO index_name_new;
Платформа Oracle также поддерживает инструкцию alter index . Данный оператор используется для изменения или перестройки существующего индекса без его удаления и повторного создания.
Синтаксис оператора для переименования индекса в Oracle имеет следующий вид:
Переименование индекса в СУБД Oracle ALTER INDEX index_name RENAME TO index_name_new;
Для переиндексации данных необходимо использовать следующий синтаксис оператора alter index :
ALTER INDEX index_name [ coalesce | [ rebuild | rebuild online ] ];
При использовании coalesce таблица не блокируется и переиндексация выполняется online. При этом индекс размещается в пределах существующей индексной структуры - соединяет блоки листа в пределах имеющихся ветвей дерева. Индексные листовые блоки быстро освобождаются для использования и не требуется много дискового пространства.
Однако coalesce генерирует много записей в журналах повторного выполнения (redo). При этом данный операнд может вызвать ошибку ORA-01555 (coalesce определяет "работу" Oracle с листовыми блоками, определенных количеством малых транзакций. А много малых транзакций, выполненных одной сессией, могут вызвать у другой сессии, выполняющей продолжительную транзакцию, эту ошибку). Кроме этого coalesce не опускает HWM индекс, т.е. место на диске не освобождает и не может переместить индекс в другое табличное пространство.
Использование rebuild позволяет быстро перемещать индекс в другое табличное пространство. Кроме этого "rebuild" создает новое дерево и уменьшает его высоту при необходимости. А также дает возможность быстро изменять storage и tablespace параметры, без необходимости удалять индекс. Может быть использован для уменьшения расходования ресурсов - передвигается отметка HWM.
Однако rebuild связан с более высокими издержками - требуется больше дискового пространства, чтобы разместить старый и новый индекс в соответствующем табличном пространстве. Кроме этого rebuild может вызвать ошибку ORA-01410: Invalid ROWID.
Rebuild "offline" может использовать существующий индекс для создания новой версии индекса, но блокирует таблицу во время выполнения.
Rebuild "online" не блокирует таблицу во время непосредственной перестройки индекса, и индекс доступен практически все время при перестроении, кроме времени переключения. Однако при этом блокируется таблица в начале и в конце перестроения. При этом старый индекс не используется для перестроения индекса, но с ним работают пользователи. Все изменения тем временем вносятся в журнальную таблицу, затем уже будут перенесены в новый индекс. Может потребоваться большая сортировка.
Таким образом, оператор coalesce особенно эффективен, когда процент проблематичного пространства к общему индексному пространству невелик (20% листовых блоков) и фрагментирован индекс несущественно. rebuild особенно эффективен, когда процент проблематичного пространства к общему индексному пространству велик и средняя степень фрагментации в пределах индексного блока листа сравнительно высокая.
В Oracle имеется несколько типов индексов:
· древовидные индексы (В-деревья).
· хешированные индексы (hash ).
· индексы на основе битовых карт или битовые индексы (bitmap ).
В-деревья были реализованы в Oracle практически с самого начала ее существования, затем появились хешированные индексы появились, а затем - битовые карты.
Понимание того, когда и где следует использовать конкретные типы индексов, очень важно для эффективного их применения. В-деревья используются наиболее часто, в то время как хешированные и битовые индексы лишь при наличии некоторых условий могут обеспечить существенные преимущества в выполнении определенных запросов.
Оператор создания индекса использует следующий синтаксис:
СREATE INDEX имя_индекса
ON имя_таблицы (имя_столбца, [¼])
Для удаления индекса используется команда
DROP INDEX <ИМЯ> (удалить)
Можно перестроить существующий индекс без его удаления и повторного создания при помощи команды:
ALTER INDEX<ИМЯ> REBUILD (перестроить индекс)
ALTER INDEX<ИМЯ> UNUSABLE (отключить индекс на время,
чтобы снова включить обратно при помощи REBUILD)
B-деревья
Видимо, наиболее популярным подходом к организации индексов в базах данных является использование техники B-деревьев. B-дерево содержит по одному индексному элементу для каждой строки таблицы, в которой имеется непустое (NOT NULL) индексное значение. С точки зрения внешнего логического представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти (рис.5.3).
Рис. 5.3 - Древовидный индекс по текстовому столбцу
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
В типовом случае структура внутренней страницы выглядит следующим образом:
При этом выдерживаются следующие свойства:
ключ(1) <= ключ(2) <= ... <= ключ(n);
в странице дерева Nm находятся ключи k со значениями ключ(m) <= k <= ключ(m+1).
Листовая страница обычно содержит значение индекса и идентификаторы строк (ROWID) и имеет следующую структуру:
Листовая страница обладает следующими свойствами:
· ключ(1) < ключ(2) < ... < ключ(t);
· сп(r) - упорядоченный список идентификаторов кортежей (tid), включающих значение ключ(r);
· листовые страницы связаны одно- или двунаправленным списком.
Поиск в B-дереве - это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной log n (m). Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.
Основной "изюминкой" B-деревьев является автоматическое поддержание свойства сбалансированности. Рассмотрим, как это делается при выполнении операций занесения и удаления записей.
При занесение новой записи выполняется:
· Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B-дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.
· Помещение записи на место. Естественно, что вся работа производится в буферах оперативной памяти. Листовая страница, в которую требуется занести запись, считывается в буфер, и в нем выполняется операция вставки. Размер буфера должен превышать размер страницы внешней памяти.
· Если после выполнения вставки новой записи размер используемой части буфера не превосходит размера страницы, то на этом выполнение операции занесения записи заканчивается. Буфер может быть немедленно вытолкнут во внешнюю память, или временно сохранен в оперативной памяти в зависимости от политики управления буферами.
· Если же возникло переполнение буфера (т.е. размер его используемой части превосходит размер страницы), то выполняется расщепление страницы. Для этого запрашивается новая страница внешней памяти, используемая часть буфера разбивается, грубо говоря, пополам (так, чтобы вторая половина также начиналась с ключа), и вторая половина записывается во вновь выделенную страницу, а в старой странице модифицируется значение размера свободной памяти. Естественно, модифицируются ссылки по списку листовых страниц.
· Чтобы обеспечить доступ от корня дерева к заново заведенной странице, необходимо соответствующим образом модифицировать внутреннюю страницу, являющуюся предком ранее существовавшей листовой страницы, т.е. вставить в нее соответствующее значение ключа и ссылку на новую страницу. При выполнении этого действия может снова произойти переполнение теперь уже внутренней страницы, и она будет расщеплена на две. В результате потребуется вставить значение ключа и ссылку на новую страницу во внутреннюю страницу-предка выше по иерархии и т.д.
· Предельным случаем является переполнение корневой страницы B-дерева. В этом случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т.е. его глубина увеличивается на единицу.
При удалении записи выполняются следующие действия:
· Поиск записи по ключу. Если запись не найдена, то удалять ничего не нужно.
· Реальное удаление записи в буфере, в который прочитана соответствующая листовая страница.
· Если после выполнения этой подоперации размер занятой в буфере области оказывается таковым, что его сумма с размером занятой области в листовых страницах, являющихся левым или правым братом данной страницы, больше, чем размер страницы, операция завершается.
· Иначе производится слияние с правым или левым братом, т.е. в буфере производится новый образ страницы, содержащей общую информацию из данной страницы и ее левого или правого брата. Ставшая ненужной листовая страница заносится в список свободных страниц. Соответствующим образом корректируется список листовых страниц.
· Чтобы устранить возможность доступа от корня к освобожденной странице, нужно удалить соответствующее значение ключа и ссылку на освобожденную страницу из внутренней страницы - ее предка. При этом может возникнуть потребность в слиянии этой страницы с ее левым или правыми братьями и т.д.
· Предельным случаем является полное опустошение корневой страницы дерева, которое возможно после слияния последних двух потомков корня. В этом случае корневая страница освобождается, а глубина дерева уменьшается на единицу.
Как видно, при выполнении операций вставки и удаления свойство сбалансированности B-дерева сохраняется, а внешняя память расходуется достаточно экономно.
Проблемой является то, что при выполнении операций модификации слишком часто могут возникать расщепления и слияния. Чтобы добиться эффективного использования внешней памяти с минимизацией числа расщеплений и слияний, применяются более сложные приемы, в том числе:
· упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;
· переливания, т.е. поддержание равновесного заполнения соседних страниц;
· слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.
Следует заметить, что при организации мультидоступа к B-деревьям, характерного при их использовании в СУБД, приходится решать ряд нетривиальных проблем. Конечно, грубые решения очевидны, например монопольный захват B-дерева на все выполнение операции модификации. Но существуют и более тонкие решения.
Сбалансированное дерево автоматически не уравновешивает распределение ключей в пределах дерева так, чтобы половина ключей находилась бы на одной стороне В-дерева, а другая половина - на другой. Очевидно, что нет необходимости перестраивать дерево всякий раз, когда добавляются или удаляются ключи. Однако если ключи добавляются или удаляются только на одной стороне дерева, то распределение индексных ключей может стать неравномерным, с изрядным числом разреженных и даже опустошенных блоков по одну сторону дерева. В этом случае индекс рекомендуется перестроить.
На В-деревьях для извлечения данных по запросу может использоваться механизм быстрого полного просмотра (fast full scan ). Этот механизм дает существенные преимущества, если все запрошенные из конкретной таблицы данные могут быть получены только из индекса. При быстром полном просмотре эффективный многоблочный ввод/вывод, обычно применяемый для полных просмотров таблиц, используется для прочтения всех листовых блоков В-дерева. Поскольку число листовых блоков индекса, скорее всего, намного меньше, чем блоков данных в таблице, для выполнения запроса требуется просмотреть меньшее число блоков. Поэтому просмотр индекса совершится значительно быстрее, чем полный просмотр таблицы, хотя иногда неравномерное распределение ключей снижает эффективность быстрого полного просмотра, поскольку требуется просмотреть большее число листовых блоков (содержащих малое или вообще нулевое число элементов). При этом следует учитывать наличие или отсутствие в таблице пустых значений, которые, как было сказано выше, в индекс не заносятся.
В-деревья можно использовать для поиска данных, как по условиям равенства, так и по условиям неравенства. Это единственный тип индексов, который можно использовать для предикатов неравенства: LIKE, BETWEEN, “>”, “>=”, “<”, “<=”. Исключение представляет случай использования предиката LIKE при сравнении с шаблоном вида ‘%выражение’ или ‘_выражение ’. В-деревья хранят только непустые значения ключей, так что можно построить разреженное В-дерево.
Платформа Oracle позволяет с помощью инструкции CREATE INDEX создавать индексы по таблицам, секционированным таблицам, кластерам и индекс-таблицам (index-organized tables), а также скалярным атрибутам объектов объектных таблиц (typed table) и столбцам вложенных таблиц. Платформа Oracle также позволяет использовать несколько типов индексов, в том числе обычные иерархические (B-tree) индексы, индексы на основе битовых карт (BITMAP) (используются для столбцов, в которых каждое значение повторяется 100 и более раз), секционированные индексы, индексы, связанные с функцией (основанные на выражении, а не на значении в столбце), и предметные индексы (domain index).
Имена индексов Oracle должны быть уникальны в пределах схемы, а не только в пределах таблицы, с которой они связаны.
Платформа Oracle также поддерживает инструкцию ALTER INDEX. Она используется для изменения или перестройки существующего индекса без его удаления и повторного создания.
Синтаксис инструкции CREATE INDEX в Oracle следующий.
CREATE INDEX имя_индекса {ON
{имя_таблицы ({столбец | выражение} [, …]) [{INDEXTYPE IS
тип_индекса | NOPARALLEL] | CLUSTER имя_кластера |
FROM имя_таблицы WHERE условие } [{LOCAL секционирование |
GLOBAL секционирование}] [параметры_физических_атрибутов] [{LOGGING | NOLOGGING}]
[{TABLESPACE имя_табличного_пространства DEFAULT}] [{COMPRESS int | NOCOMPRESS}] [{NOSORT |
SORT}] [{PARALLEL | NOPARALLEL}]
Синтаксис инструкции ALTER INDEX следующий.
ALTER INDEX имя_индекса
{{ENABLE | DISABLE} | UNUSABLE | RENAME TO новое_имя_индекса COALESCE] MONITORING USAGE | UPDATE BLOCK REFERENCES |
PARAMETERS ("параметры_00С1") | параметры_изменения_секционирования_индекса | параметры_перестройки |
)] ] [{PARALLEL | NOPARALLEL}] [{LOGGING | NOLOGGING}]
[параметры_физических_атрибутов]}
Где предложения, не входящие в стандарт ANSI, таковы:
Вместо индексирования каждой строки для каждого значения индекса создается битовая карта. Битовые карты лучше всего использовать для таблиц с небольшим числом конкурентных запросов, например таблиц с высокой интенсивностью чтения. Индексы на основе битовых карт несовместимы с индексами с глобальным секционированием, предложением INDEXTYPE и индекс-таблицами (index-organized table) без связи с таблицей соответствия (mapped table).
ASC | DESC
Определяет расположение значений индекса в восходящем (ASQ или нисходящем (DESQ порядке. Если предложение опущено, по умолчанию принимается ASC. Однако помните, что Oracle считает индексы с предложением DESC индексами, основанными на функции, так что между индексами с предложением ASC и индексами с предложением DESC есть некоторые функциональные различия. Предложения ASC и DESC нельзя использовать совместно с предложением INDEXTYPE. Предложение DESC игнорируется при использовании индексов на основе битовых карг (BITMAP).
INDEXTYPE IS munjuidenca
Создается индекс определенного пользователем типа тип_индекса. Предметные индексы (domain index) требуют, чтобы пользовательский тип уже существовал (обращайтесь к разделу «Инструкция CREATE/ALTER TYPE»). Если для пользовательского типа требуются аргументы, их можно передать с помощью предложения PARAMETERS. При желании можно параллелизировать создание типизированного индекса с помощью предложения PARALLEL, которое подробно рассматривается ниже.
CLUSTER имя_кластера
Объявляется кластерный индекс с указанием существующего имени_клаетера. В Oracle кластерный индекс физически совмещает две таблицы, которые часто опрашиваются по одинаковым столбцам, обычно столбцам первичного и внешнего ключей. (Кластеры создаются специфической для Oracle командой CREATE CLUSTER.) Таблицы и столбцы в кластерном индексе не нужно объявлять, поскольку таблицы и индексированные столбцы уже объявлялись в ранее выполненной команде CREATE CLUSTER.
Index (Индексы)
Типы индексов:
Индексы в виде B-дерева (B-tree)
– самые распространенные и используются по умолчанию
Кластерные индексы в виде B-дерева
– определяются специально для кластера
Индексы хэш-кластера
– определяются специально для хэш-кластера
Глобальные и локальные индексы
– относятся к секционированным таблицам и индексам
Индексы с инвертированным ключом
– полезны в среде Oracle Real Application Cluster
Битовые индексы
– компактные, подходят для столбцов с небольшим набором значений
Индексы на базе функций
– содержат заранее вычисленные значения функции/выражения
Индексы домена
– зависят от приложения или картриджа
B*Tree
Структура индекса выглядит так:
Блоки самого нижнего уровня в индексе, которые называют листовыми вершинами (leaf blocks ), содержат все проиндексированные ключи и идентификаторы строк (rowid на схеме), ссылающиеся на соответствующие строки. Промежуточные блоки над листовыми вершинами называют блоками ветвления (branch blocks ). Они используются для переходов по структуре. Самый верхний блок называется корневым (root block ), он относится к группе branch blocks.
Индексы состоят из одного или более уровней branch blocks и одного уровня leaf blocks.
Index height
- высота индекса, кол-во уровней индекса
blevel
- высота кол-ва уровней branch blocks
Пример
Создадим новую пустую таблицу и создадим индекс по ней. Индекс будет состоять из одного пустого блока (он будет одновременно и root и leaf блоком). Index height = 1, blevel = 0.
Когда root блок полностью заполнится указателями, произойдёт его разделение на два branch блока, над которыми будет root блок с указателями на эти два блока. Теперь Index height = 3, blevel = 2. Как на картинке ниже:
По мере заполнения разделяются(split) листовые блоки, затем branch блоки и root блок. И так далее.
Интересно отметить, что листовые блоки фактически образут двухсвязный список.
Как только найдено "начало" среди листовых вершин, т.е. первое значение, очень легко просматривать значения по порядку (это называют также просмотром диапазона по индексу, index range scan
). Проходить по структуре индекса больше не нужно; мы просто переходим по листовым вершинам.
Одно из свойств В*-дерева состоит в том, что все листовые блоки должны быть на одном уровне, если точнее, разница по высоте между ветвями дерева не может быть больше 1.
Уровень листовых блоков называют также высотой дерева
.
Все вершины выше листовых могут указывать только на содержащие более детальную информацию вершины следующего уровня, а листовые вершины указывают на конкретные идентификаторы строк или диапазоны идентификаторов строк. Большинство индексов на основе В*-дерева будут иметь высоту 2 или 3 , даже для миллионов записей. Это означает, что для поиска ключа в индексе потребуется 2 или 3 чтения, что неплохо.
Еще одно свойство - автоматическая балансировка листовых вершин : они почти всегда располагаются на одном уровне. Есть причины, по которым индекс может оказаться не идеально сбалансированным при изменении и удалении записей. Сервер Oracle будет пытаться заполнять блоки индекса не более чем на три четверти, но и это свойство может временно нарушаться при выполнении операторов DELETE и UPDATE.
Создать индекс
create index t_idx on t(owner,object_type,object_name);
- Как средство доступа к строкам в таблице.
Индекс читается, чтобы добраться до строки в таблице. Так имеет смысл обращаться к очень небольшой части строк таблицы.
- Как средство ответа на запрос.
Индекс содержит достаточно информации, чтобы дать полный ответ на запрос — к таблице вообще не придется обращаться. Индекс будет использоваться как уменьшенная версия таблицы.
Bitmap
Индексы на основе битовых карт — это структуры, в которых хранятся указатели на множество строк, соответствующих одному значению ключа индекса
, тогда как в структуре В*-дерева количество ключей индекса обычно примерно соответствует количеству строк. В индексе на основе битовых карт записей очень мало, и каждая из них указывает на множество строк. В индексе на основе В*-дерева обычно имеется однозначное соответствие — запись индекса ссылается на одну строку.
Когда следует использовать Bitmap индексы:
Для данных с небольшим количеством уникальных значений. Это данные, для которых при делении количества уникальных значений в строках на общее количество строк получается небольшое число (близкое к нулю).
Создать bitmap индекс
create bitmap index empno_bmx on t(empno);
Function Based
Индексы по функциям позволяют индексировать вычисляемые столбцы и эффективно
использовать их в запросах.
Индексы можно создавать не только по системным оракловым ф-циям, но и по своим написанным ф-циям
Создать индекс по ф-ции
create index emp_upper_idx on emp (upper(ename));
Application domain indexes(прикладные индексы)
Прикладные индексы позволяют создавать новые, еще не существующие в базе данных, типы индексов.
Например , если создается приложение, анализирующее хранящиеся в базе данных изображения и выдающее информацию об этих изображениях - скажем, используемые цвета — можно создать специальный индекс по изображениям. При добавлении изображений в базу данных будет вызываться код для извлечения информации о цветах, которая будет сохраняться отдельно (там, где сочтет нужным разработчик). При выполнении запросов, требующих вернуть "изображения в синих тонах", сервер Oracle при необходимости потребует от прикладного индекса вернуть ответ.
Избирательность индекса
Избирательность представляет собой отношение количества выбранных строк к общему количеству строк. Если это отношение мало, значит, индекс обладает высокой избирательностью. Он позволяет отбросить большую часть строк и значительно уменьшает размер результирующего набора. Подобный индекс является эффективным. Индекс, не обладающий избирательностью, не является эффективным.
Наилучшей избирательностью обладает уникальный индекс. При использовании уникального индекса возвращается только одна строка, что делает этот индекс наиболее эффективным для применения в запросах, которые должны возвращать только одну строку. Например, индексирование по столбцу, содержащему уникальный код, позволяет быстро найти требуемую строку.
Кэри Миллсап, Hotsos Enterprises, Ltd
[От гл.редактора OM/RE А.Бачина
: Публикация этой статьи имеет некую предысторию, которую я вкраце хочу поведать нашим читателям.
В журнале Oracle Magazine (весна 1995) Кери Миллсап (Cary Millsap), Грег Шаллхамер (Craig Shallahamer) и Миша Адлер (Micah Adler) опубликовали в статью "Predicting the Utility of the Nonunique Index." [Millsap и Al 1993
] ("Когда использовать неуникальный индекс"). Эта статья была переведена на русский язык и опубликована в нашем журнале "Мир Oracle", который выходил еще в бумажном издании. Интернета в нашей стране еще не было (верится с трудом, но чистая правда!), поэтому статья сохранилась лишь в архивах и памяти многих наших читателей, как прекрасный источник правильного подхода к использованию индексов. Все последние годы мне хотелось заново перевести и переопубликовать эту статью, чтобы разработчики и АБД нового поколения познакомились с правильным подходом к этой проблеме. Но когда дело дошло до дела, оказалось, что ни у кого из доступных адресатов не сохранился английский вариант этой статьи. Даже у самого автора, Кери Миллсап. Когда я к нему обратился, он посоветовал перевести и опубликовать новый ее вариант, в котором грустно отметил [4
] возможное невнимание к первоначальному тексту. Я постарался его в этом разуверить, послал ему scan-копию статьи и обложки журнала... Он был нам благодарен и разрешил переводить и публиковать статьи с сайта компании Hotsos Enterprises, чем мы, естестенно, с благодарностью еще не раз воспользуемся. Спасибо, Кери!
]
===***===***===***===
[От редакции OM/RE: На сайте корпорации Oracle появилась Oracle ACE (http://www.oracle.com/technology/community/oracle_ace/index.html) - "Аллея славы", то есть галерея наиболее прославленных Oracle-авторов,среди которых заслуженное место занимает автор данной статьи Cary Millsap. Из этой "Аллеи славы" взята публикуемая здесь фотография автора статьи. ]
Резюме
Когда следует использовать индекс? Более десяти лет разработчики приложений Oracle использовали простое rule of thumb (правило большого пальца) - эмпирическое правило для приближенных расчётов, чтобы решить, использовать ли неуникальный индекс (non-unique index). Однако, в повседневной работе мы не редко сталкиваемся с проблемами производительности, вызванными использованием этого эмпирического правила. В этой статье я излагаю следующие результаты наших исследований:
Когда использовать индекс: Традиционный Совет
В одном или каком-либо другом виде, но стандартная рекомендация, надо ли использовать индекс, по крайней мере, начиная с версии Oracle 5, звучала следующим образом:
Используйте индекс, когда запрос возвращает менее чем x% строк таблицы.
Рисунок 1 иллюстрирует понятие, когда некий порог в x% действует как точка баланса производительности Oracle в сравнении диапазонного сканирования индекса и полного сканирования таблицы, осуществляемого по путям доступа. Этот график связывает время ответа R (обычно выражаемое в секундах) в пропорции к Pr строк таблицы, которые возвращаются за данную операцию запроса.
Рисунок 1. Время ответа R в секундах как процентная функция Pr возвращаемых строк таблицы. Пунктирная линия при R = 6.75 (красная линия, если вы видите это в цвете) является временем ответа при полном просмотре таблицы. Непрерывная (синяя) линия - время ответа диапазонного сканирования индекса, который возвращает Pr процентов строк данной таблицы.
Время ответа при плане выполнения, возвращающего r строк при полном просмотре таблицы, является примерно постоянным, независимо от того, r - это одна строка или общее количество строк в таблице. Однако, время ответа диапазонного сканирования индекса увеличивается по мере того, как нарастает объем результирующих исходных строк . Процент pr = x - пороговое значение pr , когда время ответа полного просмотра таблицы и диапазонного сканирования индекса сравниваются. При значении pr < x диапазонное сканирование индекса имеет лучшую производительность. При значении pr > x лучшую производительность предоставляет полный просмотр таблицы.
Тем не менее, в этой линии рассуждения имеется большая проблема. Любое правило типа большого пальца в отношении индексов ненадежно, если существует балансовый процент типа x .
Почему правило большого пальца ненадежно
Правило большого пальца звучит примерно так: "Используйте индекс, когда запрос возвращает меньше чем x процентов от общего числа строк таблицы ". Оно основано на следующих позициях:
Наши испытания и практический опыт показали, что позиция 1) является истинной даже для очень маленьких таблиц. Запрос, возвращающий одну строку, более эффективен, когда выполняется с использованием индекса, чем посредством полного просмотра таблицы, даже если таблица содержит только одну строку. Много людей, с которыми мы обсудили это, выразили удивление таким результатом. Этот результат также противоречит вполне конкретной рекомендации Oracle: "малые таблицы не требуют индексов" [Oracle 2001a ]. Малые таблицы могут не требовать наличия индексов, но индексы на малых таблицах могут сделать вашу систему значительно более эффективной и, следовательно, значительно более масштабируемой [2 ].
Итак, мы принимаем позицию 1), но на позиции 2) начинаются большие проблемы. Иногда намного дешевле прочитать 100 % строк таблицы, используя индекс, чем при полном сканировании таблицы.
Пример: Представим таблицу с именем interface, которая занимает (high-water mark - высшая отметка использования пространства) 10,000 блоков. Хотя в своем историческом прошлом таблица interface содержала сотни тысяч строк, сегодня таблица включает только 100 строк. Эти строки произвольно рассеяны по 30 блокам таблицы. Предположим, что таблица имеет первичный ключ на столбце с названием id, на котором, конечно, построен индекс (с именем id_u1). И далее нам надо выполнить следующий запрос:
Select id, date, status from interface i ;
Если этот запрос выполнять посредством полного просмотра таблицы, то потребуется 10,000 LIO-вызовов Oracle. Мы можем слегка переделать этот запрос, чтобы позволить Oracle выполнять его, используя индекс. Если id - числовой столбец и все значения id - неотрицательные целые числа, то следующий запрос выводит желательный набор строк посредством индекса:
Select /*+ index(i id_u1) */ id, date, status from interface i where id> -1 ;
Этот запрос потребует менее 40 LIO-вызовов Oracle. Время ответа составит примерно 10,000/40, то есть в 250 раз лучше при использовании индекса, чем при выборке 100 % строк из таблицы посредством полного ее просмотра.
Существует много разных крючков и загогулин (all sorts of hooks and crooks), которые можно исследовать на этом примере. Например, если бы фраза select содержала только id или count(id) (что может быть получено из информации индекса даже без обращения к сегменту данных), то просмотр по индексу был бы еще быстрее.
Итак, чтобы быть применимым в случаях подобных этому, эмпирическое правило (большого пальца) для любого процента проиндексированных строк должно допускать возможность, что использование индекса может быть более эффективно, чем полный просмотр таблицы даже для тех запросов, которые возвращают все 100 % строк таблицы. На рисунке 2 показан этот феномен.
Рисунок 2. Эта схема отражает ситуацию, когда таблица содержит большое количество пустых блоков. Диапазонное сканирование индекса (синяя сплошная линия) быстрее, чем полный просмотр таблицы (красная пунктирная линия), даже для запроса, возвращающего 100% строк таблицы.
Существует много случаев, когда основанные на процентах эмпирические правила являются ненадежными. Имеется также большая проблема, связанная с высказанным ранее постулатом 3). Эта проблема еще покажет себя в ходе дальнейшего изложения.
Неравномерно эволюционирующий признак x
Упомянутая большая проблема эмпирического правила индексации состоит в том, что нет четкой ясности, какое значение x должно использовать. Если проследить историю рекомендаций для x в документации Oracle, то вы найдете следующее: [3 ]
Положение даже хуже, чем показано в таблице. Если память мне не изменяет, ранний выпуск производственной документации Oracle7 содержал рекомендацию для x как "1-15 процентов". Я был потрясен тем, насколько широк был диапазон. Если же углубиться в этот вопрос, некоторые из моих друзей из Oracle Applications development очень убедительно говорили, что в своих приложениях они часто наблюдали значение x более 40.
Многие люди полагают, что причина, по которой качается (wiggling) x, состоит в том, что Oracle продолжает совершенствовать работу оптимизатора (optimizer). Но это не всеобщая действительная причина. Причина же того, что значение x стал таким движущимся объектом (moving target), в том, что авторы рекомендаций не сумели выявить истинные параметры, которые дают сбалансированное значение.
Критический параметр - это число блоков Oracle ниже высшей точки заполнения (high-water mark) таблицы, которую можно игнорировать при использовании индекса . Путь построения правила создания индекса, которое превзойдет эмпирическое правило большого пальца и которое сделает жизнь более легкой, должен включать вопрос: "Какой план выполнения потребует меньшее число блоков Oracle, которые должны быть просмотрены? "
Для любого источника строк, с более чем одной строкой, индекс во много раз позволяет Вам сократить PIO-вызовы. Число PIO-вызовов для блоков данных, которое игнорируется при задействовании индекса, зависит от следующего:
Пример: Мы желаем оптимизировать следующий запрос:
select id, date from shipment where flag="x"
Притча об индексаторах
Давайте раскроем важность концепции, называемой селективностью блоков с помощью истории. Речь пойдет о …
Экстраординарная частота слова "the", вероятно, сделает эту работу абсолютно невыполнимой даже при наличии индекса. "Давайте посмотрим, где есть "the"… Ах да, "the" есть на первой странице." Хорошо, что вы отметили первую "the" страницу в индексе. Тогда щелкнете по индексу для первой страницы. Вы расположите слово после первого "the". Потом вы возвращаетесь к индексу, чтобы найти следующую страницу, на которой появляется "the" - это также страница один. Вы будете ходить вперед и назад, пока вы не посетите каждую страницу всех множеств книжных времен. Вы будете щелкать по книге назад и вперед столько много раз, что ее переплет, вероятно, полностью износится.
Теперь представим, что существует Reader"s Digest Large Print for Easier Reading (Справочник Читателя для Большого Издания для более легкого чтения) этой Brief History of Humanity (Краткой Истории Человечества). Далее представим себе, что основная книга напечатана буквами по 72 пункта. Поэтому Brief History of Humanity содержит только по 20-30 слов на странице. И хотя слово "the" достаточно общее и фактически появляется на каждой странице обычной книги, оно уже не достаточно обычно, чтобы появляться на каждой странице справочника Large Print. В этих новых условиях индекс имеет очень большую полезность для нашего небольшого проекта "find the word after the "the"" ("найти слово после "the""), потому что теперь индекс позволяет нам пропускать большее количество страниц.
Это - 72-пунктовый шрифт. Справочник Large Print for Easier Reading для книги Brief History of Humanity содержит намного меньшее количество ссылок, чем к каждой странице стандартного размера.
Разгадка мифа
Параметры, которые влияют на полезность индекса при диапазонном сканировании, при котором требуется rowid-доступ к таблице, следующие:
Понимание параметров полезности индекса разрушает миф, почему люди не могут сделать хороший выбор значения x .
Что же теперь?
Мой вам совет:
Забудьте все о правилах индексации типа большого пальца, основанных на процентах.
На самом деле не имеется никакого диапазона процентов, который даст вам надежный результат. Имеются запросы, возвращающие 1 % или меньшее число строк таблицы, которые более эффективно выполняются полным просмотром таблицы, нежели с использованием индекса. И существуют запросы, возвращающие все 100 % строк таблицы, которые более эффективно выполняются посредством индекса. Но если вы настаиваете на выборе значения для x , я рекомендую найти такое значение, которое одновременно является меньше 1% и больше или равно 100%. Так как никакое такое число не существует, я рекомендую, чтобы вы полностью переключили свое внимание в другую сторону от правил индексации типа большого пальца, основанных на процентах.
Технология оптимизации Oracle проделала длинный путь, начиная с внедрения основанного на стоимости (cost-based) оптимизатора Oracle (это было весьма хорошо в Oracle8i ). Все что требуется от Вас - это определить, какие создать индексы. Ядро Oracle только тогда будет использовать созданные вами индексы, когда это эффективно. Но создание индекса, который никогда не будет хорошо использоваться, - только трата и места, и времени . Поэтому вы должны сами решать, создавать индекс или нет? Ответ в селективности блоков.
Селективность блоков
Вы, вероятно, уже знакомы с концепцией селективности строк. Вы можете определить селективность строк данного предиката из фразы where, как число строк, возвращенных предикатом (r), разделенное на общее число строк в таблице (R):
- определение селективности строк (row selectivity)
Селективность блоков можно определять, аналогично задавая в фразе where предикат отношения числа блоков данных, содержащих по крайней мере одну строку, отвечающую условию предиката (b), к общему количеством блоков данных ниже high-water mark (B):
Определение селективности блоков (block selectivity)
Различие между селективностью строк и селективностью блоков весьма существенно, потому что селективность блоков почти всегда хуже - часто много хуже - селективности строк. Ранее на примере таблицы shipment мы видели flag ="x" . Для этого предиката получается селективность строк 1 %, а селективность блоков 100 %.
Вы можете вычислить селективность строк и селективность блоков, используя SQL-скрипт из следующего примера, который мы назвали hds.sql [Holt 2002 ].
1 rem $Header: /usr/local/hotsos/RCS/hds.sql,v 1.8 2002/01/07 18:12:27 hotsos Exp $ 2 rem Copyright (c) 2000-2002 by Hotsos Enterprises, Ltd. All rights reserved. 3 rem Author: [email protected] 4 rem Notes: Hotsos data selectivity using a full table scan for the row count. 5 6 define v_substr7 = "substr(rowid,15,4)//substr(rowid,1,8)" 7 define v_substr8 = "substr(rowid,7,9)" 8 define v_over = "substr(""&_O_RELEASE"",1,1)" 9 10 col dummy new_value v_substr 11 12 set termout off heading on pause off 13 14 select decode(&v_over, "7", "&v_substr7", "&v_substr8") dummy 15 from dual; 16 17 set termout on verify off feedback off pages 10 18 19 accept p_town prompt "TableOwner: " 20 accept p_tname prompt "TableName: " 21 accept p_clst prompt "ColumnList: " 22 accept p_where prompt "WhereClause: " 23 accept p_pgs prompt "PageSize: " 24 25 variable fblks number 26 27 declare 28 tblks number; 29 tbytes number; 30 ublks number; 31 ubytes number; 32 luefid number; 33 luebid number; 34 lublk number; 35 begin 36 sys.dbms_space.unused_space(37 upper("&p_town"), upper("&p_tname"), "TABLE", 38 tblks, tbytes, ublks, ubytes, luefid, luebid, lublk, null 39); 40:fblks:= tblks - ublks; 41 end; 42 / 43 44 col blks form 9,999,999,999 heading "Table blocks below hwm/(B)" just c 45 col nrows form 999,999,999,999 heading "Table rows/(R)" just c new_value v_nrows 46 47 select:fblks blks, count(*) nrows 48 from &p_town..&p_tname; 49 50 col bs form a17 heading "Block selectivity/(pb = b/B)" just c 51 col nblks form 9,999,999,999 heading "Block count/(b)" just c 52 col rs form a17 heading "Row selectivity/(pr = r/R)" just c 53 col nrows form 999,999,999,999 heading "Row count/(r)" just c 54 55 set pause on pause "More: " pages &p_pgs 56 57 select &p_clst, 58 lpad(to_char(count(distinct &v_substr)/:fblks*100,"990.00")//"%",17) as bs, 59 count(distinct &v_substr) nblks, 60 lpad(to_char(count(*)/&v_nrows*100,"990.00")//"%",17) rs, 61 count(*) nrows 62 from &p_town..&p_tname &p_where 63 group by &p_clst 64 order by bs desc;
Использование скрипта hds.sql очевидно. Однако, получение полной информации о распределении данных в таблице может быть очень дорогим. В зависимости от ваших данных, этот запрос может выполняться и минуты, и часы. Это объясняет, почему стоимостной оптимизатор Oracle полагается на хранимую статистику вместо самостоятельного анализа данных, когда вычисляет или утверждает план выполнения. Следующий пример иллюстрирует, как мы используем данные hds.sql.
Пример: система имеет таблицу с именем po.cs_ec_po_items . Наша цель состоит в том, чтобы оптимизировать несколько подопераций запроса, которые во фразе where используют предикат ec_po_id =:vas . Что получится, если мы создадим индекс на столбце ec_po_id ? Мы можем использовать скрипт hds.sql, чтобы получить истинную информацию о распределении данных по различным значениям ec_po_id :
Выходные данные скрипта hds.sql отсортированы по убыванию селективности блоков. Листинг обычно содержит тысячи строк, но все самые плохие данные (worst-case data) - в данном случае представляющие наиболее интересную часть - находятся наверху. Поэтому мы обычно обрываем листинг hds.sql после выдачи одной-двух страниц.
Заметим, что для этой таблицы имеет место превосходная селективность строк для каждого значения ec_po_id . "Самое плохое" значение селективности строк - только 0.54 % . Это означает, что только полпроцента строк таблицы имеет значение ec_po_id = "8" . Однако столбец селективности блоков представляет нам совсем другую историю. Селективность блоков ec_po_id = "8" составляет 63.50%. Это значит, что почти двух третях блоков таблицы содержится по крайней мере по одной строке, для который ec_po_id = "8" .
Должны ли мы создать индекс на ec_po_id ? Можно потратить полдня или более, вычисляя "back of the envelope" ("быстро и легко определяемый") ответ, пытаясь вычислить по формулам затраты плана выполнения. Но оптимизатор Oracle может сделать эту работу за вас. Наиболее точный и, в конечном счете, наименее отнимающий время метод для определения ответа состоит в том, чтобы выполнить тестирование на фактической базе данных Oracle. Лучший способ определить относительные затраты двух планов выполнения состоит в том, чтобы выполнить их на некоих тестовых данных с установкой опции sql_trace=true . Если нужна большая детальность в части, скажем, использования других (не-CPU) механизмов, которых задействует Oracle в течение выполнения запроса, то протрассируйте выполнение с использованием Oracle-события 10046 на уровне 8 [Hotsos 2002 ]. Если нужно большее количество данных о том, почему оптимизатор выбрал такой план, который сам и сделал, то протрассируйте выполнение с Oracle-событием со случаем 10053 [Lewis 2001 ].
Из листинга hds.sql мы узнаем граничные условия, которые нужно проверить. Например, мы теперь знаем, что при тестировании следует ответить на следующие запросы:
Ваше окончательное решение о построении индекса, конечно, зависит от того, превышает ли выгода от наличия индекса стоимость его наличия. Эти затраты могут включать:
Когда используется инструмент подобно скрипту hds.sql, наблюдается один из трех вариантов:
Решения в случаях 1 и 2 очевидны. А ситуация 3, вероятно, именно та, в которой вы пребываете наиболее часто. Пользователи стоимостного оптимизатора Oracle до релиза 7.3 стояли перед жестким выбором. Если индекс не создавался, то был велик риск низкой производительности при некоторых значениях во фразе where; если индекс создавался, то был риск низкой производительности для других значений. Новейшие версии стоимостного оптимизатора Oracle делают жизнь намного проще. Если в наши дни вы регулярно исполняете свои обязанности по сбору статистики , подобная ситуация намного менее вероятна, и ошибочное создание мало пригодного индекса причинит экстремальные издержки (torture - пытка) вашим пользователям.
Пример: Представим себе, что секционированная таблица содержит столбец id со следующим распределением данных:
Показанное здесь распределение данных сильно перекошено (highly skewed). Теперь выдадим следующий запрос к этой таблице:
select name from division d where id=:a1
Без гистограмм стоимостной оптимизатор может предположить, что имеются десять различных значений id, каждый id отвечает за примерно 1/10 строк таблицы. Это предположение заставит его вспомнить хорошую идею использовать индекс на столбце id. И так было бы до тех пор, пока :a1 != "01" .
Сила гистограммной (histogram-based) оптимизации состоит в том, что должным образом реализованный [9 ] гистограммный оптимизатор заметит, когда:a1 = " 01" и не будет пытаться использовать индекс на id. Без гистограммной оптимизации разработчик приложений должен или
Значения не часто распределяются произвольным образом
Недавняя документация по Oracle приводит предположение, что "строки в таблице упорядочены произвольно (randomly ordered) в отношении столбца, на котором базируется запрос" . Это предположение немного упрощает написание Oracle-документации, но это делает этот совет Oracle менее полезным, чем он мог бы быть.
В результате действий с hds.sql можно увидеть, что иногда значения столбца естественным образом группируются, и остаться сгруппированными навсегда.
Пример: таблица shipment имеет столбец состояния, называемый shipped, который принимает значение "y" , тогда и только тогда, когда пункт заказа был отгружен (shipped). Поскольку заказы имеют тенденцию отправляться, грубо говоря, в той же последовательность, что были введены, таблица shipment через какое-то время имеет хорошую естественную кластеризацию по значениям shipped="n" , как это показано на рисунке 3. Кластеризация строк с shipped="n" улучшает полезность индекса при поиске строк с shipped="n" .
Рисунок 3. Значения столбца состояния имеют тенденцию к естественной кластеризации.
Противоположностью сгруппированного распределения является однородное распределение. Если значения столбца имеет истинное однородное распределение в пределах таблицы, то экземпляры данного значения физически равноудалены друг от друга.
Пример: таблица address имеет столбец с именем state , который содержит двух литерный код штата или провинции. В приложении, которое использует эту таблицу, нет никаких очевидных отношений между временем, когда была вставлена строка клиента, и значением state клиента. Следовательно, физическое распределение каждого значения state практически однородно. Хотя state ="TX" истинно, возможно, только для одной строки из 30, лишь немногие блоки таблицы не имеют ни одной строки с state ="TX" . Рисунок 4 показывает эту ситуацию.
[Блок содержит по крайней мере одну строка с state = "TX"
Блок не содержит ни одной строки, для который state ="TX"
]
Рисунок 4. Индекс на state имеет низкую полезность для state ="TX ".
Использование здесь индекса по с state , вероятно, было бы неэффективно для поиска любого "известного" ("popular") кода штата. Но если, например, имеется один или более штатов с много меньшим количеством строк, чем наличествует блоков в таблице address , и если Вы часто ищете коды таких штатов и используете гистограммы, тогда создание индекса по state , вероятно, поможет вашему приложению.
Столбцы Status иногда могут самостоятельно группироваться естественным образом. Но при отсутствии любого искусственного внешнего влияния столбцы type в большинстве имеют тенденцию к однородному физическому распределению. Существует несколько типов воздействия на физическое хранение данных в таблице. Можно предписать определенную физическую упорядоченность данным, используя:
Без нужды не предполагайте, что распределение ваших данных случайно (random). Выясните это с помощью hds.sql. Любые приемы, предписывающие физическую упорядоченность, принесут как выгоды, так и затраты вашему бизнесу. Если изменение физического распределения данных одновременно помогает максимизировать чистую прибыль вашей компании, поток наличности (cash flow) и возврат инвестиций, тогда делайте это [Goldratt 1992 ].
Заключение
Многие источники учат, что решения по индексации надо принимать на базе анализа предиката селективности строк во фразе where . Еще хуже, когда некоторые источники обсуждают применение индексации в терминах селективности строк для всего столбца, что полностью игнорирует возможность его асимметричности. Однако селективность строк - ненадежное основание для решения о создании индекса. Лучший способ смягчать риск состоит в том, чтобы проверить фактическую производительность SQL-предложения на проверенных тестовых данных. Инструмент, подобный скрипту hds.sql, который выдает информацию о селективности блоков , повышает надежность и эффективность вашего испытания, раскрывая критические значения столбца, на котором вы собираетесь проверить производительность.
Стоимостной (cost-based) оптимизатор Oracle делает более простым ответ на вопрос, надо ли строить индекс, поскольку он вырабатывает более продвинутые решения по использованию индексов, чем это может сделать синтаксический (rule-based) оптимизатор. Но для реализаций, которые все еще полагаются на синтаксический оптимизатор Oracle, понимание важности селективности блоков может быть жизненно важно для производительности приложений Oracle. Как только определятся характеристики селективности блоков, необходимо исключить пассивный подход к физической упорядоченности ваших данных. Много возможностей, привнесенных в СУБД Oracle, начиная с выпуска 7.3, упрощают ваши действия по хранению данных в физической упорядоченности, что обеспечивает превосходную производительность.
Примечания:
