Optimizing JOINs With Order-Based Merge Algorithm

Now, we look at how to optimize and speed up homo-dimension table JOINs and primary-and-sub table JOINs. They share the same optimization method.
As we mentioned, hash join algorithm’s computational complexity degree (the number of comparisons between associated fields) is about SUM(ni*mi), which is much smaller than n*m, the degree of complexity for performing a full traversal. Yet, you need to choose the right hash function to get your luck.
If both tables are ordered by the associative fields, we can use the merge-join algorithm to handle a JOIN. The complexity degree is n+m. When both n an...