İndeksler (InterBase ve Firebird)
Alexey Kovyazin, последнее обновление 07-сен-2005
Концепция, положенная в основу индексов, проста и наглядна и является одной из важнейших основ проектирования баз данных. На основе индексов построены многие базовые объекты баз данных, и, более того, правильное использование индексов является ключом к повышению производительности приложений баз данных. Однако что такое индекс? Индекс - это упорядоченный указатель на записи в таблице. Указатель означает, что индекс содержит значения одного или нескольких полей таблицы и адреса страниц данных, где эти значения расположены (подробнее о страницах данных см. главу «Структура базы данных InterBase») (часть 4). Другими словами, индекс состоит из пар значений «значение поля» - «физическое расположение этого поля».
Таким образом, по значению поля (или полей), включенного в индекс, используя индекс, мы можем быстро найти то место в таблице, где находится запись, содержащая это значение. Упорядоченный означает, что значения полей, хранящиеся в индексе, упорядочены. Очень часто индекс сравнивают с библиотечным каталогом, в котором все книги записаны на карточки и упорядочены некоторым образом: по алфавиту или темам, и в каждой карточке содержится информация о том, где именно находится данная книга в хранилище.
Зачем нужны индексы?
Единственное, чему способствуют индексы, - это ускорение поиска записей по индексированному полю (индексированное - означает включенное в индекс). Основная функция индексов - обеспечить быстрый поиск записей в таблице. Любое использование индекса сводится к этому.
Как реализуется эта функция поиска? На входе этой функции мы имеем значение индексированного поля (или нескольких полей). В результате поиска мы должны получить всю запись, в которой индексированное поле имеет заданное значение. Сначала в индексе (точнее, в упорядоченном массиве значений индексированного поля) ищется требуемое значение, затем берется адрес страницы данных, где находится нужная запись, сервер переходит на эту страницу и читает найденную запись. Это выглядит довольно неудобно, однако поиск с использованием индекса во много раз быстрее, чем последовательный перебор всех значений из таблицы.
Если продолжить аналогию между индексом и библиотечным каталогом, мы увидим, что поиск записей с использованием индекса очень похож на поиск книги по карточке. Когда мы находим книгу в довольно небольшом каталоге (по сравнению со всем библиотечным хранилищем), мы сразу получаем информацию о том, где именно хранится книга, и можем идти прямо туда. Поиск без использования индекса можно сравнить с последовательным перебором всех книг в библиотеке!
Перебор всех записей в таблице называется прямым или естественным. Следует сказать, что, несмотря на мощность современных компьютеров, естественный перебор может быть очень долгим, если таблица содержит большое количество записей.
Как они организованы?
Индекс не является частью таблицы, это отдельный объект, связанный с таблицей и другими объектами базы данных. Это очень важный момент реализации СУБД, позволяющий отделить хранение информации от ее представления.
InterBase, как и любая другая реляционная база данных, хранит записи в таблицах в неупорядоченном виде, то есть вообще не заботится о том, как записи физически размещены в таблице. Неупорядоченное хранение означает, что две записи, добавленные в таблицу одна за другой, могут не находиться рядом. Более того, данные, извлекаемые из таблицы, также не имеют порядка, кроме того, который должен быть явно задан пользователем, выполняющим поисковый запрос.
Однако без упорядочивания хранимых данных не обойтись: конечные пользователи приложений хотят видеть данные в определенном порядке - например, фамилии людей в алфавитном порядке. Индексы решают проблему представления данных в упорядоченном виде. Значения полей, включенных в индекс, упорядочены и представлены в специальном виде, оптимизированном для поиска требуемых значений (именно это важно для создания упорядоченных последовательностей).
Разделение хранения данных и их представления дает дополнительные преимущества по сравнению с прямой сортировкой - возможно, вам потребуется сортировать исходную таблицу разными способами. Тогда вам помогут индексы - для каждой таблицы может быть до 64 индексов!
Если говорить о реализации индексов на физическом уровне, они представляют собой бинарное дерево, узлы которого представляют пары «значение поля в индексе» - «размещение данных в таблице». Поиск нужной записи в индексе выполняется с помощью механизма хэш-поиска - одного из самых быстрых алгоритмов поиска.
Применение индексов
Теперь, когда ясно, что мы можем требовать от индексов, пора узнать об их функции в базе данных. Индексы используются в трех основных случаях:
-
Ускорение выполнения запросов. Индексы создаются для полей, используемых в условиях поиска SQL-запросов.
-
Поддержка уникальности значений в полях; ограничение первичного ключа (о котором говорилось в главе «Таблицы. Первичные ключи») требует, чтобы в таблице не было двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, при вставке новой записи следует искать то же значение, которое будет вставлено. Для поиска записей используется особая разновидность индекса - уникальный индекс (см. ниже).
-
Поддержка ссылочной целостности. Ограничения внешних ключей (которые рассматриваются в главе «Ограничения базы данных») используются для проверки того, что значения, вставляемые в таблицу, обязательно существуют в другой таблице. При создании внешнего ключа автоматически создается индекс. Этот индекс применяется для ускорения запросов, использующих соединение таблиц, а также для проверки условий внешнего ключа. Мы кратко рассмотрели все возможные применения индексов. Теперь рассмотрим особенности каждого случая более подробно и ответим на наиболее часто возникающие вопросы, касающиеся применения индексов.
Ускорение выполнения запросов с помощью индексов
Выше описано, что применение индексов может значительно ускорить выполнение запросов. Это действительно так в большинстве случаев, но есть определенные оговорки. Сначала ответим на вопрос, часто возникающий у тех, кто познакомился с индексами. Если индексы ускоряют поиск в базе данных, почему бы не индексировать все поля в таблице? Есть два момента, препятствующих всеобщему индексированию, - дисковое пространство и затраты при изменении данных в таблице. Каждый созданный индекс имеет размер, равный размеру данных в индексируемом поле, плюс размер данных о размещении записей. Если создать индексы для каждого поля в таблице, их общий размер будет больше размера данных в таблице! Поэтому создание большого количества индексов приводит к огромным затратам дискового пространства.
Второй момент более важен. Это затраты при изменении данных в таблице. В реляционной СУБД, как известно, записи в таблицах неупорядочены, и поэтому добавление/удаление записей происходит без значительных затрат ресурсов сервера. Даже если запись удаляется из середины базы данных, нет перемещения объемов данных для заполнения этой пустоты - это не требуется: сервер просто пометит пустое место и запишет туда что-нибудь при необходимости. Что касается добавления, в большинстве случаев оно выполняется в конец таблицы. Однако, хотя сервер не перемещает основные данные в таблице при изменении, данные, хранящиеся в индексах, переупорядочиваются каждый раз при добавлении/удалении записей! Другими словами, серверу приходится перестраивать индекс при добавлении записи в середину таблицы. Конечно, реализация индекса так или иначе рассчитана на частые реорганизации, но эти операции тем не менее занимают время и ресурсы процессора, и при большом количестве индексов в таблице изменение данных в ней может быть намного медленнее, чем в той же таблице без индексов!
Это две основные причины, мешающие всеобщему индексированию. Кроме них, есть еще некоторые замечания, ограничивающие применение индексов. Первое - правило 20 %. Оно гласит, что если поисковый запрос возвращает более 20 % записей из таблицы, использование индекса может замедлить поиск данных! Конечно, ситуация зависит от конкретного запроса и условий, заданных для поиска, но следует помнить, что 20 % записей - это порог, когда эффективность использования индексов становится сомнительной. Второе замечание сформулировано не так четко. Оно связано с работой оптимизатора InterBase.
Оптимизатор - это совокупность механизмов, которые разрабатывают план выполнения запроса. Когда пользователь дает InterBase любой SQL-запрос, он указывает, что сервер должен вернуть после выполнения запроса, но не определяет, КАК сервер должен выполнить запрос. Оптимизатор на основе данного запроса создает план его выполнения, то есть откуда и в каком порядке будут взяты данные для выполнения запроса, какие индексы при этом будут использоваться. Когда сервер анализирует условия поиска (это в основном части выражения WHERE, ORDER BY и т. д.) для каждого поля, включенного в условие, сервер пытается использовать индекс. К сожалению, алгоритм создания плана несовершенен, и оптимизатор часто использует индексы, которые не слишком эффективны для конкретного запроса, из-за чего время выполнения может существенно замедлиться. Поэтому создание ненужных индексов может привести к созданию неоптимальных планов.
Следует отметить, что в клоне Yaffil эта проблема решена благодаря использованию современных алгоритмов составления планов. Третий случай, когда индекс не нужен, - это поля с ограниченным набором значений. Например, поле, хранящее информацию о поле человека и содержащее только два возможных значения - «F» и «M»; нет смысла индексировать это поле. Итак, мы рассмотрели основные ограничения при создании индексов. Теперь следует рассмотреть вопрос, когда необходимо использовать индексы для достижения повышения производительности. Есть 3 основных случая, когда поле должно быть индексировано:
- Когда это поле используется в условиях поиска в запросах
- Когда соединения таблиц используют это поле
- Когда это поле используется в операторе сортировки ORDER BY
Если поле применяется вышеуказанным образом, создание индекса для него может привести к повышению производительности запросов.
Рассмотрим синтаксис создания индексов. Вот полный формат команды DDL, которая позволяет создавать индексы:
CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);
Минимальное выражение, создающее индекс, выглядит следующим образом:
CREATE INDEX my_index ON Table_example(ID)
В этом примере индекс с именем my_index создается для таблицы Table_example, а поле ID является индексируемым полем. Индекс является восходящим, то есть значения в нем упорядочены по возрастанию, а также неуникальным, что означает, что поле ID может иметь несколько одинаковых значений. Это, конечно, самый простой пример индекса - самый распространенный. Как видно из описания синтаксиса, индекс может содержать не одно, а несколько полей. Такой индекс используется, когда запросы часто выполняются и содержат комбинацию индексированных полей в условиях поиска или сортировки. Например, если у нас есть таблица, содержащая поля Фамилия, Имя, Отчество, такой индекс будет применяться при выполнении запроса, использующего сортировку по Фамилии, Имени и Отчеству. В общем, не обязательно указывать условия для всех 3 полей, применяемых в индексе, чтобы использовать его преимущества. Если мы хотим отсортировать результат запроса, индекс будет использован в случае, если первое поле в условии сортировки совпадает с первым полем в индексе. Например, наш индекс будет применен в случае сортировки по Фамилии и Имени.
Согласно документации, для оптимизации выполнения запроса, содержащего в операторе WHERE соединение полей с условием OR, следует использовать не совокупный индекс, а несколько одиночных для всех полей, включенных в условие OR.
Sorunun dizin sıralama düzenine gelince, bu ya artan ya da azalan olabilir. Neden farklı sıralama düzenlerine ihtiyaç duyarız? Açıkçası, farklı sıralamalar için! İnsanları soyadına göre artan sırada sıralamak istiyorsak, artan dizini (ASC) oluştururuz; azalan sırada (Z’den A’ya) sıralamak istiyorsak - o zaman azalan! Her ikisini de istiyorsak, her iki dizini de oluşturmak zorundayız.
Dizinler kullanılarak referans bütünlüğünün desteklenmesi
Dizin tanımında bir seçenek daha vardır - UNIQUE. Bunu belirtirsek, dizin tabloya yalnızca benzersiz değerlerin eklenmesine izin verir. Aslında bu, benzersiz anahtarların uygulanmasının temelidir. Benzersiz anahtarlar veritabanlarında yaygın olarak kullanılır. Yani РК benzersiz bir anahtar-dizindir, ancak her UK bir РК değildir. Yukarıda yalnızca РК hakkında konuştuk. Birincil anahtar, benzersiz anahtarın en yaygın kullanılan türüdür. Tablo için birincil anahtar oluşturulduğunda otomatik olarak benzersiz bir dizin oluşturulur. Bu dizine RDB$PRIMARYNNN adı verilir; burada NNN, veritabanı içinde sıralı benzersiz bir sayıdır. Böylece, referans bütünlüğünün iki ana kısıtlaması - benzersiz anahtar ve birincil anahtar - benzersiz dizin kullanılarak gerçekleştirilir. Benzersizlik kavramının tanımsız değer kavramıyla bağdaşmadığı açıktır. Başka bir deyişle, benzersiz dizinlerde yer alan alanlarda NULL türünde hiçbir değer bulunmamalıdır. Bir alan için benzersiz dizin oluşturmadan önce NOT NULL kısıtlamasını ayarlamak gerekir. Dizin zaten mevcut olan veriler için oluşturuluyorsa, oluşturma sırasında dizinlenen alan tekrarlayan değerler içerip içermediği açısından kontrol edilir. İçeriyorsa, dizin oluşturmanız engellenir.
Benzersiz ve birincil anahtar kısıtlamalarının yanı sıra, dizin mekanizması referans bütünlüğünün bir kısıtlamasının daha uygulanmasının temelini oluşturur - yabancı anahtar. Yabancı anahtar kısıtlaması herhangi bir tablonun bir veya birkaç alanı için ayarlanır ve bu alanlara diğer, üst tablonun birincil anahtarında yer almayan değerlerin eklenmesini engeller. Yabancı anahtarın uygulanması için, yani üst tabloda bir değerin olup olmadığının kontrolünün yapılması için otomatik olarak özel bir dizin oluşturulur. Adı RDB$FOREIGNNN’dir; burada NNN, veritabanı içinde sıralı benzersiz bir sayıdır.
Referans bütünlüğü kısıtlamalarının uygulanması için dizin mekanizması neden kullanılır? Mesele şu ki, InterBase’deki dizinler özel, ayrıcalıklı bir konumdadır - işlem bağlamı dışında yürütüldükleri söylenir. Bu çok önemli bir özelliktir. İşlemler hakkında daha sonra, onlara ayrılan bölümde konuşacağız. Şimdi yalnızca şunu belirteceğiz: dizinler işlemlerin dışında olduğunda, aynı tablodaki verilerle aynı anda çalışan tüm kullanıcıların referans bütünlüğü kısıtlamalarına uyması gerektiği anlamına gelir.
Dizin verimliliğinin optimizasyonu
Bu bölümün başlığında bazı paradokslar bulabiliriz - dizinler, yukarıda belirtildiği gibi, sorguların yürütülmesini hızlandırmak içindir ve görünüşe göre onların da optimize edilmesi gerekir! Ama ne yapalım (hayat böyle) - birilerinin dizinlerle ilgilenmesi gerekir. Dizinlere ne olur? Neden “formlarını kaybederler”? Bir kez daha söylemek zorundayız ki dizinler ikili ağaç olarak gerçekleştirilir. Ve tabloya yeni bir kayıt eklendiğinde (güncellendiğinde, silindiğinde - nasıl isterseniz), ağaca yeni bir dal eklenir. Bu dallar ağacın ortasına değil, diğer dalların tepelerine eklenir. Yavaş yavaş ağaç giderek daha dallı (veya dengesiz) hale gelir ve arama - daha az etkili olur. Ağacın yeniden oluşturulması veya (bazı durumlarda) istatistiklerin yeniden hesaplanması durumu iyileştirebilir.
Dizinin verimliliğini geri kazandırmak için periyodik olarak yeniden oluşturulması gerekir. Dizin yeniden oluşturma şu durumlarda gerçekleşir:
- ALTER INDEX komutu kullanılarak dizin yeniden oluşturulduğunda.
- DROP INDEX ve CREATE INDEX komutları kullanılarak dizin silinip yeniden oluşturulduğunda.
- gbak aracı kullanılarak yedekleme ve yedek kopyadan geri yükleme yapıldığında.
Ayrıca istatistiklerin yeniden hesaplanmasını da kullanabilirsiniz. Ancak bu işlemin dizin durumunu değiştirmediğini, yalnızca optimize ediciye dizinin durumu hakkında kesin bilgi vererek bu dizini doğru şekilde kullanmasını sağladığını anlamak gerekir. Başka bir deyişle, istatistiklerin yeniden hesaplanması dizinin “tedavisi” değil, yalnızca durumunun doğru teşhisidir. Tüm bu dizin optimizasyon yollarını daha ayrıntılı olarak ele alalım. ALTER INDEX komutunun kullanımı şu biçime sahiptir:
ALTER INDEX name {ACTIVE | INACTIVE};
Burada name dizinin adıdır ve ACTIVE ile INACTIVE - ALTER INDEX komutu kullanılarak dönüştürülebileceği dizinin iki durumudur. ACTIVE parametresi dizinin aktif olduğu ve tüm sorgularda ve prosedürlerde uygulanabileceği anlamına gelir. Dizini INACTIVE olarak ayarlarsanız, bu kullanımının devre dışı bırakılmasıyla sonuçlanır. Ağacı yeniden düzenlemek için iki komut sırayla yürütülmelidir:
ALTER INDEX name INACTIVE; ALTER INDEX name ACTIVE;
Böylece dizin yeniden oluşturulacaktır. ALTER INDEX kullanımının bir dizi kısıtlaması vardır: birincil, benzersiz ve yabancı anahtarlarda kullanılan dizinleri yeniden oluşturamazsınız; şu anda herhangi bir sorgu tarafından kullanılıyorsa dizini yeniden oluşturamazsınız; ayrıca dizini değiştirmek için yönetici (SYSDBA) haklarına sahip olmak veya verilen dizinin oluşturucusu olmak gerekir.
DROP INDEX ve CREATE INDEX komutları kullanılarak dizinin yeniden oluşturulması, dizinin veritabanından tamamen silinmesine ve ardından boş bir sayfadan oluşturulmasına yol açar. DROP INDEX komutunun sözdizimi açıktır:
DROP INDEX dizin_adı;
Sildikten sonra, sözdizimini zaten ele aldığımız CREATE INDEX komutunu kullanarak aynı ad ve parametrelerle dizini oluşturmak gerekir. Dizini tamamen yeniden oluşturarak yeniden yapılandırma yöntemi, ALTER INDEX kullanımına benzer kısıtlamalara sahiptir.
Dizini yeniden oluşturmanın üçüncü yolu, gbak yardımcı programı tarafından oluşturulan InterBase veritabanlarının yedek kopyalarının özelliğine dayanır. Mesele şu ki, yedekleme sırasında dizine dahil edilen veriler yedek kopyaya kaydedilmez, yalnızca dizin tanımı saklanır. Yedek kopyadan geri yükleme sırasında dizin yeniden oluşturulur. Yedekleme hakkında daha fazla bilgi edinmek istiyorsanız, “Yedekleme ve yedek kopyadan geri yükleme” bölümüne (bölüm 4) bakın.
Dizin verimliliğini artırmanın dördüncü yolu, SET STATISTICS komutunu kullanarak dizinler hakkında istatistik toplamaktır. Tablo istatistiği, tablodaki farklı kayıt sayısına bağlı olarak 0 ile 1 arasında değişen bir değerdir. InterBase optimize edici, sorguda şu veya bu dizinin uygulanmasının verimliliğini tanımlamak için istatistikleri kullanır. Tablodaki kayıt sayısı önemli ölçüde değişebildiğinde (örneğin, çok sayıda ekleme veya silme nedeniyle), istatistiklerin yeniden hesaplanması verimliliği önemli ölçüde artırabilir. İstatistik yeniden hesaplama komutu şu şekildedir:
SET STATISTICS INDEX name;
Burada name, istatistikleri yeniden hesaplanan dizinin adıdır. İstatistiklerin yeniden hesaplanması dizini yeniden oluşturmaz ve bu nedenle, yukarıda açıklanan verimlilik artırma yolları için belirlenen kısıtlamaların çoğundan muaftır; yalnızca dizinin oluşturucusu veya sistem yöneticisi (SYSDBA adlı kullanıcı) istatistikleri yeniden hesaplayabilir. Doğru istatistikler, optimize edicinin herhangi bir dizini kullanıp kullanmama konusunda doğru karar vermesini sağlar.
Dizinlerin verimliliğini artırmanın birkaç yolunu ele aldık. ALTER INDEX ve DROP/CREATE INDEX komutlarını kullanarak, referans bütünlüğünü sağlamak için otomatik olarak oluşturulan sistem dizinleri hariç herhangi bir dizini yeniden oluşturabiliriz. Bu dizinleri yeniden oluşturmak istiyorsanız, tablo değiştirme ve oluşturma komutlarını - ALTER TABLE ve CREATE TABLE - kullanmalısınız çünkü bu dizinler tablo anahtarlarının ayrılmaz bir parçasıdır.