Re: Hash Join vs. Nested Loops

From: Mikito Harakiri <>
Date: Fri, 28 Feb 2003 11:43:00 -0800
Message-ID: <G2P7a.13$>

"Scott David Daniels" <Scott.Daniels_at_Acm.Org> wrote in message news:3e5ed73b$
> Mikito Harakiri wrote:
> > The last equation is not correct: my assumption was that we always
> > use Indexed Nested Loops. No database goes into production without
> > DBA creating join indexes for potentially large tables....
> (and then he goes on to describe what I'd call a merge join)
> The index provides data structure support for other physical
> join methods. If you call everything a nested loops join, then
> nested loops is all you need.


Thank you for the comment, but just to doublecheck the terminology:

Goetz Graefe "Query Evaluation Techniques for Large databases" 5.1 Nested-Loop Join Algorithm, p.106
"Finally, index nested-loops join exploits a permanent or temporary index on the inner input's join attribute..."
5.2 Merge Join Algorithms, p.106
"It [merge-join method] requires that both inputs are sorted on the join attribute."

I might have confuse you, because in my last message I suddenly switched my comparison from Nested Loops vs. Hash Join to Nested Loops vs. Sort Merge Join. But if you read the message closely enough you might notice that I never called Indexed Nested Loops as Merge Join, nor Merge Join as Indexed Nested Loops.

Once again, ordinary Nested Loops is so obviously flawed that it doesn't make sence to compare it to anything. Indexed Nested Loops, on the other hand, have performance profile comarable to either Hash Join or Sort Merge Join on large inputs. It blows them away on small inputs. Received on Fri Feb 28 2003 - 20:43:00 CET

Original text of this message