Re: Hash Join vs. Nested Loops
From: Costin Cozianu <c_cozianu_at_hotmail.com>
Date: Fri, 28 Feb 2003 12:42:43 -0800
Message-ID: <b3oh9m$1ot5o3$1_at_ID-152540.news.dfncis.de>
>
>
> I believe your original guess was right: the differences are important when
> the data is mainly on disk. The advantage of an hash-index vs. something
> like a B-tree index is that if you have a good hash function you probably
> only need to acces 1 disk page where with a B-tree this is only true if the
> whole index fits in main memory. The advantage of the merge join vs. nested
> loop with index is that chances are bigger that you still have the relevant
> pages in your page buffer when you re-encounter the same join value in the
> relation of the outside loop.
>
> -- Jan Hidders
>
>
>
Date: Fri, 28 Feb 2003 12:42:43 -0800
Message-ID: <b3oh9m$1ot5o3$1_at_ID-152540.news.dfncis.de>
Jan Hidders wrote:
> Mikito Harakiri wrote:
>
>>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.
>
>
> I believe your original guess was right: the differences are important when
> the data is mainly on disk. The advantage of an hash-index vs. something
> like a B-tree index is that if you have a good hash function you probably
> only need to acces 1 disk page where with a B-tree this is only true if the
> whole index fits in main memory. The advantage of the merge join vs. nested
> loop with index is that chances are bigger that you still have the relevant
> pages in your page buffer when you re-encounter the same join value in the
> relation of the outside loop.
>
> -- Jan Hidders
>
>
>
Plus a merge join may take advantage of an existing index (which is likely to happen in practice because DBA's typically define indexes on FK columns and joins typically follow defined FK), therefore the complexity is reduced to M+N. whereas a nested loop with index lookups will be M*logN Received on Fri Feb 28 2003 - 21:42:43 CET