Sql-server – Recursive CTE to find Total for all children

cterecursivesql servert-sql

Here is an assembly tree that I want to search using a recursive T-SQL Query (presumably CTE) with the expected results below. I want to know the total amount per assembly given any part.

Meaning if I search for 'Rivet', I want to know the total count at each level within the assembly, not just the direct children count.

Assembly (id:1)
    |
    |-Rivet
    |-Rivet
    |-SubAssembly (id:2)
    |   |
    |   |-Rivet
    |   |-Bolt
    |   |-Bolt
    |   |-SubSubAssembly (id:3)
    |      |
    |      |-Rivet
    |      |-Rivet
    |
    |-SubAssembly (id:4)
       |-Rivet
       |-Bolt

    DESIRED Results
    -------
    ID, Count
    1 , 6
    2 , 3
    3 , 2
    4 , 1

Currently, I can get the direct parents, but want to know how to extend my CTE to allow me to roll this information upward.

With DirectParents AS(
--initialization
Select InstanceID, ParentID
From Instances i 
Where i.Part = 'Rivet'

UNION ALL
--recursive execution
Select i.InstanceID, i.ParentID
From PartInstances i  INNER JOIN DirectParents p
on i.ParentID = p.InstanceID

)

select ParentID, Count(instanceid) as Totals
from DirectParents
group by InstanceID, ParentID

Results
-------
ID, Count
1 , 2
2 , 2
3 , 2
4 , 1

Creation script

CREATE TABLE [dbo].[Instances] ( 
  [InstanceID] NVARCHAR (50) NOT NULL, 
  [Part] NVARCHAR (50) NOT NULL, 
  [ParentID] NVARCHAR (50) NOT NULL, );



INSERT INTO Instances 
Values 
  (1, 'Assembly', 0), 
  (50, 'Rivet', 1), 
  (50, 'Rivet', 1), 
  (2, 'SubAssembly', 1), 
  (50, 'Rivet', 2), 
  (51, 'Bolt', 2), 
  (51, 'Bolt', 2), 
  (3, 'SubSubAssembly', 2), 
  (50, 'Rivet', 3), 
  (50, 'Rivet', 3), 
  (4, 'SubAssembly2', 1), 
  (50, 'Rivet', 4), 
  (51, 'Bolt', 4)

Best Answer

This recursive CTE (SQL Fiddle) should work with your sample:

WITH cte(ParentID) AS(
    SELECT ParentID FROM @Instances WHERE [Part] = 'Rivet'
    UNION ALL
    SELECT i.ParentID FROM cte c
    INNER JOIN @Instances i ON c.ParentID = i.InstanceID
    WHERE i.ParentID > 0
)
SELECT ParentID, count(*) 
FROM cte
GROUP BY ParentID
ORDER BY ParentID
;

Output

ParentID    Count
1           6
2           3
3           2
4           1

Note: You mentioned in comments that the question only contains a simplified sample table and real data have proper indexes and handle duplicates and data adequately.

Data used (SQL Fiddle):

DECLARE @Instances TABLE( 
    [InstanceID] int NOT NULL
    , [Part] NVARCHAR (50) NOT NULL
    , [ParentID] int NOT NULL
);

INSERT INTO @Instances([InstanceID], [Part], [ParentID])
VALUES 
    (1, 'Assembly', 0)
    , (50, 'Rivet', 1)
    , (50, 'Rivet', 1)
    , (2, 'SubAssembly', 1)
    , (50, 'Rivet', 2)
    , (51, 'Bolt', 2)
    , (51, 'Bolt', 2)
    , (3, 'SubSubAssembly', 2)
    , (50, 'Rivet', 3)
    , (50, 'Rivet', 3)
    , (4, 'SubAssembly2', 1)
    , (50, 'Rivet', 4)
    , (51, 'Bolt', 4)
;

Efficient rCTE

WITH RECURSIVE
  input AS (SELECT 'news-on-apple'::text AS slug)  -- input basic slug here once
, cte   AS (
   SELECT slug || '-' AS slug  -- append '-' once, if basic slug exists
        , 1 as suffix          -- start with suffix 1
   FROM   article
   JOIN   input USING (slug)

   UNION ALL
   SELECT c.slug, c.suffix + 1  -- increment by 1 ...
   FROM   cte     c
   JOIN   article a ON a.slug = c.slug || c.suffix  -- ... if slug-n already exists
   )
(
SELECT slug || suffix AS slug
FROM   cte
ORDER  BY suffix DESC  -- pick the last (free) one
LIMIT  1
)  -- parentheses required
UNION  ALL  -- if the basic slug wasn't taken, fall back to that
SELECT slug FROM input
LIMIT  1;

