LINQ - Jointure externe complète

Question

J'ai une liste d'identifiants de personnes et de leur prénom, et une liste d'identifiants de personnes et de leur nom de famille. Certaines personnes n'ont pas de prénom et d'autres n'ont pas de nom de famille ; j'aimerais faire une jointure externe complète sur les deux listes.

Donc les listes suivantes :

ID  FirstName
--  ---------
 1  John
 2  Sue

ID  LastName
--  --------
 1  Doe
 3  Smith

Devrait produire :

ID  FirstName  LastName
--  ---------  --------
 1  John       Doe
 2  Sue
 3             Smith

Je suis nouveau dans le domaine de LINQ (donc pardonnez-moi si je suis nul) et j'ai trouvé plusieurs solutions pour les "LINQ Outer Joins" qui se ressemblent toutes, mais qui semblent être des jointures externes gauches.

Mes tentatives jusqu'à présent ressemblent à ceci :

private void OuterJoinTest()
{
    List<FirstName> firstNames = new List<FirstName>();
    firstNames.Add(new FirstName { ID = 1, Name = "John" });
    firstNames.Add(new FirstName { ID = 2, Name = "Sue" });

    List<LastName> lastNames = new List<LastName>();
    lastNames.Add(new LastName { ID = 1, Name = "Doe" });
    lastNames.Add(new LastName { ID = 3, Name = "Smith" });

    var outerJoin = from first in firstNames
        join last in lastNames
        on first.ID equals last.ID
        into temp
        from last in temp.DefaultIfEmpty()
        select new
        {
            id = first != null ? first.ID : last.ID,
            firstname = first != null ? first.Name : string.Empty,
            surname = last != null ? last.Name : string.Empty
        };
    }
}

public class FirstName
{
    public int ID;

    public string Name;
}

public class LastName
{
    public int ID;

    public string Name;
}

Mais ceci revient :

ID  FirstName  LastName
--  ---------  --------
 1  John       Doe
 2  Sue

Qu'est-ce que je fais de mal ?

Answer 1

Mise à jour 1 : fournir une méthode d'extension réellement généralisée FullOuterJoin
Mise à jour 2 : acceptation facultative d'un IEqualityComparer pour le type de clé
Mise à jour 3 Cette mise en œuvre a pour cette cette mise en œuvre a récemment fait partie de MoreLinq - Merci les gars !

Modifier Ajouté FullOuterGroupJoin ( idéone ). J'ai réutilisé le GetOuter<> ce qui le rend un peu moins performant qu'il ne pourrait l'être, mais je vise un code "de haut niveau", pas un code optimisé à l'extrême, pour le moment.

Voyez-le en direct sur http://ideone.com/O36nWc

static void Main(string[] args)
{
    var ax = new[] { 
        new { id = 1, name = "John" },
        new { id = 2, name = "Sue" } };
    var bx = new[] { 
        new { id = 1, surname = "Doe" },
        new { id = 3, surname = "Smith" } };

    ax.FullOuterJoin(bx, a => a.id, b => b.id, (a, b, id) => new {a, b})
        .ToList().ForEach(Console.WriteLine);
}

Imprime la sortie :

{ a = { id = 1, name = John }, b = { id = 1, surname = Doe } }
{ a = { id = 2, name = Sue }, b =  }
{ a = , b = { id = 3, surname = Smith } }

Vous pouvez également fournir des valeurs par défaut : http://ideone.com/kG4kqO

    ax.FullOuterJoin(
            bx, a => a.id, b => b.id, 
            (a, b, id) => new { a.name, b.surname },
            new { id = -1, name    = "(no firstname)" },
            new { id = -2, surname = "(no surname)" }
        )

Impression :

{ name = John, surname = Doe }
{ name = Sue, surname = (no surname) }
{ name = (no firstname), surname = Smith }

Explication des termes utilisés :

La jonction est un terme emprunté à la conception des bases de données relationnelles :

