7

Question: I'm porting the below query (listing tables by foreign key dependencies) to PostGreSql.

WITH Fkeys AS (

    SELECT DISTINCT 
         OnTable       = OnTable.name
        ,AgainstTable  = AgainstTable.name 
    FROM sysforeignkeys fk 

        INNER JOIN sysobjects onTable 
            ON fk.fkeyid = onTable.id 

        INNER JOIN sysobjects againstTable  
            ON fk.rkeyid = againstTable.id 

    WHERE 1=1
        AND AgainstTable.TYPE = 'U'
        AND OnTable.TYPE = 'U'
        -- ignore self joins; they cause an infinite recursion
        AND OnTable.Name <> AgainstTable.Name
    )

,MyData AS (

    SELECT 
         OnTable = o.name 
        ,AgainstTable = FKeys.againstTable 
    FROM sys.objects o 

    LEFT JOIN FKeys
        ON o.name = FKeys.onTable 

    WHERE (1=1) 
        AND o.type = 'U' 
        AND o.name NOT LIKE 'sys%' 
    )

,MyRecursion AS (

    -- base case
    SELECT  
         TableName    = OnTable
        ,Lvl        = 1
    FROM MyData
    WHERE 1=1
        AND AgainstTable IS NULL 

    -- recursive case
    UNION ALL 

    SELECT 
         TableName = OnTable 
        ,Lvl       = r.Lvl + 1 
    FROM MyData d 
        INNER JOIN MyRecursion r 
            ON d.AgainstTable = r.TableName 
)
SELECT 
     Lvl = MAX(Lvl)
    ,TableName
    --,strSql = 'delete from [' + tablename + ']'
FROM 
    MyRecursion
GROUP BY
    TableName

ORDER BY lvl

/*
ORDER BY 

     2 ASC
    ,1 ASC

*/

Using information_schema, the query looks like this:

WITH Fkeys AS 
(
    SELECT DISTINCT 
         KCU1.TABLE_NAME AS OnTable 
        ,KCU2.TABLE_NAME AS AgainstTable 
    FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU1 
        ON KCU1.CONSTRAINT_CATALOG = RC.CONSTRAINT_CATALOG  
        AND KCU1.CONSTRAINT_SCHEMA = RC.CONSTRAINT_SCHEMA 
        AND KCU1.CONSTRAINT_NAME = RC.CONSTRAINT_NAME 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU2 
        ON KCU2.CONSTRAINT_CATALOG =  RC.UNIQUE_CONSTRAINT_CATALOG  
        AND KCU2.CONSTRAINT_SCHEMA = RC.UNIQUE_CONSTRAINT_SCHEMA 
        AND KCU2.CONSTRAINT_NAME = RC.UNIQUE_CONSTRAINT_NAME 
        AND KCU2.ORDINAL_POSITION = KCU1.ORDINAL_POSITION 

    WHERE (1=1)
    AND KCU1.TABLE_NAME <> KCU2.TABLE_NAME 
)

,MyData AS 
( 
    SELECT 
         TABLE_NAME AS OnTable  
        ,FKeys.againstTable AS AgainstTable
    FROM INFORMATION_SCHEMA.TABLES 

    LEFT JOIN FKeys
        ON TABLE_NAME = FKeys.onTable  

    WHERE (1=1) 
        AND TABLE_TYPE = 'BASE TABLE'
        AND TABLE_NAME NOT IN ('sysdiagrams', 'dtproperties') 
)

,MyRecursion AS 
(
    -- base case
    SELECT  
         OnTable AS TableName 
        ,1 AS Lvl 
    FROM MyData
    WHERE 1=1
    AND AgainstTable IS NULL 

    -- recursive case
    UNION ALL 

    SELECT 
         OnTable AS TableName
        ,r.Lvl + 1 AS Lvl 
    FROM MyData d 

    INNER JOIN MyRecursion r 
        ON d.AgainstTable = r.TableName 
)

SELECT 
     MAX(Lvl) AS Lvl 
    ,TableName
    --,strSql = 'delete from [' + tablename + ']'
FROM 
    MyRecursion
GROUP BY
    TableName

ORDER BY lvl

/*
ORDER BY 

     2 ASC
    ,1 ASC

*/

My question now is:

In SQL Server (tested on 2008 R2): Why does the query jump from 1 second to 11 minutes when I replace