Better performance without rCTE

If you worry about thousands of slugs competing for the same slug or generally want to optimize performance, I'd consider a different, faster approach.

WITH input AS (SELECT 'news-on-apple'::text  AS slug
                    , 'news-on-apple-'::text AS slug1)  -- input basic slug here
SELECT i.slug
FROM   input        i
LEFT   JOIN article a USING (slug)
WHERE  a.slug IS NULL  -- doesn't exist yet.

UNION ALL
(  -- parentheses required
SELECT i.slug1 || COALESCE(right(a.slug, length(i.slug1) * -1)::int + 1, 1)
FROM   input        i
LEFT   JOIN article a ON a.slug LIKE (i.slug1 || '%')  -- match up to last "-"
                     AND right(a.slug, length(i.slug1) * -1) ~ '^\d+$' -- suffix numbers only
ORDER  BY right(a.slug, length(i.slug1) * -1)::int DESC
)
LIMIT  1;

If the basic slug isn't taken yet, the more expensive second SELECT is never executed - same as above, but much more important here. Check with EXPLAIN ANALYZE, Postgres is smart that way with LIMIT queries. Related:
- Optimize a query on two big tables
Check for the leading string and the suffix separately, so the LIKE expression can use a basic btree index with text_pattern_ops like
```
CREATE INDEX article_slug_idx ON article (slug text_pattern_ops);
```
Detailed explanation:
- Pattern matching with LIKE, SIMILAR TO or regular expressions in PostgreSQL
Convert the suffix to integer before you apply max(). Numbers in text representation don't work.

Optimize performance

To get the optimum, consider storing the suffix separated from the basic slug and concatenate the slug as needed: concat_ws('-' , slug, suffix::text) AS slug

CREATE TABLE article (
   article_id serial PRIMARY KEY
 , title text NOT NULL
 , slug  text NOT NULL
 , suffix int
);

The query for a new slug then becomes:

SELECT slug
    || COALESCE((
          SELECT '-'::text || (max(suffix) + 1)::text
          FROM   article a
          WHERE  a.slug = i.slug), '') As slug
FROM  (SELECT 'news-on-apple'::text AS slug) i  -- input basic slug here

Ideally supported with a unique index on (slug, suffix).

Query for list of slugs

In any version of Postgres you can provide rows in a VALUES expression.

SELECT *
FROM   article
JOIN  (
   VALUES
     ('slug-foo'::text, 1)
     ('slug-bar',7)
   ) u(slug,suffix) USING (slug,suffix);

You can also use IN with a set of row-type expressions Which is shorter:

SELECT *
FROM   article
WHERE (slug,suffix) IN (('slug-foo', 1), ('slug-bar',7));

Details under this related question (as commented below):

the <set clause>'s <multiple column assignment>

For long lists, the JOIN to a VALUES expression is typically faster.

In Postgres 9.4 (released today!) you can also use the new variant of unnest() to unnest multiple arrays in parallel.

Given an array of basic slugs and a corresponding array of suffixes (as per comment):

SELECT *
FROM   article
JOIN   unnest('{slug-foo,slug-bar}'::text[]
            , '{1,7}'::int[]) AS u(slug,suffix) USING (slug,suffix);

Sql-server – Sql parent Child Query not working

Define the outer join as a separate, non-recursive, CTE:

WITH FactorColumns AS
(
  SELECT  a.FactorTitle,
          a.FactorCode,
          a.parentId,
          c.FactorColumnCode,
          c.FactorColumnTitle,
          c.FactorColumnValue,
          c.isFactorValue,
          c.FieldType
  FROM FactorSetup a
  LEFT JOIN FactorColumnSetup c ON a.FactorCode=c.FactorCode
),
...

Now just reference FactorColumns in EntityChildren – and syntactically your recursive CTE will have no outer join:

...
EntityChildren AS
(
  SELECT  f.FactorTitle,
          f.FactorCode,
          f.parentId,
          f.FactorColumnCode,
          f.FactorColumnTitle,
          f.FactorColumnValue,
          f.isFactorValue,
          f.FieldType
  FROM FactorColumns AS f

  UNION ALL 

  SELECT f.FactorTitle,
         f.FactorCode,
         f.parentId,
         f.FactorColumnCode,
         f.FactorColumnTitle,
         f.FactorColumnValue,
         f.isFactorValue,
         f.FieldType
  FROM FactorColumns AS f
  INNER JOIN EntityChildren AS e2 ON f.parentId = e2.FactorCode
)
...