Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks Nick, this is great. Is this tweak a step forward or a step backwards do you think? –  Jack Douglas Oct 21 '11 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. –  Nick Chammas Oct 21 '11 at 18:01
    
I thought you might say that - I'm inclined to agree too :) –  Jack Douglas Oct 21 '11 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) –  Jack Douglas Oct 21 '11 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. –  Nick Chammas Oct 26 '11 at 19:39

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);
share|improve this answer

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);
share|improve this answer
    
I was working on a SUBMULTISET answer and was about to post my query when yours showed up. Oh well, I still learned something. –  Leigh Riffel Oct 21 '11 at 21:53
    
@LeighRiffel - From it's description it looks perfect for Jack's use case. I'm surprised it didn't perform well. –  Nick Chammas Oct 21 '11 at 22:33
    
@Leigh ahhh, that makes sense because it was your listagg that got me thinking about 'collect', thanks :) –  Jack Douglas Oct 22 '11 at 7:12

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;
share|improve this answer
    
thanks, very interesting! –  Jack Douglas Oct 21 '11 at 14:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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