SELECT DISTINCT 
     OnTable       = OnTable.name
    ,AgainstTable  = AgainstTable.name 
FROM sysforeignkeys fk 

    INNER JOIN sysobjects onTable 
        ON fk.fkeyid = onTable.id 

    INNER JOIN sysobjects againstTable  
        ON fk.rkeyid = againstTable.id 

WHERE 1=1
    AND AgainstTable.TYPE = 'U'
    AND OnTable.TYPE = 'U'
    -- ignore self joins; they cause an infinite recursion
    AND OnTable.Name <> AgainstTable.Name

with 

SELECT DISTINCT 
     KCU1.TABLE_NAME AS OnTable 
    ,KCU2.TABLE_NAME AS AgainstTable 
FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC 

LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU1 
    ON KCU1.CONSTRAINT_CATALOG = RC.CONSTRAINT_CATALOG  
    AND KCU1.CONSTRAINT_SCHEMA = RC.CONSTRAINT_SCHEMA 
    AND KCU1.CONSTRAINT_NAME = RC.CONSTRAINT_NAME 

LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU2 
    ON KCU2.CONSTRAINT_CATALOG =  RC.UNIQUE_CONSTRAINT_CATALOG  
    AND KCU2.CONSTRAINT_SCHEMA = RC.UNIQUE_CONSTRAINT_SCHEMA 
    AND KCU2.CONSTRAINT_NAME = RC.UNIQUE_CONSTRAINT_NAME 
    AND KCU2.ORDINAL_POSITION = KCU1.ORDINAL_POSITION 

WHERE (1=1)
AND KCU1.TABLE_NAME <> KCU2.TABLE_NAME

???

As far as I can tell, there really is no significant speed difference when running only the partial queries separately. Also the result set is entirely the same (I checked every row in Excel), though ordering differs.

Below the working PostGreSQL version (finished in 35 ms on exactly the same db content [75 tables]...)
-- No warranty whatsoever --

WITH RECURSIVE Fkeys AS 
(
    SELECT DISTINCT 
         KCU1.TABLE_NAME AS OnTable 
        ,KCU2.TABLE_NAME AS AgainstTable 
    FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU1 
        ON KCU1.CONSTRAINT_CATALOG = RC.CONSTRAINT_CATALOG  
        AND KCU1.CONSTRAINT_SCHEMA = RC.CONSTRAINT_SCHEMA 
        AND KCU1.CONSTRAINT_NAME = RC.CONSTRAINT_NAME 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU2 
        ON KCU2.CONSTRAINT_CATALOG =  RC.UNIQUE_CONSTRAINT_CATALOG  
        AND KCU2.CONSTRAINT_SCHEMA = RC.UNIQUE_CONSTRAINT_SCHEMA 
        AND KCU2.CONSTRAINT_NAME = RC.UNIQUE_CONSTRAINT_NAME 
        AND KCU2.ORDINAL_POSITION = KCU1.ORDINAL_POSITION 
)

,MyData AS 
( 
    SELECT 
         TABLE_NAME AS OnTable  
        ,FKeys.againstTable AS AgainstTable
    FROM INFORMATION_SCHEMA.TABLES 

    LEFT JOIN FKeys
        ON TABLE_NAME = FKeys.onTable  

    WHERE (1=1) 
        AND TABLE_TYPE = 'BASE TABLE'
        AND TABLE_SCHEMA = 'public'
        --AND TABLE_NAME NOT IN ('sysdiagrams', 'dtproperties') 
)


,MyRecursion AS 
(
    -- base case
    SELECT  
         OnTable AS TableName 
        ,1 AS Lvl 
    FROM MyData
    WHERE 1=1
    AND AgainstTable IS NULL 

    -- recursive case
    UNION ALL 

    SELECT 
         OnTable AS TableName
        ,r.Lvl + 1 AS Lvl 
    FROM MyData d 

    INNER JOIN MyRecursion r 
        ON d.AgainstTable = r.TableName 
)

SELECT 
     MAX(Lvl) AS Lvl 
    ,TableName
    --,strSql = 'delete from [' + tablename + ']'
FROM 
    MyRecursion
GROUP BY
    TableName

ORDER BY lvl


/*
ORDER BY 

     2 ASC
    ,1 ASC

*/