• A rejoindre répétera les éléments de a autant de fois qu'il y a d'éléments dans b avec la clé correspondante (c'est-à-dire : rien si b étaient vides). Dans le jargon des bases de données, on appelle cela inner (equi)join .
• Un site jointure extérieure comprend des éléments de a pour laquelle aucun élément élément existe dans b . (c'est-à-dire : même résultat si b étaient vides). C'est ce qu'on appelle généralement left join .
• A jointure externe complète comprend les dossiers de a ainsi que b si aucun élément correspondant existe dans l'autre. (c'est-à-dire que même résultat si a étaient vides)

Quelque chose qui n'est pas généralement vu dans les SGBDR est une jointure de groupe [1] :

• A adhésion au groupe fait la même chose que ce qui est décrit ci-dessus, mais au lieu de répéter des éléments de a pour plusieurs correspondants b il groupes les enregistrements avec les clés correspondantes. C'est souvent plus pratique lorsque vous souhaitez énumérer des enregistrements "joints", sur la base d'une clé commune.

Voir aussi GroupJoin qui contient également quelques explications générales sur le contexte.

---

[1] (Je crois que Oracle et MSSQL ont des extensions propriétaires pour cela).

Code complet

Une classe d'extension généralisée pour ce type d'activité.

internal static class MyExtensions
{
    internal static IEnumerable<TResult> FullOuterGroupJoin<TA, TB, TKey, TResult>(
        this IEnumerable<TA> a,
        IEnumerable<TB> b,
        Func<TA, TKey> selectKeyA, 
        Func<TB, TKey> selectKeyB,
        Func<IEnumerable<TA>, IEnumerable<TB>, TKey, TResult> projection,
        IEqualityComparer<TKey> cmp = null)
    {
        cmp = cmp?? EqualityComparer<TKey>.Default;
        var alookup = a.ToLookup(selectKeyA, cmp);
        var blookup = b.ToLookup(selectKeyB, cmp);

        var keys = new HashSet<TKey>(alookup.Select(p => p.Key), cmp);
        keys.UnionWith(blookup.Select(p => p.Key));

        var join = from key in keys
                   let xa = alookup[key]
                   let xb = blookup[key]
                   select projection(xa, xb, key);

        return join;
    }

    internal static IEnumerable<TResult> FullOuterJoin<TA, TB, TKey, TResult>(
        this IEnumerable<TA> a,
        IEnumerable<TB> b,
        Func<TA, TKey> selectKeyA, 
        Func<TB, TKey> selectKeyB,
        Func<TA, TB, TKey, TResult> projection,
        TA defaultA = default(TA), 
        TB defaultB = default(TB),
        IEqualityComparer<TKey> cmp = null)
    {
        cmp = cmp?? EqualityComparer<TKey>.Default;
        var alookup = a.ToLookup(selectKeyA, cmp);
        var blookup = b.ToLookup(selectKeyB, cmp);

        var keys = new HashSet<TKey>(alookup.Select(p => p.Key), cmp);
        keys.UnionWith(blookup.Select(p => p.Key));

        var join = from key in keys
                   from xa in alookup[key].DefaultIfEmpty(defaultA)
                   from xb in blookup[key].DefaultIfEmpty(defaultB)
                   select projection(xa, xb, key);

        return join;
    }
}

Answer 2

Je ne sais pas si cela couvre tous les cas, mais logiquement cela semble correct. L'idée est de faire une jointure externe gauche et une jointure externe droite, puis de faire l'union des résultats.

var firstNames = new[]
{
    new { ID = 1, Name = "John" },
    new { ID = 2, Name = "Sue" },
};
var lastNames = new[]
{
    new { ID = 1, Name = "Doe" },
    new { ID = 3, Name = "Smith" },
};
var leftOuterJoin =
    from first in firstNames
    join last in lastNames on first.ID equals last.ID into temp
    from last in temp.DefaultIfEmpty()
    select new
    {
        first.ID,
        FirstName = first.Name,
        LastName = last?.Name,
    };
var rightOuterJoin =
    from last in lastNames
    join first in firstNames on last.ID equals first.ID into temp
    from first in temp.DefaultIfEmpty()
    select new
    {
        last.ID,
        FirstName = first?.Name,
        LastName = last.Name,
    };
var fullOuterJoin = leftOuterJoin.Union(rightOuterJoin);

Cela fonctionne comme écrit puisque c'est dans LINQ to Objects. Si LINQ to SQL ou autre, le processeur de requêtes pourrait ne pas supporter la navigation sûre ou d'autres opérations. Vous devrez utiliser l'opérateur conditionnel pour obtenir les valeurs de manière conditionnelle.

c'est-à-dire,

var leftOuterJoin =
    from first in firstNames
    join last in lastNames on first.ID equals last.ID into temp
    from last in temp.DefaultIfEmpty()
    select new
    {
        first.ID,
        FirstName = first.Name,
        LastName = last != null ? last.Name : default,
    };

Answer 3

Je pense qu'il y a des problèmes avec la plupart d'entre elles, y compris la réponse acceptée, parce qu'elles ne fonctionnent pas bien avec Linq over IQueryable, soit parce qu'elles font trop d'allers-retours avec le serveur et trop de retours de données, soit parce qu'elles font trop d'exécution par le client.

Pour IEnumerable, je n'aime pas la réponse de Sehe ou similaire, car elle a une utilisation excessive de la mémoire (un simple test de 10000000 deux listes a épuisé la mémoire de Linqpad sur ma machine de 32 Go).

De plus, la plupart des autres n'implémentent pas réellement une jointure externe complète correcte parce qu'ils utilisent une Union avec une jointure droite au lieu d'une Concat avec une jointure droite anti-semi, ce qui élimine non seulement les lignes de jointure interne en double du résultat, mais aussi tous les doubles qui existaient à l'origine dans les données de gauche ou de droite.

Voici donc mes extensions qui gèrent tous ces problèmes, génèrent du SQL ainsi que l'implémentation de la jointure dans LINQ to SQL directement, s'exécutent sur le serveur, et sont plus rapides et avec moins de mémoire que les autres sur les Enumerables :

public static class Ext {
    public static IEnumerable<TResult> LeftOuterJoin<TLeft, TRight, TKey, TResult>(
        this IEnumerable<TLeft> leftItems,
        IEnumerable<TRight> rightItems,
        Func<TLeft, TKey> leftKeySelector,
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector) {

        return from left in leftItems
               join right in rightItems on leftKeySelector(left) equals rightKeySelector(right) into temp
               from right in temp.DefaultIfEmpty()
               select resultSelector(left, right);
    }

    public static IEnumerable<TResult> RightOuterJoin<TLeft, TRight, TKey, TResult>(
        this IEnumerable<TLeft> leftItems,
        IEnumerable<TRight> rightItems,
        Func<TLeft, TKey> leftKeySelector,
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector) {

        return from right in rightItems
               join left in leftItems on rightKeySelector(right) equals leftKeySelector(left) into temp
               from left in temp.DefaultIfEmpty()
               select resultSelector(left, right);
    }

    public static IEnumerable<TResult> FullOuterJoinDistinct<TLeft, TRight, TKey, TResult>(
        this IEnumerable<TLeft> leftItems,
        IEnumerable<TRight> rightItems,
        Func<TLeft, TKey> leftKeySelector,
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector) {

        return leftItems.LeftOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector).Union(leftItems.RightOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector));
    }

    public static IEnumerable<TResult> RightAntiSemiJoin<TLeft, TRight, TKey, TResult>(
        this IEnumerable<TLeft> leftItems,
        IEnumerable<TRight> rightItems,
        Func<TLeft, TKey> leftKeySelector,
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector) {

        var hashLK = new HashSet<TKey>(from l in leftItems select leftKeySelector(l));
        return rightItems.Where(r => !hashLK.Contains(rightKeySelector(r))).Select(r => resultSelector(default(TLeft),r));
    }

    public static IEnumerable<TResult> FullOuterJoin<TLeft, TRight, TKey, TResult>(
        this IEnumerable<TLeft> leftItems,
        IEnumerable<TRight> rightItems,
        Func<TLeft, TKey> leftKeySelector,
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector)  where TLeft : class {

        return leftItems.LeftOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector).Concat(leftItems.RightAntiSemiJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector));
    }

    private static Expression<Func<TP, TC, TResult>> CastSMBody<TP, TC, TResult>(LambdaExpression ex, TP unusedP, TC unusedC, TResult unusedRes) => (Expression<Func<TP, TC, TResult>>)ex;

    public static IQueryable<TResult> LeftOuterJoin<TLeft, TRight, TKey, TResult>(
        this IQueryable<TLeft> leftItems,
        IQueryable<TRight> rightItems,
        Expression<Func<TLeft, TKey>> leftKeySelector,
        Expression<Func<TRight, TKey>> rightKeySelector,
        Expression<Func<TLeft, TRight, TResult>> resultSelector) {

        var sampleAnonLR = new { left = default(TLeft), rightg = default(IEnumerable<TRight>) };
        var parmP = Expression.Parameter(sampleAnonLR.GetType(), "p");
        var parmC = Expression.Parameter(typeof(TRight), "c");
        var argLeft = Expression.PropertyOrField(parmP, "left");
        var newleftrs = CastSMBody(Expression.Lambda(Expression.Invoke(resultSelector, argLeft, parmC), parmP, parmC), sampleAnonLR, default(TRight), default(TResult));

        return leftItems.AsQueryable().GroupJoin(rightItems, leftKeySelector, rightKeySelector, (left, rightg) => new { left, rightg }).SelectMany(r => r.rightg.DefaultIfEmpty(), newleftrs);
    }

    public static IQueryable<TResult> RightOuterJoin<TLeft, TRight, TKey, TResult>(
        this IQueryable<TLeft> leftItems,
        IQueryable<TRight> rightItems,
        Expression<Func<TLeft, TKey>> leftKeySelector,
        Expression<Func<TRight, TKey>> rightKeySelector,
        Expression<Func<TLeft, TRight, TResult>> resultSelector) {

        var sampleAnonLR = new { leftg = default(IEnumerable<TLeft>), right = default(TRight) };
        var parmP = Expression.Parameter(sampleAnonLR.GetType(), "p");
        var parmC = Expression.Parameter(typeof(TLeft), "c");
        var argRight = Expression.PropertyOrField(parmP, "right");
        var newrightrs = CastSMBody(Expression.Lambda(Expression.Invoke(resultSelector, parmC, argRight), parmP, parmC), sampleAnonLR, default(TLeft), default(TResult));

        return rightItems.GroupJoin(leftItems, rightKeySelector, leftKeySelector, (right, leftg) => new { leftg, right }).SelectMany(l => l.leftg.DefaultIfEmpty(), newrightrs);
    }

    public static IQueryable<TResult> FullOuterJoinDistinct<TLeft, TRight, TKey, TResult>(
        this IQueryable<TLeft> leftItems,
        IQueryable<TRight> rightItems,
        Expression<Func<TLeft, TKey>> leftKeySelector,
        Expression<Func<TRight, TKey>> rightKeySelector,
        Expression<Func<TLeft, TRight, TResult>> resultSelector) {

        return leftItems.LeftOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector).Union(leftItems.RightOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector));
    }

    private static Expression<Func<TP, TResult>> CastSBody<TP, TResult>(LambdaExpression ex, TP unusedP, TResult unusedRes) => (Expression<Func<TP, TResult>>)ex;

    public static IQueryable<TResult> RightAntiSemiJoin<TLeft, TRight, TKey, TResult>(
        this IQueryable<TLeft> leftItems,
        IQueryable<TRight> rightItems,
        Expression<Func<TLeft, TKey>> leftKeySelector,
        Expression<Func<TRight, TKey>> rightKeySelector,
        Expression<Func<TLeft, TRight, TResult>> resultSelector) {

        var sampleAnonLgR = new { leftg = default(IEnumerable<TLeft>), right = default(TRight) };
        var parmLgR = Expression.Parameter(sampleAnonLgR.GetType(), "lgr");
        var argLeft = Expression.Constant(default(TLeft), typeof(TLeft));
        var argRight = Expression.PropertyOrField(parmLgR, "right");
        var newrightrs = CastSBody(Expression.Lambda(Expression.Invoke(resultSelector, argLeft, argRight), parmLgR), sampleAnonLgR, default(TResult));

        return rightItems.GroupJoin(leftItems, rightKeySelector, leftKeySelector, (right, leftg) => new { leftg, right }).Where(lgr => !lgr.leftg.Any()).Select(newrightrs);
    }

    public static IQueryable<TResult> FullOuterJoin<TLeft, TRight, TKey, TResult>(
        this IQueryable<TLeft> leftItems,
        IQueryable<TRight> rightItems,
        Expression<Func<TLeft, TKey>> leftKeySelector,
        Expression<Func<TRight, TKey>> rightKeySelector,
        Expression<Func<TLeft, TRight, TResult>> resultSelector) {

        return leftItems.LeftOuterJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector).Concat(leftItems.RightAntiSemiJoin(rightItems, leftKeySelector, rightKeySelector, resultSelector));
    }
}

