Как известно есть три основных типа выполнения join'ов, nested loop, hash и merge.

У первого сложность A*B, у второго (A (+ B если требуется сортировка))* log B, у третьего A + B.

Соответственно у последних 2-х сложность линейная, у 1-го полиномиальная. 1-й нужен для того чтобы сократить накладные расходы (по сравнению с хэшем), но обратная сторона его, когда оптимизатор сильно не угадывает количество рядов, то запрос просто вешается.

Соответственно СУБД сплошь и рядом нарушают один из основных принципов алгоритмистики (когда сложность алгоритма ставится во главу угла, а экономия на спичках игнорируется). И поэтому становятся непредсказуемыми. (недавно нарвался на такую ситуацию)

Может кто подскажет в каких СУБД есть возможность, сказать использовать NESTED LOOP, только когда оптимизатор на 110% уверен что в таблице мало записей. А не в стиле вот у меня тут подзапрос с группировкой

ЗЫ: Естественно во всяких oracle'ах можно играть dynamic sampling'ом, но что-то мне подсказывает что в моем случае накладные расходы от него (как и вообще всего oracle'а) превысят тупое отрубание nested loop.

Dimitry Sibiryakov,

Ну предполагается что там индексы есть, потому как иначе hash join лучше.

Но вообще пусть будет A(logA+1) + B(logB+1)

Статистика,

В PostgreSQL. Индексы актуальны, там естественно ошибка в сложном случае, когда в подзапросе идет группировка на сумму, а потом фильтруется что эта сумма null, оптимизатор при actual 393 считает что запись 1, и из-за nested loop join'ов цепочкой разворачивает реальное выполнение в 20 сек.

Dimitry Sibiryakov,

Опять-таки рандомное чтение это некоторые весьма статичные затраты. То есть если у меня в запросе везде задействовано по 300 записей, то выполнение за пределы допустимого никак не выйдет. А с nested loop'ом 3 раза "умножит" и будет 27'000'000 операций и приехали.

Я понимаю это критично когда 2к юзеров и несложная функциональность, но скажем когда <20 юзеров и наоборот сложные запросы, то тогда гораздо хуже когда СУБД в клинч уходит.

locky,


Сколько по вашему i будет?

softwarer,

Если серверу не хватает памяти, пусть он лучшее ее подождет, ему же все равно вешаться... :)