Re:Speeding up SQL queries by orders of magnitude using UNION
by gfody on Monday March 22, 2021 @06:15PM
(#26548061)
> if you study engine internals, especially MergeJoin, HashJoin, NestedLoopJoin
it's called merge join because it employs the merge algorithm (linear time constant space)[1] - this can only be used when the inputs are sorted. likewise the hash join entails building a hash table and using it (linear time linear space)[2] but the inputs don't have to be sorted. the point of these is to avoid the O(N*M) nested loop
it's called merge join because it employs the merge algorithm (linear time constant space)[1] - this can only be used when the inputs are sorted. likewise the hash join entails building a hash table and using it (linear time linear space)[2] but the inputs don't have to be sorted. the point of these is to avoid the O(N*M) nested loop
[1] https://en.wikipedia.org/wiki/Merge_algorithm
[2] https://en.wikipedia.org/wiki/Hash_join