La différence entre un Anti-Semi-Join droit est principalement sans importance avec Linq to Objects ou dans la source, mais fait une différence du côté du serveur (SQL) dans la réponse finale, en supprimant un élément inutile. JOIN .

Le codage manuel de Expression pour gérer la fusion d'un Expression<Func<>> en un lambda pourrait être amélioré avec LinqKit, mais il serait bien que le langage/compilateur ait ajouté une aide pour cela. Le site FullOuterJoinDistinct y RightOuterJoin sont incluses pour être complètes, mais je n'ai pas réimplémenté les fonctions FullOuterGroupJoin encore.

J'ai écrit une autre version d'une jointure extérieure complète pour IEnumerable pour les cas où la clé est ordonnable, ce qui est environ 50% plus rapide que de combiner la jointure externe gauche avec la semi-jonction anti droite, au moins sur les petites collections. Il parcourt chaque collection après le tri une seule fois.

J'ai également ajouté une autre réponse pour une version qui fonctionne avec EF en remplaçant le Invoke avec une extension personnalisée.

Answer 4

Je suppose que l'approche de @sehe est plus forte, mais jusqu'à ce que je la comprenne mieux, je me retrouve à sauter sur l'extension de @MichaelSander. Je l'ai modifiée pour qu'elle corresponde à la syntaxe et au type de retour de la méthode intégrée Enumerable.Join() décrite ci-dessous. aquí . J'ai ajouté le suffixe "distinct" par rapport au commentaire de @cadrell0 sous la solution de @JeffMercado.

