CODEWITHSUNDEEP
sqlpostgresqlcommon-table-expressioncombinatoricsrecursive-query
frankhommers
frankhommers

Reputation: 1315

concatenate recursive cross join

I need to concatenate the name in a recursive cross join way. I don't know how to do this, I have tried a CTE using WITH RECURSIVE but no success.

I have a table like this:

group_id | name
---------------
13       | A
13       | B
19       | C
19       | D
31       | E 
31       | F 
31       | G

Desired output:

combinations
------------
ACE
ACF
ACG
ADE
ADF
ADG
BCE
BCF
BCG
BDE
BDF
BDG

Of course, the results should multiply if I add a 4th (or more) group.

Upvotes: 3

Views: 1487

Answers (2)

Erwin Brandstetter
Erwin Brandstetter

Reputation: 658292

The recursive query is a bit simpler in Postgres:

WITH RECURSIVE t AS (  -- to produce gapless group numbers
   SELECT dense_rank() OVER (ORDER BY group_id) AS grp, name
   FROM   tbl
   )
, cte AS (
   SELECT grp, name
   FROM   t
   WHERE  grp = 1

   UNION ALL
   SELECT t.grp, c.name || t.name
   FROM   cte c
   JOIN   t ON t.grp = c.grp + 1
   )
SELECT name AS combi
FROM   cte
WHERE  grp = (SELECT max(grp) FROM t)
ORDER  BY 1;

The basic logic is the same as in the SQL Server version provided by @lad2025, I added a couple of minor improvements.

Or you can use a simple version if your maximum number of groups is not too big (can't be very big, really, since the result set grows exponentially). For a maximum of 5 groups:

WITH t AS (  -- to produce gapless group numbers
   SELECT dense_rank() OVER (ORDER BY group_id) AS grp, name AS n
   FROM   tbl
   )
SELECT concat(t1.n, t2.n, t3.n, t4.n, t5.n) AS combi
FROM        (SELECT n FROM t WHERE grp = 1) t1
LEFT   JOIN (SELECT n FROM t WHERE grp = 2) t2 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 3) t3 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 4) t4 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 5) t5 ON true
ORDER  BY 1;

Probably faster for few groups. LEFT JOIN .. ON true makes this work even if higher levels are missing. concat() ignores NULL values. Test with EXPLAIN ANALYZE to be sure.

SQL Fiddle showing both.

Upvotes: 1

Lukasz Szozda
Lukasz Szozda

Reputation: 176024

Native Postgresql Syntax:

SqlFiddleDemo

WITH RECURSIVE cte1 AS
(
  SELECT *, DENSE_RANK() OVER (ORDER BY group_id) AS rn
  FROM mytable
),cte2 AS
(
  SELECT 
    CAST(name AS VARCHAR(4000)) AS name,
    rn
  FROM cte1
  WHERE rn = 1
  UNION ALL
  SELECT
    CAST(CONCAT(c2.name,c1.name) AS VARCHAR(4000)) AS name
    ,c1.rn
  FROM cte1 c1
  JOIN cte2 c2
    ON c1.rn = c2.rn + 1
)
SELECT name as combinations
FROM cte2
WHERE LENGTH(name) = (SELECT MAX(rn) FROM cte1)
ORDER BY name;

Before:

I hope if you don't mind that I use SQL Server Syntax:

Sample:

CREATE TABLE #mytable(
   ID       INTEGER  NOT NULL
  ,TYPE     VARCHAR(MAX) NOT NULL
);
INSERT INTO #mytable(ID,TYPE) VALUES (13,'A');
INSERT INTO #mytable(ID,TYPE) VALUES (13,'B');
INSERT INTO #mytable(ID,TYPE) VALUES (19,'C');
INSERT INTO #mytable(ID,TYPE) VALUES (19,'D');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'E');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'F');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'G');

Main query: 

WITH cte1 AS
(
  SELECT *, rn = DENSE_RANK() OVER (ORDER BY ID)
  FROM #mytable
),cte2 AS
(
  SELECT 
    TYPE = CAST(TYPE AS VARCHAR(MAX)),
    rn
  FROM cte1
  WHERE rn = 1
  UNION ALL
  SELECT
    [Type]      = CAST(CONCAT(c2.TYPE,c1.TYPE) AS VARCHAR(MAX))
    ,c1.rn
  FROM cte1 c1
  JOIN cte2 c2
    ON c1.rn = c2.rn + 1
)
SELECT *
FROM cte2
WHERE LEN(Type) = (SELECT MAX(rn) FROM cte1)
ORDER BY Type;

LiveDemo

I've assumed that the order of "cross join" is dependent on ascending ID.

  • cte1 generate DENSE_RANK() because your IDs contain gaps
  • cte2 recursive part with CONCAT
  • main query just filter out required length and sort string

Upvotes: 2

Related Questions