[API Proposal]: Introduce LeftJoin LINQ operator

@jeffhandley

Background and motivation

Background

LINQ has a Join operator, which, like its SQL INNER JOIN counterpart, correlates elements of two sequences based on matching keys; the LINQ join implementation internally creates a Lookup for the inner sequence, and then loops over the outer sequence, doing a lookup for the matching inner elements. In SQL database parlance, this is known as the hash join strategy (SQL Server docs, PostgreSQL docs as well as this useful post).

In addition to the above, SQL also has LEFT JOIN, which returns outer elements even if there's no corresponding inner ones; LINQ, in contrast, lacks this operator. The LINQ conceptual documentation shows how to combine existing operators to achieve a left join:

var query = students
    .GroupJoin(departments, student => student.DepartmentID, department => department.ID, (student, departmentList) => new { student, subgroup = departmentList })
    .SelectMany(
        joinedSet => joinedSet.subgroup.DefaultIfEmpty(),
        (student, department) => new
        {
            student.student.FirstName,
            student.student.LastName,
            Department = department.Name
        });

There are two issues with the above suggestion:

It's complicated, requiring combining 3 different LINQ operators in a specific way, and is easy to accidentally get wrong. Many EF users have complained about the complexity of this construct for expressing a simple SQL LEFT JOIN.
It is inefficient - the combination of operators adds significant overhead compared to a single operator using a hash join (as Join does).

Proposal

This proposes introducing a 1st-class LeftJoin operator, which operates very similar to Join, except that it returns outer elements for which no inner element could be correlated. Aside from being much simpler to use than GroupJoin/SelectMany, it would also simply use Lookup internally - just like Join - and would therefore be much faster.

An initial implementation shows significant performance improvement compared to GroupJoin/SelectMany; LeftJoin is always faster than the equivalent GroupJoin/SelectMany construct, since GroupJoin itself constructs and uses a Lookup internally to implement an inner join internally - just like LeftJoin does - but also adds additional work on top.

BenchmarkDotNet v0.14.0, macOS Sequoia 15.1.1 (24B91) [Darwin 24.1.0]
Apple M2 Max, 1 CPU, 12 logical and 12 physical cores
.NET SDK 9.0.100
  [Host]     : .NET 9.0.0 (9.0.24.52809), Arm64 RyuJIT AdvSIMD
  DefaultJob : .NET 9.0.0 (9.0.24.52809), Arm64 RyuJIT AdvSIMD

Method	InnersPerOuter	OuterCount	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
LeftJoin	1	1	97.73 ns	0.402 ns	0.376 ns	0.64	0.00	0.0573	-	-	480 B	0.71
GroupJoin_SelectMany	1	1	153.02 ns	0.370 ns	0.309 ns	1.00	0.00	0.0811	-	-	680 B	1.00

LeftJoin	1	10	488.66 ns	5.764 ns	5.391 ns	0.57	0.01	0.2031	-	-	1704 B	0.57
GroupJoin_SelectMany	1	10	856.40 ns	4.305 ns	4.027 ns	1.00	0.01	0.3567	-	-	2984 B	1.00

LeftJoin	1	100	4,814.61 ns	19.884 ns	17.627 ns	0.59	0.00	1.7090	0.0534	-	14344 B	0.54
GroupJoin_SelectMany	1	100	8,173.26 ns	37.560 ns	35.134 ns	1.00	0.01	3.1586	0.1068	-	26424 B	1.00

LeftJoin	1	1000	47,619.93 ns	227.566 ns	201.731 ns	0.59	0.00	16.2964	3.4790	-	136728 B	0.53
GroupJoin_SelectMany	1	1000	80,828.42 ns	323.010 ns	302.144 ns	1.00	0.01	30.6396	6.5918	-	256808 B	1.00

LeftJoin	10	1	300.03 ns	3.089 ns	2.580 ns	0.70	0.01	0.1316	-	-	1104 B	0.85
GroupJoin_SelectMany	10	1	430.06 ns	3.919 ns	3.273 ns	1.00	0.01	0.1554	-	-	1304 B	1.00

LeftJoin	10	10	2,954.84 ns	28.864 ns	25.587 ns	0.87	0.01	0.9460	0.0076	-	7944 B	0.86
GroupJoin_SelectMany	10	10	3,397.03 ns	9.497 ns	8.419 ns	1.00	0.00	1.1024	0.0114	-	9224 B	1.00

LeftJoin	10	100	31,873.63 ns	120.088 ns	106.455 ns	0.81	0.02	9.1553	0.7324	-	76744 B	0.86
GroupJoin_SelectMany	10	100	39,299.04 ns	743.548 ns	856.271 ns	1.00	0.03	10.5591	0.8545	-	88824 B	1.00

LeftJoin	10	1000	402,837.52 ns	5,140.127 ns	4,808.078 ns	0.88	0.01	90.8203	30.2734	-	760728 B	0.86
GroupJoin_SelectMany	10	1000	457,658.94 ns	5,117.136 ns	4,786.572 ns	1.00	0.01	104.9805	34.6680	-	880808 B	1.00

LeftJoin	100	1	1,906.55 ns	9.026 ns	8.443 ns	0.83	0.01	0.6981	0.0019	-	5848 B	0.97
GroupJoin_SelectMany	100	1	2,310.49 ns	29.862 ns	27.933 ns	1.00	0.02	0.7210	0.0038	-	6048 B	1.00

LeftJoin	100	10	18,861.98 ns	366.707 ns	560.001 ns	0.85	0.03	6.5918	0.2747	-	55384 B	0.98
GroupJoin_SelectMany	100	10	22,285.02 ns	189.605 ns	177.356 ns	1.00	0.01	6.7444	0.2747	-	56664 B	1.00

LeftJoin	100	100	197,041.60 ns	2,033.092 ns	1,802.283 ns	0.83	0.01	65.6738	15.8691	-	551144 B	0.98
GroupJoin_SelectMany	100	100	236,428.77 ns	1,920.429 ns	1,702.410 ns	1.00	0.01	67.1387	16.6016	-	563224 B	1.00

LeftJoin	100	1000	2,628,960.79 ns	22,819.664 ns	21,345.528 ns	0.85	0.03	656.2500	316.4063	-	5504731 B	0.98
GroupJoin_SelectMany	100	1000	3,113,006.15 ns	62,259.419 ns	95,076.717 ns	1.00	0.04	671.8750	328.1250	-	`5624811` B	1.00

LeftJoin	1000	1	17,487.96 ns	203.775 ns	180.641 ns	0.84	0.01	5.8594	0.1221	-	49056 B	1.00
GroupJoin_SelectMany	1000	1	20,818.61 ns	251.607 ns	210.103 ns	1.00	0.01	5.8594	0.1831	-	49256 B	1.00

LeftJoin	1000	10	175,500.86 ns	2,377.458 ns	1,856.162 ns	0.77	0.02	58.1055	11.9629	-	487464 B	1.00
GroupJoin_SelectMany	1000	10	228,064.76 ns	4,414.845 ns	4,907.089 ns	1.00	0.03	58.3496	12.6953	-	488744 B	1.00

