Joins
Sort-Merge Join
join_matching_rows(join_column_values, R_row, S_row, R_sorted, S_sorted):
S_match = S_sorted // Iterator to scan matching rows
// Keep scanning S as long as we have rows, and the R and S rows match.
while R_row != NULL &&
S_row != NULL &&
column_values(R_row, R_join_columns) == join_column_values:
column_values(S_row, S_join_columns) == join_column_values:
output join(R_row, S_row)
// Go to next S row
S_row = S_match.next()
// If we have left the sequence of S rows matching join_column_values,
// then advance R and start scanning the matching S rows again.
if column_values(S_row, S_join_columns) > join_column_values:
R_row = R_sorted.next()
if column_values(R_row, R_join_columns) == join_column_values:
// R has a new row matching the join_column_values, so scan S again.
S_match.close()
S_match.open()
S_row = S_match.next()
// R has advanced to the first row exceeding join_column_values.
// S needs to have the same property, so:
S_sorted = S_match
|