Как работает индекс?

Давайте повторим принципы работы индекса. Для этого рассмотрим следующий простой SQL-запрос:

SELECT emp.empno
,emp.ename
FROM employees emp
WHERE emp.ename = 'SMITH'

Способ, которым этот запрос выберет данные, зависит от того, индексирован ли (и как) столбец ENAME в таблице EMPLOYEES, а также от того, какая версия Oracle7 и режим оптимизатора используются. Вот некоторые возможные варианты.

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

2. Имеется обычный индекс для столбца ENAME. Oracle последовательно читает уровни индекса по нисходящей до тех пор, пока не достигнет блока-листа, в котором значение SMITH либо присутствует, либо не присутствует Если обнаружен один или более экземпляров ключа SMITH, то за этими экземплярами следует идентификатор строки, что позволяет процессору запросов найти блоки данных, содержащие значение SMITH, и перейти прямо в эти строки. Имея эту информацию, процессор запросов может непосредственно обращаться к данным (предполагая, что не произошла миграция строки; миграцию строк мы рассмотрим в главе 9). Конечно, если вы используете оптимизатор по стоимости и статистика показывает, что данный столбец не является высоко избирательным, оптимизатор может выбрать полное сканирование таблицы. В версии 7.3, где строятся гистограммы значений столбцов, более вероятно, что для SMITH будет инициировано полное сканирование таблицы, а для ENSOR или STEVENSON — нет. В версиях 7.2 и ниже одно и то же действие будет выполнено для каждого значения; если индекс высокоизбирательный, он будет использован, а если нет, то не будет. Что делает индекс высокоизбирательным? Довольно эмпирическое вправило гласит: индекс будет классифицирован как высоко избирательный, если он содержит более двадцати разных ключевых значений.

3. Имеется составной индекс для нескольких столбцов, первым из которых является ENAME. Этот случай аналогичен описанному в п. 2, за тем исключением, что для индексированного поиска будет использоваться только лидирующая часть индексного ключа. У неуникальных индексов Oracle есть одна привлекательная особенность: идентификаторы строк с равными ключами (например, имеется много людей с фамилией Смит), хранятся в порядке их следования. Эта особенность дает следующее преимущество. Если строки для двух Смитов находятся в одном и том же физическом блоке базы данных, мы обратимся к ним по порядку. Почти во всех случаях это приводит к минимизации числа перемещений головок диска между блоками (если требуемые данные еще не находятся в системной глобальной области — SGA). К сожалению, несмотря на то, что мы используем лидирующую часть составного индекса, базовая последовательность будет соответствовать полному ключу. В результате можно ожидать, что операция поиска будет менее эффективна, чем при использовании одностолбцового индекса. Индекс также будет более длинным, что увеличивает объем сканирования. Однако эти факторы не оказывают заметного влияния и не оправдывают создание индекса по (ENAME), если уже есть и необходим индекс по (ENAME, INITIAL).

4. Имеется составной индекс для нескольких столбцов, но столбец ENAME не является первым из них. Этот индекс не используется, поэтому производится полное сканирование таблицы (как в п. 1).

5. Имеется хеш-ключ для столбца ENAME (таблица находится в хеш-кластере по столбцу ENAME). К SMITH применяется алгоритм хеширования, и хешированное значение используется для чтения блока кластеризованных данных. Если алгоритм хороший и размер кластера задан правильно, то этот блок должен содержать искомые строки. В противном случае, возможно, придется прочитать один или несколько связанных блоков, прежде чем будут найдены наши данные или обнаружится, что служащих по фамилии SMITH нет. В любом случае мы должны провести поиск хешированного значения во всех связанных блоках, которых может быть несколько (или, в патологических случаях, несколько тысяч).

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

7. Таблица кластеризована, но столбец ENAME не является ни кластерным ключом, ни лидирующей частью другого индекса. Кластер сканируется почти так же, как в п. 1, за исключением того, что каталог строк в блоке-заголовке кластера используется для поиска в этом блоке строк, входящих в таблицу EMPLOYEES. Каждая из этих строк проверяется на наличие в ней фамилии SMITH.

8. Столбец ENAME является объектом bitmap-индекса. Для значения SMITH извлекается битовая карта (если таковая имеется), которая раскрывается в список идентификаторов строк, соответствующих условию запроса. Затем осуществляется чтение этих строк для выполнения запроса. Если ключевых значений всего несколько, то создание битовой карты для каждого значения ключа (по одному биту на строку в каждой карте) рационально в плане использования памяти и обеспечивает довольно эффективный поиск. Однако для индекса по фамилии может понадобиться большое число таких битовых карт, причем для большинства фамилий они наверняка будут очень разреженными (т.е. почти все биты будут "выключены").

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

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

Предположим, что не всегда в запросе выполняется сравнение на равенство (как в нашем примере) и нам приходится выдавать запросы, например, такого вида:

SELECT emp.empno
, emp.sal
FROM employees emp
WHERE emp.ename LIKE 'SM%';

В этом случае мы, вероятно, выбрали бы индекс, имеющий структуру В*-дерева, или полное сканирование таблицы. По мере того как искомое выражение будет сокращаться до "S%", полное сканирование таблицы будет выглядеть более приемлемым. Оптимизатор по стоимости в версии 7.3 сумеет выполнить оптимизацию правильно, но проектировщику следует помнить о проблеме связанной переменной, которую мы рассматриваем в разделе "Проблема связанной переменной" этой главы.

Дата добавления: 2015-08-09