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

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

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

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

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

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

Ссылки [ править ]