Это простой nested-loop join алгоритм, предназначенный для работы на двух отношениях, R и S.
for tuple r in R:
for tuple s in S:
test (r, s) to see if they meet the join condition
По-видимому, наихудшее число поисков для этого алгоритма равно n(r) + b(r), что является # изкортежи в R плюс количество блоков в R.
Почему это так? Почему S не играет никакой роли в количестве запросов.