Good material. Joins can be also categorized by the used join algorithm. The simplest join is a nested loop join. In this case a larger dataset is iterated an

Good material. Joins can be also categorized by the used join algorithm. The simplest join is a nested loop join. In this case a larger dataset is iterated and another small dataset is combined using a simple key lookup. Then there is a merge join. In this case two larger datasets are first sorted using merge sort and then aligned linearly. Then there is a hash join. For the hash join a hash table is generated first based on the smaller dataset and the larger dataset is iterated and the join is made by making a hash lookup to the generated hash table. The difference between nested loop join and hash join might be confusing. In case of a nested loop join the second table is not loaded from the storage medium first, instead an index is used to lookup the location of the records. This has O(log n) complexity for each lookup. For hash join the table is loaded and hash table is generated. In this case each lookup has O(1) complexity but creation of hash table is expensive (it has O(n) complexity) and is only worth the cost when the dataset is relatively large.