Merge join
Algoritmo de junção para relações já ordenadas: percorre as duas ao mesmo tempo, como um zíper, e emite as linhas que casam. O(N+M) sem ordenação extra.
É ótimo quando as duas entradas já vêm ordenadas pela chave da junção, tipicamente por causa de um índice B-tree. Se não vierem, o planejador pode escolher o "sort-merge join": ordena primeiro, faz o merge depois, ao custo de O(N log N). O concorrente é o hash join, mais rápido quando a memória dá conta; o merge join vence quando os dados não cabem na memória e quando preserva a ordenação na saída, o que pode dispensar um ORDER BY. O PostgreSQL prefere hash join por padrão, e o merge join só brilha com muitos dados ordenados.