Page Oriented Nested Loop Join - QUERY OPTIMIZATION

Question

This could be a strange question. I have googled the problem and I couldn't find even the term that I am looking for.

I am learning about QUERY OPTIMATION in DB, and now I am on calculating the COST. I have learnt about Nested Loop Joins which is categorized as

1. Simple Nested Loop Join (SNLJ)
2. Page Oriented Nested Loop Join (PONLJ)
3. Block Oriented Nested Loop Join (BONLJ)

I am ok with SNLJ and BONLJ but I couldn't find any article or tutorial regarding PONLJ. The only think I know about PONLJ is

For each page read from R, get all pages of S, and write out matching pairs of tuples , where r is in R-page and S is in S-page. Cost = M + M*N

I need more explanation on this. Appreciate well described answers.

Thank you.

Answer 1

This is a bit long for a comment.

I'm not sure what the confusion is -- that is, your short description makes sense to me.

The idea in a nested loop join is that the code cycles through the rows in one table. Then for each row in one table, it looks up matching rows in the second table by comparing each possible pairs of rows.

Normally, you would understand this by looping the the rows individually. But the fact is that databases store rows in other units, particularly on pages.

PONLJ loops through each page in the table and then loops through all the rows on that page. Although this sounds like two loops, it is really going through all the rows only once.

The same process is repeated on the second table.