Recursing both ways along a chain - SQL Server 2008 R2

[FunkyDexter]

This feels like it should be easy but I just can't quite nail it.

I'm working on a system that logs "Persons".
One Person can be "Merged" into another to indicate that they're actually the same person.
In order to support Unmerging, rather than physically merging the two records and repointing all their child records in other tables, instead we hold a "Merge" record which says e.g. Person A has Been Merged into Person B. From an end users point of view Person A then ceases to exist (only people who haven't been merged into someone else appear in the UI) although, in data terms, Person A's record does still exist and has all it's children attached to it - it's just that the whole caboodle will henceforth be considered part of Person B.

A couple of extra rules:-
A person can only ever be merged into 1 other person.
That person could then be merged into a third and so on. Forming a "Chain"
Many persons can be merged into 1 person.

Hope that all makes sense

So here's some data that would produce a single "merged" person (ID 6) out of several original persons:-

Insert into MergedPersons
(MergedPersonID, MergedIntoPersoniD)
Values (2,3),
(3,4),
(4,5),
(5,6),
(7,6),
(8,7),
(9,7);

I'm now looking for an efficient way, given a single merge pairing, to get every person id in the chain. My first thought was simply to use a recursive cte. However, because I might start with a pairing in the middle of a chain I need to recurse in both directions along it. I therefore wrote this:-

with cteMergeChain as
(
      Select [Merged Person ID], [Merged Into Person ID]
      From People.[Merged Persons]
      Where [Merged Person ID] in (@PersonID1, @PersonID2)
      and [Merged Into Person ID] in (@PersonID1, @PersonID2)
      
      Union All
      
      (Select MP.[Merged Person ID], MP.[Merged Into Person ID]
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.[Merged Person ID] = MP.[Merged Into Person ID]
           or MC.[Merged Into Person ID] = MP.[Merged Person ID])
)
Select [Merged Person ID]
From cteMergeChain

Union

Select [Merged Into Person ID]
From cteMergeChain

...but that creates an infinite recursion.

Say I start with pairing (4,5). My first iteration will get me additional pairings:-
(3,4) and (5,6). OK so far.
But the next iteration, as well as finding (2,3) and (7,6), will return me (4,5) again. Thus begins an infinite recursion.

My first thought was simply to add an Except to the recursing part of the cte:-

with cteMergeChain as
(
      Select [Merged Person ID], [Merged Into Person ID]
      From People.[Merged Persons]
      Where [Merged Person ID] in (@PersonID1, @PersonID2)
      and [Merged Into Person ID] in (@PersonID1, @PersonID2)
      
      Union All
      
      (Select MP.[Merged Person ID], MP.[Merged Into Person ID]
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.[Merged Person ID] = MP.[Merged Into Person ID]
           or MC.[Merged Into Person ID] = MP.[Merged Person ID]
      Except 
      Select [Merged Person ID], [Merged Into Person ID]
      From cteMergeChain)
)
Select [Merged Person ID]
From cteMergeChain

Union

Select [Merged Into Person ID]
From cteMergeChain

However that's not allowed because "Recursive member of a common table expression 'cteMergeChain' has multiple recursive references". Which is SQL Server speak for "you can't refer back to the cte a second time".

At the moment I've fallen back on recursing all the way along to the end of the chain in one direction, getting the ID at the end of the chain and then using that as the start point to recurse all the way back to the other end, collecting all the IDs as I go. This seems a bit wasteful though.

I've cut this a few ways but I just can't seem to come up with a solution that recurses in both directions at the same time without causing an infinite recursion.

Anyone got any suggestions?

[techgnome]

I've got an idea or two... but I'm getting ready for my annual review in a couple min here... I've done something similar... I'll see if I can remember just how I did it... but I think it involved a two-step process of walking the chain back up to the top to get the root of all things.. then back down again to get all the children along the way...

-tg

[techgnome]

See if this is any help...
it uses a recursive CTE to walk the chain from anywhere back up to the top... then uses that top as an anchor for another CTE that then walks it back down....

create Table MergedPersons (MergedPersonID int, MergedIntoPersonID int)
go
Insert into MergedPersons
(MergedPersonID, MergedIntoPersoniD)
Values (2,3),
(3,4),
(4,5),
(5,6),
(7,6),
(8,7),
(9,7);
go
declare @P1ID int, @P2ID int
set @P1ID = 4; set @P2ID = 5
;with MergeChain as (
  select MergedPersonID, MergedIntoPersonID, 1 as Sequence
  from MergedPersons 
  where MergedPersonID = @P1ID and MergedIntoPersonID = @P2ID 

  union all

  select MP.MergedPersonID, MP.MergedIntoPersonID, MC.Sequence + 1 as Sequence
  from MergedPersons MP
  inner join MergeChain MC 
    on MP.MergedIntoPersonID = MC.MergedPersonID
), MergeChainTop as (
  select 
    top 1 
    MergedPersonID, MergedIntoPersonID
  from MergeChain
  order by Sequence desc
), MergeChain2 as (
  select MP.MergedPersonID, MP.MergedIntoPersonID, 1 as Sequence
  from MergeChainTop MCT
  inner join MergedPersons MP on MCT.MergedPersonID = MP.MergedPersonID and MCT.MergedIntoPersonID = MP.MergedIntoPersonID

  union all

  select MP.MergedPersonID, MP.MergedIntoPersonID, MC.Sequence + 1 as Sequence
  from MergedPersons MP
  inner join MergeChain2 MC 
    on MP.MergedPersonID = MC.MergedIntoPersonID
)
select * from MergeChain2
go


drop table MergedPersons
go

MergeChain CTE starts in the middle and returns all parent records... MergeChainTop CTE then orders them in reverse (based on the Sequence number that's generated) and returns the first (last) record, which is the top record. That is then used in the inner join as the anchor in the MergeChain2 CTE to walk the line back down.
Results:

MergedPersonID         MergedIntoPersonID    Sequence
2                               3                               1
3                               4                               2
4                               5                               3
5                               6                               4

-tg

[FunkyDexter]

I think it involved a two-step process of walking the chain back up to the top to get the root of all things.. then back down again to get all the children along the way...

Yeah, that's what I'm doing at the moment. It seems kinda daft to walk back and forward across the same ground though. It feels like there should be a better way but I just can't seem to find it - maybe there isn't one.

I got some mileage out of introducing a "direction of travel" type field so the links found in the forward direction would only look for further links in the forward direction and links in the backward direction would only look for further links in the backward direction. That would prevent it re-finding the start point. Turned out to be a dead end, though, because of this : "Many persons can be merged into 1 person". That means that when I'm walking forward I still need to look back, just not at the particular link I just walked forward from. Maybe I could have fields to hold the whole previous link... I might give that a try tomorrow.

My gut tells me there's something in the "except" approach. After all, that's the closest analogy for what I'm trying to do on each pass: "find me any link, in either direct, which you don't already know about". I just can't seem to find a way of forcing it into the syntax though.

[techgnome]

The only other thing I can think of still involves two CTE's one that travels in one direction, and one that goes in the other, and then union them together... you'd have to make sure your anchor doesn't get counted twice, but that's not too difficult.

-tg

[FunkyDexter]

Woot! Finally managed it. The trick was to "remember" the last person ID on each iteration and make sure I didn't re-add it. To do that I had to separate the forward and back recursion elements into two different blocks. Here's the final result:-

Declare @PersonID1 bigint = 5
Declare @PersonID2 bigint = 4;
 
with cteMergeChain as
(
      Select [Merged Into Person ID] PersonID, Cast(null as BigInt) as LastPersonID, 1 as Iter, cast('Start' as NVarChar(20)) as Direction
      From People.[Merged Persons]
      Where [Merged Person ID] = @PersonID1 and [Merged Into Person ID] = @PersonID2
      Or [Merged Into Person ID] = @PersonID1 and [Merged Person ID] = @PersonID2
      
      Union All
      
      Select MP.[Merged Person ID], MC.PersonID, Iter + 1, cast('Merged Into' as NVarChar(20))
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.PersonID = MP.[Merged Into Person ID]
           and not (isnull(MC.LastPersonID, 0) = MP.[Merged Person ID])
           
      Union All
      
      Select MP.[Merged Into Person ID], MC.PersonID, Iter + 1, cast('Merged From' as NVarChar(20))
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.PersonID = MP.[Merged Person ID]
           and not (isnull(MC.LastPersonID, 0) = MP.[Merged Into Person ID])
)
 
Select *
From cteMergeChain

The Iter and Direction fields aren't really needed, they're just there as part of my investigation/debugging process.

Thanks as always for you input, TG.



Edit> A trivial improvement is to use both the Merged From and Merged To in the root. Won't make alot of difference but could potentially save a single iteration:-

Declare @PersonID1 bigint = 5
Declare @PersonID2 bigint = 4;
 
with cteMergeChain as
(
      (Select [Merged Into Person ID] PersonID, [Merged Person ID] LastPersonID, 1 as Iter, cast('Start' as NVarChar(20)) as Direction
      From People.[Merged Persons]
      Where [Merged Person ID] = @PersonID1 and [Merged Into Person ID] = @PersonID2
      Or [Merged Into Person ID] = @PersonID1 and [Merged Person ID] = @PersonID2
      union
      Select [Merged Person ID] PersonID, [Merged Into Person ID] LastPersonID, 1 as Iter, cast('Start' as NVarChar(20)) as Direction
      From People.[Merged Persons]
      Where [Merged Person ID] = @PersonID1 and [Merged Into Person ID] = @PersonID2
      Or [Merged Into Person ID] = @PersonID1 and [Merged Person ID] = @PersonID2)
      
      
      Union All
      
      Select MP.[Merged Person ID], MC.PersonID, Iter + 1, cast('Merged Into' as NVarChar(20))
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.PersonID = MP.[Merged Into Person ID]
           and not (isnull(MC.LastPersonID, 0) = MP.[Merged Person ID])
           
      Union All
      
      Select MP.[Merged Into Person ID], MC.PersonID, Iter + 1, cast('Merged From' as NVarChar(20))
      From cteMergeChain MC
      Join People.[Merged Persons] MP
           on MC.PersonID = MP.[Merged Person ID]
           and not (isnull(MC.LastPersonID, 0) = MP.[Merged Into Person ID])
)
 
Select *
From cteMergeChain

[techgnome]

Sweet! I'll have to remember this thread. We've got a similar setup for this same type scenario, merging of records. We've also got quite a few tables that also make use of the HIERARCHYID type in SQL Server that I find myself needing to traverse. Something like this might come in handy.

-tg