Solutions to Related Tables Challenge

Last week I provided a T-SQL Challenge involving writing a recursive query that returns tables related to an input table directly or indirectly through foreign key relationships. You can find the challenge details here. The tricky part wasn’t really to come up with any solution that works, rather to come up with a solution using a recursive query. With this constraint the challenge became much more difficult—especially coming up with a solution that performs reasonably.

I’d like to thank all those who sent solutions, including Peter Larsson (Peso), Geri Reshef and Rubén Garrigós. Special thanks go to Peso for his help in benchmarking solutions in his environment and in sending corrections to other solutions. I know that many others tried to solve the puzzle and would like to thank you for your efforts—it is a difficult challenge!

The sample data I provided last week is far too simple to be used to test the performance of the solutions. Peso tested some of the solutions in his data warehouse with 160 tables and this way we got more realistic measures. I created a new set of tables—smaller than Peso’s environment, yet more complex than last week’s—and this was sufficient to show the performance differences between the solutions. Here’s the new sample data:

USE testfk;

CREATE TABLE dbo.T2(c2 INT PRIMARY KEY);

CREATE TABLE dbo.T3(c3 INT PRIMARY KEY);

CREATE TABLE dbo.T4(c4 INT PRIMARY KEY);

CREATE TABLE dbo.T5(c5 INT PRIMARY KEY);

CREATE TABLE dbo.T1(c1 INT PRIMARY KEY,

c2 INT REFERENCES dbo.T2,

c3 INT REFERENCES dbo.T3,

c4 INT REFERENCES dbo.T4,

c5 INT REFERENCES dbo.T5);

CREATE TABLE dbo.T6(c6 INT PRIMARY KEY,

c2 INT REFERENCES dbo.T2,

c3 INT REFERENCES dbo.T3);

CREATE TABLE dbo.T7(c7 INT PRIMARY KEY,

c3 INT REFERENCES dbo.T3,

c4 INT REFERENCES dbo.T4);

CREATE TABLE dbo.T8(c8 INT PRIMARY KEY,

c4 INT REFERENCES dbo.T4,

c5 INT REFERENCES dbo.T5);

CREATE TABLE dbo.T9(c9 INT PRIMARY KEY,

c2 INT REFERENCES dbo.T2,

c5 INT REFERENCES dbo.T5);

CREATE TABLE dbo.T10(c10 INT PRIMARY KEY,

c6 INT REFERENCES dbo.T6,

c3 INT REFERENCES dbo.T3);

CREATE TABLE dbo.T11(c11 INT PRIMARY KEY,

c3 INT REFERENCES dbo.T3,

c7 INT REFERENCES dbo.T7);

CREATE TABLE dbo.T12(c12 INT PRIMARY KEY,

c7 INT REFERENCES dbo.T7,

c4 INT REFERENCES dbo.T4);

CREATE TABLE dbo.T13(c13 INT PRIMARY KEY,

c4 INT REFERENCES dbo.T4,

c8 INT REFERENCES dbo.T8);

CREATE TABLE dbo.T14(c14 INT PRIMARY KEY,

c5 INT REFERENCES dbo.T5,

c8 INT REFERENCES dbo.T8);

CREATE TABLE dbo.T15(c15 INT PRIMARY KEY,

c5 INT REFERENCES dbo.T5,

c9 INT REFERENCES dbo.T9);

CREATE TABLE dbo.T16(c16 INT PRIMARY KEY,

c2 INT REFERENCES dbo.T2,

c9 INT REFERENCES dbo.T9);

CREATE TABLE dbo.T17(c17 INT PRIMARY KEY,

c2 INT REFERENCES dbo.T2,

c6 INT REFERENCES dbo.T6);

And here’s a graphical depiction of the relationships:

These tables are created in the testfk database used last week in addition to the other tables already there (tables A, B, C, D, E, F, G).

The performance measures I’ll provide are against this data model, using warm cache, not including parse and compile time. I used the following input for the performance test:

DECLARE @table AS NVARCHAR(261) = N'dbo.T1';

