SQL: Combinations by Type

Question

I have sets organized by type. I want to find all unique combinations of sets, taking one set from each type. So I start with this:

table1:
row_id  type    set
1       a       1
2       a       2
3       a       3
4       b       4
5       b       5
6       c       6

and want to get this:

table2:
row_id  combo_id    type    set
1       1           a       1
2       1           b       4
3       1           c       6
4       2           a       2
5       2           b       4
6       2           c       6
7       3           a       3
8       3           b       4
9       3           c       6
10      4           a       1
11      4           b       5
12      4           c       6
13      5           a       2
14      5           b       5
15      5           c       6
16      6           a       3
17      6           b       5
18      6           c       6

The first idea might be to use CROSS JOIN and get something like this:

table3:
row_id  combo_id    a_set   b_set   c_set
1       1           1       4       6
2       2           2       4       6
3       3           3       4       6
4       4           1       5       6
5       5           2       5       6
6       6           3       5       6

However, my real data has thousands of types with no upper bound on that number, so I think the setup in table2 is necessary.

I see there are many Stack Overflow questions about SQL combinations. However, none that I found addressed sorting by type, let alone an unbounded number of types.

I'm using PLSQL Developer with Oracle 10g. Thanks!

Answer 1

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE table1 ( "rowid", "type", "set" ) AS
          SELECT 1, 'a', 1 FROM DUAL
UNION ALL SELECT 2, 'a', 2 FROM DUAL
UNION ALL SELECT 3, 'a', 3 FROM DUAL
UNION ALL SELECT 4, 'b', 4 FROM DUAL
UNION ALL SELECT 5, 'b', 5 FROM DUAL
UNION ALL SELECT 6, 'c', 6 FROM DUAL
//
CREATE TYPE combo_sets AS OBJECT(
  "type" CHAR(1),
  idx    NUMBER(5,0),
  sets   SYS.ODCINUMBERLIST
);
//
CREATE TYPE t_combo_sets AS TABLE OF combo_sets;
//
CREATE TYPE combo AS OBJECT(
  "rowid"    NUMBER(8,0),
  "comboid"  NUMBER(8,0),
  "type"     CHAR(1),
  "set"      NUMBER(5,0)
);
//
CREATE TYPE t_combos AS TABLE of combo;
//
CREATE OR REPLACE FUNCTION get_combos
RETURN t_combos PIPELINED
AS
  v_combo_sets t_combo_sets;
  i            NUMBER(5,0);
  r            NUMBER(5,0) := 1;
  c            NUMBER(5,0) := 1;
BEGIN
  SELECT combo_sets( 
           "type",
           1,
           CAST( COLLECT( "set" ORDER BY "set" ) AS SYS.ODCINUMBERLIST )
         )
  BULK COLLECT INTO v_combo_sets
  FROM table1
  GROUP BY "type";

  i := 1;
  WHILE i <= v_combo_sets.COUNT LOOP
    FOR j IN 1 .. v_combo_sets.COUNT LOOP
      PIPE ROW(
        combo(
          r,
          c,
          v_combo_sets(j)."type",
          v_combo_sets(j).sets( v_combo_sets(j).idx )
        )
      );
      r := r + 1;
    END LOOP;
    c := c + 1;

    i := 1;
    WHILE i <= v_combo_sets.COUNT AND v_combo_sets(i).idx = v_combo_sets(i).sets.COUNT LOOP    
      v_combo_sets(i).idx := 1;
      i := i + 1;
    END LOOP;
    IF i <= v_combo_sets.COUNT THEN
      v_combo_sets(i).idx := v_combo_sets(i).idx + 1;
    END IF;
  END LOOP;

  RETURN;
END;
//

Query 1:

SELECT *
FROM   TABLE( get_combos )

Results:

| rowid | comboid | type | set |
|-------|---------|------|-----|
|     1 |       1 |    a |   1 |
|     2 |       1 |    b |   4 |
|     3 |       1 |    c |   6 |
|     4 |       2 |    a |   2 |
|     5 |       2 |    b |   4 |
|     6 |       2 |    c |   6 |
|     7 |       3 |    a |   3 |
|     8 |       3 |    b |   4 |
|     9 |       3 |    c |   6 |
|    10 |       4 |    a |   1 |
|    11 |       4 |    b |   5 |
|    12 |       4 |    c |   6 |
|    13 |       5 |    a |   2 |
|    14 |       5 |    b |   5 |
|    15 |       5 |    c |   6 |
|    16 |       6 |    a |   3 |
|    17 |       6 |    b |   5 |
|    18 |       6 |    c |   6 |

Answer 2

One method to arrive at your table2 representation would be to use an Up-and-Down hierarchical query:

with table1(row_id, type, val) as (
select 1, 'a', 1 from dual union all
select 2, 'a', 2 from dual union all
select 3, 'a', 3 from dual union all
select 4, 'b', 4 from dual union all
select 5, 'b', 5 from dual union all
select 6, 'c', 6 from dual
), t2 as (
select row_id
     , type
     , DENSE_RANK() OVER (ORDER BY type desc) type_id
     , val
  from table1
), Up as (
select row_number() over (partition by CONNECT_BY_ISLEAF
                              order by SYS_CONNECT_BY_PATH(row_id, ',')) combo_id
     , SYS_CONNECT_BY_PATH(row_id, ',') path_id
     , prior SYS_CONNECT_BY_PATH(row_id, ',') parent_path_id
     , t2.* 
     , CONNECT_BY_ISLEAF leaf
  from t2
 connect by type_id = prior type_id+1
 start with type_id = 1
), Down as (
select row_number() over (order by CONNECT_BY_ROOT combo_id, type) row_id
     , CONNECT_BY_ROOT combo_id combo_id
     , type
     , val
  from Up
  connect by path_id = prior parent_path_id
  start with leaf = 1
)
select * from Down;

In this solution subquery t2 adds a sequential id for each unique type I've ordered them in reverse order so that the first traversal will end up with type 'a' as the leaf nodes.

In the first tree traversal (subquery Up) I add a unique combo code to all the leaf records for grouping purposes and add the path_id and parent_path_id columns used in the next tree traversal. This is also the stage where all the new rows are generated.

In the second tree traversal (subquery Down) I start at the leaf nodes from the Up traversal and climb back down to the root keeping the root (leaf?) combo_id generated in the prior traversal. No additional rows are generated in this stage since it's a straight shot from the leaf back to the root of the tree.

The final result:

  ROW_ID   COMBO_ID T        VAL
-------- ---------- - ----------
       1          1 a          1
       2          1 b          4
       3          1 c          6
       4          2 a          2
       5          2 b          4
       6          2 c          6
       7          3 a          3
       8          3 b          4
       9          3 c          6
      10          4 a          1
      11          4 b          5
      12          4 c          6
      13          5 a          2
      14          5 b          5
      15          5 c          6
      16          6 a          3
      17          6 b          5
      18          6 c          6

 18 rows selected 

If you want your Table3 representation you can change the select * from Down to this:

select row_number() over (order by combo_id) row_id
     , pvt.*
  from (select combo_id, type, val from Down)
 pivot (max(val) "SET"
   for (type) in ('a' A
                 ,'b' B
                 ,'c' C)) pvt;

Yielding the following result:

    ROW_ID   COMBO_ID      A_SET      B_SET      C_SET
---------- ---------- ---------- ---------- ----------
         1          1          1          4          6
         2          2          2          4          6
         3          3          3          4          6
         4          4          1          5          6
         5          5          2          5          6
         6          6          3          5          6