Shortest Path in SQL Server using hierarchyid

Introduction

Sometimes, we need to store our map in a database and save some data related to the map. I've tried to do this, and I've found the path between the streets.

The benefit of my way is set base manipulation, as SQL Server optimizer has multi-thread processing for set base manipulation. and search in set base processing can have binary search efficient.

As you can see, I have 20 or more streets and alleys in the map, for storing them to database, I design this table:

The logic of my Table is that each node(street) can have multiple parents and for each parent, it has one record, and each node(street) can have multiple child(street):

Using the Code

First Step

At first, I needed to store my map to table, I got a screen shot of Google map and inserted it into my table using a procedure.

Take a look at my table design:

CREATE TABLE [dbo].[WayTree](
	[ID] [int] IDENTITY(1,1) NOT NULL,
	[WayName] [nvarchar](300) NULL,
	[WayHierarchyID] [hierarchyid] NULL,
	[WayLevel]  AS ([WayHierarchyID].[GetLevel]()) PERSISTED,
	[WayAncestor]  AS ([WayHierarchyID].[GetAncestor]((1))) PERSISTED,
	[Cost] [decimal](18, 0) NULL,
PRIMARY KEY CLUSTERED 
(
	[ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, _
IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY] 

Cost is the distance of child from his parent!

And procedure is:

create proc [dbo].[InsertChild] (@ParrentID int, @ChildName nvarchar(100), @cost Decimal)
 as 
 begin
 Declare @ParrentHierarchyID HierarchyID 
 if ((select count(*) from WayTree where id = @ParrentID)=0)
 begin
 insert into WayTree (WayName, WayHierarchyID, Cost) values(@ChildName,N'/', 0 )
 end
 else
 begin
 insert into WayTree(WayName,  WayHierarchyID, Cost) 
 select @ChildName,
   WayHierarchyID.GetDescendant((select max(WayHierarchyID.ToString()) 
					from WayTree w
					where WayHierarchyID.IsDescendantOf_
					((select  w2.WayHierarchyID from WayTree w2 where w2.ID = @ParrentID)) = 1
					and w.WayHierarchyID.GetLevel()=w3.WayHierarchyID.GetLevel()+1), null).ToString(),
   @cost from WayTree w3 where ID = @ParrentID

 end
 end 

As you can see for inserting WayHierarchyID, I add some code, the reason is that we need to find last direct child of parent(@ParentID), you can find the direct child with function GetLevel(), because always this term [child.GetLevel() = Parent.GetLevel()+1] is true, for example the input of procedure is:

@ParentID = 11 

and the hierarchyid of record with id = 11 is N'/1/2'

and it has three direct children : N'/1/2/1', N'/1/2/2', N'/1/2/3'

so next child has this hierarchyid : N'/1/2/4'

which we find this hierarchyid with function .GetDescendant()

Please note the logical errors in procedure are not completely handled as it depends on each business logic.

The last thing I need to do for inserting a map is calling my procedure, in fact I don't insert all the node , just some of them, you can find ChildName from map, if you ask why I use the ID of parent instead of its name in my procedure, I want you to go to the table design and check its logic, each street can have multiple records as it can have multiple parents, so its name is not useful, we need its ID, but you can solve this problem in UI:

exec InsertChild 1 , N'EmamKHomeini', 0
exec InsertChild 1 , N'Basti', 2
exec InsertChild 2 , N'Aftab', 2
exec InsertChild 2 , N'Laleh1', 2
exec InsertChild 2 , N'Laleh2', 4
exec InsertChild 2 , N'Mahtab', 5
exec InsertChild 2 , N'Laleh3', 6
exec InsertChild 2 , N'Laleh4', 8
exec InsertChild 2 , N'Laleh5', 10
exec InsertChild 1 , N'Soheil', 5
exec InsertChild 1 , N'Mokhaberat', 8
exec InsertChild 11 , N'M_Alley1', 3
exec InsertChild 11 , N'M_Alley2', 5
exec InsertChild 11 , N'Laleh4', 7
exec InsertChild 11 , N'MokhaberatAlley3', 8
exec InsertChild 1 , N'Isargaran', 10
exec InsertChild 16 , N'I_Alley1', 3
exec InsertChild 16 , N'I_Alley2', 5
exec InsertChild 16 , N'I_Alley3', 8
exec InsertChild 1 , N'Farhangian', 13
exec InsertChild 20 , N'I_Alley1', 3
exec InsertChild 20 , N'I_Alley2', 5
exec InsertChild 20 , N'I_Alley3', 8
exec InsertChild 20 , N'Farhang1', 3
exec InsertChild 20 , N'Farhang2', 5
exec InsertChild 20 , N'Farhang3', 8

Second Step

Writing the query to find path, and shortest path between two locations:

The major logic of my query is retrieving all the parent/child of beginning street in a recursive way, and parent/child of result node to last, so I have all the nodes which have relation with beginning node, then I create path between nodes by adding direct parents and children together.

At last, I found the path which includes beginning and destination.

declare @Beginning nvarchar(100) = N'Laleh4'
declare @Destination nvarchar(100) = N'Farhang3'
declare @MaxRecursion int = 4 -- be note in worth case the max recursion 
--is the sum of location with two or more parents + the length of longest WayLevel
;with cte as (
select 1 as RowNumber,Begining.WayName BeginingName, _
Begining.WayHierarchyID as BeginingHierarchyID, _
Begining.WayHierarchyID.ToString() as BeginingHierarchyIDString,
	   Begining.Cost BeginingCost,
	   RelatedWay.WayName RelatedWayName,
	   RelatedWay.WayHierarchyID.ToString() as RelatedHierarchyIDString,
	   RelatedWay.WayHierarchyID as RelatedHierarchyID,
	   RelatedWay.Cost RelatedWayCost
from WayTree Begining 
inner join WayTree RelatedWay on (RelatedWay.WayHierarchyID.IsDescendantOf_
( Begining.WayHierarchyID) = 1 and Begining.WayHierarchyID != RelatedWay.WayHierarchyID 
								  and RelatedWay.WayLevel =  Begining.WayLevel + 1) or
								    (Begining.WayHierarchyID.IsDescendantOf_
								    (RelatedWay.WayHierarchyID) = 1 and _
								    Begining.WayHierarchyID != RelatedWay.WayHierarchyID
								  and Begining.WayLevel = RelatedWay.WayLevel + 1)
where Begining.WayName= @Beginning 

	 union all

select  c.RowNumber + 1 as RowNumber,  Begining.WayName BeginingName, _
Begining.WayHierarchyID as BeginingHierarchyID,
	   Begining.WayHierarchyID.ToString() as BeginingHierarchyIDString,
	   Begining.Cost BeginingCost, 
	   RelatedWay.WayName RelatedWayName,
       RelatedWay.WayHierarchyID.ToString() as RelatedHierarchyIDString,
	   RelatedWay.WayHierarchyID as RelatedHierarchyID,
	   RelatedWay.Cost RelatedWayCost
from cte c
inner join WayTree as Begining on c.RelatedWayName = Begining.WayName 
inner join WayTree RelatedWay on ((RelatedWay.WayHierarchyID.IsDescendantOf_
(Begining.WayHierarchyID) = 1 and Begining.WayHierarchyID != RelatedWay.WayHierarchyID
								   and RelatedWay.WayLevel = Begining.WayLevel + 1) or
								  (Begining.WayHierarchyID.IsDescendantOf_
								  ( RelatedWay.WayHierarchyID) = 1 and _
								  Begining.WayHierarchyID != RelatedWay.WayHierarchyID
								   and Begining.WayLevel = RelatedWay.WayLevel + 1))

where c.RowNumber<@MaxRecursion
 and RelatedWay.WayHierarchyID != c.BeginingHierarchyID
 and RelatedWay.WayHierarchyID != Begining.WayHierarchyID

 ), cte2 as (

select distinct cte.BeginingName, _
cte.BeginingHierarchyIDString,cte.BeginingHierarchyID, cte.BeginingCost,
			    cte.RelatedWayName, cte.RelatedHierarchyIDString, _
			    cte.RelatedHierarchyID, cte.RelatedWayCost
from cte
)

,cte4 as(

select  1 AS RowNumber, BeginingHierarchyID, BeginingHierarchyIDString,BeginingName , _
CAST(cte2.BeginingName AS nvarchar(MAX)) as waypath, cast(BeginingCost as decimal) _
as cost ,cast(0 as decimal)pathcost
from cte2
union all 
select 1 as RowNumber, RelatedHierarchyID, RelatedHierarchyIDString, RelatedWayName, _
CAST(cte2.RelatedWayName AS nvarchar(MAX)) as waypath, cast(RelatedWayCost as decimal) _
as cost,cast(0 as decimal) as pathcost
from cte2

union all

select C.RowNumber + 1, c2.BeginingHierarchyID,C2.BeginingHierarchyIDString,C2.BeginingName, 
cast((c.waypath+'.'+C2.BeginingName) as nvarchar(MAX)) as waypath,
cast(case when c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 then c2.BeginingCost
		when c2.BeginingHierarchyID.IsDescendantOf_
		(c.BeginingHierarchyID )=1 then c2.BeginingCost end as decimal),
cast(c.pathcost + cast(case when c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 then c.Cost
		when c2.BeginingHierarchyID.IsDescendantOf_
		(c.BeginingHierarchyID )=1 then c2.BeginingCost end as decimal)
														  as decimal)
from cte4 c 
inner join cte2 c2 on (c.BeginingHierarchyID.IsDescendantOf_
(c2.BeginingHierarchyID)=1 and c.BeginingHierarchyID.GetLevel() = _
c2.BeginingHierarchyID.GetLevel()+1 and c.waypath not like N'%'+c2.BeginingName+N'%')
			or (c2.BeginingHierarchyID.IsDescendantOf_
			(c.BeginingHierarchyID )=1 and c.BeginingHierarchyID.GetLevel() _
			+1 = c2.BeginingHierarchyID.GetLevel() and c.waypath not like N'%'+c2.BeginingName+N'%')
    WHERE C.RowNumber<10
)
select * into #temp  from cte4 
OPTION (MAXRECURSION 10);
select distinct * from #Temp
where waypath like N'%'+@Destination+'%'
and waypath like N'%'+@Beginning+'%' 

Remember in the worst case, the max recursion is the sum of location with two or more parents + the length of longest WayLevel.

Points of Interest

I think if we want to show shortest path to users, the best way could be saving them after process, and when user wants the result, just showing the result, without process.