LeftJoin	1000	100	2,092,691.16 ns	39,429.196 ns	77,829.392 ns	0.86	0.04	582.0313	250.0000	-	4871947 B	1.00
GroupJoin_SelectMany	1000	100	2,422,638.76 ns	47,560.763 ns	84,539.215 ns	1.00	0.05	582.0313	246.0938	-	4884027 B	1.00

LeftJoin	1000	1000	42,875,766.40 ns	738,934.130 ns	691,199.444 ns	0.89	0.02	5900.0000	1700.0000	100.0000	48712842 B	1.00
GroupJoin_SelectMany	1000	1000	47,966,803.96 ns	925,858.818 ns	1,066,220.392 ns	1.00	0.03	5888.8889	1666.6667	111.1111	48832891 B	1.00

Benchmark code

[MemoryDiagnoser]
public class LeftJoinBenchmarks
{
    [Params(1, 10, 100, 1000, Priority = 1)]
    // [Params(1, Priority = 1)]
    public int InnersPerOuter { get; set; }

    [Params(1, 10, 100, 1000, Priority = 2)]
    // [Params(1, Priority = 2)]
    public int OuterCount { get; set; }

    private Outer[] _outers = null!;
    private Inner[] _inners = null!;

    class Outer
    {
        public int Id { get; set; }
        public string? OuterPayload { get; set; }
    }

    class Inner
    {
        public int Id { get; set; }
        public int OuterId { get; set; }
        public string? InnerPayload { get; set; }
    }

    private const int RandomSeed = 42;

    [GlobalSetup]
    public void Setup()
    {
        _outers = new Outer[OuterCount];
        _inners = new Inner[OuterCount * InnersPerOuter];

        var remainingInners = new List<Inner>(OuterCount * InnersPerOuter);
        for (var outerId = 0; outerId < OuterCount; outerId++)
        {
            _outers[outerId] = new Outer { Id = outerId, OuterPayload = $"Outer{outerId}" };

            for (var j = 0; j < InnersPerOuter; j++)
            {
                var innerId = outerId * j + j;
                remainingInners.Add(new Inner { Id = innerId, OuterId = outerId, InnerPayload = $"Inner{innerId}" });
            }
        }

        var random = new Random(RandomSeed);

        for (var i = 0; i < _inners.Length; i++)
        {
            var j = random.Next(0, remainingInners.Count);
            _inners[i] = remainingInners[j];
            remainingInners.RemoveAt(j);
        }

        Debug.Assert(remainingInners.Count == 0);
    }

    [Benchmark]
    public int LeftJoin()
        => _outers.LeftJoin(_inners, o => o.Id, i => i.OuterId, (o, i) => new { o.OuterPayload, i?.InnerPayload }).Count();

    [Benchmark(Baseline = true)]
    public int GroupJoin_SelectMany()
        => _outers
            .GroupJoin(_inners, o => o.Id, i => i.OuterId, (o, inners) => new { Outer = o, Inners = inners })
            .SelectMany(
                joinedSet => joinedSet.Inners.DefaultIfEmpty(),
                (o, i) => new
                {
                    o.Outer.OuterPayload,
                    i?.InnerPayload
                })
            .Count();
}

LeftJoin operator prototype implementation

private static IEnumerable<TResult> LeftJoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer,
    IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector,
    Func<TOuter, TInner?, TResult> resultSelector, IEqualityComparer<TKey>? comparer)
{
    using (IEnumerator<TOuter> e = outer.GetEnumerator())
    {
        if (e.MoveNext())
        {
            Lookup<TKey, TInner> innerLookup =
                Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
            do
            {
                TOuter item = e.Current;
                Grouping<TKey, TInner>? g = innerLookup.GetGrouping(outerKeySelector(item), create: false);
                if (g is null)
                {
                    yield return resultSelector(item, default);
                }
                else
                {
                    int count = g._count;
                    TInner[] elements = g._elements;
                    for (int i = 0; i != count; ++i)
                    {
                        yield return resultSelector(item, elements[i]);
                    }
                }
            } while (e.MoveNext());
        }
    }
}

Note: The current LINQ documentation for GroupJoin/SelectMany shows using AsQueryable, for no apparent reason. The addition of AsQueryable here adds very significant perf overhead - see dotnet/docs#43807 for benchmarks and a proposal to remove AsQueryable from that code sample.

Additional Notes