public static class MyExtensions {

    public static IEnumerable<TResult> FullJoinDistinct<TLeft, TRight, TKey, TResult> (
        this IEnumerable<TLeft> leftItems, 
        IEnumerable<TRight> rightItems, 
        Func<TLeft, TKey> leftKeySelector, 
        Func<TRight, TKey> rightKeySelector,
        Func<TLeft, TRight, TResult> resultSelector
    ) {

        var leftJoin = 
            from left in leftItems
            join right in rightItems 
              on leftKeySelector(left) equals rightKeySelector(right) into temp
            from right in temp.DefaultIfEmpty()
            select resultSelector(left, right);

        var rightJoin = 
            from right in rightItems
            join left in leftItems 
              on rightKeySelector(right) equals leftKeySelector(left) into temp
            from left in temp.DefaultIfEmpty()
            select resultSelector(left, right);

        return leftJoin.Union(rightJoin);
    }

}

Dans l'exemple, vous l'utiliserez comme suit :

var test = 
    firstNames
    .FullJoinDistinct(
        lastNames,
        f=> f.ID,
        j=> j.ID,
        (f,j)=> new {
            ID = f == null ? j.ID : f.ID, 
            leftName = f == null ? null : f.Name,
            rightName = j == null ? null : j.Name
        }
    );

