Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
 "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
Как известно есть три основных типа выполнения 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.
27 авг 11, 14:04    [11189400]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54849

А куда это в оценке merge делась сортировка?..

Posted via ActualForum NNTP Server 1.4

27 авг 11, 14:39    [11189497]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
Dimitry Sibiryakov,

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

Но вообще пусть будет A(logA+1) + B(logB+1)
27 авг 11, 14:46    [11189521]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Статистика
Guest
Скорее откуда это в HASH взялась сортировка?

И в какой СУБД у вас выпадает в Nested loop? Статистика актуальна по индексам по которым идет соединение? Какое кол-во записей в каждой из двух таблиц?
27 авг 11, 14:48    [11189530]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
locky
Member

Откуда: Харьков, Украина
Сообщений: 62034
вообще говоря, циклы - самый "лёгкий" для ресурсов способ объединения
и хэш, и мердж требуют порядочных накладных расходов

но, если кому не нравится - тот всегда может использовать хинты или план-гайды
27 авг 11, 15:15    [11189625]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54849

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

Да неужели? Доступ по индексу вообще-то дороже сортировки из-за рандомного чтения...

Posted via ActualForum NNTP Server 1.4

27 авг 11, 15:25    [11189657]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
Статистика,

В PostgreSQL. Индексы актуальны, там естественно ошибка в сложном случае, когда в подзапросе идет группировка на сумму, а потом фильтруется что эта сумма null, оптимизатор при actual 393 считает что запись 1, и из-за nested loop join'ов цепочкой разворачивает реальное выполнение в 20 сек.
27 авг 11, 15:35    [11189692]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
Dimitry Sibiryakov,

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

Я понимаю это критично когда 2к юзеров и несложная функциональность, но скажем когда <20 юзеров и наоборот сложные запросы, то тогда гораздо хуже когда СУБД в клинч уходит.
27 авг 11, 15:39    [11189697]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
locky
Member

Откуда: Харьков, Украина
Сообщений: 62034
что-то я не понимаю, как при циклах с индексами у нас происходит умножение к-ва записей.
27 авг 11, 15:42    [11189703]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
locky,

int i=0;
for(A a : as)
   for(B b : bs)
       i++;
return i;


Сколько по вашему i будет?
27 авг 11, 15:47    [11189717]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
locky
Member

Откуда: Харьков, Украина
Сообщений: 62034
Bond_JamesBond
locky,

int i=0;
for(A a : as)
   for(B b : bs)
       i++;
return i;


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

так индексы вроде есть, не? :)
для вложенного цикла
27 авг 11, 16:24    [11189791]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Статистика
Guest
У PostgreSQL нету IOS, так что даже при покрывающих индексах merge у него тоже будет с рандомным чтением. Указывай хинт для использования hash join.
27 авг 11, 18:47    [11190067]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Критик
Member

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


В том же MSSQL можно задать хинт.

Или перед выполнением запроса пересчитать статистику по таблицам, тогда у оптимизатора будут верные на 99% данные)
28 авг 11, 12:22    [11191484]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
softwarer
Member

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

Мало записей - оно не совсем всегда в кассу, поскольку NESTED LOOP позволяет выдать первые записи быстро. И соответственно, быстро заполнить видимую первую страницу даже если данных много.

Ну а так как бы Вы хотите несколько странного. С тем же успехом NL может быть единственным выбором, если на сервере не хватает памяти. И если всё это и всё прочее попытаться сформулировать... собственно и получается оптимизатор.

Возможность сказать... мне так помнится, в старых ораклах можно быть регулировать склонность выбирать NL, задавая параметры, определяющие сравнительную привлекательность многоблочного и одноблочного чтения (INDEX_COST_ADJ_чеготовэтомроде).
29 авг 11, 00:06    [11192800]     Ответить | Цитировать Сообщить модератору
 Re: "Фатальный" Nested Loop Join  [new]
Bond_JamesBond
Guest
softwarer,

Если серверу не хватает памяти, пусть он лучшее ее подождет, ему же все равно вешаться... :)
29 авг 11, 11:28    [11193812]     Ответить | Цитировать Сообщить модератору
Все форумы / Сравнение СУБД Ответить