MergeJoin - lobodava/artisan-orm GitHub Wiki

MergeJoin is an in-memory helper for stitching together flat result sets into a parent / child object graph. It walks the master and detail enumerables forward once — O(N + M) for matching ordered input — and calls your delegate for each linked pair. It does not construct a hash lookup; enumerators and the collections created by your callbacks can still allocate.

Pairs naturally with ReadToLists for assembling graphs from a single round-trip.

You query parent + child tables in one round trip:

select * from dbo.vwGrandRecords order by Id;
select r.*
from dbo.vwRecordsWithTypes r
inner join dbo.vwGrandRecords gr on gr.Id = r.GrandRecordId
order by gr.Id, r.Id;

You get back two flat lists. You want them wired up so each parent has its Records collection populated and each child has its GrandRecord back-reference set. The natural LINQ approach allocates a Dictionary keyed by the parent id and probes it once per child:

var byParent = grandRecords.ToDictionary(gr => gr.Id);
foreach (var r in records)
{
    var gr = byParent[r.GrandRecordId];
    r.GrandRecord = gr;
    gr.Records ??= new List<Record>();
    gr.Records.Add(r);
}

MergeJoin does the same wiring without the Dictionary — it walks both lists in parallel and matches consecutive runs:

grandRecords.MergeJoin(
    gr => gr.Records ??= new List<Record>(),
    records,
    isMasterDetailLink:        (gr, r) => gr.Id == r.GrandRecordId,
    joinedMasterDetailAction:  (gr, r) => { r.GrandRecord = gr; gr.Records.Add(r); });

Details must form contiguous runs in the order of their masters, and every detail must belong to a supplied master.

For a two-level graph, sorting masters by Id and details by MasterId in the same direction satisfies the ordering part. If the query filters masters, apply the same selection to details.

The implementation advances the detail cursor only after a match; it does not skip orphan or out-of-order details. For example, masters [1, 2] and detail parent IDs [0, 1, 2] produce no matches: the first unmatched detail blocks the later ones. Masters with no details are fine. Treat filtering and ORDER BY as part of the result-set contract.

public static void MergeJoin<TMaster, TDetail>(
    this IEnumerable<TMaster> masterList,
    Action<TMaster>?          eachMasterAction,    // optional per-master init
    IEnumerable<TDetail>      detailList,
    Func<TMaster, TDetail, bool> isMasterDetailLink,
    Action<TMaster, TDetail>     joinedMasterDetailAction)
    where TMaster : class
    where TDetail : class;

The eachMasterAction is called before any details are joined to that master — useful for allocating the children collection (gr.Records ??= new List<Record>()) so masters with zero details still have an empty (not null) list.

When a master has two unrelated child collections — say, records and payments — use the sibling overload. This example assumes GrandRecord.Payments and a Payment type with GrandRecordId and GrandRecord members:

grandRecords.MergeJoin(
    records,
    (gr, r) => gr.Id == r.GrandRecordId,
    (gr, r) => { r.GrandRecord = gr; (gr.Records ??= new List<Record>()).Add(r); },

    payments,
    (GrandRecord gr, Payment p) => gr.Id == p.GrandRecordId,
    (GrandRecord gr, Payment p) => { p.GrandRecord = gr; (gr.Payments ??= new List<Payment>()).Add(p); });

Single pass over the masters; each master consumes its details from list 1, then from list 2. Both detail lists must follow the master traversal order and contain no unmatched parent keys. The explicitly typed delegates above distinguish this overload from the nested three-level overload.

For hierarchies like GrandRecord → Record → ChildRecord:

var (grandRecords, records, childRecords) =
    repo.ReadToLists<GrandRecord, Record, ChildRecord>("dbo.GetGrandRecords");

grandRecords.MergeJoin(
    records,
    (gr, r) => gr.Id == r.GrandRecordId,
    (gr, r) => { r.GrandRecord = gr; (gr.Records ??= new List<Record>()).Add(r); },

    childRecords,
    (Record r, ChildRecord cr) => r.Id == cr.RecordId,
    (Record r, ChildRecord cr) => { cr.Record = r; (r.ChildRecords ??= new List<ChildRecord>()).Add(cr); });

