voldermar666Допустим есть 2 таблицы по х сток в каждой.


X1 и X2, во внешней и внутренней таблицах JOIN-а, соответственно

voldermar666И мы делаем inner join (left join, ...)
между ними по id.
Выполняется этот join за время t.


Время это не совсем неделимо. Дело в том, что в запросе почти никогда не
выполняется одна лишь операция JOIN-а двух таблиц в чистом виде.
Обычно в запросе происходит какая-то фильтрация по внешней таблице
и JOIN со внутренней таблицей (в процессе которого также может происходить доп. фильтрация).
Так что лучше разбить это время на два времени:
t1 -- время фильтрации записей во внешней таблице

t2_0 -- время выполнения JOIN-а одной записи внешней таблицы со всеми записями внутренней.

В итоге

t = t1 + X1_sel * t2_0

где X1_sel -- кол-во записей в X1 после фильтрации.


voldermar666Как в среднем увеличится время выполнения операции join,
если в левой таблице данных стало 2x строк (например апач лог).


А теперь можно говорить о задаче.

У нас есть X1, X1_sel и X2.
Как зависит X1_sel от X1 ?
Можно сказать только, что X1_sel <= X1 . В остальном можно утверждать, что X1_sel от X1 не зависит. Оно может быть любым, может быть и одна запись, а могут быть все записи (X1).
Поэтому говорить о влиянии кол-ва записей во внешней таблице на стоимость операции JOIN бессмысленно, лучше говорить о
производительности JOIN-а одной записи внешней таблицы в зависимости от размера внутренней.

Как выглядит эта зависимость ?
Она будет разной в зависимости от выбраного СУБД алгоритма выполнения JOIN-а.

Я расскажу только о самом распространённом и самом оптимальном в OLTP алгоритме -- nested loop join (NLJ или NL).
Заключается он в том, что JOIN выполняется в двух вложенных циклах, внешний -- по записям внешней таблице, а
внутренний -- по записям внутренней. В теле внутреннего цикла для текущей записи внешней таблицы проверяется
очередная запись внутренней таблицы на выполнение условия JOIN-а и, если они есть, на выполнение условий фильтрации по внутренней таблице.

Далее возможно 2 случая:

JOIN выполняется с какими-то экзотическими условиями типа <, !=, > и так далее, и/или не используется индекс для внутренней таблицы. Это неинтересные случаи, потому что это либо какие-то сугубо учебные задачи, либо случаи клинического идиотизма разработчиков запросов и БД, либо случаи, когда производительность JOIN-а нас не интересует (она в этом случае будет O( X1 * X2 ), т.е. O(X^2))

JOIN выполняется по равенству двух полей и с использованием индекса.

Вот последний случай и рассмотрим.

Очевидно, что на одну запись внешней таблицы одна запись внутренней будет находится за

O( log X2 )

Если во внутренней таблице таких записей будет много (назовём это кол-во X2_sel), они все будут располагаться в индексе друг за другом и за первой записью. И время их чтения будет не зависеть от X2 (оно реально не зависит от X2). Тогда оценка будет

O( log( X2) + X2_sel * ts0 )
Поскольку константы в O выкидываются, то получим в итоге

O( log( X2) + с ) = O( log X2 )

Это для одной записи внешней таблицы.
Для всех --

O( X1_sel * log X2 )

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

voldermar666То есть существует ли зависимость среднего времени выgолнения
операции join от количества входных данных? O(n), O(n*n)?


Тут конечно разговор не о среднем времени, а о оценке O. Это -- верхняя граница стоимости алгоритма.
Не средняя оценка.


Также я хочу сказать о других алгоритмах выполнения JOIN-а.
Это -- MERGE, SORT-MERGE и HASH(table)-JOIN.
Приведу примерно стоимости их тоже. Достаточно умозрительно выведенные, но в итоге всё же это дожно показывать примерную сложность.


NL -- O( X1_sel * log X2 )

MERGE -- O( log X1 + log X2 + max( X1_sel , X2_sel ) ) или O(max( X1 , X2 ) ) если полный JOIN всех записей без фильтров

SORT-MERGE -- O( X1 * log X1 + X2 * log X2 + max( X1_sel , X2_sel ) )

HASH(table)-JOIN. -- O( X2 + X1_sel * 1 )

Dimitry SibiryakovТы не поверишь, но она зависит от их реализации в конкретной СУБД.
У сферического join в вакууме в предположении о постоянстве числа записей и способа
доступа к ведомой таблице: NL - O(N), HASH - O(N), MERGE - O(N*logN).


Если на одну запись внешней таблицы, то

NL - O(logN),
HASH - O(N/X1_sel)
MERGE - O( X2 / X1_sel ) (хотя тут сложно очень выделить стоимость именно на 1 запись внешней таблицы)


O(N) -- это стоимость только когда JOIN без индекса и NL. Полная его стоимость O(N * M) , или в моих терминах O(X1_sel * X2)

voldermar666То есть существует ли зависимость среднего времени выgолнения
операции join от количества входных данных? O(n), O(n*n)?

Да, и самое главное -- выводы, которые ты должен сделать.

JOIN -- ОЧЕНЬ ЛЁГКАЯ и БЫСТРАЯ операция, если она выполняется по равенству и по иднексу (это 99 случаев JOIN-а на практике).

Самое главное, чтобы из внешней таблицы на входе JOIN-а дожно быть мало записей, иначе JOIN даже по индексу превратится в кошмар.