The expected output is (not necessarily in this order):

obj_schema_name obj_name

---------------- ---------

dbo T15

dbo T16

dbo T17

dbo T2

dbo T3

dbo T4

dbo T5

dbo T1

dbo T6

dbo T7

dbo T8

dbo T9

dbo T10

dbo T11

dbo T12

dbo T13

dbo T14

First, I’d like to emphasize that the constraint to come up with a solution based on a recursive query was just to increase the puzzle’s level of difficulty. In practical terms, it makes sense to address such need using a loop-based solution. Loop-based solutions in this case are far simpler and more efficient than recursive solutions. Here’s the one I showed last week (call it Itzik Loop) with a minor revision to return the input table when it has no related tables (remember to include in the code the declaration and initialization of the input @table provided earlier):

DECLARE @T AS TABLE ( id INT NOT NULL PRIMARY KEY );

INSERT INTO @T(id)

SELECT OBJECT_ID(@table) AS id

WHERE OBJECT_ID(@table) IS NOT NULL

UNION

SELECT referenced_object_id

FROM sys.foreign_keys

WHERE parent_object_id = OBJECT_ID(@table)

UNION

SELECT parent_object_id

FROM sys.foreign_keys

WHERE referenced_object_id = OBJECT_ID(@table);

WHILE @@ROWCOUNT > 0

INSERT INTO @T(id)

SELECT referenced_object_id AS id

FROM sys.foreign_keys AS FK

JOIN @T

ON FK.parent_object_id = [@T].id

UNION

SELECT parent_object_id

FROM sys.foreign_keys AS FK

JOIN @T

ON FK.referenced_object_id = [@T].id

EXCEPT

SELECT id FROM @T;

SELECT OBJECT_SCHEMA_NAME(id) AS obj_schema_name, OBJECT_NAME(id) AS obj_name

FROM @T;

The statistics for this solution on my system with the new sample data are: Duration: 4 ms, Reads: 587.

Here’s another loop-based solution provided by Peso (call it Peso Loop):

DECLARE @Tables TABLE

(

TableID INT PRIMARY KEY

)

INSERT @Tables

(

TableID

)

SELECT [object_ID] AS TableID

FROM SYS.TABLES

WHERE [object_ID] = OBJECT_ID(@table)

WHILE @@ROWCOUNT > 0

INSERT @Tables

(

TableID

)

SELECT DISTINCT TableID

FROM (

SELECT fk.REFERENCED_OBJECT_ID AS TableID

FROM SYS.FOREIGN_KEYS AS fk

INNER JOIN @Tables AS t ON t.TableID = fk.PARENT_OBJECT_ID

UNION ALL

SELECT fk.PARENT_OBJECT_ID AS TableID

FROM SYS.FOREIGN_KEYS AS fk

INNER JOIN @Tables AS t ON t.TableID = fk.REFERENCED_OBJECT_ID

) AS w

WHERE NOT EXISTS(SELECT * FROM @Tables AS t WHERE t.TableID = w.TableID)

SELECT

OBJECT_SCHEMA_NAME(TableID) AS obj_schema_name,

OBJECT_NAME(TableID) AS obj_name

FROM @Tables;

The stats I got for this solution are: Duration: 4 ms, reads: 728. In short, both loop-based solutions are pretty efficient as you can see.

As for recursive solutions, I’ll start with the ones I came up with, then I’ll provide also the ones by Peso, Geri and Rubén.

My first attempt at a solution using a recursive query is the following (call it Itzik Recursive 1):

WITH C AS

(

SELECT OBJECT_ID(@table) AS obj,

'.' + CAST(OBJECT_ID(@table) AS VARCHAR(MAX)) + '.' AS objpath

WHERE OBJECT_ID(@table) IS NOT NULL

UNION ALL

SELECT D.obj, D.objpath + CAST( D.obj AS VARCHAR(MAX) ) + '.'

FROM ( SELECT

CASE WHEN C.obj = F.parent_object_id

THEN F.referenced_object_id

ELSE F.parent_object_id

END AS obj, objpath

FROM C

JOIN sys.foreign_keys AS F

ON C.obj IN (F.parent_object_id, F.referenced_object_id) ) AS D

WHERE objpath NOT LIKE '%.' + CAST(obj AS VARCHAR(10)) + '.%'

)