The third level joins to Record, not GrandRecord. In the nested overload, sub-detail callbacks run before the callback that attaches that record to its master, so do not rely on the master back-reference being assigned already.

Required ordering:

• Masters: GrandRecord.Id.
• Details: (GrandRecordId, Record.Id).
• Sub-details: the corresponding (GrandRecordId, RecordId, ChildRecord.Id) path.

Sorting sub-details globally by RecordId is insufficient when record IDs interleave between masters. For example, records visited as parent 1 / record 100, then parent 2 / record 5 require sub-details for record 100 before those for record 5.

The sample database's views provide the columns expected by its mappers. A query shape with the required ordering and matching parent selection is:

select * from dbo.vwGrandRecords order by Id;

select r.*
from dbo.vwRecordsWithTypes r
inner join dbo.vwGrandRecords gr on gr.Id = r.GrandRecordId
order by gr.Id, r.Id;

select child.*
from dbo.vwChildRecords child
inner join dbo.Records r on r.Id = child.RecordId
inner join dbo.vwGrandRecords gr on gr.Id = r.GrandRecordId
order by gr.Id, r.Id, child.Id;

If only some masters are selected, use that same selection for all three result sets. See the repository's GetGrandRecords procedure and filtered counterpart.

When SQL already guarantees the required traversal order and matching parent selection, MergeJoin avoids a lookup allocation. If those preconditions are inconvenient, use GroupJoin or an explicit lookup and choose how to handle unmatched details. Compare performance with the actual data rather than assuming one strategy is always faster.

• Forgot order by in the SQL. Symptoms: details silently dropped, parent collections shorter than expected, no exception. Fix: always sort the detail SELECT by the foreign key it joins on.

• Sorted by the wrong column. If Records are sorted globally by Id instead of following GrandRecordId, the forward cursor can encounter a detail whose parent has already been passed and stop matching later details. It does not restart the detail list for each master.

• Filtered masters but unfiltered details. A detail for a missing master can block all later details. Apply the parent selection to every descendant result set.

• Different direction. Both lists must be sorted in the same direction (both ascending, typically). Mixing ASC and DESC will silently miss matches.

• Forgot eachMasterAction on the empty-children case. A master with zero matching details will keep its Children property at null (or whatever initial value the mapper assigned). Use eachMasterAction to initialise the collection unconditionally.

public IList<GrandRecord> GetAll()
{
    return GetByCommand(cmd =>
    {
        cmd.UseProcedure("dbo.GetGrandRecords");
        // Result sets follow the full parent/detail ordering shown above.
        // The views include all columns required by the sample mappers.

        var (grandRecords, records, childRecords) =
            cmd.ReadToLists<GrandRecord, Record, ChildRecord>();

        grandRecords.MergeJoin(
            gr => gr.Records ??= new List<Record>(),

            records,
            (gr, r) => gr.Id == r.GrandRecordId,
            (gr, r) => { r.GrandRecord = gr; gr.Records.Add(r); },

            childRecords,
            (Record r, ChildRecord cr) => r.Id == cr.RecordId,
            (Record r, ChildRecord cr) => {
                r.ChildRecords ??= new List<ChildRecord>();
                cr.Record = r;
                r.ChildRecords.Add(cr);
            });

        return grandRecords;
    });
}

One round trip, three result sets, and three lists joined under an explicit ordering contract. The implementation is a forward cursor walk, not a general SQL-style join.

In 4.1.0, the helper disposes every acquired detail enumerator on normal completion and exceptional exit, including when a later enumerator cannot be acquired. It does not take ownership of the source enumerable objects. Resource cleanup does not relax the ordered-input and no-orphan preconditions above.

See also:

• ReadToLists — multi-result-set tuples
• Negative identities and object graph saving — the inverse direction (graph -> tables)
• What's New in v4