It also seems that 

AND KCU1.TABLE_NAME <> KCU2.TABLE_NAME

is superfluous when using information_schema, so it should actually be faster.

Improve this question
10
  • 7
    I checked out the execution plan for your main query and f*ck me, it's a mess. oi41.tinypic.com/2zz0q41.jpg I think that's your problem.
    – ta.speot.is
    Mar 19, 2012 at 5:08
  • @ta.speot.is: True, but I was hoping to know the reason for the mess. Since PG finishes in 35 ms --> Filing bug report with MS.
    – Quandary
    Mar 19, 2012 at 5:32
  • 1
    @BrandonMoore - It allows you, for better or worse, to programmaticaly add clauses without having to verify if you should also add a where.
    – Lieven Keersmaekers
    Mar 19, 2012 at 7:12
  • 1
    @Brandon Moore: As Lieven says (only as long as every additional condition is and, if it was or, it would need to be 1=2), but mainly for me in order to quickly be able to comment out any and condition without generating a syntax error, for testing purposes.
    – Quandary
    Mar 19, 2012 at 7:58
  • 2
    Just looking at the execution plan for the partial queries looks like joining on the id field is (unsurprisingly) more efficient than joining on the strings NAME, SCHEMA etc. BTW you should be using the sys.objects etc. not the deprecated sysobjects
    – Martin Smith
    Mar 19, 2012 at 10:31

2 Answers 2

Reset to default
12

I would probably abandon the INFORMATION_SCHEMA views here and use the new sys. views (as opposed to the backward compatibility ones) instead, or at least materialize the results of the JOIN into an indexed table first.

Recursive CTEs always get the same basic plan in SQL Server where each row is added to a stack spool and processed one by one. This means that the join between REFERENTIAL_CONSTRAINTS RC, KEY_COLUMN_USAGE KCU1, KEY_COLUMN_USAGE KCU2 will happen as many times as the result of the following query SELECT COUNT(*) FROM MyRecursion.

Which I assume in your case (from the 11 mins execution time) is probably many thousands of times so you need the recursive part to be as efficient as possible. Your query will be performing the following type of thing thousands of times.

   SELECT  
           KCU1.TABLE_CATALOG,
           KCU1.TABLE_SCHEMA,
           KCU1.TABLE_NAME
    FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC 
    INNER JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU1 
        ON KCU1.CONSTRAINT_CATALOG = RC.CONSTRAINT_CATALOG  
        AND KCU1.CONSTRAINT_SCHEMA = RC.CONSTRAINT_SCHEMA 
        AND KCU1.CONSTRAINT_NAME = RC.CONSTRAINT_NAME 
    INNER JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU2 
        ON KCU2.CONSTRAINT_CATALOG =  RC.UNIQUE_CONSTRAINT_CATALOG  
        AND KCU2.CONSTRAINT_SCHEMA = RC.UNIQUE_CONSTRAINT_SCHEMA 
        AND KCU2.CONSTRAINT_NAME = RC.UNIQUE_CONSTRAINT_NAME 
        AND KCU2.ORDINAL_POSITION = KCU1.ORDINAL_POSITION 
    WHERE KCU2.TABLE_NAME = 'FOO'

(Side note: Both versions of your query will return incorrect results if same table name in different schemas)

As you can see the plan for this is pretty horrible.

Plan

Comparing this with the plan for your sys query which is somewhat simpler.

SELECT OnTable = OnTable.name, 
       AgainstTable = AgainstTable.name 
FROM   sysforeignkeys fk 
       INNER JOIN sysobjects OnTable 
         ON fk.fkeyid = OnTable.id 
       INNER JOIN sysobjects AgainstTable 
         ON fk.rkeyid = AgainstTable.id 
WHERE  AgainstTable.name = 'FOO'

Plan 2

you may be able to encourage the intermediate materialisation without creating a #temp table explicitly by changing the definition of MyData to

MyData AS 
( 
    SELECT TOP 99.999999 PERCENT
         TABLE_NAME AS OnTable  
        ,Fkeys.AgainstTable AS AgainstTable
    FROM INFORMATION_SCHEMA.TABLES 

    LEFT JOIN Fkeys
        ON TABLE_NAME = Fkeys.OnTable  

    WHERE (1=1) 
        AND TABLE_TYPE = 'BASE TABLE'
        AND TABLE_NAME NOT IN ('sysdiagrams', 'dtproperties') 
        ORDER BY TABLE_NAME
)