This proposal also helps LINQ provider such as EF - the ability to directly express a SQL LEFT JOIN comes up regularly.
For inner value types, the operator returns default when an outer has no inners; this makes it impossible to distinguish between an inner not being found, and the inner being found but being null. This is similar to e.g. FirstOrDefault; although it's quite contrived for LeftJoin, see below for some notes and alternative API designs.
Mostly for symmetry's sake, we could also introduce RightJoin(), which is the reverse of LeftJoin() (i.e. elements from the inner sequence are returned if no correlated outer is found). Right joins are seldom used in SQL, and it's always possible to flip the sequences around to express the join as a left join instead.
In theory, we could also introduce an operator to perform a FULL OUTER JOIN, which is a combination of LEFT and RIGHT JOIN (elements from both outer and inner are returned even if there's no correlated element on the other side). This is, however, a rare operation and not generally very useful, and is more complicated to implement efficiently. We can do this later if the need arises, but should keep naming in mind.
Naming-wise:
- Following the full operation name, we could call the operator LeftOuterJoin instead of LeftJoin; though the OUTER keyword is optional in all major SQL databases, and routinely dropped. LeftJoin is a lighter, more accessible name.
- It may seem a bit odd to introduce the very SQL-oriented LeftJoin, RightJoin. However, LINQ operators already follow SQL naming (e.g. Where/Select rather than Filter/Map).
- We could have JoinLeft, JoinRight to have all join operators grouped together in Intellisense (though the naming is less intuitive).
Corresponding syntax could be added to LINQ expression syntax, on the C# side (just like join) - but this is optional. Proposal: Proposal: introduce left and right join clauses to C# query expression syntax csharplang#8892.
We should consider an analyzer+code fix to transform the current recommended GroupJoin/SelectMany into the new LeftJoin - including with the unneeded AsQueryable shown in the docs - as many people have been copy-pasting that and have very slow code (see this).

/cc @jeffhandley @dotnet/area-system-linq @dotnet/efteam

API Proposal

namespace System.Linq;

public static class Enumerable
{
    // Alternative naming: LeftOuterJoin
    public static IEnumerable<TResult> LeftJoin<TOuter, TInner, TKey, TResult>(
        this IEnumerable<TOuter> outer,  
        IEnumerable<TInner> inner,
        Func<TOuter, TKey> outerKeySelector,
        Func<TInner, TKey> innerKeySelector,
        Func<TOuter, TInner?, TResult> resultSelector);

    public static IEnumerable<TResult> LeftJoin<TOuter, TInner, TKey, TResult>(
        this IEnumerable<TOuter> outer,  
        IEnumerable<TInner> inner,
        Func<TOuter, TKey> outerKeySelector,
        Func<TInner, TKey> innerKeySelector,
        Func<TOuter, TInner?, TResult> resultSelector,
        IEqualityComparer<TKey>? comparer);

// ... plus optionally RightJoin version of the above
}

public static class Queryable
{
    public static System.Linq.IQueryable<TResult> LeftJoin<TOuter,TInner,TKey,TResult>(
        this System.Linq.IQueryable<TOuter> outer,
        System.Collections.Generic.IEnumerable<TInner> inner,
        System.Linq.Expressions.Expression<Func<TOuter,TKey>> outerKeySelector,
        System.Linq.Expressions.Expression<Func<TInner,TKey>> innerKeySelector,
        System.Linq.Expressions.Expression<Func<TOuter,TInner?,TResult>> resultSelector);
	
    public static System.Linq.IQueryable<TResult> Join<TOuter,TInner,TKey,TResult>(
        this System.Linq.IQueryable<TOuter> outer,
        System.Collections.Generic.IEnumerable<TInner> inner,
        System.Linq.Expressions.Expression<Func<TOuter,TKey>> outerKeySelector,
        System.Linq.Expressions.Expression<Func<TInner,TKey>> innerKeySelector,
        System.Linq.Expressions.Expression<Func<TOuter,TInner?,TResult>> resultSelector,
        System.Collections.Generic.IEqualityComparer<TKey>? comparer);
}

// If we decide to also introduce RightJoin (or RightOuterJoin):

public static class Enumerable
{
    // Alternative naming: RightOuterJoin
    public static IEnumerable<TResult> RightJoin<TOuter, TInner, TKey, TResult>(
        this IEnumerable<TOuter> outer,  
        IEnumerable<TInner> inner,
        Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector,
        Func<TOuter?, TInner, TResult> resultSelector);

    public static IEnumerable<TResult> RightJoin<TOuter, TInner, TKey, TResult>(
        this IEnumerable<TOuter> outer,  
        IEnumerable<TInner> inner,
        Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector,
        Func<TOuter?, TInner, TResult> resultSelector,
        IEqualityComparer<TKey>? comparer);

// ... plus optionally RightJoin version of the above
}

public static class Queryable
{
    public static System.Linq.IQueryable<TResult> RightJoin<TOuter,TInner,TKey,TResult>(
        this System.Linq.IQueryable<TOuter> outer,
        System.Collections.Generic.IEnumerable<TInner> inner,
        System.Linq.Expressions.Expression<Func<TOuter,TKey>> outerKeySelector,
        System.Linq.Expressions.Expression<Func<TInner,TKey>> innerKeySelector,
        System.Linq.Expressions.Expression<Func<TOuter?,TInner,TResult>> resultSelector);
	
    public static System.Linq.IQueryable<TResult> RightJoin<TOuter,TInner,TKey,TResult>(
        this System.Linq.IQueryable<TOuter> outer,
        System.Collections.Generic.IEnumerable<TInner> inner,
        System.Linq.Expressions.Expression<Func<TOuter,TKey>> outerKeySelector,
        System.Linq.Expressions.Expression<Func<TInner,TKey>> innerKeySelector,
        System.Linq.Expressions.Expression<Func<TOuter?,TInner,TResult>> resultSelector,
        System.Collections.Generic.IEqualityComparer<TKey>? comparer);
}

API Usage

var query = outers.LeftJoin(inners, o => o.Id, i => i.OuterId, (o, i) => new { o.OuterPayload, i?.InnerPayload });

Value types and alternative LeftJoin API shapes

As pointed out above, the fact that the result selector accepts a defaultable inner means that it's impossible to distinguish between no inner being found for an outer, and the situation where the inner itself happens to be the default (thanks for discussion on this, @eiriktsarpalis). This problem isn't specific to this proposal, other operators (e.g. FirstOrDefault) have the same problem.

An alternative API to address this would pass a boolean to the result selector, representing whether an inner was found or not:

public static IEnumerable<TResult> LeftJoin<TOuter, TInner, TKey, TResult>(
	this IEnumerable<TOuter> outer,  
	IEnumerable<TInner> inner,
	Func<TOuter, TKey> outerKeySelector,
        Func<TInner, TKey> innerKeySelector,
	Func<TOuter, bool, TInner, TResult> resultSelector);

Alternatively, with the upcoming introduction of discriminated unions to .NET, an Optional type could allow the same thing:

public static IEnumerable<TResult> LeftJoin<TOuter, TInner, TKey, TResult>(
	this IEnumerable<TOuter> outer,  
	IEnumerable<TInner> inner,
	Func<TOuter, TKey> outerKeySelector,
        Func<TInner, TKey> innerKeySelector,
	Func<TOuter, Optional<TInner>, TResult> resultSelector);

However, it seems that cases where the distinction between "not found" and "found but default" matters are especially rare for joining; the inner key selector would have to accept a null/default inner and "extract" a key out of that (matching the outer key); not impossible, but definitely feels contrived. It's also possible to work around the ambiguity (in some cases) by switching to a nullable value type.

In other words, we should IMHO avoid making the API more complex/heavy for everyone because of a 1% case.

Previous related issues

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

@roji

Your Additional Notes covered all the questions and naming thoughts I had, @roji. Thanks for including all of that.

@stephentoub

@stephentoub - Is this something we should also consider for PLINQ?

(For others - because of the internals of PLINQ, it's not possible for third parties to implement their own operators, as it is with normal LINQ)

@stephentoub

@stephentoub - Is this something we should also consider for PLINQ?

From an API perspective, #98689 covers adding to PLINQ any APIs added to LINQ that PLINQ doesn't already have. I don't think this particular API is any more special than the others already omitted, so I'd just want to lump this one in with those.

From an implementation perspective, I suspect the PLINQ implementation would just be the code @roji wrote in his opening comments, with that operator implemented by delegating to GroupJoin/SelectMany. Doing a full-fledged open-coded implementation of PLINQ's would be a lot of difficult to validate code.

because of the internals of PLINQ, it's not possible for third parties to implement their own operators

When doing an open-coded implementation, sure. But anyone can layer an implementation on top of the existing operators, just as with LINQ, e.g.

public static ParallelQuery<TResult> LeftJoin<TOuter, TInner, TKey, TResult>(
    this ParallelQuery<TOuter> outer, ParallelQuery<TInner> inner,
    Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector,
    Func<TOuter, TInner?, TResult> resultSelector) =>
    outer.GroupJoin(inner, outerKeySelector, innerKeySelector, (outerItem, innerItem) => (outerItem, innerItem))
         .SelectMany(joinedSet => joinedSet.innerItem.DefaultIfEmpty(), (joinedSet, innerItem) => resultSelector(joinedSet.outerItem, innerItem));

@roji

From an implementation perspective, I suspect the PLINQ implementation would just be the code @roji wrote in his opening comments, with that operator implemented by delegating to GroupJoin/SelectMany. Doing a full-fledged open-coded implementation of PLINQ's would be a lot of difficult to validate code.

@stephentoub I know very little about PLINQ, but assuming an implementation of Join already exists, wouldn't an implementation of LeftJoin be very similar (just as the non-PLINQ implementation of LeftJoin is very similar to the Join implementation)?

wouldn't an implementation of LeftJoin be very similar (just as the non-PLINQ implementation of LeftJoin is very similar to the Join implementation)?

Likely. But to put it in context, this is the LINQ implementation of Join:

runtime/src/libraries/System.Linq/src/System/Linq/Join.cs

Lines 48 to 74 in 342936c

    
           private static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey>? comparer) 
        
           { 
        
               using (IEnumerator<TOuter> e = outer.GetEnumerator()) 
        
               { 
        
                   if (e.MoveNext()) 
        
                   { 
        
                       Lookup<TKey, TInner> lookup = Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer); 
        
                       if (lookup.Count != 0) 
        
                       { 
        
                           do 
        
                           { 
        
                               TOuter item = e.Current; 
        
                               Grouping<TKey, TInner>? g = lookup.GetGrouping(outerKeySelector(item), create: false); 
        
                               if (g is not null) 
        
                               { 
        
                                   int count = g._count; 
        
                                   TInner[] elements = g._elements; 
        
                                   for (int i = 0; i != count; ++i) 
        
                                   { 
        
                                       yield return resultSelector(item, elements[i]); 
        
                                   } 
        
                               } 
        
                           } 
        
                           while (e.MoveNext()); 
        
                       } 
        
                   } 
        
               }

and this monster is the PLINQ implementation:

runtime/src/libraries/System.Linq.Parallel/src/System/Linq/Parallel/QueryOperators/Binary/JoinQueryOperator.cs

Lines 16 to 282 in 342936c

    
               /// <summary> 
        
               /// A join operator takes a left query tree and a right query tree, and then yields the 
        
               /// matching pairs between the two. LINQ supports equi-key-based joins. Hence, a key- 
        
               /// selection function for the left and right data types will yield keys of the same 
        
               /// type for both. We then merely have to match elements from the left with elements from 
        
               /// the right that have the same exact key. Note that this is an inner join. In other 
        
               /// words, outer elements with no matching inner elements do not appear in the output. 
        
               /// 
        
               /// Hash-joins work in two phases: 
        
               /// 
        
               ///    (1) Building - we build a hash-table from one of the data sources. In the case 
        
               ///            of this specific operator, the table is built from the hash-codes of 
        
               ///            keys selected via the key selector function. Because elements may share 
        
               ///            the same key, the table must support one-key-to-many-values. 
        
               ///    (2) Probing - for each element in the data source not used for building, we 
        
               ///            use its key to look into the hash-table. If we find elements under this 
        
               ///            key, we just enumerate all of them, yielding them as join matches. 
        
               /// 
        
               /// Because hash-tables exhibit on average O(1) lookup, we turn what would have been 
        
               /// an O(n*m) algorithm -- in the case of nested loops joins -- into an O(n) algorithm. 
        
               /// We of course require some additional storage to do so, but in general this pays. 
        
               /// </summary> 
        
               /// <typeparam name="TLeftInput"></typeparam> 
        
               /// <typeparam name="TRightInput"></typeparam> 
        
               /// <typeparam name="TKey"></typeparam> 
        
               /// <typeparam name="TOutput"></typeparam> 
        
               internal sealed class JoinQueryOperator<TLeftInput, TRightInput, TKey, TOutput> : BinaryQueryOperator<TLeftInput, TRightInput, TOutput> 
        
               { 
        
                   private readonly Func<TLeftInput, TKey> _leftKeySelector; // The key selection routine for the outer (left) data source. 
        
                   private readonly Func<TRightInput, TKey> _rightKeySelector; // The key selection routine for the inner (right) data source. 
        
                   private readonly Func<TLeftInput, TRightInput, TOutput> _resultSelector; // The result selection routine. 
        
                   private readonly IEqualityComparer<TKey>? _keyComparer; // An optional key comparison object. 
        
                   //--------------------------------------------------------------------------------------- 
        
                   // Constructs a new join operator. 
        
                   // 
        
                   internal JoinQueryOperator(ParallelQuery<TLeftInput> left, ParallelQuery<TRightInput> right, 
        
                                              Func<TLeftInput, TKey> leftKeySelector, 
        
                                              Func<TRightInput, TKey> rightKeySelector, 
        
                                              Func<TLeftInput, TRightInput, TOutput> resultSelector, 
        
                                              IEqualityComparer<TKey>? keyComparer) 
        
                       : base(left, right) 
        
                   { 
        
                       Debug.Assert(left != null && right != null, "child data sources cannot be null"); 
        
                       Debug.Assert(leftKeySelector != null, "left key selector must not be null"); 
        
                       Debug.Assert(rightKeySelector != null, "right key selector must not be null"); 
        
                       Debug.Assert(resultSelector != null, "need a result selector function"); 
        
                       _leftKeySelector = leftKeySelector; 
        
                       _rightKeySelector = rightKeySelector; 
        
                       _resultSelector = resultSelector; 
        
                       _keyComparer = keyComparer; 
        
                       _outputOrdered = LeftChild.OutputOrdered; 
        
                       SetOrdinalIndex(OrdinalIndexState.Shuffled); 
        
                   } 
        
                   public override void WrapPartitionedStream<TLeftKey, TRightKey>( 
        
                       PartitionedStream<TLeftInput, TLeftKey> leftStream, PartitionedStream<TRightInput, TRightKey> rightStream, 
        
                       IPartitionedStreamRecipient<TOutput> outputRecipient, bool preferStriping, QuerySettings settings) 
        
                   { 
        
                       Debug.Assert(rightStream.PartitionCount == leftStream.PartitionCount); 
        
                       if (LeftChild.OutputOrdered) 
        
                       { 
        
                           if (ExchangeUtilities.IsWorseThan(LeftChild.OrdinalIndexState, OrdinalIndexState.Increasing)) 
        
                           { 
        
                               PartitionedStream<TLeftInput, int> leftStreamInt = 
        
                                   QueryOperator<TLeftInput>.ExecuteAndCollectResults(leftStream, leftStream.PartitionCount, OutputOrdered, preferStriping, settings) 
        
                                   .GetPartitionedStream(); 
        
                               WrapPartitionedStreamHelper<int, TRightKey>( 
        
                                   ExchangeUtilities.HashRepartitionOrdered(leftStreamInt, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken), 
        
                                   rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); 
        
                           } 
        
                           else 
        
                           { 
        
                               WrapPartitionedStreamHelper<TLeftKey, TRightKey>( 
        
                                   ExchangeUtilities.HashRepartitionOrdered(leftStream, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken), 
        
                                   rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); 
        
                           } 
        
                       } 
        
                       else 
        
                       { 
        
                           WrapPartitionedStreamHelper<int, TRightKey>( 
        
                               ExchangeUtilities.HashRepartition(leftStream, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken), 
        
                               rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); 
        
                       } 
        
                   } 
        
                   //--------------------------------------------------------------------------------------- 
        
                   // This is a helper method. WrapPartitionedStream decides what type TLeftKey is going 
        
                   // to be, and then call this method with that key as a generic parameter. 
        
                   // 
        
                   private void WrapPartitionedStreamHelper<TLeftKey, TRightKey>( 
        
                       PartitionedStream<Pair<TLeftInput, TKey>, TLeftKey> leftHashStream, PartitionedStream<TRightInput, TRightKey> rightPartitionedStream, 
        
                       IPartitionedStreamRecipient<TOutput> outputRecipient, CancellationToken cancellationToken) 
        
                   { 
        
                       if (RightChild.OutputOrdered && LeftChild.OutputOrdered) 
        
                       { 
        
                           PairOutputKeyBuilder<TLeftKey, TRightKey> outputKeyBuilder = new PairOutputKeyBuilder<TLeftKey, TRightKey>(); 
        
                           IComparer<Pair<TLeftKey, TRightKey>> outputKeyComparer = 
        
                               new PairComparer<TLeftKey, TRightKey>(leftHashStream.KeyComparer, rightPartitionedStream.KeyComparer); 
        
                           WrapPartitionedStreamHelper<TLeftKey, TRightKey, Pair<TLeftKey, TRightKey>>(leftHashStream, 
        
                               ExchangeUtilities.HashRepartitionOrdered(rightPartitionedStream, _rightKeySelector, _keyComparer, null, cancellationToken), 
        
                               outputKeyBuilder, outputKeyComparer, outputRecipient, cancellationToken); 
        
                       } 
        
                       else 
        
                       { 
        
                           LeftKeyOutputKeyBuilder<TLeftKey, int> outputKeyBuilder = new LeftKeyOutputKeyBuilder<TLeftKey, int>(); 
        
                           WrapPartitionedStreamHelper<TLeftKey, int, TLeftKey>(leftHashStream, 
        
                               ExchangeUtilities.HashRepartition(rightPartitionedStream, _rightKeySelector, _keyComparer, null, cancellationToken), 
        
                               outputKeyBuilder, leftHashStream.KeyComparer, outputRecipient, cancellationToken); 
        
                       } 
        
                   } 
        
                   private void WrapPartitionedStreamHelper<TLeftKey, TRightKey, TOutputKey>( 
        
                       PartitionedStream<Pair<TLeftInput, TKey>, TLeftKey> leftHashStream, PartitionedStream<Pair<TRightInput, TKey>, TRightKey> rightHashStream, 
        
                       HashJoinOutputKeyBuilder<TLeftKey, TRightKey, TOutputKey> outputKeyBuilder, IComparer<TOutputKey> outputKeyComparer, 
        
                       IPartitionedStreamRecipient<TOutput> outputRecipient, CancellationToken cancellationToken) 
        
                   { 
        
                       int partitionCount = leftHashStream.PartitionCount; 
        
                       PartitionedStream<TOutput, TOutputKey> outputStream = 
        
                           new PartitionedStream<TOutput, TOutputKey>(partitionCount, outputKeyComparer, OrdinalIndexState); 
        
                       for (int i = 0; i < partitionCount; i++) 
        
                       { 
        
                           JoinHashLookupBuilder<TRightInput, TRightKey, TKey> rightLookupBuilder = 
        
                               new JoinHashLookupBuilder<TRightInput, TRightKey, TKey>(rightHashStream[i], _keyComparer); 
        
                           outputStream[i] = new HashJoinQueryOperatorEnumerator<TLeftInput, TLeftKey, TRightInput, TRightKey, TKey, TOutput, TOutputKey>( 
        
                               leftHashStream[i], rightLookupBuilder, _resultSelector, outputKeyBuilder, cancellationToken); 
        
                       } 
        
                       outputRecipient.Receive(outputStream); 
        
                   } 
        
                   internal override QueryResults<TOutput> Open(QuerySettings settings, bool preferStriping) 
        
                   { 
        
                       QueryResults<TLeftInput> leftResults = LeftChild.Open(settings, false); 
        
                       QueryResults<TRightInput> rightResults = RightChild.Open(settings, false); 
        
                       return new BinaryQueryOperatorResults(leftResults, rightResults, this, settings, false); 
        
                   } 
        
                   //--------------------------------------------------------------------------------------- 
        
                   // Returns an enumerable that represents the query executing sequentially. 
        
                   // 
        
                   internal override IEnumerable<TOutput> AsSequentialQuery(CancellationToken token) 
        
                   { 
        
                       IEnumerable<TLeftInput> wrappedLeftChild = CancellableEnumerable.Wrap(LeftChild.AsSequentialQuery(token), token); 
        
                       IEnumerable<TRightInput> wrappedRightChild = CancellableEnumerable.Wrap(RightChild.AsSequentialQuery(token), token); 
        
                       return wrappedLeftChild.Join( 
        
                           wrappedRightChild, _leftKeySelector, _rightKeySelector, _resultSelector, _keyComparer); 
        
                   } 
        
                   //--------------------------------------------------------------------------------------- 
        
                   // Whether this operator performs a premature merge that would not be performed in 
        
                   // a similar sequential operation (i.e., in LINQ to Objects). 
        
                   // 
        
                   internal override bool LimitsParallelism 
        
                   { 
        
                       get { return false; } 
        
                   } 
        
               } 
        
               /// <summary> 
        
               /// Class to build a HashJoinHashLookup of right elements for use in Join operations. 
        
               /// </summary> 
        
               /// <typeparam name="TElement"></typeparam> 
        
               /// <typeparam name="TOrderKey"></typeparam> 
        
               /// <typeparam name="THashKey"></typeparam> 
        
               internal sealed class JoinHashLookupBuilder<TElement, TOrderKey, THashKey> : HashLookupBuilder<TElement, TOrderKey, THashKey> 
        
               { 
        
                   private readonly QueryOperatorEnumerator<Pair<TElement, THashKey>, TOrderKey> _dataSource; // data source. For building. 
        
                   private readonly IEqualityComparer<THashKey>? _keyComparer; // An optional key comparison object. 
        
                   internal JoinHashLookupBuilder(QueryOperatorEnumerator<Pair<TElement, THashKey>, TOrderKey> dataSource, IEqualityComparer<THashKey>? keyComparer) 
        
                   { 
        
                       Debug.Assert(dataSource != null); 
        
                       _dataSource = dataSource; 
        
                       _keyComparer = keyComparer; 
        
                   } 
        
                   public override HashJoinHashLookup<THashKey, TElement, TOrderKey> BuildHashLookup(CancellationToken cancellationToken) 
        
                   { 
        
                       HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> lookup = 
        
                           new HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>>(_keyComparer); 
        
                       JoinBaseHashBuilder baseHashBuilder = new JoinBaseHashBuilder(lookup); 
        
                       BuildBaseHashLookup(_dataSource, baseHashBuilder, cancellationToken); 
        
                       return new JoinHashLookup(lookup); 
        
                   } 
        
                   protected override void Dispose(bool disposing) 
        
                   { 
        
                       Debug.Assert(_dataSource != null); 
        
                       _dataSource.Dispose(); 
        
                   } 
        
                   /// <summary> 
        
                   /// Adds TElement,TOrderKey values to a HashLookup of HashLookupValueLists. 
        
                   /// </summary> 
        
                   private readonly struct JoinBaseHashBuilder : IBaseHashBuilder<TElement, TOrderKey> 
        
                   { 
        
                       private readonly HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> _base; 
        
                       public JoinBaseHashBuilder(HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> baseLookup) 
        
                       { 
        
                           Debug.Assert(baseLookup != null); 
        
                           _base = baseLookup; 
        
                       } 
        
                       public bool Add(THashKey hashKey, TElement element, TOrderKey orderKey) 
        
                       { 
        
                           HashLookupValueList<TElement, TOrderKey> currentValue = default(HashLookupValueList<TElement, TOrderKey>); 
        
                           if (!_base.TryGetValue(hashKey, ref currentValue)) 
        
                           { 
        
                               currentValue = new HashLookupValueList<TElement, TOrderKey>(element, orderKey); 
        
                               _base.Add(hashKey, currentValue); 
        
                               return false; 
        
                           } 
        
                           else 
        
                           { 
        
                               if (currentValue.Add(element, orderKey)) 
        
                               { 
        
                                   // We need to re-store this element because the pair is a value type. 
        
                                   _base[hashKey] = currentValue; 
        
                               } 
        
                               return true; 
        
                           } 
        
                       } 
        
                   } 
        
                   /// <summary> 
        
                   /// A wrapper for the HashLookup returned by JoinHashLookupBuilder. 
        
                   /// 
        
                   /// Since Join operations do not require a default, this just passes the call on to the base lookup. 
        
                   /// </summary> 
        
                   private sealed class JoinHashLookup : HashJoinHashLookup<THashKey, TElement, TOrderKey> 
        
                   { 
        
                       private readonly HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> _base; 
        
                       internal JoinHashLookup(HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> baseLookup) 
        
                       { 
        
                           Debug.Assert(baseLookup != null); 
        
                           _base = baseLookup; 
        
                       } 
        
                       public override bool TryGetValue(THashKey key, ref HashLookupValueList<TElement, TOrderKey> value) 
        
                       { 
        
                           return _base.TryGetValue(key, ref value); 
        
                       } 
        
                   } 
        
               } 
        
           }

