Индексирование

Материал из ПИЭ.Wiki

Перейти к: навигация, поиск

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

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

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

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

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

Каждая таблица БД может иметь один или несколько индексов. Индексы создаются по одной колонке или нескольким колонкам таблицы. Колонки, входящие в индекс, принято называть ключевыми полями (key fields), или ключами. Индексы могут быть уникальными и неуникальными. Уникальность индекса означает, что не существует двух строк с одним и тем же значением ключа индекса. Неуникальный индекс может иметь несколько ключей с одинаковыми значениями.

Основными целями создания индексов в БД являются:

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

На этапе создания физической модели данных ХД необходимо принять ряд важных решений о том, что и как индексировать; при этом важно четко сформулировать правила индексирования. Для каждого ИТ-проекта с ХД необходимо создать и оформить в письменном виде правила индексирования как часть общих правил обеспечения производительности. Поддержка и сопровождение индексов в процессе эксплуатации ХД является в основном задачей администратора БД. Решая задачи обеспечения производительности, администратор БД будет ставить вопрос о перепроектировании ее физической структуры (обратные задачи проектирования), в том числе и вопрос об удалении и создании новых индексов. Он может решать эти задачи самостоятельно. Тем более важно знать, по каким правилам и из каких соображений создавались индексы того или иного типа. Разработка таких правил значительно повысит качество эксплуатации ХД с точки зрения обеспечения ее производительности.

Чтобы решать эти задачи, проектировщик должен знать, как работает индекс, какие типы индексов поддерживает СУБД, и понимать смысл методов индексирования.

Индекс со структурой B-Tree

Индекс на основе сбалансированной иерархической структуры (или индекс B-Tree, balanced tree structured object) напоминает дерево, если смотреть на него снизу вверх. При работе СУБД с этой структурой сначала считывается самый верхний блок — корневой узел (root), затем блок на следующем уровне — блок-ветвь (branch), и так далее, до тех пор, пока не будет извлечен блок-лист (leaf) с индексируемыми колонками (колонкой) строки. Обратим внимание, что значения индексируемых колонок сохраняется в индексе (рис. 1.1).

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

Концептуальная организация B-Tree индекса

Рис. 1.1. Концептуальная организация B-Tree индекса

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

  1. когда строка имеет длину более одной физической страницы файловой структуры БД — так называемая расщепленная строка ;
  2. когда строка за время своего существования в БД увеличилась и была перемещена из исходной страницы в другую страницу — так называемая мигрировавшая строка.

Индекс B-Tree характеризуется количеством уровней в индексе – высотой (height). Чем меньше уровней, тем выше производительность.

Индекс B-Tree — это физический объект реляционной БД, организованный по принципу сбалансированной иерархической структуры и обладающий набором свойств. Сформулируем некоторые свойства индексов со структурой B-Tree.

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

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

  • Значения в индексе упорядочиваются по ключевому значению, а физические страницы индекса организуются в двунаправленный список. Это обеспечивает последовательный доступ к индексу и позволяет использовать индекс для выполнения операции ORDER BY в запросе.

  • Индекс можно использовать для поиска как точного соответствия, так и диапазона значений.

  • Индексы могут быть построены для нескольких колонок таблицы — так называемый составной индекс. СУБД использует составные индексы для выполнения тех запросов, в которых задана лидирующая часть составного ключа. Например, составной индекс {"Фамилия" (Ename), "Должность" (Job)} для обработки запроса SELECT * FROM EMPLOYEE WHERE Job='Инженер'; применяться не будет.

  • СУБД обычно сама принимает решение, использовать индекс или нет.

  • Значения колонок NULL не индексируются. Если для таких колонок строится индекс, то СУБД будет отказываться применять его в некоторых операциях, например, ORDER BY.

В СУБД семейства MS SQL Server все индексы организованы на основе сбалансированной иерархической структуры. Помимо того, что индексы обладают свойствами уникальности ( UNIQUE ) и неуникальности, индексы в СУБД семейства MS SQL Server могут быть кластеризованными ( CLUSTERED ) или некластеризованными ( NONCLUSTERED ), являющимися индексами по умолчанию.

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

Некластеризованный индекс – это индекс, в котором задается логическое упорядочение для таблицы. Логический порядок строк в некластеризованном индексе не влияет на их физический порядок. Для каждой таблицы можно создать до 999 некластеризованных индексов, независимо от того, каким образом они создаются: неявно, с помощью ограничений PRIMARY KEY и UNIQUE, или явно, с помощью команды CREATE INDEX.

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

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

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

В зависимости от типов данных каждая структура кластеризованного индекса состоит из одной или более единиц распределения, которые применяются для хранения и управления данными секциями. Для каждой секции кластеризованный индекс содержит как минимум одну единицу распределения IN_ROW_DATA. Для хранения столбцов больших объектов ( LOB ) кластеризованному индексу требуется одна единица распределения LOB_DATA для каждой секции. Кроме того, для хранения строк переменной длины, которые превышают ограничение на размер строки, равное 8 060 байтам, для каждой секции требуется одна единица распределения ROW_OVERFLOW_DATA.

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

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

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

