InterBase: тормозология и глюконавтика
Страница 6. Индексы

Индексы

• По конкретному значению выйти на нужную запись. Это, в частности, используется при поиске и при проверке на дублирование значений ключа.
• Выйти на следующую запись после текущей в порядке возрастания/убывания значений поля. Многократно выполняя эту функцию, можно выбрать всю таблицу в отсортированном порядке. Бывает полезно для отработки соединений.
• Комбинируя две предыдущие функции можно пройтись по записям с заданным диапазоном значений.
• Сортировка означает группировку - в процессе прохода по индексу легко идентифицировать границы групп.
• Выйти на запись с минимальным/максимальным значением поля (как выяснилось, этого InterBase 4.x не умеет, хотя пятый по слухам научился).

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

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

А вот с балансировкой дело довольно нехорошо. Дело в том, что до версии 5.5 interbase не умел автоматически балансировать свои индексы. 5.5 умеет, но только на ODS 9. В остальных случаях единственный способ - разактивизировать индекс и создать его заново. Это проходит для пользовательских индексов, но для системных, то есть тех, которые созданы, как часть ключевых ограничений - никак. Только полный перебэкап.

Казалось бы, что за проблема - балансировка? При случайных обновлениях данных вероятность того, что дерево сильно разбалансируется и станет длинным, действительно мала. Но вот только на практике слишком многие и слишком важные индексы обновляются неслучайно. Классический случай - первичный ключ из генератора. Добавляются значения строго по возрастанию. А это значит, что они будут добавляться строго в одну ветку дерева. В результате эта ветка разрастается в линейный список. И начинаются тормоза. Причём замечу, не при разработке и обычно не при тестировании, а при реальной работе. И далеко не сразу, а тогда, когда база существенно заполнена. Ещё один повод регулярно бэкапиться.

Этот же эффект нужно учитывать при массовой вставке. Если есть возможность, то лучше снять со вставляемой таблицы все индексы и все ключевые ограничения, которые её так или иначе касаются. А потом, после заполнения - создать. Свежесозданные индексы всегда сбалансированы правильно.

Тем не менее похоже, что interbase одними "деревянными" операциями не ограничивается. В планах имеется возможность указать сканирование таблицы по нескольким индексам сразу. Детали этого процесса, как обычно, неизвестны, но в некоторых местах эта операция названа побитовым слиянием. Возможно, намекают на то, что структура индекса предусматривает наличие битов при наличии определённых значений. В таком случае для поиска записей, удовлетворяющих одному и другому условию можно сделать побитовое "и" двум участкам индексов. Оставшиеся биты будут соответствовать нужным значениям. Аналогично можно проделывать "или", инверсию, и следовательно, всё что угодно.

Вот только применимость таких стурктур, насколько мне известно, сильно ограничена. Как разработчики interbase их присобачили к деревьям и насколько это реально полезно, сказать затрудняюсь.

Хотя есть и другое предположение: что interbase просто вычисляет пересечение и объединение множеств значений из нескольких индексов вполне обычными для деревьев методами. Или чем-то похожим на слияние отсортированных последовательностей, которое будет описано ниже. Только вот биты тут уже получаются непричём. В общем, факт в том, что проход по нескольким индексам работает, и достаточно эффективно. Когда interbase этим не злоупотребляет.

К страницам индексов применимы примерно те же соображения о заполненности, что и к страницам данных таблиц. Та же утилита gstat выдаёт по индексам следующую информацию:

• Глубину дерева (depth)
• Количество терминальных страниц (которые со ссылками на записи данных, leaf buckets)
• Количество ссылок в индексе (nodes)
• Среднюю длинну данных (average data length), которая почему-то всегда 0.
• Общее количество продублированных значений и максимальное количество дубликатов одного значения (dup, используется для оценки эффективности поиска записи через данный индекс). Если индекс уникальный, то эти параметры обнуляются - уникальный индекс считается самым эффективным в смысле поиска.
• Распределение заполненности страниц, как и для таблиц.

В разделе про таблицы я писал, в частности, о том, как interbase обращается со строками. Всё бы это ничего, данные пертурбации почти не заметны с точки зрения клиента, за исключением одного случая. Когда создаётся индекс, суммарная длинна всех значений, составляющих ключ, обязана уместиться в 256 байт. Иначе interbase пошлёт Вас по-дальше.

Буфер ключа формируется из размеров значений, взятых по максимуму. То есть значения Integer расходуют по 4 байта, Double precision - 8 байт, и т. д. Под строку будет отведена длинна, описанная в метаданных. Независимо от того, char это, или varchar. Зато никаких двухбайтовых заголовков. Правда, у ключа в целом есть заголовок длинной 4 байта.

И вот тут-то выясняется, что строки в национальных кодировках помещаются в индекс в трёхбайтовом формате! То есть упомянутая 20-символьная строка, если она русская, займёт 60 байт. Таким образом, если мы индексируем одно русское строковое поле, то его максимальная длинна может быть (256 - 4) / 3 = 84 символа. Когда-то раньше я говорил, что 64, но тогда я не понимал природу ситуации. Точная цифра - 84. Дальше - Кю. Если же в составе индексируемого ключа присутствуют другие значения, то останется ещё меньше. А индексировать часто нужно именно национальные строки, чтобы не различались заглавные и строчные буквы в соответствии с правлиами нашего языка.

Тем не менее, один мужик (читал где-то на https://interbase.demo.ru) изобрёл способ, как с этим боросться. Я, правда, пока не испытывал, но думаю, должно работать.

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

Далее к таблице приписывается поле с кодировкой nne, той же длинны, что и индексируемое. Затем к таблице приписывается триггер, который по обновлению русского поля автоматически записывает соответствующее значение в верхнем регистре в дополнительное "космополитичное" поле. Если в таблице уже есть данные, нужно её проапдейтить, чтобы дополнительное поле засинхронизировалось с основным. После чего по дополнительному полю строится индекс. Этот индекс сможет проглотить строки до 252 байт длинной. И он будет упорядочен именно без учёта регистра, поскольку строки соответствующим образом обработаны. Во многих случаях этого достаточно.

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

В заключение ещё одно замечание: при поиске по строковому полю индекс используется только при сравнениях с целой строкой (=, <, >). В некоторых случаях индекс используется при starting with. Остальные операции (like, containing) всегда делают свою работу перебором, причём по записям самой таблицы, а не индекса. Хотя индекс содержит информацию колонки таблицы, но в более компактной форме. Однако interbase такое не умеет.