Joins
Sort-Merge Join
// Advance iterators over sorted data to find matches
while R_row != NULL && S_row != NULL:
// Advance R_sorted until current R row is no longer smaller
while column_values(R_row, R_join_columns) < column_values(S_row, S_join_columns):
R_row = R_sorted.next()
// Advance S_sorted until current S row is no longer smaller
while column_values(S_row, s_join_columns) < column_values(R_row, R_join_columns):
S_row = S_sorted.next()
// Possibilities:
// - R_row is NULL, indicating we've seen all of R.
// - S_row is NULL, indicating we've seen all of S.
// - Both rows not NULL but no match on join columns
// - Both rows not NULL and they match on join columns
if R_row != NULL &&
S_row != NULL &&
column_values(R_row, R_join_columns) == column_values(S_row, S_join_columns):
join_matching_rows(column_values(R_row, R_join_columns), R_row, S_row, R_sorted, S_sorted)
// R_sorted, S_sorted have now moved past the rows that matched.
|