Если таблица является кучей (то есть не содержит кластеризованный индекс ), то указатель строки является указателем на строку. Указатель строится на основе идентификатора файла ( ID ), номера страницы и номера строки на странице. Весь указатель целиком называется идентификатором строки ( RID ).

Если для таблицы имеется кластеризованный индекс или индекс построен на индексированном представлении, то указатель строки — это ключ кластеризованного индекса для строки. Если кластеризованный индекс не является уникальным индексом, то SQL Server создает все имеющиеся повторяющиеся ключи уникальными путем добавления внутри созданного значения, называемого uniqueifier. Это четырехбайтовое значение невидимо для пользователей. Оно применяется тогда, когда необходимо сделать кластеризованный ключ уникальным, чтобы использовать в некластеризованных индексах. SQL Server получает строку данных путем поиска по кластеризованному индексу, задействуя ключ кластеризованного индекса, который хранится в конечной строке некластеризованного индекса.

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

В зависимости от типов данных в некластеризованном индексе каждая его структура будет содержать одну или более единиц распределения, в которых хранятся данные для определенной секции. Каждый некластеризованный индекс будет иметь по меньшей мере одну единицу распределения IN_ROW_DATA на секцию, в которой хранятся страницы сбалансированного дерева индекса. Некластеризованный индекс будет также содержать одну единицу распределения LOB_DATA на секцию, если в индексе есть столбцы типа большого объекта (LOB). Кроме того, некластеризованный индекс будет включать одну единицу распределения ROW_OVERFLOW_DATA на секцию, если в индексе имеются столбцы переменной длины, в которых превышается максимальный размер строки, равный 8 060 байт.

Исключительно индексные таблицы и другие типы индексов на основе B-Tree

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

В некоторых СУБД, в частности в СУБД Oracle, исключительно индексные таблицы поддерживаются. Исключительно индексная таблица является индексом типа B-Tree БД, который одновременно исполняет роль таблицы. Все данные такой таблицы хранятся в индексе. Преимущество создания полностью индексированных таблиц состоит в экономии места хранения на диске и сокращении объема ввода-вывода, поскольку ключевые колонки нет необходимости сохранять еще раз в таблице. Результат выполнения запроса будет получен на основе данных, сохраненных в индексной таблице.

Исключительно индексная таблица в СУБД Oracle создается с помощью команды SQL CREATE TABLE.

Команда CREATE TABLE не отличается ничем от других команд создания таблиц — до тех пор, пока не встретится предложение ORGANIZATION INDEX, которое указывает СУБД на создание исключительно индексной таблицы. Для размещения индекса на диске указывается табличное пространство. Параметр PCTTHRESHOLD говорит, что оставшуюся часть строки нужно сохранять в заданном табличном пространстве — сегменте переполнения, если данная строка превышает размер физической страницы базы данных на указанное число процентов. Параметр INCLUDING определяет имя колонки, с которой строка индексной таблицы делится на две части: индексную и переполнения. Эта колонка может быть частью первичного ключа таблицы или неключевой колонкой. Все неключевые колонки, которые следуют за указанной колонкой, размещаются в сегменте переполнения, который определяется ключевым словом OVERFLOW.

В СУБД семейства MS SQL Server нет предопределенной возможности создавать исключительно индексные таблицы. Однако в ряде практических случаев в СУБД этого семейства можно создавать структуры, аналогичные исключительно индексным таблицам. Для этого может быть использован некластеризованный индекс с включенными колонками (опция INCLUDE команды CREATE INDEX).

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

В семействе СУБД Oracle предусмотрено еще несколько типов индексов, которые позволяют улучшить традиционные для всех СУБД индексы со структурой B-Tree. К таким модификациям, помимо исключительно индексных таблиц, относятся битовые индексы, индексы с обращением ключа, индексы на основе значения функций.

Каждый бит так называемого битового (bitmap) индекса относится к идентификатору строки ROWID (который в Oracle создается и хранится для каждой строки и используется во внутренней организации индексов ) в табличном объекте. Если некоторая строка содержит данное ключевое значение, то в индексе для этого значения сохраняется единица. Такая организация индекса может в некоторых случаях значительно повысить производительность выборки данных, т. к. для извлечения строк с определенными значениями индекса СУБД нужно лишь найти все единицы, отвечающие ключу. Физически такой индекс организован на основе структуры B-Tree, но задача сводится к поиску данной строки за счет одной операции чтения битовой индексной структуры. Этот тип индекса очень эффективен для индексирования колонок с небольшим кардинальным числом — пол, цвет и т.д. Если значений у колонки будет много, то объем ввода-вывода будет возрастать.