SELECT DISTINCT

OBJECT_SCHEMA_NAME(obj) AS obj_schema_name,

OBJECT_NAME(obj) AS obj_name

FROM C;

The anchor member returns the input table. The recursive member returns a row for each counterpart of the tables that appeared in the previous round as either a referencing or a referenced table. For each edge, the code constructs a dot separated path with all of the object ids of the objects leading to the current. In each recursive round, the code filters out nodes that already appear in their parent node’s path.

This solution is short (in terms of amount of code) and elegant, but isn’t very fast. It creates all possible paths starting with the input node and made of unique nodes. As you can imagine, the number of paths can explode quickly to a large number with additions of new related tables.

The statistics I got for this solution are: Duration: 7,812, Reads: 2,949,749.

In order for a recursive solution to be really fast you need to avoid constructing multiple different paths and visit each node only once. The two main challenges are: 1. How to apply DISTINCT logic in the recursive member without using the DISTINCT clause (not allowed in recursive member). 2. Avoid building multiple different paths when multiple nodes are counterparts in a foreign key relationship with a single node from the previous round.

Both challenges have a solution. Challenge 1 can be handled by calculating a row number partitioned by the node and then filtering only rows with row number 1. Challenge 2 can be handled by using a FOR XML PATH query to concatenate multiple nodes into one. Here’s the complete solution code (call it Itzik Recursive 2):

WITH C AS

