| Author |
 Topic  |
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
 Posted - 09/13/2007 : 02:40:21
|
Hi,
I'm attemping to create a query that shows how users are connected to other users thru their friends list. (Degrees of seperation) I'm not sure what the best approach is, and I have seen some pretty advanced stuff in these threads.
What I need brought back is each invididual user in the connection. For example if I was looking at user "bob"
Bob is connected to you via Bill -> Jennifer -> Max -> Lisa
If anyone can point me in the direction of what to do it would be greatly appreciated!
thanks for any help!! :)
mike123
The simple table structure of "tblFriends"
CREATE TABLE [dbo].[tblFriends](
[UserID] [int] NOT NULL,
[FriendID] [int] NOT NULL,
[dateAdded] [smalldatetime] )
Some references below:
I found this thread and did some reading on "expanding networks",it seems to be most exact description of what I am looking for, but there doesnt seem to be any code.
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=32729
This stuff below gets pretty complicated, but looks very interesting! I've attempted to install all the functions on my box, but as of right now the queries are taking a huge amount of time, I'm still checking my integration etc... (One query I stopped after 16 minutes execution) I have about 500k rows in this "tblFriends" table
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 04:20:48
|
You should have read the complete thread (http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097).-- Prepare sample data
DECLARE @Contacts TABLE (pFrom VARCHAR(2), pTo VARCHAR(2))
INSERT @Contacts
SELECT 'A', 'B' UNION ALL
SELECT 'B', 'D' UNION ALL
SELECT 'C', 'A' UNION ALL
SELECT 'C', 'E' UNION ALL
SELECT 'G', 'C' UNION ALL
SELECT 'B', 'G' UNION ALL
SELECT 'F', 'D' UNION ALL
SELECT 'E', 'F'
/*
A - B
/ / \
C - G D
\ /
E - F
*/
-- Initialize search parameters
DECLARE @StartNode VARCHAR(2),
@EndNode VARCHAR(2),
@Iteration INT,
@LastRowID INT
SELECT @StartNode = 'e',
@EndNode = 'g',
@Iteration = 0,
@LastRowID = 0
-- Create staging tables
DECLARE @Tracks TABLE (oldTrack INT, newTrack INT, pFrom VARCHAR(2), pTo VARCHAR(2))
DECLARE @Stage TABLE (Iteration INT, Track INT, pFrom VARCHAR(2), pTo VARCHAR(2), RowID INT IDENTITY(1, 1))
-- Insert starting points
INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT 0,
ROW_NUMBER() OVER (ORDER BY pFrom),
pFrom,
pTo
FROM (
SELECT pFrom,
pTo
FROM @Contacts
WHERE pFrom = @StartNode
UNION ALL
SELECT pTo,
pFrom
FROM @Contacts
WHERE pTo = @StartNode
) AS x
INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT -1,
Track,
pFrom,
pFrom
FROM @Stage
WHERE Iteration = 0
WHILE SCOPE_IDENTITY() > @LastRowID
BEGIN
SELECT @Iteration = @Iteration + 1,
@LastRowID = SCOPE_IDENTITY()
DELETE FROM @Tracks
INSERT @Tracks
(
oldTrack,
newTrack,
pFrom,
pTo
)
SELECT p.Track AS oldTrack,
p.Track + ROW_NUMBER() OVER (PARTITION BY p.Track ORDER BY c.pTo) - 1 AS newTrack,
c.pFrom,
c.pTo
FROM (
SELECT pFrom,
pTo
FROM @Contacts
UNION ALL
SELECT pTo,
pFrom
FROM @Contacts
) AS c
INNER JOIN (
SELECT Track,
pTo
FROM @Stage
WHERE Iteration = @Iteration - 1
) AS p ON p.pTo = c.pFrom
WHERE c.pFrom <> @EndNode
AND NOT EXISTS (SELECT * FROM @Stage AS s WHERE s.pFrom = c.pTo)
INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT @Iteration,
oldTrack,
pFrom,
pTo
FROM @Tracks
WHERE oldTrack = newTrack
INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT s.Iteration,
t.newTrack,
s.pFrom,
s.pTo
FROM @Tracks AS t
INNER JOIN @Stage AS s ON s.Track = t.oldTrack
WHERE t.oldTrack <> t.newTrack
AND s.Iteration < @Iteration
UNION ALL
SELECT @Iteration,
newTrack,
pFrom,
pTo
FROM @Tracks
WHERE oldTrack <> newTrack
END
-- Show the expected output
SELECT ROW_NUMBER() OVER (ORDER BY LEN(Path), Track) AS Track,
REPLACE(Path, '#', ' -> ') AS Path
FROM (
SELECT DISTINCT s1.Track,
STUFF((SELECT TOP 100 PERCENT '#' + s2.pTo FROM @Stage AS s2 WHERE s2.Track = s1.Track ORDER BY s2.Iteration FOR XML PATH('')), 1, 1, '') AS Path
FROM @Stage AS s1
) AS u
ORDER BY LEN(Path),
Track
E 12°55'05.25"
N 56°04'39.16" |
Edited by - SwePeso on 09/13/2007 04:52:38 |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 04:54:10
|
Output from above sample code is Track Path
----- ---------------------
1 E -> C -> G
2 E -> F -> D -> B -> G
3 E -> C -> A -> B -> G
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 05:33:10
|
Or do you only want one path, the shortest?
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 06:33:22
|
This solution is fast even for 500,000 membersCREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromNodeName VARCHAR(10),
@ToNodeName VARCHAR(10),
@ReturnAsResultset TINYINT = 0
)
AS
SET NOCOUNT ON
-- Initialize variables
DECLARE @FromNodeID INT,
@ToNodeID INT,
@NodeID INT,
@Cost INT,
@PathID INT
-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
NodeName VARCHAR(20),
Cost INT,
PathID INT,
Calculated TINYINT
)
-- Stage all nodes
INSERT #Nodes
(
NodeName,
Calculated
)
SELECT pFrom,
0
FROM tblFriends
UNION
SELECT pTo,
0
FROM tblFriends
--Check to see if FromNode exists
SELECT @FromNodeID = NodeID,
@NodeID = NodeID
FROM #Nodes
WHERE NodeName = @FromNodeName
IF @FromNodeID IS NULL
BEGIN
SET @FromNodeName = ISNULL(@FromNodeName, '')
RAISERROR ('From nodename ''%s'' can not be found.', 16, 1, @FromNodeName)
RETURN
END
--Check to see if ToNode exists
SELECT @ToNodeID = NodeID
FROM #Nodes
WHERE NodeName = @ToNodeName
IF @ToNodeID IS NULL
BEGIN
SET @ToNodeName = ISNULL(@ToNodeName, '')
RAISERROR ('To nodename ''%s'' can not be found.', 16, 1, @ToNodeName)
RETURN
END
-- Create staging table for all paths
CREATE TABLE #Paths
(
PathID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
FromNodeID INT,
ToNodeID INT,
Cost INT
)
-- Stage all paths
INSERT #Paths
(
FromNodeID,
ToNodeID,
Cost
)
SELECT nFrom.NodeID,
nTo.NodeID,
c.Cost
FROM (
SELECT pFrom,
pTo,
1 AS Cost
FROM tblFriends
UNION
SELECT pTo,
pFrom,
1
FROM tblFriends
) AS c
INNER JOIN #Nodes AS nFrom ON nFrom.NodeName = c.pFrom
INNER JOIN #Nodes AS nTo ON nTo.NodeName = c.pTo
UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromNodeID
WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN #Paths AS Paths ON Paths.FromNodeID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
AND ToNodes.Calculated = 0
UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID
SET @NodeID = NULL
SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
END
CREATE TABLE #Map
(
RowID INT IDENTITY(-1, -1),
FromNodeName VARCHAR(10),
ToNodeName VARCHAR(10),
Cost INT
)
IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
BEGIN
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
RETURN
END
WHILE @FromNodeID <> @ToNodeID
BEGIN
SELECT @FromNodeName = FromNodes.NodeName,
@ToNodeName = ToNodes.NodeName,
@Cost = ToNodes.Cost,
@PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN #Paths AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
WHERE ToNodes.NodeID = @ToNodeID
INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT @FromNodeName,
@ToNodeName,
@Cost
SELECT @ToNodeID = Paths.FromNodeID
FROM #Paths AS Paths
WHERE Paths.PathID = @PathID
END
INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT FromNodeName,
FromNodeName,
0
FROM #Map
WHERE RowID = SCOPE_IDENTITY()
IF @ReturnAsResultset = 1
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
WHERE RowID > SCOPE_IDENTITY()
ORDER BY RowID
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + m.ToNodeName
FROM #Map AS m
ORDER BY m.RowID
FOR XML PATH('')
)
, 1, 6, '')
, '#x07;', ' -> ') AS Path
E 12°55'05.25"
N 56°04'39.16" |
Edited by - SwePeso on 09/13/2007 07:27:28 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 06:44:21
|
If you have noticed, I also have added a "cost", which can be translated as "how well do they know eachother".
For example
1) Family (low cost)
2) Classmate (middle cost)
3) Know of (high cost)
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/13/2007 : 15:25:03
|
quote:
Originally posted by Peso
Or do you only want one path, the shortest?
Either all the paths, or just the shortest path are both great solutions for me. I am assuming that performance is going to be very similar.
Thanks! :)
mike123 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 15:29:35
|
No, all paths will be sending your server to a crawl. Because ALL paths are calculated.
Try the solution posted 09/13/2007 : 06:33:22 and post back what you think.
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/13/2007 : 15:35:03
|
Hi Peso,
I am attempting to integrate your suggestions on the following SPROC. I have come up with the following modifications, since I am working with INT columns rather than what was posted.
I've let this code run against my table and I just stopped it after 12 minutes. You said this should run fast, and I'm sure its probably an error on my end, but I'm not sure what types of results to expect. There are about 500k rows in the friends table.
Does anything stick out on this SPROC as completely wrong ?
1.) Basically I changed all the VarChar columns to INT's
2.) I changed the parameters to a more appropriate name for this installation.
3.) I changed the pFrom to friendID and pTo to userID
Thanks very much for your help!! I am very excited at the possibility of getting this running smoothly 
ALTER PROCEDURE dbo.uspDijkstraResolve
(
@FromNode_userID INT,
@ToNode_userID INT,
@ReturnAsResultset TINYINT = 0
)
AS
SET NOCOUNT ON
-- Initialize variables
DECLARE @FromNodeID INT,
@ToNodeID INT,
@NodeID INT,
@Cost INT,
@PathID INT
-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
NodeName INT,
Cost INT,
PathID INT,
Calculated TINYINT
)
-- Stage all nodes
INSERT #Nodes
(
NodeName,
Calculated
)
SELECT friendID,
0
FROM tblFriends
UNION
SELECT userID,
0
FROM tblFriends
--Check to see if FromNode exists
SELECT @FromNodeID = NodeID,
@NodeID = NodeID
FROM #Nodes
WHERE NodeName = @FromNode_userID
IF @FromNodeID IS NULL
BEGIN
--SET @FromNode_userID = ISNULL(@FromNode_userID, '')
SET @FromNode_userID = ISNULL(@FromNode_userID, 0)
RAISERROR ('From nodename ''%s'' can not be found.', 16, 1, @FromNode_userID)
RETURN
END
--Check to see if ToNode exists
SELECT @ToNodeID = NodeID
FROM #Nodes
WHERE NodeName = @ToNode_userID
IF @ToNodeID IS NULL
BEGIN
--SET @ToNode_userID = ISNULL(@ToNode_userID, '')
SET @ToNode_userID = ISNULL(@ToNode_userID, 0)
RAISERROR ('To nodename ''%s'' can not be found.', 16, 1, @ToNode_userID)
RETURN
END
-- Create staging table for all paths
CREATE TABLE #Paths
(
PathID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
FromNodeID INT,
ToNodeID INT,
Cost INT
)
-- Stage all paths
INSERT #Paths
(
FromNodeID,
ToNodeID,
Cost
)
SELECT nFrom.NodeID,
nTo.NodeID,
c.Cost
FROM (
SELECT friendID,
userID,
1 AS Cost
FROM tblFriends
UNION
SELECT userID,
friendID,
1
FROM tblFriends
) AS c
INNER JOIN #Nodes AS nFrom ON nFrom.NodeName = c.friendID
INNER JOIN #Nodes AS nTo ON nTo.NodeName = c.userID
UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromNodeID
WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN #Paths AS Paths ON Paths.FromNodeID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
AND ToNodes.Calculated = 0
UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID
SET @NodeID = NULL
SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
END
CREATE TABLE #Map
(
RowID INT IDENTITY(-1, -1),
FromNodeName INT,
ToNodeName INT,
Cost INT
)
IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
BEGIN
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
RETURN
END
WHILE @FromNodeID <> @ToNodeID
BEGIN
SELECT @FromNode_userID = FromNodes.NodeName,
@ToNode_userID = ToNodes.NodeName,
@Cost = ToNodes.Cost,
@PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN #Paths AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
WHERE ToNodes.NodeID = @ToNodeID
INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT @FromNode_userID,
@ToNode_userID,
@Cost
SELECT @ToNodeID = Paths.FromNodeID
FROM #Paths AS Paths
WHERE Paths.PathID = @PathID
END
INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT FromNodeName,
FromNodeName,
0
FROM #Map
WHERE RowID = SCOPE_IDENTITY()
IF @ReturnAsResultset = 1
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
WHERE RowID > SCOPE_IDENTITY()
ORDER BY RowID
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + m.ToNodeName
FROM #Map AS m
ORDER BY m.RowID
FOR XML PATH('')
)
, 1, 6, '')
, '#x07;', ' -> ') AS Path
|
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/13/2007 : 15:50:18
|
Export the tblFriends table (only relevant columns as userid and friendid).
Zip the CSV file and mail it to me.
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/13/2007 : 16:46:52
|
| sent via sqlteam!, thank you |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/14/2007 : 17:50:25
|
I have hosted a CSV of the friends table here, in case sqlteam mail didnt get thru. Thanks again very much appreciated !! :)
cheers,
mike123
http://www.mediafire.com/?8mddstxmbx0 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/15/2007 : 02:56:34
|
I got it. It's weekend right now 
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/15/2007 : 05:05:48
|
quote:
Originally posted by Peso
I got it. It's weekend right now
Have a great weekend my friend !
cheers,
mike123 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/15/2007 : 17:53:12
|
1) Make a UNIQUE index over {userID, friendID}.
2) Add an IDENTITY column PathID with an UNIQUE CLUSTERED index.
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/15/2007 : 17:57:22
|
CREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromID INT,
@ToID INT,
@ReturnAsResultset TINYINT = 0
)
AS
SET NOCOUNT ON
-- Initialize variables
DECLARE @NodeID INT,
@Cost INT,
@PathID INT
-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT PRIMARY KEY CLUSTERED,
Cost INT,
PathID INT,
Calculated TINYINT
)
-- Stage all nodes
INSERT #Nodes
(
NodeID,
Calculated
)
SELECT DISTINCT userID,
0
FROM tblFriends
--Check to see if FromNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @FromID)
BEGIN
RAISERROR ('FromID ''%d'' can not be found.', 16, 1, @FromID)
RETURN
END
--Check to see if ToNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID)
BEGIN
RAISERROR ('To nodename ''%d'' can not be found.', 16, 1, @ToID)
RETURN
END
UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromID
SET @NodeID = @FromID
WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + 1
WHEN FromNodes.Cost + 1 < ToNodes.Cost THEN FromNodes.Cost + 1
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN tblFriends AS Paths ON Paths.userID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.friendID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + 1 < ToNodes.Cost)
AND ToNodes.Calculated = 0
UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID
SET @NodeID = NULL
SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
IF @NodeID = @ToID
SET @NodeID = NULL
END
CREATE TABLE #Map
(
RowID INT IDENTITY(1, 1),
FromNodeID INT,
ToNodeID INT
)
IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID AND Cost IS NULL)
BEGIN
SELECT FromNodeID,
ToNodeID
FROM #Map
RETURN
END
WHILE @FromID <> @ToID
BEGIN
SELECT @PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN tblFriends AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.userID
WHERE ToNodes.NodeID = @ToID
INSERT #Map
(
FromNodeID,
ToNodeID
)
SELECT @ToID,
@FromID
SELECT @FromID = @ToID,
@ToID = Paths.userID
FROM tblFriends AS Paths
WHERE Paths.PathID = @PathID
END
IF @ReturnAsResultset = 1
SELECT FromNodeID,
ToNodeID
FROM #Map
WHERE RowID > 1
ORDER BY RowID DESC
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + CONVERT(VARCHAR, m.FromNodeID)
FROM #Map AS m
ORDER BY m.RowID DESC
FOR XML PATH('')
)
, 1, 6, '')
, '& # x 0 7 ;', ' -> ') AS Path -- No spaces between "& # x 0 7 ;" I only posted them that way because of forum filtering
E 12°55'05.25"
N 56°04'39.16" |
Edited by - SwePeso on 09/15/2007 18:29:36 |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/15/2007 : 20:15:00
|
Hi Peso,
I've tried to debug this myself, but currently unable to figure out exactly how to modify this.
I don't want to get it working incorrectly either. Any idea what this error might be ?
The line is in bold below.
Thank you very very much!! :)
mike123
Server: Msg 207, Level 16, State 1, Procedure uspDijkstraResolve, Line 123
Invalid column name 'PathID'.
quote:
Originally posted by Peso
CREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromID INT,
@ToID INT,
@ReturnAsResultset TINYINT = 0
)
AS
SET NOCOUNT ON
-- Initialize variables
DECLARE @NodeID INT,
@Cost INT,
@PathID INT
-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT PRIMARY KEY CLUSTERED,
Cost INT,
PathID INT,
Calculated TINYINT
)
-- Stage all nodes
INSERT #Nodes
(
NodeID,
Calculated
)
SELECT DISTINCT userID,
0
FROM tblFriends
--Check to see if FromNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @FromID)
BEGIN
RAISERROR ('FromID ''%d'' can not be found.', 16, 1, @FromID)
RETURN
END
--Check to see if ToNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID)
BEGIN
RAISERROR ('To nodename ''%d'' can not be found.', 16, 1, @ToID)
RETURN
END
UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromID
SET @NodeID = @FromID
WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + 1
WHEN FromNodes.Cost + 1 < ToNodes.Cost THEN FromNodes.Cost + 1
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN tblFriends AS Paths ON Paths.userID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.friendID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + 1 < ToNodes.Cost)
AND ToNodes.Calculated = 0
UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID
SET @NodeID = NULL
SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
IF @NodeID = @ToID
SET @NodeID = NULL
END
CREATE TABLE #Map
(
RowID INT IDENTITY(1, 1),
FromNodeID INT,
ToNodeID INT
)
IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID AND Cost IS NULL)
BEGIN
SELECT FromNodeID,
ToNodeID
FROM #Map
RETURN
END
WHILE @FromID <> @ToID
BEGIN
SELECT @PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN tblFriends AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.userID
WHERE ToNodes.NodeID = @ToID
INSERT #Map
(
FromNodeID,
ToNodeID
)
SELECT @ToID,
@FromID
SELECT @FromID = @ToID,
@ToID = Paths.userID
FROM tblFriends AS Paths
WHERE Paths.PathID = @PathID
END
IF @ReturnAsResultset = 1
SELECT FromNodeID,
ToNodeID
FROM #Map
WHERE RowID > 1
ORDER BY RowID DESC
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + CONVERT(VARCHAR, m.FromNodeID)
FROM #Map AS m
ORDER BY m.RowID DESC
FOR XML PATH('')
)
, 1, 6, '')
, '& # x 0 7 ;', ' -> ') AS Path -- No spaces between "& # x 0 7 ;" I only posted them that way because of forum filtering
E 12°55'05.25"
N 56°04'39.16"
|
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/16/2007 : 05:17:52
|
You table tblFriens do need a PathID column, preferrably the IDENTITY column of that table. It has to be unique.
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/16/2007 : 16:00:43
|
Hi Peso,
Ok, I just added an IDENTITY column, and got it working. I am guessing I should probably tune the indexes now?
Also I wondering what the best way to fix this error I am getting when I run against 2 nodes that don't connect. For example
Server: Msg 50000, Level 16, State 1, Procedure uspDijkstraResolve, Line 45
To nodename '500' can not be found.
Also I am wondering how difficult it would be to bring back the results in multiple rows (one for each step) Reason being is that I would like to do a JOIN and bring back the users name as well.
Your thoughts and help much appreciated!
Thanks very much :)
mike123 |
Edited by - mike123 on 09/16/2007 22:58:25 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29138 Posts |
Posted - 09/17/2007 : 01:02:42
|
1) There is an option fot that! Change the default third parameter to 1 instead of missing/null/non-1.
2) If two nodes can't connect you get an empty resultset back.
3) The error you get is that the person/node you start with, can't be found at all.
E 12°55'05.25"
N 56°04'39.16" |
|
|
|
mike123
Flowing Fount of Yak Knowledge
1462 Posts |
Posted - 09/17/2007 : 01:25:38
|
Hey Peso,
1.) I didnt realize that, works perfectly will attempt the JOIN modification now :)
2/3.) By design, not all users have entries in "tblFriends", so I believe that I might be encountering this error by design. I'll see if I can prevent this situation from executing in the web tier, otherwise maybe I will have to integrate it with the main "Users" table ? I'll do more testing first.
4.) I have 500k rows, I just executed a search and it took 3 minutes and 33 seconds, and it brought back 5 degrees of relations. What type of performance do you think I should be expecting ? I'm guessing some index adjustment needs to be made now that I added a new IDENTITY column.
5.) Do you think there are any optimizations I can do inside the query to make any decent difference ? Mainly I am thinking of stripping functionality that I wont use ( the weight part, multiple return type options) but I'm not sure how significant of a difference that would make.
Thanks once again for your continued support!
mike123
|
|
|
|
Topic |
|
|
|
recursion / expanding networks
