Оптимизации подзапросов в 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 станет более эффективным. В прочем, ни один из вариантов с подзапросами никогда не будет эффективнее, чем оптимальный план в варианте с соединением. Потому невозможность автоматической раскрутки подзапросов в соединения является важным недостатком, который следует учитывать.