Point taken :) Maybe we can have a common implementation with a flag/enum that determines left vs. inner... If that works..

@Mr0N I'm very unclear on what it is you're asking for there, some usage examples may help clarify.

It seems that the LeftJoin interface was meant to work like in this method. In SQL, for example, you don’t have to first select the fields to compare and then compare them separately; you can directly select the fields and compare them in one function. This results in the join of two tables, which can’t be changed. In the interface above, you first need to choose the fields to join, and then in a separate function, you compare those fields, which doesn’t seem very logical, because it could be done in one function.

select * from tab as t
left join jTab as j on t.id = j.id -- function

You can reduce the entire LeftJoin method interface from three functions to one.

var result = tab.LeftJoin(jTab,a=>a.join.id==a.input.id);

Well, it's not that easy to implement so that with the help of a single function two collections can be joined using Func<JoinTypeInput<TInput, TJoin>, bool>. Essentially, the information from this function is quite sufficient to join the two collections. The function returns true or false, meaning whether the two elements are equal or not.

var result = tab.LeftJoin(jTab,a=>a.join.id==a.input.id);

Both the existing Join() operator and the proposed new LeftJoin() operator represent equijoin operations only; while SQL allows you to join over any expression function (e.g. SELECT * FROM a JOIN b ON b.x > a.y). This is a very intentional design: since only equality is supported, the internal implementation constructs a lookup table for the keys of the inner collection, and then loops over the outer collection, performing hash lookups. This is known in SQL databases as a "hash join", and is generally a much more efficient joining strategy than simply looping over all the inner elements for each outer element (that's known as a "nested loop join").

In other words, the fact that LINQ Join and LeftJoin are constrained to equijoins only - and their signatures look the way they do - allows them to perform much, much better than if they accepted an arbitrary bool-returning lambda, as in your example.

By the way, SQL works the same way: the database can perform hash joins for equijoins, but the moment you use a non-equality operator in your join condition, that join strategy cannot be used, and you may end up with a far slower implementation (though what exactly happens varies).

We could consider introducing an additional overload, which looks like what you propose (i.e. accepts a bool-returning lambda). This would unrelated to this LeftJoin proposal, since we'd also do it for Join and GroupJoin; it would also probably be quite a pit of failure, as users would be tempted to use it and get much worse performance compared to the existing overloads.

I would like contributing to the implementation of these new LINQ operators.
Tell me if you would accept a PR for this.

@manandre

@manandre that's appreciated, but I have a PR mostly already ready (I did the work so that I could benchmark - mostly tests and cleanup remain)...

C# query syntax proposal: dotnet/csharplang#8892

Implement LINQ LeftJoin and RightJoin

Implement LINQ LeftJoin and RightJoin (#110872)

Might be a bit too late given this is closed already, but anyways:

Based on myself complementing and using (streaming) join operators in a fair number of prod apps for a whole while , my personal experience is that the default value for value types is a big pain point, and in retrospect my biggest regret in how I defined the first iteration of these operators (whichever was essentially the same as in this proposal).

In particular, I probably misunderstand, but I didn't quite follow this:

However, it seems that cases where the distinction between "not found" and "found but default" matters are especially rare for joining; the inner key selector would have to accept a null/default inner and "extract" a key out of that (matching the outer key); not impossible, but definitely feels contrived. It's also possible to work around the ambiguity (in some cases) by switching to a nullable value type.

By definition of a left joins, you would invoke the result selector as long as there is an element from the outer sequence, even if no element from the inner sequence matches this value at all. Ie

new int[] {1).LeftJoin(new int[0], x=>x, x=>x, (outer, inner) => outer+inner

Would surely produce the result 1, without the inner key selector being invoked at all - yet the result selector being invoked, but unable to tell if "inner" is 0 because of a genuine 0 value in the sequence, or whether that's a missing value.

Personally, these days I favor either an optional type for the inner type, or different overloads for where T:class vs where T:null, with the latter then working with Nullable of T - though I guess that might not be possible for linq.

The proposed alternative of transforming the input sequence to some optional type works as well of course. But performance considerations aside, this puts the burden on the caller (developer) to realise default(T) may need special consideration (I've seen way too many bugs even in sophisticated code bases surrounding nullability of unconstrained generics!). Whereas an explicit formulation of optionality virtually forces the caller to differentiate between genuine default(T) and truly missing values.

Separately, it might also be worth a thought whether the join key should be passed as an argument into the result selector, so it doesn't need to be recalculated if needed

@fabianoliver

@fabianoliver note that this was discussed at length, both in the original proposal above (including alternative API shapes), and in the API review (see video).

The main point here (as previously discussed), is that in a great many cases (probably the vast majority), the distinction simply isn't necessary. Join (and LeftJoin/RightJoin) are very commonly used on sequences of (non-nullable) classes, with the join key being a property on them; in these scenarios, receiving a null inner in the result selector is an unambiguous indication that no correlated inner could be found.

So this would be a matter of making the complicated API more complex/less usable for the vast majority of usages (where the distinction doesn't matter), so that in the (small) minority of cases where the distinction does matter, it would be more difficult to get wrong. I think that's the wrong tradeoff, especially given that a good workaround does exist for those cases (make the input sequence optional).

Besides, although I agree the C# situation around unconstrained generic nullability isn't ideal, this is the way that existing LINQ operators (and various other non-LINQ functions) work; for example, DefaultIfEmpty has the exact same behavior.

or different overloads for where T:class vs where T:null

I'm not sure this is what you're proposing, but having two LeftJoin overloads where the only difference between them is the resultSelector argument acceping a Nullable<T> instead of a T would cause difficulties for type inference and Intellisense. It would again degrade the common-case experience for an edge case which most people shouldn't need to care about.

Separately, it might also be worth a thought whether the join key should be passed as an argument into the result selector, so it doesn't need to be recalculated if needed

What would be the use-case for this? There's no such thing for the regular, already-existing Join operator (whose example LeftJoin/RightJoin follow) , and I'm not aware of any user requests for this...

Issue tracking LINQ support for full outer join: #124787

Navigation Menu

Repository navigation

[API Proposal]: Introduce LeftJoin LINQ operator #110292

Background and motivation

Background

Proposal

Additional Notes

API Proposal

API Usage

Value types and alternative LeftJoin API shapes

Previous related issues

31 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	private static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey>? comparer)
	{
	using (IEnumerator<TOuter> e = outer.GetEnumerator())
	{
	if (e.MoveNext())
	{
	Lookup<TKey, TInner> lookup = Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
	if (lookup.Count != 0)
	{
	do
	{
	TOuter item = e.Current;
	Grouping<TKey, TInner>? g = lookup.GetGrouping(outerKeySelector(item), create: false);
	if (g is not null)
	{
	int count = g._count;
	TInner[] elements = g._elements;
	for (int i = 0; i != count; ++i)
	{
	yield return resultSelector(item, elements[i]);
	}
	}
	}
	while (e.MoveNext());
	}
	}
	}

	/// <summary>
	/// A join operator takes a left query tree and a right query tree, and then yields the
	/// matching pairs between the two. LINQ supports equi-key-based joins. Hence, a key-
	/// selection function for the left and right data types will yield keys of the same
	/// type for both. We then merely have to match elements from the left with elements from
	/// the right that have the same exact key. Note that this is an inner join. In other
	/// words, outer elements with no matching inner elements do not appear in the output.
	///
	/// Hash-joins work in two phases:
	///
	/// (1) Building - we build a hash-table from one of the data sources. In the case
	/// of this specific operator, the table is built from the hash-codes of
	/// keys selected via the key selector function. Because elements may share
	/// the same key, the table must support one-key-to-many-values.
	/// (2) Probing - for each element in the data source not used for building, we
	/// use its key to look into the hash-table. If we find elements under this
	/// key, we just enumerate all of them, yielding them as join matches.
	///
	/// Because hash-tables exhibit on average O(1) lookup, we turn what would have been
	/// an O(n*m) algorithm -- in the case of nested loops joins -- into an O(n) algorithm.
	/// We of course require some additional storage to do so, but in general this pays.
	/// </summary>
	/// <typeparam name="TLeftInput"></typeparam>
	/// <typeparam name="TRightInput"></typeparam>
	/// <typeparam name="TKey"></typeparam>
	/// <typeparam name="TOutput"></typeparam>
	internal sealed class JoinQueryOperator<TLeftInput, TRightInput, TKey, TOutput> : BinaryQueryOperator<TLeftInput, TRightInput, TOutput>
	{
	private readonly Func<TLeftInput, TKey> _leftKeySelector; // The key selection routine for the outer (left) data source.
	private readonly Func<TRightInput, TKey> _rightKeySelector; // The key selection routine for the inner (right) data source.
	private readonly Func<TLeftInput, TRightInput, TOutput> _resultSelector; // The result selection routine.
	private readonly IEqualityComparer<TKey>? _keyComparer; // An optional key comparison object.

	//---------------------------------------------------------------------------------------
	// Constructs a new join operator.
	//

	internal JoinQueryOperator(ParallelQuery<TLeftInput> left, ParallelQuery<TRightInput> right,
	Func<TLeftInput, TKey> leftKeySelector,
	Func<TRightInput, TKey> rightKeySelector,
	Func<TLeftInput, TRightInput, TOutput> resultSelector,
	IEqualityComparer<TKey>? keyComparer)
	: base(left, right)
	{
	Debug.Assert(left != null && right != null, "child data sources cannot be null");
	Debug.Assert(leftKeySelector != null, "left key selector must not be null");
	Debug.Assert(rightKeySelector != null, "right key selector must not be null");
	Debug.Assert(resultSelector != null, "need a result selector function");

	_leftKeySelector = leftKeySelector;
	_rightKeySelector = rightKeySelector;
	_resultSelector = resultSelector;
	_keyComparer = keyComparer;
	_outputOrdered = LeftChild.OutputOrdered;

	SetOrdinalIndex(OrdinalIndexState.Shuffled);
	}

	public override void WrapPartitionedStream<TLeftKey, TRightKey>(
	PartitionedStream<TLeftInput, TLeftKey> leftStream, PartitionedStream<TRightInput, TRightKey> rightStream,
	IPartitionedStreamRecipient<TOutput> outputRecipient, bool preferStriping, QuerySettings settings)
	{
	Debug.Assert(rightStream.PartitionCount == leftStream.PartitionCount);

	if (LeftChild.OutputOrdered)
	{
	if (ExchangeUtilities.IsWorseThan(LeftChild.OrdinalIndexState, OrdinalIndexState.Increasing))
	{
	PartitionedStream<TLeftInput, int> leftStreamInt =
	QueryOperator<TLeftInput>.ExecuteAndCollectResults(leftStream, leftStream.PartitionCount, OutputOrdered, preferStriping, settings)
	.GetPartitionedStream();
	WrapPartitionedStreamHelper<int, TRightKey>(
	ExchangeUtilities.HashRepartitionOrdered(leftStreamInt, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken),
	rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken);
	}
	else
	{
	WrapPartitionedStreamHelper<TLeftKey, TRightKey>(
	ExchangeUtilities.HashRepartitionOrdered(leftStream, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken),
	rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken);
	}
	}
	else
	{
	WrapPartitionedStreamHelper<int, TRightKey>(
	ExchangeUtilities.HashRepartition(leftStream, _leftKeySelector, _keyComparer, null, settings.CancellationState.MergedCancellationToken),
	rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken);
	}
	}

	//---------------------------------------------------------------------------------------
	// This is a helper method. WrapPartitionedStream decides what type TLeftKey is going
	// to be, and then call this method with that key as a generic parameter.
	//

	private void WrapPartitionedStreamHelper<TLeftKey, TRightKey>(
	PartitionedStream<Pair<TLeftInput, TKey>, TLeftKey> leftHashStream, PartitionedStream<TRightInput, TRightKey> rightPartitionedStream,
	IPartitionedStreamRecipient<TOutput> outputRecipient, CancellationToken cancellationToken)
	{
	if (RightChild.OutputOrdered && LeftChild.OutputOrdered)
	{
	PairOutputKeyBuilder<TLeftKey, TRightKey> outputKeyBuilder = new PairOutputKeyBuilder<TLeftKey, TRightKey>();
	IComparer<Pair<TLeftKey, TRightKey>> outputKeyComparer =
	new PairComparer<TLeftKey, TRightKey>(leftHashStream.KeyComparer, rightPartitionedStream.KeyComparer);

	WrapPartitionedStreamHelper<TLeftKey, TRightKey, Pair<TLeftKey, TRightKey>>(leftHashStream,
	ExchangeUtilities.HashRepartitionOrdered(rightPartitionedStream, _rightKeySelector, _keyComparer, null, cancellationToken),
	outputKeyBuilder, outputKeyComparer, outputRecipient, cancellationToken);
	}
	else
	{
	LeftKeyOutputKeyBuilder<TLeftKey, int> outputKeyBuilder = new LeftKeyOutputKeyBuilder<TLeftKey, int>();

	WrapPartitionedStreamHelper<TLeftKey, int, TLeftKey>(leftHashStream,
	ExchangeUtilities.HashRepartition(rightPartitionedStream, _rightKeySelector, _keyComparer, null, cancellationToken),
	outputKeyBuilder, leftHashStream.KeyComparer, outputRecipient, cancellationToken);
	}
	}

	private void WrapPartitionedStreamHelper<TLeftKey, TRightKey, TOutputKey>(
	PartitionedStream<Pair<TLeftInput, TKey>, TLeftKey> leftHashStream, PartitionedStream<Pair<TRightInput, TKey>, TRightKey> rightHashStream,
	HashJoinOutputKeyBuilder<TLeftKey, TRightKey, TOutputKey> outputKeyBuilder, IComparer<TOutputKey> outputKeyComparer,
	IPartitionedStreamRecipient<TOutput> outputRecipient, CancellationToken cancellationToken)
	{
	int partitionCount = leftHashStream.PartitionCount;

	PartitionedStream<TOutput, TOutputKey> outputStream =
	new PartitionedStream<TOutput, TOutputKey>(partitionCount, outputKeyComparer, OrdinalIndexState);

	for (int i = 0; i < partitionCount; i++)
	{
	JoinHashLookupBuilder<TRightInput, TRightKey, TKey> rightLookupBuilder =
	new JoinHashLookupBuilder<TRightInput, TRightKey, TKey>(rightHashStream[i], _keyComparer);
	outputStream[i] = new HashJoinQueryOperatorEnumerator<TLeftInput, TLeftKey, TRightInput, TRightKey, TKey, TOutput, TOutputKey>(
	leftHashStream[i], rightLookupBuilder, _resultSelector, outputKeyBuilder, cancellationToken);
	}

	outputRecipient.Receive(outputStream);
	}

	internal override QueryResults<TOutput> Open(QuerySettings settings, bool preferStriping)
	{
	QueryResults<TLeftInput> leftResults = LeftChild.Open(settings, false);
	QueryResults<TRightInput> rightResults = RightChild.Open(settings, false);

	return new BinaryQueryOperatorResults(leftResults, rightResults, this, settings, false);
	}

	//---------------------------------------------------------------------------------------
	// Returns an enumerable that represents the query executing sequentially.
	//

	internal override IEnumerable<TOutput> AsSequentialQuery(CancellationToken token)
	{
	IEnumerable<TLeftInput> wrappedLeftChild = CancellableEnumerable.Wrap(LeftChild.AsSequentialQuery(token), token);
	IEnumerable<TRightInput> wrappedRightChild = CancellableEnumerable.Wrap(RightChild.AsSequentialQuery(token), token);

	return wrappedLeftChild.Join(
	wrappedRightChild, _leftKeySelector, _rightKeySelector, _resultSelector, _keyComparer);
	}

	//---------------------------------------------------------------------------------------
	// Whether this operator performs a premature merge that would not be performed in
	// a similar sequential operation (i.e., in LINQ to Objects).
	//

	internal override bool LimitsParallelism
	{
	get { return false; }
	}
	}

	/// <summary>
	/// Class to build a HashJoinHashLookup of right elements for use in Join operations.
	/// </summary>
	/// <typeparam name="TElement"></typeparam>
	/// <typeparam name="TOrderKey"></typeparam>
	/// <typeparam name="THashKey"></typeparam>
	internal sealed class JoinHashLookupBuilder<TElement, TOrderKey, THashKey> : HashLookupBuilder<TElement, TOrderKey, THashKey>
	{
	private readonly QueryOperatorEnumerator<Pair<TElement, THashKey>, TOrderKey> _dataSource; // data source. For building.
	private readonly IEqualityComparer<THashKey>? _keyComparer; // An optional key comparison object.

	internal JoinHashLookupBuilder(QueryOperatorEnumerator<Pair<TElement, THashKey>, TOrderKey> dataSource, IEqualityComparer<THashKey>? keyComparer)
	{
	Debug.Assert(dataSource != null);

	_dataSource = dataSource;
	_keyComparer = keyComparer;
	}

	public override HashJoinHashLookup<THashKey, TElement, TOrderKey> BuildHashLookup(CancellationToken cancellationToken)
	{
	HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> lookup =
	new HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>>(_keyComparer);
	JoinBaseHashBuilder baseHashBuilder = new JoinBaseHashBuilder(lookup);

	BuildBaseHashLookup(_dataSource, baseHashBuilder, cancellationToken);

	return new JoinHashLookup(lookup);
	}

	protected override void Dispose(bool disposing)
	{
	Debug.Assert(_dataSource != null);

	_dataSource.Dispose();
	}

	/// <summary>
	/// Adds TElement,TOrderKey values to a HashLookup of HashLookupValueLists.
	/// </summary>
	private readonly struct JoinBaseHashBuilder : IBaseHashBuilder<TElement, TOrderKey>
	{
	private readonly HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> _base;

	public JoinBaseHashBuilder(HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> baseLookup)
	{
	Debug.Assert(baseLookup != null);

	_base = baseLookup;
	}

	public bool Add(THashKey hashKey, TElement element, TOrderKey orderKey)
	{
	HashLookupValueList<TElement, TOrderKey> currentValue = default(HashLookupValueList<TElement, TOrderKey>);
	if (!_base.TryGetValue(hashKey, ref currentValue))
	{
	currentValue = new HashLookupValueList<TElement, TOrderKey>(element, orderKey);
	_base.Add(hashKey, currentValue);
	return false;
	}
	else
	{
	if (currentValue.Add(element, orderKey))
	{
	// We need to re-store this element because the pair is a value type.
	_base[hashKey] = currentValue;
	}
	return true;
	}
	}
	}

	/// <summary>
	/// A wrapper for the HashLookup returned by JoinHashLookupBuilder.
	///
	/// Since Join operations do not require a default, this just passes the call on to the base lookup.
	/// </summary>
	private sealed class JoinHashLookup : HashJoinHashLookup<THashKey, TElement, TOrderKey>
	{
	private readonly HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> _base;

	internal JoinHashLookup(HashLookup<THashKey, HashLookupValueList<TElement, TOrderKey>> baseLookup)
	{
	Debug.Assert(baseLookup != null);

	_base = baseLookup;
	}

	public override bool TryGetValue(THashKey key, ref HashLookupValueList<TElement, TOrderKey> value)
	{
	return _base.TryGetValue(key, ref value);
	}
	}
	}
	}

[API Proposal]: Introduce LeftJoin LINQ operator #110292

Description

Background and motivation

Background

Proposal

Additional Notes

API Proposal

API Usage

Value types and alternative LeftJoin API shapes

Previous related issues

Activity

dotnet-policy-service commented on Dec 1, 2024

jeffhandley commented on Dec 1, 2024

Clockwork-Muse commented on Dec 2, 2024

stephentoub commented on Dec 2, 2024

roji commented on Dec 2, 2024

stephentoub commented on Dec 2, 2024

roji commented on Dec 2, 2024

31 remaining items

Mr0N commented on Dec 14, 2024

Mr0N commented on Dec 14, 2024

roji commented on Dec 14, 2024

manandre commented on Dec 14, 2024

roji commented on Dec 15, 2024

roji commented on Dec 15, 2024

fabianoliver commented on Jan 21, 2025

roji commented on Jan 22, 2025

roji commented on Feb 24, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions