Соединение вложенного цикла

Соединение вложенных циклов — это простой алгоритм , который объединяет два отношения с помощью двух вложенных циклов . Операции соединения важны для управления базами данных .

Алгоритм

Два отношения $R$ и $S$ соединяются следующим образом:

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

Этот алгоритм будет включать n _r *b _s + b _r блочные передачи и n _r +br _r поиск, где _br и b _s — количество блоков в отношениях R и S соответственно, а n _r — количество кортежей в отношении R. .

Алгоритм работает в $O(|R||S|)$ ввод/вывод, где $|R|$ и $|S|$ количество кортежей, содержащихся в $R$ и $S$ соответственно, и его можно легко обобщить для объединения любого количества отношений...

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

Вариант соединения индекса

Если внутреннее отношение имеет индекс атрибутов, используемых в соединении, то наивное соединение вложенного цикла можно заменить объединением индекса.

algorithm index_join is
    for each tuple r in R do
        for each tuple s in S in the index lookup do
            yield tuple <r,s>

Временная сложность для этого варианта улучшается с $O(|R||S|){\text{ to }}O(|R|\log |S|)$

См. также

• Хэш-соединение
• Соединение сортировки-слияния