Is LINQ Join operator using Nested Loop, Merge, or HashSet Joins?
Asked Answered
D

1

6

Does anyone know what Join algorith does LINQ performs with its Join operator.

Is it NestedLoop, Merge, or HashSet? Is there any way to specify a different one, if supported?

Regards Albert

Driskill answered 13/10, 2009 at 17:8 Comment(2)
Depends on the provider.Furfur
I meant while using Linq To ObjectsDriskill
G
9

First it effectively creates a lookup from the "inner" sequence, then iterates through the outer sequence. It can then look up each key from the outer sequence and yield each appropriate pair. Something like this (ignoring argument validation etc):

public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>
    (this IEnumerable<TOuter> outer,
     IEnumerable<TInner> inner,
     Func<TOuter, TKey> outerKeySelector,
     Func<TInner, TKey> innerKeySelector,
     Func<TOuter, TInner, TResult> resultSelector)
{
    Lookup<TKey, TInner> lookup = inner.ToLookup(innerKeySelector);
    foreach (TOuter outerItem in outer)
    {
        TKey key = outerKeySelector(outerItem);
        foreach (TInner innerItem in lookup[key])
        {
            yield return resultSelector(outerItem, innerItem);
        }
    }
}

The lookup will use a hash table internally for the keys, so that it's efficient to look up any individual key.

Grueling answered 13/10, 2009 at 17:44 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.