5

For example, starting with a table like this:

create table t as 
select 'A' as x, level as y from dual connect by level<=5
union all 
select 'B' as x, level+2 as y from dual connect by level<=5
union all 
select 'C' as x, level as y from dual connect by level<=3
union all 
select 'D' as x, level+2 as y from dual connect by level<=3;

alter table t add primary key (x, y);

select * from t;

X Y                      
- -
A 1                      
A 2                      
A 3                      
A 4                      
A 5                      
B 3                      
B 4                      
B 5                      
B 6                      
B 7                      
C 1                      
C 2                      
C 3                      
D 3                      
D 4                      
D 5         

How do I get this:

SUBSET_X SUPERSET_X 
-------- ---------- 
D        A          
C        A          
D        B         

I'm posting my own effort as an answer but wondering if there is some other fancy way, perhaps with analytics or a set operator I don't know about

--edit

My test data unintentionally implies that the sets always consist of consecutive integers - unfortunately this is not true with my real data.

4 Answers 4

2

This is similar to your first approach, Jack, with a few differences.

  • It does all the counting in batches as opposed to in the HAVING clause. HAVING is a post aggregation filter, which is why sticking the COUNT in there is slow.
  • It is easier to read by grace of the CTEs which break up the work into smaller chunks.
  • Like your approach, it works both on Oracle 9.2+ and SQL Server 2005+ (and any other RDBMS that supports CTEs).

Your indexing strategy shouldn't matter that much if you are querying the whole table at once, but if you are interested in specific sets I recommend you have indexes both on (x, y) and (y, x).

One way or the other, this query should run very quickly:

WITH set_sizes AS (
  SELECT x, COUNT(*) AS set_size  -- "size" is a reserved keyword in Oracle
  FROM t
  GROUP BY x
)
, intersection_sizes AS (
  SELECT 
      sub.x     sub_x
    , super.x   super_x
    , COUNT(*)  intersection_size
  FROM 
                t sub
    INNER JOIN  t super
      ON  sub.y = super.y
      AND sub.x <> super.x
  GROUP BY
      sub.x
    , super.x
)
SELECT xs.sub_x, xs.super_x
FROM 
              set_sizes           ss
  INNER JOIN  intersection_sizes  xs
    ON  ss.x = xs.sub_x
    AND ss.set_size = xs.intersection_size
;

Edit: Per your tests against a large data set, it looks like this query is the speediest.

6
  • Thanks Nick, this is great. Is this tweak a step forward or a step backwards do you think? Oct 21, 2011 at 17:27
  • @JackDouglas - I would say a step back in readability and perhaps also in performance. The query is less readable because of the DECODE and sub.x < super.x (your intentions are not as obvious), and I bet the OR in the final join condition will yield a worse plan than the AND. Oct 21, 2011 at 18:01
  • I thought you might say that - I'm inclined to agree too :) Oct 21, 2011 at 18:07
  • 1
    My testing on a larger data set suggests this is the fastest solution by some margin (the tweaked version in my comment is even faster but not by enough to justify how hard it is to read) Oct 21, 2011 at 19:20
  • @JackDouglas - Do your tests take caching into account so that one query cannot benefit from data cached by another? Adjusting for that may give you surprisingly different results. Oct 26, 2011 at 19:39
3

This does the trick but is not terribly fast:

select t1.x as subset_x, t2.x as superset_x
from t t1 join t t2 on(t1.y=t2.y and t1.x<>t2.x)
group by t1.x, t2.x
having count(*)=(select count(*) from t where x=t1.x);
3

This also does the trick but 'not terribly fast' would be a huge understatement this time unfortunately - I'm posting it anyway in case it is of academic interest to anyone:

with w as (select x, cast(collect(y) as table_integer) as ys from t group by x)
select w1.x as subset_x, w2.x as superset_x
from w w1 join w w2 on (w1.x<>w2.x and w1.ys submultiset of w2.ys);
3
  • I was working on a SUBMULTISET answer and was about to post my query when yours showed up. Oh well, I still learned something. Oct 21, 2011 at 21:53
  • @LeighRiffel - From it's description it looks perfect for Jack's use case. I'm surprised it didn't perform well. Oct 21, 2011 at 22:33
  • @Leigh ahhh, that makes sense because it was your listagg that got me thinking about 'collect', thanks :) Oct 22, 2011 at 7:12
3

This won't be fast either, but it is an alternative. It requires 11.2, but could be done in an earlier version if you create a custom aggregate function that does the same thing listagg does.

SELECT aa.x, bb.x FROM
(SELECT x, listagg(y, ',%,') WITHIN GROUP (ORDER BY y) z FROM t GROUP BY x) aa
JOIN
(SELECT x, listagg(y, ',,') WITHIN GROUP (ORDER BY y) z FROM t GROUP BY x) bb
ON bb.z LIKE '%' || aa.z || '%' AND aa.x <> bb.x;
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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