Алгоритмы выполнения соединения: поблочное соединение, усовершенствование алгоритма поблочного соединения, соединение по индексу

Поблочное соединение.

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

Для каждого блока Br отношения r выполнить

Для каждого блока Bs отношения s выполнить

Для каждого кортежа tr блока Br выполнить

Для каждого кортежа ts блока Bs выполнить

Если пара (ts, tr) соответствует условию

то tr?ts добавить к результату

Основное отличие состоит в том, что для просмотра внутреннего отношения не осуществляется чтение нового блока на каждой итерации цикла, что повышает эффективность. Теперь количество обращений к диску будет br*bs+br.

Этот алгоритм можно усовершенствовать.

Если соединение осуществляется по ключу, то выполнение цикла просмотра внутреннего отношения можно прекратить после нахождения первой же пары, удовлетворяющей условию соединения.

Если размеры памяти позволяют, то можно считывать объемы информации, большие, чем блок, что уменьшает количество обращений к диску.

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

Соединение по индексу.

Для каждого кортежа внешнего отношения r осуществляется просмотр индекса, построенного по отношению s. Строки, удовлетворяющие условию соединения, читаются из отношения. Отбор строк отношения s по кортежу отношения r аналогичен выполнению селекции отношения s по условию, задаваемому кортежем tr. Стоимость такого поиска будет составлять. br+nr*c, где с – стоимость селекции в отношении s.

Этот алгоритм работает как с физически существующими индексами, так и с индексами временно построенными для выполнения запроса.