tag

#joins

2 pages tagged

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.15 Hash Joins

5.15 Hash Joins Problem You need to join two collections by matching keys. A nested loop join compares every item from the first collection with every item from the second collection. This is simple, but it costs O(nm) for collections of sizes n and m . A hash join reduces this cost by indexing one side in a hash map. Solution Build a hash map from the smaller collection, then...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Sort Merge Join Sort Phase

Sort Merge Join Sort Phase The sort phase of sort-merge join orders each input relation by the join key before the merge phase begins. If an input is already ordered by a suitable index or previous query operator, the database can skip sorting that input. This phase is important because the merge join itself requires ordered streams. Without sorted inputs, the join cannot advance both sides efficiently. Problem Given two...