В СУБД семейства MS SQL Server возможность создания битовых индексов средствами диалекта SQL отсутствует.

В индексе с обращением ключа (reverse-key index) применяется обращение байтов индексируемой колонки числового типа. Этот прием позволяет получать равномерное распределение значений колонок среди блоков-листков индекса со структурой B-Tree, который хорошо подходит для индексирования колонок с последовательной нумерацией или нумерацией с заданным шагом. Заметим, что такие индексы применяются только для возвращения отдельных строк, и с их помощью нельзя выполнить поиск значений в некотором диапазоне. В СУБД Oracle нельзя применить опцию REVERSE к битовым индексам и к исключительно индексным таблицам.

В СУБД семейства MS SQL Server возможность создания индексов с обращением значения ключа средствами диалекта SQL отсутствует.

Если в предложении WHERE применяется функция по индексированной колонке, то обычно СУБД не используют этот индекс при организации доступа к строкам таблицы. Но при создании индекса на основе значения функции (function-based index), которая является той же функцией, что и в предложении WHERE, СУБД как семейства Oracle, так и семейства MS SQL Server использует такой индекс для считывания строк, удовлетворяющих критерию отбора.

В СУБД семейства MS SQL Server вычисляемые колонки могут иметь свойство PERSISTED. Это означает, что компонент Database Engine хранит вычисленные значения в таблице и обновляет их при обновлении любых колонок, от которых зависит вычисляемый столбец. Компонент Database Engine использует эти материализованные значения, когда создает индекс по колонке и когда запрос обращается к индексу.

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

  1. вычисляемые столбцы, основанные на выражениях языка Transact-SQL, функциях CLR и методах пользовательских типов данных CLR, отмеченных пользователем как детерминированные;
  2. вычисляемые столбцы, основанные на выражениях, которые определены компонентом Database Engine как детерминированные, но не являются точными.

При наличии в БД такого индекса СУБД будет его использовать при обработке запроса описанного в данном примере.

В СУБД семейства MS SQL Server можно создавать и использовать фильтрованные индексы, для создания таких индексов в команде CREATE INDEX предусмотрена возможность использования предложения WHERE

.

Применение предложения WHERE <filter_predicate> создает отфильтрованный индекс путем указания строк для включения в индекс. Отфильтрованный индекс должен быть некластеризованным индексом для таблицы. Также создается статистика фильтрации для строк данных отфильтрованного индекса.

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

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

О некоторых параметрах проектирования индексов

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

Кардинальностью колонки (cardinality) таблицы называется число дискретных различных значений колонки, которые встречаются в строках таблицы. Например, если в таблице "Служащий" (EMPLOYEE) мы заводим колонку для указания пола – "Пол" (SEX), то кардинальность этой колонки есть 2, так в природе у людей существует только два пола — мужской и женский. Для колонки первичного ключа кардинальность будет равна числу строк в таблице.

Причина, по которой кардинальность колонки важна для проектирования индексов, состоит в том, что кардинальность индексируемой колонки определяет число уникальных входов, которые должны сохраняться в индексе, т.е. число записей в индексе. Так, для индексируемой колонки "Пол" (SEX) будут существовать два уникальных входа, которые будут повторяться много раз в индексе. При предположении равновероятного распределения пола сотрудников на 100000 строк в таблице "Служащий" (EMPLOYEE) каждый вход индекса будет повторяться 50000 раз. СУБД вряд ли будут принимать решение об использовании такого индекса при построении плана запроса.

Определить кардинальность потенциальной колонки индексирования в существующей таблице БД достаточно просто.

SELECT COUNT (DISTINCT колонка) FROM таблица;

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

Хорошими кандидатами для индексирования обычно являются:

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

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

Факторы, влияющие на низкую эффективность индексов:

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

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

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

Плохими кандидатами для индексирования обычно являются:

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

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

  • колонки с часто изменяемыми значениями. Индекс для таких колонок часто обновляется, что приводит к его переполнению, поскольку в большинстве алгоритмов обработки B-Tree-индексов физическая страница индекса становится доступной для распределения данных только после того, как из нее будет удалена последняя запись. В частности, это обстоятельство приводит к созданию дополнительных страниц индекса и уровней индекса ;

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

Следует соблюдать следующие общие правила при создании индексов.

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

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

  1. гарантировать уникальность значений колонки, которая будет индексироваться;
  2. увеличить производительность обработки запросов в ХД. Это, кстати, единственная разумная причина для создания неуникальных индексов.
Характеристика колонок для создания индексов

Рис. 1.2. Характеристика колонок для создания индексов

Просмотры
Инструменты

Besucherzahler russian mail order brides
счетчик посещений
Rambler's Top100
Лингафонные кабинеты  Интерактивные доски  Интерактивная приставка Mimio Teach