Welcome to TDBSoverflow, Our class's own StackOverflow. Our rules:
  1. Use only meaningful and self-explanatory titles
  2. Tag your questions with meaningful keywords
  3. Use upvotes and downvotes to rate the answers
  4. When you receive a satisfying answer - Click the "V" button
Remember: you may get up to 5 bonus points to your final grade!

Result of an Index Nested Loop Join is always unsoreted?

0 votes

Hi all,

I have two questions on JOIN algorithms:

1.Lets say that I have two relations/tables R(A,B) and S(C,D) with Sorted indices on B and D respectively.
Say I perform an Index Nested Loop Join on  B=D, will the resulting table be sorted according to B\D?

2. Is it safe to assume that in Simple Nested Loop Join, Page-Oriented Nested Loop Join and  Block Nested Loop Join if the data entries are sorted in memory with respect to the field on which we are joining the two relations on, then the result will also be sorted with respect to that field or is the order of tuple/pages is arbitrary as opposed to lets say, reading the data from the lowest address to the highest?


asked Feb 5, 2018 by uribracha (3,110 points)

1 Answer

+1 vote
Best answer
About 1:

I think that Index nested loop join is only using an index on the relation in the inner loop (I guess there is a way to use 2 indices, but it's not something we covered). Therefore, result is not guaranteed to be sorted.

A confirmation from Amit would be nice, though.
answered Feb 5, 2018 by Assaf (31,090 points)
selected Feb 5, 2018 by uribracha
Okay, lets be even more specific, lets say that the outer relation data entries are sorted according to the field the join is being performed on.
I think that in this case the result is guaranteed to be sorted.
I agree - in this case it will be sorted.