À l'avenir, au fur et à mesure que j'apprendrai, j'ai le sentiment que je migrerai vers la logique de @sehe, étant donné sa popularité. Mais même dans ce cas, je devrai être prudent, car je pense qu'il est important d'avoir au moins une surcharge qui correspond à la syntaxe de la méthode ".Join()" existante si possible, pour deux raisons :

1. La cohérence des méthodes permet de gagner du temps, d'éviter les erreurs et d'éviter les comportements involontaires.
2. Si une méthode ".FullJoin()" prête à l'emploi est créée à l'avenir, j'imagine qu'elle essaiera de conserver la syntaxe de la méthode ".Join()" existante si elle le peut. Si c'est le cas, si vous voulez migrer vers cette méthode, vous pouvez simplement renommer vos fonctions sans changer les paramètres ou vous inquiéter du fait que des types de retour différents puissent casser votre code.

Je suis encore novice en matière de génériques, d'extensions, d'instructions Func et d'autres fonctionnalités, et les commentaires sont donc les bienvenus.

EDITAR: Il ne m'a pas fallu longtemps pour réaliser qu'il y avait un problème avec mon code. Je faisais un .Dump() dans LINQPad et je regardais le type de retour. C'était juste IEnumerable, donc j'ai essayé de le faire correspondre. Mais quand j'ai fait un .Where() ou un .Select() sur mon extension, j'ai eu une erreur : "'System Collections.IEnumerable' ne contient pas de définition pour 'Select' et ...". Au final, j'ai pu faire correspondre la syntaxe d'entrée de .Join(), mais pas le comportement de retour.

EDITAR: Ajout de "TResult" au type de retour de la fonction. J'ai manqué cela en lisant l'article de Microsoft, et bien sûr, cela a du sens. Grâce à cette correction, il semble que le comportement de retour soit conforme à mes objectifs après tout.

Answer 5

Voici une méthode d'extension permettant de le faire :

public static IEnumerable<KeyValuePair<TLeft, TRight>> FullOuterJoin<TLeft, TRight>(this IEnumerable<TLeft> leftItems, Func<TLeft, object> leftIdSelector, IEnumerable<TRight> rightItems, Func<TRight, object> rightIdSelector)
{
    var leftOuterJoin = from left in leftItems
        join right in rightItems on leftIdSelector(left) equals rightIdSelector(right) into temp
        from right in temp.DefaultIfEmpty()
        select new { left, right };

    var rightOuterJoin = from right in rightItems
        join left in leftItems on rightIdSelector(right) equals leftIdSelector(left) into temp
        from left in temp.DefaultIfEmpty()
        select new { left, right };

    var fullOuterJoin = leftOuterJoin.Union(rightOuterJoin);

    return fullOuterJoin.Select(x => new KeyValuePair<TLeft, TRight>(x.left, x.right));
}