Дмитрий Попов, popov@krista.ru
25.12.2001
Во-первых, о применимости данного опыта. Я говорю о Linux, потому что я именно на нём это дело испытывал. Конкретно -- на Slackware 7.1 с доустановленными обновлениями из Slackware-current. Однако на самом деле подобные сооружения должны работать на любой версии любой юниксообразной системы. Главное, чтобы в этой системе работал InterBase и chroot.
Во-вторых, я пробовал виртуализовать только Classic. Есть мысли о том, как это можно сделать в Super, изложены ниже.
Итак, создав в файловой системе ветку, по структуре напоминающую систему в целом, и содержащую файлы, необходимые для запуска нужного приложения, можно создать для него виртуальную среду, достаточно сильно изолированную от остальной части системы. В этой среде с помощью системного вызова chroot или одноимённой команды можно запускать нужные процессы, видящие в качестве корня только свою ветку. Этот изменённый корень наследуется процессами, так что выйти за его пределы они обычно не могут.
Тут же замечу, что хотя chroot и способствует усложнению взлома системы со стороны процессов, работающих в ``защищённой'' среде, тем не менее полных гарантий сам по себе не даёт. Особенно если в рамках среды chroot существуют процессы с правами root, есть программы suid, и т. п. Список требований достаточно длинный, и к сожалению никто не может поручиться, что полный. Так что безопасность -- вообще отдельный вопрос, который мы сейчас не рассматриваем.
В системе одновременно может функционировать сколько угодно виртуальных сред на основе chroot. Точнее -- столько, на сколько хватит ресурсов. При этом в разных средах может быть установлен разный софт разных версий. Главное, чтобы он нормально взаимодействовал с ядром системы, так как оно у всех общее. К счастью, в Linux системные вызовы в последние годы существенно не менялись, особенно в той части, которая нужна для InterBase. И версии libc разных поколений с текущими ядрами вполне нормально уживаются. В моём случае было ядро 2.2.18, libc 5.4.46 в ветке для InterBase 4.0, glibc 2.2.1 во всех.
И последний из теоретических вопросов -- как поделить между серверами сеть. Ведь клиенты ожидают, что в сервере будет работать только один InterBase, и он должен ``слушать'' знаменитый порт 3050. Проблема решается навешиванием на сетевой интерфейс машины нескольких адресов IP, которым через hosts/DNS присваиваются разные имена. Далее пишется небольшая программка (у меня был скрипт на Perl), которая в зависимости от адреса, на который пришло соединение, делает chroot в нужную среду, и запускает там местный gds_inet_server.
Вообще надо сказать, что для таких операций, как создание веток файловой системы под chroot, запуска различных команд из inetd в зависимости от адреса соединения, и т. п., существуют готовые инструменты. Однако в те дни, когда я это делал, на солнце были вспышки, спутниковая тарелка, через которую у нас Инет, глючила всеми возможными способами, да и просто было лениво ``вылезать наружу''. Тем более что самопальные решения оказались не такими уж и сложными.
Итак, понадобилось тестировать разрабатываемый софт с разными версиями IB. А так же средство для конвертации баз между разными ODS через backup-restore. Для установки были выбраны дистрибутивы:
Первым делом нужно было сформировать сами виртуальные среды. Я начал с того, что сформировал ``пустышку'', в которой были набросаны файлы, минимально необходимые для запуска инсталятора всего остального. В Slackware -- installpkg из пакета hdsetup.tgz. Понадобились каталоги /bin, /sbin, /lib (часть крупных, но ненужных файлов выкинул), /tmp (пустой), кое-что из /var. Выяснял методом тыка, периодически запуская что-нибудь наподобие chroot виртуальный-корень /sbin/installpkg /bash.tgz, и выясняя, чего ему ещё не хватает. Сам bash.tgz, естественно, тоже пришлось положить в ту самую ветку, чтобы он был виден изнутри.
После того, как инсталятор в виртуальной среде ожил, тем же путём (то есть закидыванием пакета в каталог, и запуском инсталятора ``внутри'' были поставлены aaa_base, bin, elflibs, etc, fileutils, find, glibcso, grep, gzip, hdsetup (для чистоты), ldso, perl, tar, txtutils, util, zoneinfo.
Полученная ветка файловой системы была заархивирована и использовалась впоследствии в качестве заготовки. С ней было снято три копии, под три варианта InterBase. В каждую копию был положен соответствующий дистрибутив, после чего делалось chroot виртуальный-корень /bin/bash и в получившейся комстроке делалась обычная установка. Инсталятор обновлял /etc/services и /etc/inetd.conf, которые видел, и которые к реальному функционированию системы отношения не имели.
При этом иногда возникали небольшие проблемы, что чего-то не хватало. В этом случае я либо дописывал файлы из основной системы, либо доставлял пакеты. К сожалению, не всё фиксировал, так что точно перечислить теперь затрудняюсь, но при надлежащем знании своей системы это выяснить несложно.
В заключение установок каждой ветки создавался каталог /database (в соответствующей ветке) и ему настраивались права для логина interbase. Сам логин был руками внесён в /etc/passwd и /etc/shadow каждой ветки, но исходно был создан в основной системе. При таких копированиях важно проследить, чтобы один и тот же пользователь везде получил один и тот же номер uid. Кроме этого были сняты атрибуты suid и sgid со всех файлов в ветках chroot. На всякий случай.
После того, как локальные подключения в пределах каждого chrootбыли
проверены на работоспособность, я перешёл к сетевой части. Во-первых,
были изготовлены дополнительные адреса, и навешаны через
ifconfig eth0:0 192.168.1..., ifconfig eth0:1 192.168.1....
И соответственно прописаны в местном DNS.
Далее был написан скрипт. Привожу то, что возникло в результате отладки.
#!/usr/bin/perl
# (C) Dmitri Popov, 2001
# Freeware
use Socket;
my $sockaddr = getsockname(STDIN);
exit if ! $sockaddr;
open(LOGSTREAM, '>>/var/log/gdsconnect');
my ($port, $addr) = sockaddr_in($sockaddr);
$addr = inet_ntoa($addr);
dolog("addr=$addr");
runserver('/roots/ib5', '/usr/interbase')
if( $addr eq '192.168.1.251' );
runserver('/roots/fb', '/opt/interbase')
if( $addr eq '192.168.1.252' );
runserver('/roots/ib4', '/usr/interbase')
if( $addr eq '192.168.1.253' );
exit 133; # паранойя
sub runserver
{ my $root = shift;
my $base = shift;
dolog("root=$root, base=$base");
chdir($root);
chroot($root);
exec( "/bin/su interbase -c"
. "$base/bin/gds_inet_server");
}
sub dolog
{ my $str = shift;
printf LOGSTREAM "%s %s\n",
scalar localtime(), $str;
}
Замечания
Ну и последняя операция состояла в том, чтобы запускать этот скрипт из inetd. Перед этим необходимо обеспечить наличие gds_db в глобальном /etc/services, если его там ещё нет. Содрать можно с любого результата установки в chroot. Непосредственно в (глобальный!) inetd.conf пошла строчка:
gds_db stream tcp nowait.100 root /usr/sbin/tcpd /usr/local/sbin/gdsconnect
Обратите внимание -- запуск идёт от рута. Это необходимо для того, чтобы сработал chroot. Переключение на interbase производится уже после.
Конечно, заработало не сразу. Приходилось вставлять в скрипт вызовы dolog() с подробностями. Большинство из них из окончательной версии удалены.
Как известно, супер функционирует сам, без помощи inetd. На постоянной основе. В связи с чем фокус с chrootна каждое подключение не проходит. Сервера должны изначально сидеть каждый в своей ветке, и при этом слушать каждый свой адрес. В самом InterBase средств для этой цели нет. Но прикрутить на мой взгляд тоже можно, но несколько хитрее.
Во-первых, в ветках файловых систем для каждого сервера в его etc/services можно прописать разные порты для gds_db. Таким образом, они смогут запуститься, не переконфликтовав друг с другом, так как будут слушать сеть на всех локальных адресах, но на разных портах.
Далее можно взять документацию по системе, и почитать на тему NAT, то есть трансляции адресов в пакетах. С помощью подобного механизма можно заставить пакеты прозрачным для клиента и сервера образом менять свою адресную информацию. В Linux-2.4.x и iptables задача представляется решаемой.
Или можно взять программу-редиректор (их мне попадалось множество, сам иногда использую redir), и вызывать её из вышеприведённого скрипта с нужными ключами заместо gds_inet_server. Таким образом, получается прокси-классик, запускающий индивидуальное перенаправление для каждого клиента.
Дмитрий Попов, popov@krista.ru
25.12.2001
Вообще преобразование запроса 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 существует ограничение на объём текста запроса. Поскольку сам запрос простой (поиск по ключу), а подготовка выполняется лишь раз на несколько сотен записей, такой подход может оказаться вполне оправданным.
Поводом для создания данного произведения послужила переписка, происходившая в конце 2 тысячелетия нашей эры в su.dbms.interbase(впоследствии народ переместился на новое место -- news://forums.demo.ru/epsylon.public.interbase ). Среди прочих была в частности затронута тема подзапросов в InterBase. После чего переписка с одним из участников (Oleg LOA <loa@mail.ru>) переключилась на почту. Пытаясь доказать друг другу свой опыт вперемежку со сложившимися заблуждениями мы провели несколько экспериментов и накопали ряд весьма полезных фактов. Что я и решил огласить народу.
Мои же данные таковы: Дмитрий Евгеньевич Попов, сетевой администратор в НПО ``Криста'', организации, ведущей разработки (в том числе) нескольких проектов на основе InterBase. Сам в прошлом -- разработчик на этой платформе.
Почтовые адреса:
Домашний:
popov@rybinsk.ru
Рабочий:
popov@krista.ru
В последствии, когда мысли по подзапросам были более-менее подробно изложены, я начал вспоминать другие темы и решил их тоже добавлять сюда. Надо сказать, что это не первый мой заход с целью изложить свой опыт работы с InterBase. Ещё пару лет назад я брался сделать нечто подобное для своих коллег по работе. Однако результат получился достаточно беспорядочный, да и часть информации уже либо успела устареть, либо по ходу жизни была либо опровергнута, либо существенно уточнена. Уж очень много было плохо проверенных предположений. Надеюсь, что данное произведение получится лучше.
Всё началось несколько месяцев назад, когда ряд моих коллег обнаружил
(не без ужаса), что иногда к серверу можно подключиться под SYSDBA не
вводя пароля. Или с паролем, гораздо более длинным, нежели он реально
установлен. В ходе дальнейших разбирательств выяснилось, что даже
убивание переменных ISC_USER и ISC_PASSWORD проблему
иногда не устраняет -- вводишь SYSDBA, жмёшь Enter, и оказываешься в
базе под полными правами.
В конце концов выяснилось, что коварные переменные были установлены ... в сервере. И этого оказалось достаточно. В результате методичного перебора комбинаций было выяснено следующее (сервер был тогда 4.2/NT).
ISC_*, то подставляются значения из
переменных.
ISC_*.
isc4.gdb.
Таким образом, кроме явно вводимых имени и пароля, существует ещё два неявных источника этой информации на клиенте и на сервере. О которых, естественно, не следует забывать, и особенно оставлять без присмотра. Особенно опасно это со стороны сервера -- ведь тогда этим может воспользоваться любой клиент.
Наименее актуальна данная проблема для классической архитектуры
под *nix. Ведь inetd обычно запускается из стартовых скриптов системы,
в то время как ISC_* устанавливаются в пользовательском окружении,
где-нибудь в profile. За весь свой опыт не помню, чтобы эти вещи
у меня пересеклись.
Абсолютно безопасна с точки зрения данной проблемы, на мой взгляд, платформа NetWare. Там переменных окружения вообще нет. По крайней мере в те времена, когда я имел дело с 3.11 и 3.12, ничего такого не было. Хотя конечно, NetWare неудобна для сервера баз данных по другим причинам.
С другой стороны, наиболее вероятна подобная ситуация под NT, с её возможностью глобальной настройки переменных, включаемых во все окружения. 10 раз подумайте, прежде чем добавлять туда что-либо, особенно пароль! И даже если это не связано с InterBase . Собственно под NT данная опасность и была обнаружена.
Аналогичным образом потенциально опасны настройки, сделанные в
autoexec.bat под Win9x. Кроме того, об окружении никогда
нельзя забывать, когда запускаешь сервер ``руками'', на какой бы
платформе это ни происходило.
/etc/passwd
или /etc/shadow в isd4.gdb (поле users.passwd). И обратно.
При этом всё работало.
Здесь надо заметить, что упомянутая технология на самом деле предусматривает шифрование лишь первых 64 бит пароля, то есть 8 символов. С учётом выкидывания пробелов. Остальные символы могут быть любыми. Благодаря этому, например, вместо ``masterkey'' можно написать ``masterkeyxyz'', и даже ``masterke''.
Всё это нормально работало до тех пор, пока на всех платформах был crypt(), использовавший для шифрования стандартный алгоритм DES. Но предположение об этом вообще-то, уже не уже само по себе сомнительно, потому что полной гарантии относительно того, что алгоритм и формат шифрования не изменится, не было. Именно такое изменение впоследствии и произошло.
Но сначала почва для проблем была дополнительно подготовлена при портировании InterBase на платформы, не имеющие crypt(). Естественно, в код, специфичный для этих платформ была включена функция crypt(), позаимствованная из Unix. Однако в InterBase для предыдущих платформ это заимствование внесено не было. Таким образом возник ещё один повод, чтобы с одной стороны поменялось, а с другой -- нет.
И наконец, настал тот день, когда алгоритм шифрования под Unix начал меняться. Вместо старого, по нынешним временам малоразрядного и обросшего несметным количеством кряков DES функцию crypt() научили MD5. Если не вдаваться в подробности, то MD5 шифрует по другому алгоритму (строго говоря -- это алгоритм хеширования, обратную операцию, то есть расшифровку, вообще не поддерживает) и работает с паролями большей длины. И естественно, если на одном конце пароль зашифрован по одной технологии, а на другом конце соединения установлена другая, то сравнение потерпит неудачу и пользователь до работы допущен не будет.
Замена произошла, насколько мне известно, при переходе к glibc 2.1, в частности в системах Linux и FreeBSD. Более того, новая версия пакета системных библиотек содержала по умолчанию поддержку нового MD5, а старый DES поставлялся в виде отдельной библиотеки descrypt, которую следовало доустановить при острой необходимости в обратной совместимости. Многие пользователи и администраторы с непривычки этот момент упустили.
В результате возникла ситуация, в типичном случае примерно следующая: клиенты под Windows используют DES (единственное, что зашито в них авторами InterBase), а сервера под *nix -- MD5. Подключиться невозможно. Более того, база isc4.gdb, поставляемая с InterBase, изначально содержит SYSDBA/masterkey, причём пароль зашифрован именно DES. В результате после такой установки даже первые администраторские подключения внутри одной системы осуществить невозможно.
К сожалению, я не могу сказать, как дальше будет развиваться ситуация с платформами и технологиями шифрования. Пока же наиболее разумный и правильный подход -- привести всё к единому, давно принятому в InterBase стандарту, DES. То есть при установке сервера под *nix необходимо удостовериться, что необходимые библиотеки установлены. К счастью, начиная с glibc2.2 похоже, что обе технологии шифрования будут поставляться вместе и ничего доустанавливать не потребуется.
select ... from соответствующим образом. Однако по ходу
эксплуатации этого механизма мне не раз приходилось натыкаться на проблемы.
Которые, как выяснилось после детального разбирательства, опять же
упираются в планирование.
Основная ситуация, когда эти проблемы могут проявиться - соединение процедуры и простой таблицы. Где-то в недрах оптимизатора особенности процедур учитываются не до конца.
Так же должен отметить, что в отличие от предыдущей темы, поведение оптимизатора заметно изменилось в процессе развития InterBaseмежду версиями 4 и 6. Правда, с четвёркой давно таких экспериментов не устраивал, но на моей памяти случались совершенно странные ситуации, заканчивавшиеся падением сервера с сообщениями в стиле ``Internal gds consistency check''. Из шестёрки, на которой проводил эксперименты, такого получить не удалось. Более того, заставить её выйти на ``кривой'' план удалось только ручным планированием.
Но обо всём по порядку. Первопричина всех неприятностей - то, что ядро
InterBase до сих пор не умеет делать соединение типа join с хранимыми
процедурами. Здесь имеется в виду не конструкция join в
select ... from, а одна из технологий соединения в plan.
Факт, достойный сожаления, поскольку такое соединение во многих ситуациях
-- одно из самых эффективных.
Так вот, по моим наблюдениям, в 4.2 оптимизатор мог совершенно спокойно
сгенерировать план типа join(sp natural, table index(...)). После
чего попытка выполнить такой план заканчивалась последствиями различной
тяжести. В 5-ых версиях ситуация стала реже, а последствия перестали
быть катастрофическими. Наконец, как я уже отмечал, в 6 оптимизатор
вроде как научился преодолевать свою склонность к join, видя процедуру.
Конечно, лучше было бы реализовать такой join, нежели предотвращать,
но и на том спасибо. Однако это всего лишь моё предположение, попытки
копать исходный код не привели меня к однозначному выводу о причинах такого
поведения -- вполне возможно, что мне просто повезло.
create procedure sp1(n integer)
returns(id integer, x integer) as
begin
for select id, x from test1 into :id, :x do
begin
x = :x+:n; suspend;
end
end
Далее, как обычно, выполняем запросы со включённым отображением плана.
select * from sp1(3); PLAN (TEST1 NATURAL)
Первый сюрприз. Если тело запроса заключено в оператор for select,
то план выдаётся со ссылкой именно на этот запрос, а не на процедуру.
Можно подумать, что InterBase вникает во внутренние особенности процедуры
и учитывает это при планировании внешнего запроса. Однако это всего
лишь ``оптический обман''.
select * from sp1(3) where id=5 PLAN (TEST1 NATURAL)
Если бы гипотеза была верна, то условие id=5 внеслось бы в
where внутри процедуры, и план был основан на индексе первичного
ключа. Невозможность такой оптимизации на самом деле проистекает
из архитектуры InterBase. Для каждой процедуры выполняется компиляция в BLR,
и тем самым фактически формируется фиксированный план для
всех запросов и вообще всех операций, описанных внутри. В то время
как план (и BLR) внешнего запроса может всего лишь вызвать процедуру,
обеспечив обмен параметрами.
Но возвращаемся к основной теме.
select * from sp1(3) sp, test2 t where sp.id = t.id PLAN MERGE (SORT (T NATURAL),SORT (TEST1 NATURAL)) select * from test2 t, sp1(3) sp where sp.id = t.id PLAN MERGE (SORT (T NATURAL),SORT (TEST1 NATURAL)) select * from sp1(3) sp inner join test2 t on sp.id = t.id PLAN MERGE (SORT (T NATURAL),SORT (TEST1 NATURAL))
Неизменный результат. Правда, эксперимент проводился на IB6.
Все процедурные особенности изолируются от остальной части
плана через SORT(). Не самый эффективный, но безопасный
вариант.
select * from sp1(3) sp, test2 t where sp.id = t.id plan join(sp natural, t index(rdb$primary2)) Statement failed, SQLCODE = -104 invalid request BLR at offset 71 -BLR syntax error: expected TABLE at offset 71, encountered 125
BLR 125 -- это (судя по jrd/blr.h) pid - procedure id. То есть
для осуществления join нужна реальная таблица.
Ещё одна особенность, точнее на этот раз пожалуй даже глупость, которую периодически пытаются сделать новички. Ну например так:
select * from sp1(t.id) sp, test2 t
То есть в качестве параметра процедуры идёт одно из полей другого соединяемого отношения. Никогда не пройдёт. По той простой причине, что при любой технологии сначала выполняется соединение, а уже потом появляются поля.
Если не совсем понятно, то задумайтесь над таким фактом. Если допустить,
что можно в качестве параметров употреблять поля из того же from,
то почему нельзя употреблять поля той же процедуры. И что получаем?
From sp1(sp.id) sp. Интересно, можно ли этому придумать ...
ну если не разумную интерпретацию, то хотя бы способ реализации? Мне
что-то на ум ничего не приходит.
Таким образом правильный способ реализации следующий:
for select ... from test2 t into :id, ... do for select ... from sp1(:id) into ... do suspend;
По-длиннее, конечно. Но зато никаких неоднозначностей.
join, а не sort merge.
select * from test2 t left join sp1(t.id) on 0=0; PLAN JOIN (T NATURAL,TEST1 NATURAL)Странное условие на конце запроса предназначено единственно для успокоения синтаксического анализатора. Невозможность merge вполне объяснима -- ведь при этом обе таблицы вычисляются независимо и только потом сливаются вместе. Что при связи по параметру невозможно.
При работе же через join и внешнем соединении, InterBase делает
``сплошной'' проход по ``внешней'' стороне соединения (то есть
эта сторона разумеется сама по себе может фильтроваться, в том
числе и по индексам, но только внутри себя), и для каждой
полученной записи вычисляет ``довесок'' из другой таблицы. Если
вычислить не получилось, то присоединяются значения null.
Подстановка параметров при этом тоже срабатывает.
Заключительная неожиданность этой области -- попробуем вручную
добавить к этому запросу план через join.
select * from test2 t left join sp1(t.id) sp on 0=0 plan sort merge(t natural, sp natural); Statement failed, SQLCODE = -104 invalid request BLR at offset 77 -BLR syntax error: expected TABLE at offset 77, encountered 125Ничего не замечаете? Сравните с предыдущим примером, где я тоже пытался планировать соединение с процедурой вручную. Как ни парадоксально, ругань совершенно та же самая. InterBase захотел реальную таблицу вместо процедуры. Хотя в прошлый раз он этого хотел с
join, а с merge совершенно нормально
работал, а теперь наоборот. Всего-то добавилось слово left.
Вообще-то рекурсия для SQL -- вещь достаточно неестественная. Тем не менее жизнь довольно часто подбрасывает ситуации, когда её требуется реализовать. Причём эффективно. Именно в базе. И данных вполне может оказаться приличное количество. Об одном таком случае в вкратце попробую рассказать. Случай весьма примечательный тем, что сначала было найдено очевидное решение, а затем -- эффективное. Разница в скорости составила два порядка.
В развитии данной истории принимали активное участие Мария Баркова и Сергей Степанов -- сотрудники проекта Архив. Другую информацию о работе с деревьями в SQL вообще и InterBase в частности можно найти на здесь, (в разделе «Прочее» есть ряд ссылок по теме деревьев).
Ну и последняя часть рассказа с участием UDF всплыла в ходе переписки с Евгением Жилкиным (Eugene Zhilkin, CS Ltd) в декабре 2001 года.
Итак, в БД имеется дерево. То есть таблица, в структуре которой предусмотрена ссылка на родительскую запись той же таблицы. Однако одной такой ссылкой дело, естественно, не ограничивалось -- присутствовало значительное количество других полей, часть из которых изрядного объёма, другая -- ссылки на прочие таблицы. Короче, таблица не всегда лёгкая даже для обычных, нерекурсивных выборок. Кроме этого, различные справочные и детализирующие таблицы, с которыми главная (древесная) таблица связана многочисленными ключами, тоже примитивизмом не отличались.
Так вот, задача стояла примерно так: выявить (и выдать список ключей) те
записи главной таблицы, у которых нет ни одного из трёх оговорённых
видов детализации, и так же нет ни у одного ``потомка'' записи согласно
главной таблице. Детализация в данном случае -- одна из других таблиц,
ссылающихся на главную через foreign key. Соотношение -- многие
(детализация) - к - одному (главная таблица).
Таким образом, требовалось пройтись по главной таблице, выявить в ней поддеревья, по каждой ветке поддерева проверить наличие записей детализации, и если по всему поддереву наличие нигде обнаружено, вернуть ключ корня этого поддерева. То есть как выяснится чуть позже, решить задачу можно несколькими способами, но результат, естественно, должен быть эквивалентным. Надеюсь, я не слишком Вас запутал.
Основные трудности, как можно видеть, следующие:
Почти буквально как поставлена задача. Процедура обходит поддеревья и выбирает подходящие записи. Выбор основан на подсчёте количества нужных записей детализации по всему поддереву. Таким образом, на вход принимается ссылка на ``родителя'' проверяемых записей, в качестве результата возвращается множество, включающее в себя для каждой записи ключ (ID), дополнительную информацию (которая нас здесь не слишком интересует), и количество найденных записей детализации нужного вида (RefCount).
Если передать в качестве параметра NULL, то процедура пройдётся
по всем корням поддеревьев, потому что они ``родителя'' не имеют. И
соответственно будет проверена вся база.
Имена главных героев изменены :-).
alter procedure sp_Ver1(RefRoot integer)
returns ( ID integer, ...дополнительная информация...,
RefCount integer) as
declare variable ChildRefCount; /* Количество потомков
с детализацией */
begin
for select m.ID, ...дополнительная информация...
from MainTable m, ...справочники...
where ( (m.RefParent = :RefRoot) or
(m.RefParent is null) and (:RefRoot is null))
and (...соединение со справочниками...)
into :ID, ...
do begin
RefCount = 0;
/* Если нет детализации по текущей
главной записи ... */
if ((not exists( select ID from Детализация
where RefMain = :ID and..ещё условия))
and (not exists(другая детализация ...))...)
then begin /* ... то проверяем потомков рекурсивно */
if (exists( select ID from MainTable
where RefParent = :ID))
then begin /* Если потомки есть, то идем по ним */
for select RefCount from sp_Ver1(:ID)
into :ChildRefCount do
RefCount = :RefCount + :ChildRefCount;
end
end /* if not exists */
else RefCount = 1;
suspend;
end /* for select from MainTable */
end /* procedure */
Возвращаемое значение RefCount -- это конечно не полное количество. Для задачи важно лишь определить, нулевое оно, или нет.
Можно конечно покритиковать это решение за несколько избыточное местами
применение exists(), но оптимизация таких мелочей сути бы
не изменила -- работает такое неизбежно долго -- порядка часа. Плюс-минус
в ту или другую сторону в зависимости от мощности сервера и других
второстепенных факторов.
Так как процедура рекурсивная, то создаётся в два приёма. Сначала пустая с нужным заголовком (в примере опущено), а затем окончательная, ссылающаяся на собственный, уже существующий, заголовок.
И тем не менее, любая реляционная СУБД больше приспособлена к работе с линейными потоками записей а не с деревьями. В данном случае, хоть мы и имеем дело с деревом, то это лишь часть задачи. Другие части -- проверка наличия детализации и выборка дополнительной информации. Выполняются вполне традиционным образом. Таким образом, основное направление следующего шага в том, чтобы взять все эти три подзадачи, и поделить.
Данное решение уже позволило сократить обработку с часа до минуты на тех же данных.
alter procedure sp_GetAllChildren(ParentID integer)
returns (ChildID integer) as
declare variable DirectChildID integer;
begin
ChildID = :ParentID; suspend;
for select ID from MainTable
where RefParent=:ParentID into :DirectChildID do
begin
ChildID = :DirectChildID;
suspend;
for select ChildID
from sp_GetAllChildren(:DirectChildID)
where ChildID <> :DirectChildID
into :ChildID do
suspend;
end /* for select from MainTable */
end /* procedure */
Выборка включает в себя в том числе и корень поддерева, переданный в качестве параметра. По этой причине внутри приняты меры, чтобы не выдавать наружу узлы по два раза.
create procedure sp_Ver2
returns ( ID integer, ...доп. информация...,
RefCount integer) as
declare variable ChildID integer; /* Ссылка на потомка
текущей записи */
declare variable RefDescr integer; /* Ссылка на справочник
из главной таблицы
для доп. информации */
begin
for select ID, RefDescr from MainTable
into :ID, :RefDescr do
begin
RefCount = 0;
for select ChildID from sp_Ver2(:ID)
into :ChildID do
if( exists( select ID from Детализация
where RefMain = :ChildID ...)
or exists(другая детализация ...) ...
then RefCount = :RefCount + 1;
if( :RefCount = 0 )
then begin
select ...доп. информация... from Справочник
where ID = :RefDescr into :...;
suspend;
end /* if :RefCount = 0 */
end /* for select */
end /* procedure */
Следует заметить, что выборка справочников для главной таблицы, которые в данном случае играют весьма вспомогательную роль, отложена на самый конец и делается исключительно для тех записей, что уже однозначно попадают в окончательный результат. В основном цикле выбирается лишь ссылка на справочник (ну в жизни разумеется ссылка в таблице не одна, но сути это не меняет).
Кроме этого, в процессе ``доводки'' процедуры была сделана ещё одна
оптимизация. Если внимательно посмотреть на внутренний цикл, то можно
обнаружить, что выполнять его следует только пока не найдено ни одной
записи с детализацией. К сожалению, простых средств прекратить
цикл в InterBase нет, но можно добавить в выборку for select
условие where RefCount = 0. Это по крайней мере сделает
лишнюю прокрутку цикла холостой.
Таким образом, в результате всех описанных мер мы получили выигрыш более чем на полтора порядка. Но оказалось, что и это не предел. Ещё одна неэффективность этого подхода в том, что записи главной таблицы (всё-таки) часто анализируются по-нескольку раз. Один раз -- сами по себе, другие -- как чьи-то потомки (подчинённые). Вот тут-то, при анализе этой неэффективности, у меня и родилась мысль подойти к задаче ``с другого конца''. Начать обработку не с главной таблицы, а как раз с исключаемых детализаций. А на главную выйти в конце.
Кроме того, что было сказано в предыдущем абзаце, этот вариант ещё и наиболее правильный с точки зрения сведения всей обработки к к линейным операциям. Достаточно сказать, что он не рекурсивный, даже несмотря на то, что имеет дело с рекурсивной структурой.
create procedure sp_ListExcluded
returns (ID integer) as
begin
for select RefMain from Детализация where ...
union select RefMain from ДругаяДетализация ...
into :ID do
begin
suspend;
while(:ID is not null) do /* проход до корня */
begin
select RefParent from MainTable
where ID =:ID into :ID;
if(:ID is not null)
then suspend;
end /* while id is not null */
end /* for select union */
end /* procedure */
Внешний цикл делается через union, а не union all.
Конечно, второй сам по себе эффективнее, но в данном случае выборки
изрядно пересекаются, так что ликвидировать дубликаты с точки зрения
последующей работы важнее.
Конечно, при данной технологии одна и та же запись главной таблицы
всё-таки может попасть выборку несколько раз, если у неё
в дереве имеется несколько подчинённых узлов. Но это совершенно
несложно устранить путём select distinct id from sp_ListExcluded.
Опять же, distinct может показаться ресурсоёмкой операцией --
сортировка ведь. Однако в данном случае речь идёт исключительно
о сортировке ключей, целых чисел. Физический объём измеряется
не мегабайтами, а сотнями килобайт. Для современного сервера совершенно
немного. Так что опасаться не за что. Как раз самое
время принять меры, чтобы ужать выборку.
Остаётся пройтись по главной таблице и извлечь из неё записи, отсутствующие
в результате sp_ListExcluded. Если бы не некоторые ``но'', то вполне
вероятно, что можно было бы обойтись одним запросом примерно такого вида:
select ID
from MainTable m left outer join sp_ListExcluded x
on o.ID = x.ID
where x.ID is null
Хитрость заключается в том, что внешнее соединение для недостающих
записей формирует NULL (из процедуры он появиться не может),
и именно такие записи отлавливаются условием where.
К сожалению, на момент, когда это всё происходило, вопрос
о соединении с процедурами не был
изучен, а версия InterBase была 4.2, то есть гораздо более привередливая
к такого рода операциям. Провернуть запрос такого вида напрямую не
удалось. Пришлось создавать временную таблицу, загонять в неё выборку
select distinct из процедуры, а затем соединять. И с главной
таблицей, и со справочниками -- всё сразу получилось достаточно
просто и эффективно.
В целом данный вариант оказался примерно вдвое быстрее предыдущего, рекурсивного. Временную таблицу оказалось всё-таки немного полезнее проиндексировать. Даже несмотря на накладные расходы на её заполнение и очистку, получившиеся возможности оптимизации дали существенный выигрыш. Правда следует заметить, что решение не было рассчитано на частое выполнение таких операций. Вполне возможно, что если их часто повторять без очистки старых версий, то торможение от временной таблицы возросло бы во много раз.
Ну и под конец -- о способе Евгения Жилкина, фактически выходящем за рамки SQL. Как известно, InterBase поддерживает такой механизм, как UDF. То есть функции пользователя, вызываемые из SQL, и написанные на компилируемых языках. Работающие по этой причине весьма быстро. Как оказалось, быстрее временных таблиц. Дальше процитирую первоисточник:
Целью задачи был расчёт кол-ва необходимых деталей, стандартных и покупных изделий, материалов, состава необходимых операций и трудовых ресурсов, стоимости операций, покупных изделий и т.п. для производства единицы изделия, входящего в конечный заказ на производство. Задача решалась для разных предприятий (машиностроение/приборостроение) с учётом особенностей опытного-мелкосерийного и серийного производства. Основной алгоритм (т.н. "разузлование") заключался в том, что для каждой сборочной единицы (СЕ) определялись её составляющие: ДСЕ (детали и сборочные единицы), СТИ (стандартные изделия), ПКИ (покупные изделия), материальные операции и трудовые операции. И так уровень за уровнем [Д]СЕ (и СТИ) "расползались" на аналогичные составляющие. Каждое разузлование записывалось (по каждой сущности) в виде итогов (итоговое кол-во, стоимость и т.п.) в таблицу.
Нулевой вариант, отметённый "с гневом" сразу - "вытягивать на клиента и считать". На "больших" заказах - данных - огромное количество.
Первый подход был сделан очень похожим способом на описанный тобою (i.e. процедурная рекурсия), только осложнялся он тем, что связочных таблиц - несколько, и каждая со своими свойствами. От данного метода ушли, т.к. время обработки одного "среднего" заказа составляло от 50 мин до 2-3 часов. На "больших" IB обваливался. И ещё иногда случались обвалы даже на "простых заказах" - чуть ниже опишу причины.
Второй подход был похож на твой последний, но отличался тем, что данные скидывались в промежуточную таблицу. Заодно по ней определялось - проходили ли мы конкретный узел или нет. Т.е. как таковой, рекурсии уже не было. По времени - примерно аналогично, но обвалов не случалось.... Значительно на время влияли факторы IB: "свеженькая" БД (после backup/restore) или нет; первым разузловывался "большой" заказ или наоборот. И т.п. т.е. влияло больше размазывание страниц, отводимых на временную таблицу, по файлу данных.
И наконец - третий и последний вариант. Его необходимость продиктовывалась тем, что некоторые пользователи иногда ошибались и "зацикливали" связи. Легко найти циклы, когда они на одном-двух уровнях, но на большем - очень трудно. Это и вызывало слёты IB при рекурсивном методе. А при втором подходе - иногда - неверные результаты (т.к. всё зависело от того, на какую "вершину" цикла попадёт в первый раз алгоритм. Если как раз на ту, в которой сидела некорректная связь, то алгоритм не зацикливался, но неправильно учитывал количественную взаимосвязь сущностей внутри цикла и их собственные ответвления ниже, вне цикла).
Мы сделали dll, которая содержала набор udf для инициализации (закачки данных) функцию расчёта, и набор функций выкачивания данных обратно. При расчёте, заодно, производился поиск циклов, и при обнаружении - состав циклов выводился обратно и сохранялся в базе для последующего ручного разбора.
Изюминка, собственно состоит в том, что udf ОЧЕНЬ быстро вызывается и ОЧЕНЬ быстро обрабатывает данные. Первые варианты такого решения привели к расчёту за 1 - 8 мин. Впоследствии, проанализировав - на что больше всего тратится времени, поняли - на выделение памяти под элементы в TList (!!!). Дело в том, что он выделяет (и довыделяет (метод Grow)) памяти по-умолчанию - очень мало. При закачке таблиц с миллионами записей, тратилось время на подобное "отрывочное" выделение. Немного модифицировав класс TList, получили расчёт даже самых больших заказов - за 2 мин. Причём половина ( 40-45%) этого времени тратилась на подготовку и вызов процедур на клиентском месте (из них 20% тратилось на обработку процедуры, которая с помощью select'ов загоняла данные в dll), а другая ( 50%) тратилась на вызов функций из dll по вытягиванию результатов и "распихиванию" их в таблицы результатов. Вызов функции расчёта длился 1 секунду МАКСИМУМ !!! Правда, часть подготовки к расчешу производилась ещё и в функциях запихивания данных.
Если изобразить в терминах SQL что производилось, то происходило примерно следующее:
Закачка в DLL:
create procedure eprDenode_Init
(
....
)
returns
(
aSessionID integer
)
as
dummy integer;
begin
aSessionID = gen_ID(...);
insert into Sessions
...
(aSessionID, ....);
dummy = udf...Init (aSessionID,...);
eprDenode_Init_1 (aSessionID);
eprDenode_Init_2 (aSessionID);
....
end
^
create procedure eprDenode_Init_1
(aSessionID integer)
as
dummy integer;
begin
select distinct 1 from .... z
where udf...SaveZData1 ( :aSessionID, z.ID,
z.ChildID, z.Quantity, ....) = 0
and udf...SaveZData2 (....) = 0
into :Dummy;
select distinct 1 from .... y
where udf...SaveYData1 (:aSessionID, y.ID, y.Prise, ....) = 0
and udf...SaveYData2 (....) = 0
into :Dummy;
..... select distinct 1 from .... j
where udf...SaveJData1 ( :aSessionID, j.ID, j.MaterialID,
j.MeasureID, j.Quantity ....) = 0
and udf...SaveJData2 (....) = 0
into :Dummy;
.....
end
^
Выкачка данных произведена, запускаем расчёт
create procedure eprDenode_Calc (aSessionID integer) returns (Res integer) as begin Res = udf...Calc (aSessionID); end ^
Выкачка данных из DLL и сохранение их в табл. результатов
create procedure eprDenode_Save
(
aSessionID integer
)
as
dummyI integer;
dummyD double precision;
....
i integer;
begin
i = udfGetNextArecID(aSessionID);
while i>0 do
begin
DummyI = udfGetCurrAParamI (aSessionID, i);
DummyD = udfGetCurrAParamD (aSessionID, i);
....
insert into ... /* табл. результатов*/
values
(i, DummyI, DummyD, .....)
.....
i = udfGetNextArecID(aSessionID);
end
.....
i = udfGetNextBrecID(aSessionID);
while i>0 do
begin
DummyI = udfGetCurrBParamI (aSessionID, i);
DummyD = udfGetCurrBParamD (aSessionID, i);
....
insert into ... /* табл. результатов*/
values
(i, DummyI, DummyD, .....)
.....
i = udfGetNextBrecID(aSessionID);
end
.....
end
^
То, что время на загрузку данных в DLL и выгрузку данных их DLL примерно одинаково, объясняется тем, что загрузка проста и быстра, выполняются простыми командами select, но грузить надо очень много данных. Выгрузка обратная - более трудоёмкая операция (т.к. в один момент функция может вернуть только одно значение, кода (процедурного) много и он скомпилирован в псевдокоманды, выполняются операции insert) , но данных намного меньше (количественно).
Limitations: применять только на Classic (использовался IB 4.0/NT). На суперах - проблемы с невозможностью распознать сессию пользователя и одновременный расчёт двумя пользователями невозможен. Вариант решения - применение отдельного сервера приложений, который осуществляет запуск подобного расчёта.
Теперь что я думаю по данному поводу. В целом оно слегка похоже на мой ``обратный'' вариант, но вместо временной таблицы используются структуры данных, доступные UDF. Обычно (при традиционном использовании) вызовы этих функций работают автономно друг от друга, обрабатывая отдельные скалярные данные. Здесь же речь фактически идёт о создании специализированного программного модуля под задачу, имеющего интерфейс к InterBase в виде набора UDF в одной библиотеке. И вполне вероятно, что подобный подход может пригодиться не только по поводу рекурсии.
Сразу попутно замечу, что позже мной было написано введение в оптимизацию запросов в InterBase, где изложены базовые принципы.
Итак, в InterBase, как и в любой нормальной СУБД на базе SQL, можно в рамках
многих запросов писать вложенные подзапросы типа select, заключая
их в круглые скобки. Целей употребления такой конструкции, и соответственно
способов её интерпретации может быть несколько.
Во-первых, подзапрос как правило можно написать в том месте, где
требуется получить/вычислить какое-либо одно значение. В этом случае
просто на месте значения пишут подзапрос в скобках. При этом фраза
select этого подзапроса должна возвращать ровно одно поле,
а логика остальных частей должна обеспечивать, чтобы возвращалось
не более одной записи. Если не будет сформировано ни одной, то
подзапрос возвращает null, если же несколько, то возникнет
ошибка. Подзапросы подобного рода могут фигурировать, в частности,
в вычисляемых выражениях или в операциях сравнения.
Во-вторых, подзапросы могут употребляться в специальных конструкциях, где они возвращают не одно, а множество значений. Примерами таких конструкций являются:
выражение IN (подзапрос)
выражение =ALL (подзапрос)
выражение =SOME (подзапрос)
выражение =ANY (подзапрос)
Вроде бы всё. Последние две конструкции --
полные синонимы, но ANY лучше не употреблять, особенно если
хорошо знаете английский. Потому что штука весьма двусмысленная.
Во всех перечисленных конструкциях подзапрос может возвращать более одной записи. Хотя поле по-прежнему должно быть только одно. Так как сравнивается с одним значением внешнего запроса.
Некоторые граждане, в том числе в su.dbms.interbase, предлагали, в качестве доработки к IB сделать возможность извлекать несколько полей, и сравнивать их со списком значений за один приём. Чтож, операция действительно была бы полезна, но на суть того, что описано выше и ниже это не повлияет.
Далее о подзапросах первого вида будем говорить, что они существуют в скалярном контексте, а второго вида -- во множественном. Принципы терминологии взяты из языка Perl.
Кроме этого существует конструкция EXISTS(подзапрос),
однако в нашем случае она не представляет интереса, о чём ниже.
Всё то, что я написал в этом разделе может показаться второстепенным. Однако это совершенно не так, и у меня были веские основания начать именно с этого. Потому что обработка тех и других видов подзапросов в 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.
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 станет более эффективным. В прочем, ни один из вариантов
с подзапросами никогда не будет эффективнее, чем оптимальный план
в варианте с соединением. Потому невозможность автоматической раскрутки
подзапросов в соединения является важным недостатком, который следует
учитывать.
Разнообразные места, откуда я обычно черпаю информацию по InterBase. К сожалению, не всегда доходят руки зафиксировать все (потенциально) интересные ссылки, так что список, естественно, далёк от полноты. И естественно, сам не откажусь от новых ссылок по теме.
:-). Самые подходящие под темы этого
документа находятся здесь.