Вообще преобразование запроса SQL в алгоритм, реализующий его путём элементарных операций над записями в базе -- задача достаточно сложная. Точнее, сложны качественные решения, работающие эффективно без ручного вмешательства, и дающие на выходе эффективные алгоритмы. Названия для этого процесса встречаются разные, чаще всего -- ``планирование'' или ``оптимизация'' запросов. Собственно план -- это и есть то, что получается на выходе и может быть исполнено без каких-либо дальнейших неоднозначностей.
К сожалению, InterBase в смысле оптимизации, мягко говоря, не лучшее изделие. Тем не менее, существуют и обходные возможности -- задавать планы отработки запросов вручную. И хотя и таким способом желаемая производительность иногда достижима ценой изрядного ручного труда, тем не менее для эффективной работы знания ручного и автоматического планирования InterBase просто необходимы.
Некоторых специальных случаев этой темы я касался выше; вот теперь дошли руки написать более общее введение.
В конечном итоге всё сводится к обращениям к отдельным таблицам. InterBase умеет осуществлять доступ к ним тремя способами.
Здесь и далее названия операций и форма их записи будет использоваться в том же виде, в каком они задаются в части plan оператора select, а так же в том, в каком их выдаёт большинство утилит, предоставляющих такую возможность. К счастью, синтаксис прост и в пределах InterBase стандартизирован.
Это самый тупой, самый универсальный, и самый неэффективный способ -- полный перебор. InterBase просто читает данные таблицы из базы с самого начала и либо до конца либо до того момента, когда найдёт всё, что требовалось. Смотря что наступит раньше. Оптимизатор обычно применяет natural, когда не в состоянии извлечь пользу из чего-либо другого. При ручном планировании его следует избегать, за исключением тех случаев, когда по смыслу задачи известно, что таблица должна быть выдана вся. Или почти вся и невыдаваемая часть несущественна.
Поиск по индексу. Один из двух способов использования индекса. Применяется тогда, когда известно значение поля, по которому существует индекс, и нужно извлечь остальную запись. Значение может быть известно из условия, например, here id = :param, или из соединения с другой таблицей, where t1.ref_id = t2.id. В последнем случае имеется в виду способ соединения join.
В случае применения нескольких индексов для обращения к одной и той же таблице производится их конвертация в битовые маски, в которых единицы и нули соответствуют подходящим и неподходящим записям. Эта технология обычно используется для эффективного вычисления сложных условий типа field1 = value1 and field2 = value2. В этом случае можно две маски, полученных из двух индексов, объединить через побитовую операцию and. На выходе единицы будут соответствовать тем записям, которые удовлетворяют и тому, и другому условию. Аналогичным образом возможна и отработка or.
В оптимизаторе InterBase версий 4.х была одна весьма нехорошая недоработка, часто заставлявшая его использовать путём битового слияния все индексы, какие только применимы в данном случае. Очевидно, что данная операция - не панацея, расходы на считывание и обработку дополнительных индексов могут и не окупиться. Это следует учитывать как при ручном планировании, так и при анализе автоматических планов.
Данный способ обращения тоже использует индекс, но не с целью поиска, а с целью перебора всей таблицы. Основных отличий от natural -- два. Во-первых, записи на выходе получаются в заданном порядке. Отсюда главная область применения -- order by и group by. Хотя бывает и для других целей. Во-вторых, в отличие от natural, сама выборка обычно происходит менее эффективно, потому что порядок хранения практически никогда не соответствует порядку выборки по индексу, так что приходится дёргать головку диска в разные части базы.
Обратите внимание, что имена индексов, служащих параметрами для index, берутся в скобки, в то время, как для order -- нет. Потому что в последнем случае индекс всегда ровно один.
Ну и теперь пройдёмся по операциям, которые применяются ``поверх'' трёх перечисленных.
Это ``любимый'' способ соединения таблиц, который оптимизатор применяет для реализации соединений между таблицами. Какое именно соединение -- внутреннее или внешнее, и с какой стороны внешнее -- однозначно определяется исходным запросом, так что в плане никогда не пишется.
На вход поступает несколько потоков записей. Эти потоки могут быть сформированы как операциями над одиночными таблицами, которые описаны только что, так и соединениями, и сортировками. На выходе, естественно, тоже получается поток записей, но один.
Пример:
join (t1 order rdb$primary5, t2 index (rdb$foreign33))
Альтернативный способ соединения. Порой единственный выход, если отсутствуют подходящие индексы. Дело в том, что join насколько хорош при их наличии, настолько же плох при отсутствии. Ведь он делает цикл по записям первого потока, для каждой делает поиск во втором потоке, для каждой полученной из второго -- в третьем потоке, и т. д. Достаточно, чтобы хотя бы в одном месте поиск шёл через natural, а не через index, и тормоза гарантированы. Разве что только если есть таблица, которая нужна полностью и она в joinе на первом месте.
Итак, merge сортирует все потоки, поступающие ему на вход, после чего сливает их за один проход. Возможно это именно при соединении по условию равенства и при условии отсортированности потоков записей по ключам соединения. Конечно, это тяжёлая операция, но зависимость времени от объёма данных остаётся чуть более линейной, то есть быстрее, чем вложенный перебор нескольких потоков, и в ряде случаев приемлемо.
Эту операцию обычно не пишут в ``ручных'' планах, однако её часто выдаёт InterBase при описании планов реально применяемых. Пересортировать поток записей, полученных одним из вышеприведённых способов, может понадобиться по разным причинам. Может быть нужно отработать group by или order by при отсутствии индекса. А может быть индекс и есть, но его использование сделает невозможным эффективные операции в другой части плана. Может быть нужно подготовить поток записей к merge. Или удалить дубликаты по требованию distinct или union.
Писать вручную не нужно по той причине, что потребность однозначно вытекает из исходного запроса и других конструкций плана. В старых версиях InterBase ещё было принято писать ``sort merge''. В принципе, не будет ничего страшного, если написать sort в том месте плана, где оно применимо и реально требуется.
И это фактически весь набор базовых операций, к которым InterBase должен свести любой запрос, связанный с поиском и выборкой данных. Косвенным образом при обновлениях и удалениях применяется index и natural, однако планы можно вписывать только в select. Ситуацию, правда, бывает возможно смягчить -- об этом чуть позже.
Некоторые из наиболее часто попадающихся вещей, об отсутствии которых приходится жалеть:
(f1, f2),
то было бы логично where f1=:param order by f2 отработать по нему.
Ведь часть дерева (составляющего основу структуры индекса), соответствующая
конкретному значению f1, оказывается автоматически отсортированной в порядке
по f2.
Хотя с другой стороны, InterBase всё-таки версионник, и потому использование в нём механизмов, традиционных для обычных, блокировочных СУБД порой приводит к весьма неожиданным эффектам. Но не буду уклоняться от основной темы.
Довольно тёмная область, на самом деле. И постоянно всеми ругаемая. По той причине, что InterBase не всегда умеет эффективно использовать даже те возможности, что предоставляют его собственные механизмы доступа.
(Ранее здесь был абзац со ссылками на описания процесса оптимизации запросов в IB. В мае 2004 года один из читателей - Вячеслав Буфетов - подсказал, что все ссылки уже устарели. Найти новые адреса документов тоже к сожалению не получилось. Хотя я и не работаю больше в данной области, тем не менее на всякий случай эти ссылки оставлю, может кто найдёт ... http://www.ibase.ru/devinfo/SETPLAN.TXT и http://www.ibphoenix.com/ibp_quep.html)
Аналогичного рода информацию можно найти в справке по SQL и в документации (pdf). В теории всё выглядит вроде бы прилично, но на практике -- не очень. Переводить мне, как и всем остальным, на данный момент лениво, так что пока пропущу.
Немаловажную роль в процессе выбора планов (и не только автоматического, но и ручного) играют индексы. По поводу них ряд ссылок можно найти у Дмитрия Кузьменко.
К каждому индексу в базе приписан набор параметров -- статистика. Эти параметры должны отражать реальное состояние индекса, количество записей в нём, долю повторяющихся значений, и т. п. Их основная цель -- позволить оптимизатору оценить, насколько трудоёмкой окажется данная операция над данным индексом. Очевидно, что чем лучше эта информация соответствует действительности, тем лучше будет работать оптимизатор, а значит и InterBase в целом.
К сожалению, на практике всё бывает не так хорошо. Когда индекс создаётся для пустой таблицы, его статистика так же состоит из параметров пустой таблицы. И когда таблица заполняется данными, статистика становится полным враньём. Аналогичная ситуация возникает, когда состояние таблицы меняется радикальным образом (добавляется или удаляется большое количество записей).
Заставить InterBase перегенерировать статистику можно двумя способами:
Итак, планы вписываются в структуру оператора select. То есть
зарезервированное слово plan, и дальше сам план буквально в том виде, в
котором я его описал выше. Место для этой конструкции - после
from/where/group/having, и перед union/order. Не следует
смущаться того, что order by пишется после плана -- план всё-таки может
применяться для и оптимизации упорядочения, если это упорядочение относится
именно к данному select, а не к результату union нескольких
подзапросов.
Для пущей наглядности -- простой пример:
select * from t1, t2 where t1.id = t2.id
plan join( t2 natural,
t1 index(rdb$primary2))
order by t1.id;
Индекс rdb$primary2 -- это по t2(id).
Как правило, легче всего в первый раз прогнать проблемный запрос без плана, взять то, что сделал InterBase, дописать в запрос, и затем извращать по собственному разумению.
Большая проблема состоит в том, что приходится вписывать в планы имена
системных индексов. Универсального решения проблемы, к сожалению, не существует.
По крайней мере в нынешних версиях InterBase. В своё время я пришёл к тому, что лучше
прочитать из базы rdb$indices join rdb$index_segments при подключении
клиента, и далее по ходу работы использовать прочитанное -- благо информация
по объёму невелика.
Что касается хранимых процедур и триггеров, то здесь могут быть и другие
неприятности. В InterBase версий 4.х база с планами в процедурах
не восстанавливалась (backup проходил нормально) по той причине, что
индексы окончательно создавались уже после процедур. В более поздних
версиях это поправили, но проблема с ``нестабильностью'' ссылок на системные
индексы осталась. С другой стороны, в процедурах часто можно ``раскрутить''
запрос в набор вложенных for select, что бывает приблизительно
аналогично плану с явным join(...), в том числе и по эффективности,
поскольку всё происходит внутри сервера. Засчёт этого обычно удаётся косвенным
путём удовлетворить потребность в явных планах.
Просматривая автоматически сгенерированные планы, легко убедиться, что
планы для подзапросов, отдельных частей union, и запросов внутри
процедур генерируются по отдельности. Точно так же их нужно и указывать --
приписывая к ``своему'' select'у. Ситуация, когда к одному
select'у в сложной конструкции приписан план, а к другому -- нет,
вполне допустима. InterBase в этом случае сам ``додумает'' то, что остаётся.
Однако если в каком-то месте план написан, то он должен быть написан
для своего запроса (select-from-where) целиком.
Если сложный запрос выдаёт множество планов, то планы подзапросов выдаются
isql (и другими подобными инструментами) перед планом содержащего
их запроса, в том порядке, в котором они перечислены в исходнике.
Аналогичные принципы при выдаче планов процедур, только они часто
склеиваются в одну строку и приобретают не очень удобный для просмотра
вид. Планы запросов, расположенных в теле цикла for select при этом
выдаются аналогично подзапросам -- до плана самого for select.
Вообще если бы не последняя особенность, то я бы посоветовал такую
метафору: представьте, что в исходном запросе все планы вписаны явно, и
запомните их порядок. Порядок выдачи должен соответствовать.
Ну и в заключение этой части замечу, что с ситуация с выдачей планов в прошлых версиях была существенно хуже, нежели в шестёрке. Мне попадались, например, были представления с distinct, которые, если включить их в запрос, просто отключали выдачу плана.
Один из самых объёмных частных случаев. Общий принцип состоит в том, что InterBase пытается ``раскрыть'' запрос, находящийся у представления внутри, и сгенерировать общий план, включающий в себя как представление, так и охватывающий запрос. Однако далеко не всё и не всегда при этом возможно.
Самый удобный случай -- когда внутри представления находится либо одна таблица, либо соединение нескольких внутренним соединением (явным или неявным -- не важно). При этом в представлении не должно быть группировок, или distinct, так как они вызывают пересортировку и практически неминуемо заставляют отработать представление отдельно от остального запроса. Так же не должно быть процедур и агрегатных функций. То есть только обычные соединения и фильтрация. В этом случае InterBase сможет спокойно объединить списки соединяемых таблиц, и реализовать соединение в любом подходящем порядке. Вовсе не обязательно, чтобы сначала соединялись таблицы внутри представления, а затем те, что вне его.
В качестве иллюстрации приведу пару примеров:
create view vt1t2(id, v1, v2)
select t1.id, t1.v, t2.v
from t1, t2
where t1.id = t2.id;
select count(*) from vt1t2, t3
where vt1t2.id = t3.id;
Предполагаем, что id -- везде ключи, и соответственно по ним имеются индексы. План в последнего запроса у меня образовался следующий:
PLAN JOIN ( T3 NATURAL,
VT1T2 T2 INDEX (RDB$PRIMARY3),
VT1T2 T1 INDEX (RDB$PRIMARY2) )
Мне кажется, отсюда уже должно быть достаточно очевидно, как это работает. Во-первых, имена таблиц, находящихся в недрах представлений, двойные. Сначала пишется имя представления, а за ним через пробел -- имя таблицы внутри представления. Кстати, и в том, и в другом месте (и не только в связи с представлениями) можно употреблять и алиасы -- краткие временные имена, присваиваемые таблицам в пределах одного запроса. В ``двойном'' случае в качестве первого имени допускается алиас, определённый во внешнем запросе, а в качестве второго -- алиас, определённый внутри представления. Ну и как обычно, алиасы становятся обязательными там, где на уровне исходных имён таблиц существует неоднозначность.
В данном случае InterBase объединил оба соединения (и то, что снаружи представления, и то, что внутри) в одно. Причём сначала соединяется ``внешняя'' и ``внутренняя'' таблица, прямо через границу представления, а затем к ним подсоединяется третья.
К сожалению, в жизни довольно часто попадаются случаи, когда в представлении к таблицам применяются не только соединения и фильтры. В таком случае у InterBase резко сужается круг возможностей, и он строит для представления строго ``автономный'' план, который затем вкладывается в план внешнего запроса, как отдельный поток. А поскольку на выходе этот поток обычно даёт неотсортированную последовательность записей, лишённую всяких индексов, то соединение с остальными таблицами происходит через merge.
Конечно, если под рукой есть реальные данные, то можно просто запустить запрос на них, и посмотреть, за сколько времени он отработает. А так же перегенерировать статистику, чтобы уменьшить склонность InterBase к глупостям. Однако так бывает не всегда, да и данные могут измениться со временем. Так что нужны более объективные показатели.
Наиболее полезный источник информации -- статистика запроса, выдаваемая
самим InterBase. В isql её можно получить, включив режим
set stats on. Смысл выдаваемых чисел следующий:
Основная цель оптимизации -- естественно, сокращение всех параметров. В большинстве случаев расход ресурсов определяется их суммарным расходом на каждом этапе обработки плана. Если же данные параметры выглядят приемлемо, но время отработки запроса с точки зрения клиента всё равно велико, то причину вероятнее всего нужно искать не в сервере, а либо в клиенте, либо в обмене между ними, в частности -- в работе сети.
Если в плане есть сортировки, то нужно учитывать, что они могут обрабатываться двумя способами -- в памяти, и на диске (во временном файле). Довольно часто бывает, что программа отлаживается на сравнительно небольшом объёме данных. В результате сортировка делается в памяти и быстро. Однако когда реальные данные превышают доступный объём, происходит резкое падение производительности. Дело в том, что InterBase выгружает всё сортируемое множество на диск даже если в памяти не уместится хотя бы одна его запись. Это следует учитывать, чтобы оно не стало неожиданностью впоследствии.
Оценить размер сортируемого множества записей можно двумя способами
-- теоретически и экспериментально. В первом случае нужно вычислить
количество и физический объём записей, поступающих на вход сортировки
согласно плану. Обычно это то, что выдаёт часть плана, взятая конструкцией
SORT(...) в скобки. При этом следует учитывать, что InterBase отрабатывает
фильтровые условия по возможности раньше, так что если в запросе есть условия,
применимые только к таблицам, оказавшимся внутри SORT, и не требующие
для проверки таблиц ``снаружи'', то InterBase обычно использует их. Правда, детали
этого процесса уже не наблюдаемы.
Для экспериментальной оценки нужно создать условия, чтобы сортировка
проводилась через диск. Данных взять по-больше, а в настройках сервера
кэш-буферов сделать по-меньше. После чего запустить запрос и посмотреть
размеры файлов и расход пространства во временном каталоге (c:\temp,
или куда он у вас настроен). Каждая сортировка начинается в памяти. Когда
память, выделенная запросу, кончается, создаётся временный файл и данные
начинают поступать в него. Когда выборка исходных (для данной части плана)
потоков заканчивается, файл достигает максимального размера. После чего
начинается его вычитывание, но уже в другом порядке. Размер уже не меняется,
но начинается выдача данных на выходе сортировки. Если это последняя
сортировка в плане, то есть самая внешняя, то начинается выдача записей
клиенту.
Отсюда, кстати, видно ещё одно важное свойство -- планы с sort выдают записи только по окончании последней сортировки, в то время как планы, целиком построенные на index, order и join, выдают записи сразу же. Процессы сканирования исходных таблиц и выдачи записей клиенту при таких планах протекают одновременно. Это в частности полезно при выводе фрагментов таблиц в интерактивном режиме -- остановив приём записей, клиент избавляет сервер от необходимости дорабатывать план до конца.
Однако часто бывают и такие ситуации, когда сортировки не избежать совсем. В этом случае следует стремиться к уменьшению объёма сортируемых записей. Рассмотрим простой запрос:
select много-длинных-полей
from таблица
order by мало-коротких-полей
Довольно часто (опять же, обычно в интерактивных программах) из подобного
запроса нужны не все данные, а только несколько первых записей. Однако
конструкцию select top n ... нынешние версии InterBase не понимают.
В таком случае гораздо быстрее будет работать конструкция:
for select ключ from таблица
order by мало-коротких-полей
into :ключ do
begin
select остальные-поля
from таблица where ключ = :ключ into :...;
suspend;
end
Длиннее, конечно. Но зато сортируется гораздо меньший объём информации,
так что вероятность того, что он уместится в памяти гораздо выше. Во
многих случаях возможна и дальнейшая оптимизация -- использование
rdb$db_key или where current of в теле цикла, дабы
исключить лишний поиск.
Если подобный запрос динамически формируется с клиента, то ситуация несколько осложняется. В процедуру его по понятным причинам не загонишь, а многократное исполнение тела цикла через сеть может привести к дополнительным задержкам. Тем не менее, если вычитывается только несколько первых записей, то технология применима -- как правило, большие сортировки тормозят ситуацию гораздо больше. В остальных случаях нужно принимать решения исходя из конкретной скорости того и другого варианта. Возможная оптимизация здесь состоит в том, чтобы сначала прочитать на клиента набор ключей в заданном порядке, а затем, для оставшейся части операции, применить условие where ключ in (xxx, yyy, zzz, ...). Если количество прочитанных ключей превышает несколько сотен, то такой запрос нужно делить на части -- у InterBase существует ограничение на объём текста запроса. Поскольку сам запрос простой (поиск по ключу), а подготовка выполняется лишь раз на несколько сотен записей, такой подход может оказаться вполне оправданным.