Testing against Adventureworks2008 on my machine this brought the runtime down from about 10 seconds to 250ms (after the first run was out of the way as the plan took 2 seconds to compile). It adds an eager spool to the plan that materialises the result of the Join on the first recursive call then replays it on subsequent calls. This behaviour is not guaranteed however and you may want to upvote the Connect item request Provide a hint to force intermediate materialization of CTEs or derived tables

I would feel safer creating the #temp table explicitly as below rather than relying on this behaviour.

CREATE TABLE #MyData
(
OnTable SYSNAME,
AgainstTable NVARCHAR(128) NULL,
UNIQUE CLUSTERED (AgainstTable, OnTable)
);

WITH Fkeys AS 
(
    SELECT DISTINCT 
         KCU1.TABLE_NAME AS OnTable 
        ,KCU2.TABLE_NAME AS AgainstTable 
    FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU1 
        ON KCU1.CONSTRAINT_CATALOG = RC.CONSTRAINT_CATALOG  
        AND KCU1.CONSTRAINT_SCHEMA = RC.CONSTRAINT_SCHEMA 
        AND KCU1.CONSTRAINT_NAME = RC.CONSTRAINT_NAME 

    LEFT JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KCU2 
        ON KCU2.CONSTRAINT_CATALOG =  RC.UNIQUE_CONSTRAINT_CATALOG  
        AND KCU2.CONSTRAINT_SCHEMA = RC.UNIQUE_CONSTRAINT_SCHEMA 
        AND KCU2.CONSTRAINT_NAME = RC.UNIQUE_CONSTRAINT_NAME 
        AND KCU2.ORDINAL_POSITION = KCU1.ORDINAL_POSITION 

    WHERE (1=1)
    AND KCU1.TABLE_NAME <> KCU2.TABLE_NAME 
)

,MyData AS 
( 
    SELECT 
         TABLE_NAME AS OnTable  
        ,Fkeys.AgainstTable AS AgainstTable
    FROM INFORMATION_SCHEMA.TABLES 

    LEFT JOIN Fkeys
        ON TABLE_NAME = Fkeys.OnTable  

    WHERE (1=1) 
        AND TABLE_TYPE = 'BASE TABLE'
        AND TABLE_NAME NOT IN ('sysdiagrams', 'dtproperties') 
)
INSERT INTO #MyData
SELECT *
FROM MyData;


WITH MyRecursion AS 
(
    -- base case
    SELECT  
         OnTable AS TableName 
        ,1 AS Lvl 
    FROM #MyData
    WHERE 1=1
    AND AgainstTable IS NULL 

    -- recursive case
    UNION ALL 

    SELECT 
         OnTable AS TableName
        ,r.Lvl + 1 AS Lvl 
    FROM #MyData d 

    INNER JOIN MyRecursion r 
        ON d.AgainstTable = r.TableName 
)

SELECT 
     MAX(Lvl) AS Lvl 
    ,TableName
    --,strSql = 'delete from [' + tablename + ']'
FROM 
    MyRecursion
GROUP BY
    TableName

ORDER BY Lvl

DROP TABLE #MyData

or alternatively

Improve this answer
1
  • Great answer. And thanks for the side note, that's a nice catch. I think for the time being I feel safer keeping the older version for SQL Server instead of creating a persistent/tem table. I intend to replace sysobjects with sys.objects. Hopefully no bad surprises there. A CTE hint would indeed be good, given the fact that the optimizer is, unlike its pg counterpart, not intelligent enough to recognize this automagically. BTW until now I didn't realize one can export the execution plan as image. One of the 4 things I learned from this post - thank you.
    – Quandary
    Mar 20, 2012 at 17:40
2

In both cases you are querying views, that is left for compatibilty: Compatibilty views and Information Schema Views.

Use catalog views instead to get best performance (msdn: "We recommend that you use catalog views because they are the most general interface to the catalog metadata and provide the most efficient way to obtain, transform, and present customized forms of this information")..

Improve this answer
1
  • 3
    Information Schema is not left for compatibility, it's part of the SQL standart (92+) ...
    – Quandary
    Mar 19, 2012 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.