Опыт работы с InterBase. Неожиданности и хитрости в оптимизации подзапросов

• выражение IN (подзапрос)
• выражение =ALL (подзапрос)
• выражение =SOME (подзапрос)
• выражение =ANY (подзапрос)

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

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

Некоторые граждане, в том числе в su.dbms.interbase, предлагали, в качестве доработки к IB сделать возможность извлекать несколько полей, и сравнивать их со списком значений за один приём. Что ж, операция действительно была бы полезна, но на суть того, что описано выше и ниже это не повлияет.

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

Кроме этого существует конструкция EXISTS(подзапрос), однако в нашем случае она не представляет интереса, о чём ниже.

Всё то, что я написал в этом разделе, может показаться второстепенным. Однако это совершенно не так, и у меня были веские основания начать именно с этого. Потому что обработка тех и других видов подзапросов в InterBase различается радикальным образом.

Распространённые заблуждения

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

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

С другой стороны, некоррелированные подзапросы построены исключительно на основе собственных таблиц и процедур и из внешнего контекста ничего не требуют. Такой запрос можно вызвать отдельно, ничего в нём не изменив. И результат такого запроса, соответственно, на одних и тех же данных постоянен. Отсюда вывод: нет смысла вызывать такой подзапрос несколько раз, достаточно при первом вызове запомнить результат, и затем использовать его для внешнего запроса.

Вот это и есть то самое заблуждение. Точнее, их тут даже два.

Некоррелированный подзапрос независим от контекста.

Ну, независим-то он - независим, но это ещё не значит, что никак не связан. Фактически подзапрос всегда используется для сравнения каких-то его полей с какими-то внешними значениями. И учёт этого факта в ряде ситуаций может быть довольно успешно использован, чтобы ликвидировать часть работы во время выполнения подзапроса.

Некоррелированный подзапрос выполняется один раз.

Это один из подходов, применяемых в большинстве СУБД. Однако в InterBase это правда, только для подзапросов в скалярном контексте. Для множественного контекста применяется совершенно другой подход, описанный в следующем разделе.

Как оно работает на самом деле

Итак, вернёмся к нашим контекстам. В скалярном контексте InterBase действительно принимает во внимание, коррелированный подзапрос, или нет. Если нет, то запрос вызывается единожды, результат (одно значение) запоминается, и используется при отработке внешнего запроса примерно так же, как обычный параметр.

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

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

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

Когда подзапрос вызывается конструкцией типа значение IN (select поле ...), то, если внимательно подумать, нам и не нужны все записи подзапроса. Нужно найти те, у которых поле имеет значение. А это значит, что оптимизатор может со спокойной душой добавить подзапросу в where дополнительное условие ...) and поле=значение. А это, в свою очередь вполне может привести к тому, что по данному полю будет использован индекс, или оно послужит основой для других способов оптимизации.

И кстати, данная оптимизация не делается для подзапросов в скалярном контексте. Они отрабатываются совершенно независимо. Хотя в них она могла быть тоже отнюдь не бесполезной. Ещё одна загадка природы.

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

Серия примеров

Данные

create table test1( id integer not null primary key,
x integer );
create table test2( id integer not null primary key,
y integer);

Поскольку эксперимент проводился на свежесозданной базе, индексы первичных ключей получили те же номера, что и таблицы - rdb$primary1 и rdb$primary2. Других индексов нет.

Таблицы заполнены записями очень простого вида:

insert into test1(id, x) values(1, 10);
insert into test1(id, x) values(2, 20);
...
insert into test1(id, x) values(10, 100);
insert into test2(id, y) values(1, 110);
insert into test2(id, y) values(2, 120);
...
insert into test2(id, y) values(10, 200);

Все дальнейшие запросы приводятся с планами, полученными путём включения set plan в isql.

Оптимизация скалярного подзапроса

Точнее, доказательство её отсутствия.

select x from test1
where id = (select id from test2 where y = 130);

PLAN (TEST2 NATURAL)
PLAN (TEST1 INDEX (RDB$PRIMARY1))

По своей привычке InterBase выдаёт планы подзапросов первыми, до плана основного запроса.

Как можно видеть, условие в подзапросе вида id = id_извне никак на него не повлияло - он обрабатывается полным перебором. Попытка явно подсунуть ему план с индексом по test2(id) к успеху не приводит - возвращается ошибка. Зато внешний запрос индекс использует.

Теперь попробуем написать в точности то же самое, но через IN.

Аналогичный запрос, но через IN()

select x from test1
where id in (select id from test2 where y=130);

PLAN (TEST2 INDEX (RDB$PRIMARY2))
PLAN (TEST1 NATURAL)

Может показаться смешным, но замена = на IN перевернула весь план буквально с точностью до наоборот. Теперь внешний запрос начинает отрабатывать своё условие перебором, зато внутренний начинает чувствовать контекст. Условие из контекста аккуратно подходит под его индекс, что и используется.

С другой стороны, если вытащить подзапрос и попытаться исполнить его отдельно, то план с индексом не будет воспринят. Потому что для единственного оставшегося условия он совершенно не к месту.

Надо сказать, что оба запроса на самом деле дают результат, эквивалентный следующему соединению:

select test1.x from test1, test2
where test1.id=test2.id and test2.y=130;

Вариант со скалярным подзапросом даёт план, эквивалентный следующему:

PLAN JOIN (TEST2 NATURAL,TEST1 INDEX (RDB$PRIMARY1))

А вариант с множественным действует примерно так:

PLAN JOIN (TEST1 NATURAL,TEST2 INDEX (RDB$PRIMARY2))

В данном случае первый вариант эффективнее. Он делает один проход по test2, находит в ней всего одну запись, у которой y = 130, и с полученным значением выполняет внешний запрос. Вариант с соединением, однако, является более общим, так как скалярный подзапрос приведёт к ошибке, если записей с y = 130 окажется несколько.

Второй вариант, с IN это как раз стерпит, однако он менее эффективен, так как вызывает поиск по table2 на каждой итерации внешнего запроса. Правда, сам этот поиск делается по индексу.

И здесь ещё один существенный момент: при отработке подзапросов типа IN(...), =SOME(...), =ANY(...) перебор останавливается после первой же записи, выданной подзапросом. В то время как =ALL(...) будет работать либо до конца, либо до первой записи, не удовлетворяющей условию. То есть при удачном стечении обстоятельств, если ``подходящая'' запись всплывёт на первой же итерации подзапроса, всё может быть очень эффективно. А возможна и обратная ситуация.

Естественно, те же соображения применимы и при других видах сравнения. Операции <, <=, <> так же можно внести во внутренний запрос. Хотя пользы от этого, конечно, будет гораздо меньше, чем от равенства.

Кстати, в двух описанных примерах можно вместо y = 130 в подзапросе сделать x = 30 во внешнем запросе. На планы это не повлияет, поскольку и в том, и в другом случае условия налагаются на неиндексируемые поля. Однако оценки эффективности поменяются местами, и вариант с подзапросом через IN станет более эффективным. В прочем, ни один из вариантов с подзапросами никогда не будет эффективнее, чем оптимальный план в варианте с соединением. Потому невозможность автоматической раскрутки подзапросов в соединения является важным недостатком, который следует учитывать.