I'm studying advanced database and I can not understand some concepts related to the join. I hope I'm in the right place to post my doubts, otherwise I'm sorry.
I realized that to make the equijoin there are several families. In particular, the family that is based on the Cartesian product includes three main methods: nested loops, nested blocks and nested scans.
The nested loop method iterates on the outer relation R (tipically the smaller one) and for each tuple of R, it scans the internal relation S and applies the join condition. Then it just use the join definition: Cartesian product + selection. The cost of this process is:
C = |R| + |R| * |S|
You can get an improvement if instead of considering the tuples, consider the pages. In this case the cost is:
C = P_R + |R| * P_S
Why? I do not understand.
From what I remember of Operating Systems, the logical memory is divided into pages and the physical memory in frames, where the pages are of the same size of the frames. This is done to permit the non-contiguous allocation of files.
A tuple instead of what corresponds? I guess as a record (one line) of a table, but in this context what is it?
The nested blocks method is a further improvement because in main memory maintains a block of tuples of R. The improvement is obtained by scanning S only once for each group of tuples of R. A version of this charging algorithm in the tuples of R memory, then proceeds to S and examines the memory to find the S tuples that match any tuple of R. This reduces the number of necessary S scans. In this case the cost is:
C = P_R + P_R * P_S
I must admit that I did not understand very well this algorithm. Someone could explain it better?
Thus a block is a set of tuples? And a set of tuples form one page? I'm very confused.
Maybe some sketch could help me, I have not found that showed the tuples.
Thank you all
Nested loops (tuple)
I apologize but I have not yet understood the nested loop (pages) and nested block :(
What do you mean with "We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R"?
And with "In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost"?
I feel a bit stupid, sorry.