(

SELECT

CAST('.' + STR(OBJECT_ID(@table), 11) + '.' AS VARCHAR(MAX)) AS entirepath,

CAST('~' + STR(OBJECT_ID(@table), 11) + '~' AS VARCHAR(MAX)) AS lastpath

WHERE OBJECT_ID(@table) IS NOT NULL

UNION ALL

SELECT

REPLACE(entirepath, '~', '.') + '.',

SUBSTRING(entirepath, CHARINDEX('~', entirepath), LEN(entirepath)) + '~'

FROM (

SELECT CAST(entirepath AS VARCHAR(MAX)) AS entirepath

FROM (

SELECT element AS [text()]

FROM (

SELECT

CASE n WHEN 1 THEN entirepath ELSE obj END AS element,

ROW_NUMBER() OVER(PARTITION BY CASE n WHEN 1 THEN entirepath ELSE obj END

ORDER BY (SELECT NULL)) AS rownum

FROM (

SELECT

LEFT(entirepath, LEN(entirepath) - 1) AS entirepath,

'~' + STR(obj, 11) AS obj

FROM (

SELECT

C.entirepath,

CAST(

CASE WHEN C.lastpath LIKE '%~' + STR(F.parent_object_id, 11) + '~%'

THEN F.referenced_object_id

ELSE F.parent_object_id

END AS VARCHAR(10)) AS obj

FROM C

JOIN sys.foreign_keys AS F

ON C.lastpath LIKE '%~' + STR(F.parent_object_id, 11) + '~%'

OR C.lastpath LIKE '%~' + STR(F.referenced_object_id, 11) + '~%'

) AS D1

WHERE entirepath NOT LIKE '%.' + STR(obj, 11) + '.%'

) AS D2

CROSS JOIN (SELECT 1 UNION ALL SELECT 2) AS Nums(n)

) AS D3

WHERE rownum = 1

ORDER BY element

FOR XML PATH('')

) AS D4(entirepath)

WHERE entirepath IS NOT NULL

) AS D5

Split AS

(

SELECT

CAST(SUBSTRING(lastpath, 2, 11) AS INT) AS obj,

STUFF(lastpath, 1, 12, '') AS lastpath

FROM C

UNION ALL

SELECT

CAST(SUBSTRING(lastpath, 2, 11) AS INT) AS obj,

STUFF(lastpath, 1, 12, '') AS lastpath

FROM Split

WHERE lastpath '~'

)

SELECT

OBJECT_SCHEMA_NAME(obj) AS obj_schema_name,

OBJECT_NAME(obj) AS obj_name

FROM Split;

Observe in the CTE C that only one path is built in each iteration of the recursive query, concatenating the path built by the previous round and the qualifying items from the current round (concatenation done with FOR XML PATH). The code uses a trick to distinguish between the part of the path representing nodes accessed prior to current round and nodes added in this round (could be more than one). The trick is to use different separators for the two sections in the layer of the code that concatenates all parts—old (. as separator) and new (~ as separator). The reason to include both sections in the same string and not as different strings is that a FOR XML PATH query can return only one string. Then a layer of code on top can extract the last part of the path (section starting with ~) giving it the attribute name lastpart, and replace all ocurrences of the character ~ with . to return the entire path, giving it the attribute name entirepath.

Finally, another recursive query called Split extracts the node ids from the lastpath attribute calculated in each round. First round (anchor member) handles first node in each lastpath, second round (already recursive query) handles second node in each last path, and so on, until no more nodes exist.

Since this solution visits each node only once it is very fast. The performance stats I got for it are: Duration: 17, Reads: 2,129.

Following are solutions using recursive queries by Peso, Geri and Ruben and their performance statistics.

Here’s Peso’s solution (Call it Peso Recursive):

WITH cteTables (ChildTableName, ParentTableName)

AS (

SELECT CASE x.Permutation

WHEN 0 THEN c.TABLE_NAME

ELSE p.TABLE_NAME

END AS ChildTableName,

CASE x.Permutation

WHEN 0 THEN p.TABLE_NAME

ELSE c.TABLE_NAME

END AS ParentTableName

FROM (

SELECT CONSTRAINT_SCHEMA + '.' + CONSTRAINT_NAME AS CONSTRAINT_NAME,

UNIQUE_CONSTRAINT_SCHEMA + '.' + UNIQUE_CONSTRAINT_NAME AS UNIQUE_CONSTRAINT_NAME

FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS

) AS rc

INNER JOIN (

SELECT CONSTRAINT_SCHEMA + '.' + CONSTRAINT_NAME AS CONSTRAINT_NAME,

CAST(TABLE_SCHEMA + '.' + TABLE_NAME AS VARCHAR(MAX)) AS TABLE_NAME

FROM INFORMATION_SCHEMA.CONSTRAINT_TABLE_USAGE

) AS c ON c.CONSTRAINT_NAME = rc.CONSTRAINT_NAME

INNER JOIN (

SELECT CONSTRAINT_SCHEMA + '.' + CONSTRAINT_NAME AS CONSTRAINT_NAME,

CAST(TABLE_SCHEMA + '.' + TABLE_NAME AS VARCHAR(MAX)) AS TABLE_NAME

FROM INFORMATION_SCHEMA.CONSTRAINT_TABLE_USAGE

) AS p ON p.CONSTRAINT_NAME = rc.UNIQUE_CONSTRAINT_NAME

CROSS JOIN (

SELECT 0 UNION ALL

SELECT 1

) AS x(Permutation)

WHERE c.TABLE_NAME p.TABLE_NAME

), cteHierarchy(TableName, TablePath)

AS (

SELECT TableName,

CHAR(2) + TableName + CHAR(2) AS TablePath

FROM (

SELECT CAST(TABLE_SCHEMA + '.' + TABLE_NAME AS VARCHAR(MAX)) AS TableName

FROM INFORMATION_SCHEMA.TABLES

) AS d

WHERE TableName = @table

UNION ALL

SELECT t.ParentTableName AS TableName,

h.TablePath + t.ParentTableName + CHAR(2) AS TablePath

FROM cteHierarchy AS h

INNER JOIN cteTables AS t ON t.ChildTableName = h.TableName

WHERE h.TablePath NOT LIKE '%' + CHAR(2) + t.ParentTableName + CHAR(2) + '%'

)

SELECT TableName

FROM cteHierarchy

ORDER BY TablePath;

Statistics: Duration: 258,447, Reads: 19,714,744.

Here’s Geri’s solution (call it Geri Recursive):

With T1 As

(Select Distinct Schema_Name(P.schema_id)+'.'+P.name P,

Schema_Name(R.schema_id)+'.'+R.name R

From sys.foreign_key_columns F

Inner Join sys.objects P

On F.parent_object_id=P.object_id

Inner Join sys.objects R

On F.referenced_object_id=R.object_id),

T2 As

(Select ROW_NUMBER() Over(Order By Case When @table =P Then 1 When @table =R Then 2 Else 3 End,P,R) Mispar,

From T1),

T3 As

(Select Cast(0 As Int) Mispar,

P PR,

(-1) Idcun,

Cast(','+P+','+R+',' As Varchar(Max)) S_in

From T2

Where Mispar=1

And @table In (P,R)

Union

Select Cast(1 As Int) Mispar,

R PR,

(-1) Idcun,

Cast(','+P+','+R+',' As Varchar(Max)) S_in

From T2

Where Mispar=1

And @table In (P,R)

Union All

Select Cast(Mispar As Int),

Case When Idcun=1 Then R When Idcun=2 Then P Else '' End PR,

Case When Idcun=2 Then 1 Else Idcun End Idcun,

Cast(S_in+Case When Idcun=1 Then R+',' When Idcun=2 Then P+',' Else '' End As Varchar(Max)) S_in

From (Select T2.Mispar,

T2.P,

T2.R,

Case When T3.S_in Like '%,'+T2.P+',%' And T3.S_in Not Like '%,'+T2.R+',%' Then 1

When T3.S_in Not Like '%,'+T2.P+',%' And T3.S_in Like '%,'+T2.R+',%' Then 2

Else 0 End Idcun,

T3.S_in

From T3

Inner Join T2

On T3.Mispar+1=T2.Mispar

And T3.Mispar>0

Where T3.Idcun0) T

Union All

Select Cast(Mispar As Int),

Case When Idcun=1 Then R When Idcun=2 Then P Else '' End PR,

Case When Idcun=2 Then 1 Else Idcun End Idcun,

Cast(S_in+Case When Idcun=1 Then R+',' When Idcun=2 Then P+',' Else '' End As Varchar(Max)) S_in

From (Select T2.Mispar,

T2.P,

T2.R,

Case When T3.S_in Like '%,'+T2.P+',%' And T3.S_in Not Like '%,'+T2.R+',%' Then 1

When T3.S_in Not Like '%,'+T2.P+',%' And T3.S_in Like '%,'+T2.R+',%' Then 2

Else 0 End Idcun,

T3.S_in

From T3

Inner Join T2

On T3.Idcun=1

And T2.Mispar=1) T)

Select Distinct PR

From T3

Where PR''

OPTION(MAXRECURSION 0);

Statistics: Duration: 680, Reads: 156,951. Quite fast as you can see.

And here’s Ruben’s solution (call it Ruben Recursive):

WITH referenced(id,level)

(

SELECT referenced_object_id AS id, (select count(*) from sys.foreign_keys) level

FROM sys.foreign_keys FK

WHERE referenced_object_id = OBJECT_ID(@table) or parent_object_id = OBJECT_ID(@table)

UNION ALL

SELECT

case

when (parent_object_id = id) then referenced_object_id

else parent_object_id

end

AS id,

referenced.level-1 level

FROM sys.foreign_keys FK

JOIN referenced ON (referenced_object_id = id or parent_object_id = id)

AND (referenced_object_idparent_object_id)

AND referenced.level >= 1

)

SELECT DISTINCT OBJECT_SCHEMA_NAME(id) AS obj_schema_name, OBJECT_NAME(id) AS obj_name

FROM referenced;

Statistics: I stopped it after it ran for 30 minutes.

Cheers,

Comments

Plain text