Merge join
Joinalgoritme voor reeds gesorteerde relaties: beide tegelijk doorlopen (zoals een ritssluiting) en de overeenkomende rijen uitvoeren. O(N+M) zonder extra sortering. Optimaal als beide invoeren op de joinsleutel gesorteerd zijn, meestal via passende B-tree-indexen.
Is de invoer niet gesorteerd, dan kan de planner een "sort-merge join" kiezen: eerst sorteren, dan samenvoegen, tegen een prijs van O(N log N). Concurrent: de hash join is sneller als het geheugen volstaat; de merge join is beter bij te weinig geheugen en behoudt de sorteervolgorde in de uitvoer, zodat een ORDER BY achteraf kan vervallen. Klassiek gebruik: datawarehouse-queries met meerdere joins op dezelfde gesorteerde sleutel. De PostgreSQL-planner kiest standaard liever een hash join; de merge join komt zelden uit de verf, behalve bij grote gesorteerde datasets en joins met lage cardinaliteit.