Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
 эффективность алгоритма join  [new]
voldermar666
Member

Откуда:
Сообщений: 7
Здравствуйте, уважаемые участники форума.
Вопрос следующий:
Допустим есть 2 таблицы по х сток в каждой.
И мы делаем inner join (left join, ...)
между ними по id.
Выполняется этот join за время t.
Как в среднем увеличится время выполнения операции join,
если в левой таблице данных стало 2x строк (например апач лог).

То есть существует ли зависимость среднего времени выgолнения
операции join от количества входных данных? O(n), O(n*n)?
15 мар 14, 14:52    [15729171]     Ответить | Цитировать Сообщить модератору
 Re: эффективность алгоритма join  [new]
Dimitry Sibiryakov
Member

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

Ты не поверишь, но join может делаться как минимум тремя разными способами и у них всех -
разная сложность. Почитай документацию на свою СУБД.

Posted via ActualForum NNTP Server 1.5

15 мар 14, 14:55    [15729175]     Ответить | Цитировать Сообщить модератору
 Re: эффективность алгоритма join  [new]
voldermar666
Member

Откуда:
Сообщений: 7
Ок, если не сложно назови сложность этих видов джойнов.
15 мар 14, 14:56    [15729179]     Ответить | Цитировать Сообщить модератору
 Re: эффективность алгоритма join  [new]
Dimitry Sibiryakov
Member

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

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

Posted via ActualForum NNTP Server 1.5

15 мар 14, 15:03    [15729200]     Ответить | Цитировать Сообщить модератору
 Re: эффективность алгоритма join  [new]
voldermar666
Member

Откуда:
Сообщений: 7
Большое спасибо!
15 мар 14, 15:04    [15729204]     Ответить | Цитировать Сообщить модератору
 Re: эффективность алгоритма join  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709
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 )
  • 15 мар 14, 23:26    [15731241]     Ответить | Цитировать Сообщить модератору
     Re: эффективность алгоритма join  [new]
    MasterZiv
    Member

    Откуда: Питер
    Сообщений: 34709
    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)
    15 мар 14, 23:31    [15731263]     Ответить | Цитировать Сообщить модератору
     Re: эффективность алгоритма join  [new]
    MasterZiv
    Member

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


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

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

    Самое главное, чтобы из внешней таблицы на входе JOIN-а дожно быть мало записей, иначе JOIN даже по индексу превратится в кошмар.
    15 мар 14, 23:35    [15731279]     Ответить | Цитировать Сообщить модератору
    Все форумы / Сравнение СУБД Ответить