[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Базы данных, SQL" / Оглавление документа

Подразделы

• С чем мы имеем дело
• Распространённые заблуждения
• Как оно работает на самом деле
• Серия примеров
  • Данные.
  • Оптимизация скалярного подзапроса.
  • Аналогичный запрос, но через IN().

Неожиданности и хитрости в оптимизации подзапросов

С чем мы имеем дело

Сразу попутно замечу, что позже мной было написано введение в оптимизацию запросов в InterBase, где изложены базовые принципы.

Итак, в InterBase, как и в любой нормальной СУБД на базе SQL, можно в рамках многих запросов писать вложенные подзапросы типа select, заключая их в круглые скобки. Целей употребления такой конструкции, и соответственно способов её интерпретации может быть несколько.

Во-первых, подзапрос как правило можно написать в том месте, где требуется получить/вычислить какое-либо одно значение. В этом случае просто на месте значения пишут подзапрос в скобках. При этом фраза select этого подзапроса должна возвращать ровно одно поле, а логика остальных частей должна обеспечивать, чтобы возвращалось не более одной записи. Если не будет сформировано ни одной, то подзапрос возвращает null, если же несколько, то возникнет ошибка. Подзапросы подобного рода могут фигурировать, в частности, в вычисляемых выражениях или в операциях сравнения.

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

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

Партнёры:

Хостинг: