Блокировать вложенный цикл

Блочно -вложенный цикл ( BNL ) — это алгоритм, используемый для соединения двух отношений в реляционной базе данных . ^[1]

Этот алгоритм ^[2] является разновидностью простого соединения вложенного цикла и объединяет два отношения $R$ и $S$ («внешний» и «внутренний» объединяют операнды соответственно). Предполагать $|R|<|S|$ . В традиционном соединении вложенного цикла: $S$ будет сканироваться один раз для кортежа каждого $R$ . Если есть много подходящих $R$ кортежей, особенно если нет подходящего индекса для ключа соединения на $S$ , эта операция будет очень дорогой.

Алгоритм соединения блочных вложенных циклов совершенствует простое соединение вложенных циклов за счет только сканирования $S$ один раз для группы каждой $R$ кортежи. Здесь группы представляют собой непересекающиеся множества кортежей в $R$ и объединение всех групп имеет те же кортежи, что и $R$ . Например, один из вариантов объединения вложенных циклов блоков считывает страницу всю $R$ кортежи в память и загружают их в хеш-таблицу . Затем он сканирует $S$ и исследует хэш-таблицу, чтобы найти $S$ кортежи, соответствующие любому из кортежей на текущей странице $R$ . Это уменьшает количество сканирований $S$ которые необходимы.

algorithm block_nested_loop_join is
    for each page pr in R do
        for each page ps in S do
            for each tuple r in pr do
                for each tuple s in ps do
                    if r and s satisfy the join condition then
                        yield tuple <r,s>

Более агрессивный вариант этого алгоритма загружает столько страниц $R$ столько, сколько может поместиться в доступной памяти, загружая все такие кортежи в хеш-таблицу, а затем многократно сканируя $S$ . Это еще больше сокращает количество сканирований $S$ которые необходимы. Фактически, этот алгоритм по сути является частным случаем классического алгоритма хэш-соединения . ^{[ нужна ссылка ]}

Вложенный цикл блоков выполняется $O(P_{r}P_{s}/M)$ Вводы/выводы, где $M$ — количество доступных страниц внутренней памяти и $P_{r}$ и $P_{s}$ размер $R$ и $S$ соответственно в страницах. Примечание в этом блоке выполняется вложенный цикл $O(P_{r}+P_{s})$ Вводы/выводы, если $R$ помещается в доступную внутреннюю память.

Ссылки

^ «8.2.1.14 Блокировка соединений вложенного цикла и пакетного доступа к ключам» . Справочное руководство по MySQL 5.6 . Корпорация Оракл . Проверено 2 августа 2015 г.
^ «Блокировать соединение вложенного цикла» . МарияДБ . Корпорация MariaDB Ab . Проверено 2 августа 2015 г.

[mysql-1] «8.2.1.14 Блокировка соединений вложенного цикла и пакетного доступа к ключам» . Справочное руководство по MySQL 5.6 . Корпорация Оракл . Проверено 2 августа 2015 г.

[MariaDB-2] «Блокировать соединение вложенного цикла» . МарияДБ . Корпорация MariaDB Ab . Проверено 2 августа 2015 г.

[1]

[2]