This discussion is archived
8 Replies Latest reply: Feb 1, 2013 4:37 PM by chris227 RSS

Looking for gaps (SQL, not PL/SQL)

988543 Newbie
Currently Being Moderated
Hi,

This is a SQL (not PL/SQL) question.

Let's say I have the following table:

COLtype          COLnumber
AA               1
AA               2
AA               4
AA               5
BB               1
BB               2
BB               3
BB               5
CC               1
CC               5

How do I find all gaps? I expect a result:

COLtype          COLnumber
AA               3
BB               4
CC               2
CC               3
CC               4


I tried to use query:

SELECT COLnumber + 1, COLtype FROM table a1
WHERE NOT EXISTS (
SELECT NULL FROM table a2
     WHERE
a1.COLtype = a2.COLtype
and (a2.COLnumber = a1.COLnumber + 1)
)

but I received as result:

COLtype          COLnumber
AA               3
AA               6
BB               4
BB               6
CC               2
CC               3
CC               4
CC               6

Any other solutions, ideas?

Thanks in advance!
Gaspar

Edited by: 985540 on 2013-02-01 02:59
  • 1. Re: Looking for gaps (SQL, not PL/SQL)
    grir28 Newbie
    Currently Being Moderated
    Hi, something like that could help:
    SELECT 
      groups.COLtype, nums.no 
    FROM 
      (Select COLtype, min(COLnumber) mi, max(COLnumber) ma 
       From your_table Group By COLtype) groups,                          /* all "groups" */
      (Select level no From dual 
       Connect By level <= (Select max(COLnumber) From your_table)) nums  /* all possible numbers from 1 to max */
    WHERE nums.no between groups.mi and groups.ma 
      and Not Exists(Select 1 From your_table 
                     Where your_table.COLtype = groups.COLtype 
                       and your_table.COLnumber = nums.no)
  • 2. Re: Looking for gaps (SQL, not PL/SQL)
    Purvesh K Guru
    Currently Being Moderated
    One way of doing it:
    with data as
    (
      select 'AA' col1, 1 col2 from dual union all
      select 'AA', 2 from dual union all
      select 'AA', 4 from dual union all
      select 'AA', 5 from dual union all
      select 'BB', 1 from dual union all
      select 'BB', 2 from dual union all
      select 'BB', 3 from dual union all
      select 'BB', 5 from dual union all
      select 'CC', 1 from dual union all
      select 'CC', 5 from dual
    ),
    get_data as
    (
      select *
        from (
              select col1,
                     col2,
                     case
                      when col2 + 1 != lead(col2) over (partition by col1 order by col2) 
                        then lead(col2) over (partition by col1 order by col2)
                      else
                        null
                     end nxt_col2
                from data
             )
       where nxt_col2 is not null
    )
    select col1, 
           col2 + level missing_col2
      from get_data
    connect by level <= nxt_col2 - col2 - 1
           and prior col1 = col1
           and prior dbms_random.value is not null
      order by col1, missing_col2;
    
    COL1 MISSING_COL2           
    ---- ---------------------- 
    AA   3                      
    BB   4                      
    CC   2                      
    CC   3                      
    CC   4
  • 3. Re: Looking for gaps (SQL, not PL/SQL)
    Bawer Journeyer
    Currently Being Moderated
    another way:
    with t as
    (
      select 'AA' col1, 1 col2 from dual union all
      select 'AA', 2 from dual union all
      select 'AA', 4 from dual union all
      select 'AA', 5 from dual union all
      select 'BB', 1 from dual union all
      select 'BB', 2 from dual union all
      select 'BB', 3 from dual union all
      select 'BB', 5 from dual union all
      select 'CC', 1 from dual union all
      select 'CC', 5 from dual
    )
    select * from ( select distinct col1 from t ) s1
    cross join ( select level as col2 from dual connect by level <= ( select max(col2) from t) ) s2
    where (s1.col1, s2.col2 ) not in (select col1, col2 from t)
  • 4. Re: Looking for gaps (SQL, not PL/SQL)
    988543 Newbie
    Currently Being Moderated
    Thank you very much for all the ideas.

    My example started and ended in small numbers.
    However, I'm really starting number 100,000 (min (COLnumber)) and ending at 999.999 (max (COLnumber)), the proposed solutions do not work effectively.

    COLtype     COLnumber
    AA     100.001
    AA     100.002
    AA     100.004
    AA     100.005
    ..     .. (no other gaps)
    AA     101.005
    BB     100.001
    BB     100.002
    BB     100.003
    BB     100.005
    ..     .. (no other gaps)
    BB     100.902
    CC     100.001
    CC     100.005
    ..     .. (no other gaps)
    CC     100.205

    Edited by: 985540 on 2013-02-01 05:30
  • 5. Re: Looking for gaps (SQL, not PL/SQL)
    Hoek Guru
    Currently Being Moderated
    the proposed solutions do not work effectively.
    What are we supposed to deduct from from such a statement?
    Is there anything wrong with performance or the results?

    Please post a small testcase as explained and demonstrated in #7, 8 and 9 @ {message:id=9360002}
  • 6. Re: Looking for gaps (SQL, not PL/SQL)
    Solomon Yakobson Guru
    Currently Being Moderated
    First let define gaps. If we have:
    COLtype COLnumber
    AA      3
    AA      4
    Are:
    COLtype COLnumber
    AA      1
    AA      2
    missing? If so is there an assumption COLnumber always starts with 1 or we just looking for gaps between existing numbers? For now I'll assume we are looking for gaps between existing numbers. Then:
    with t as (
               select  coltype,
                       colnumber,
                       lag(colnumber,1,colnumber - 1)
                         over(
                              partition by coltype
                              order by colnumber
                             ) prev_colnumber
                 from  tbl
              )
    select  coltype,
            colnumber - column_value colnumber
      from  t,
            table(
                  cast(
                       multiset(
                                select  level
                                  from  dual
                                  connect by level < colnumber - prev_colnumber
                               )
                       as sys.OdciNumberList
                      )
                 )
      where colnumber - prev_colnumber > 1
      order by coltype,
               colnumber
    /
    
    CO  COLNUMBER
    -- ----------
    AA          3
    BB          4
    CC          2
    CC          3
    CC          4
    
    SQL> explain plan for
      2  with t as (
      3             select  coltype,
      4                     colnumber,
      5                     lag(colnumber,1,colnumber - 1)
      6                       over(
      7                            partition by coltype
      8                            order by colnumber
      9                           ) prev_colnumber
     10               from  tbl
     11            )
     12  select  coltype,
     13          colnumber - column_value colnumber
     14    from  t,
     15          table(
     16                cast(
     17                     multiset(
     18                              select  level
     19                                from  dual
     20                                connect by level < colnumber - prev_colnumber
     21                             )
     22                     as sys.OdciNumberList
     23                    )
     24               )
     25    where colnumber - prev_colnumber > 1
     26    order by coltype,
     27             colnumber
     28  /
    
    Explained.
    
    SQL> @?\rdbms\admin\utlxpls
    
    PLAN_TABLE_OUTPUT
    ----------------------------------------------------------------------------------------------------
    Plan hash value: 1739894384
    
    ----------------------------------------------------------------------------------------------------
    | Id  | Operation                            | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
    ----------------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT                     |      | 81680 |  2552K|       |   991   (1)| 00:00:12 |
    |   1 |  SORT ORDER BY                       |      | 81680 |  2552K|  3216K|   991   (1)| 00:00:12 |
    |   2 |   NESTED LOOPS                       |      | 81680 |  2552K|       |   277   (1)| 00:00:04 |
    |*  3 |    VIEW                              |      |    10 |   300 |       |     4  (25)| 00:00:01 |
    |   4 |     WINDOW SORT                      |      |    10 |   170 |       |     4  (25)| 00:00:01 |
    |   5 |      TABLE ACCESS FULL               | TBL  |    10 |   170 |       |     3   (0)| 00:00:01 |
    
    PLAN_TABLE_OUTPUT
    ----------------------------------------------------------------------------------------------------
    |   6 |    COLLECTION ITERATOR SUBQUERY FETCH|      |  8168 | 16336 |       |    27   (0)| 00:00:01 |
    |*  7 |     CONNECT BY WITHOUT FILTERING     |      |       |       |       |            |          |
    |   8 |      FAST DUAL                       |      |     1 |       |       |     2   (0)| 00:00:01 |
    ----------------------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       3 - filter("COLNUMBER"-"PREV_COLNUMBER">1)
       7 - filter(LEVEL<:B1-:B2)
    
    
    PLAN_TABLE_OUTPUT
    ----------------------------------------------------------------------------------------------------
    Note
    -----
       - dynamic sampling used for this statement (level=2)
    
    25 rows selected.
    
    SQL> 
    SY.
  • 7. Re: Looking for gaps (SQL, not PL/SQL)
    chris227 Guru
    Currently Being Moderated
    with data as ( 
    select 'AA' COLtype, to_number(100001) COLnumber from dual union all
    select 'AA', to_number(100002) from dual union all
    select 'AA', to_number(100004) from dual union all
    select 'AA', to_number(100005) from dual union all
    select 'A' COLtype, to_number(100001) COLnumber from dual union all
    select 'A', to_number(100002) from dual union all
    select 'A', to_number(100004) from dual union all
    select 'A', to_number(100003) from dual
    )
    , numbers(mn, mx) as (
     select
     min(colnumber) mn -- replace with 100000 if wanted
    ,max(colnumber) mx -- replace with 999999 if wanted
    from data
    union all
     select
     mn + 1
    ,mx
    from numbers
    where
    mn+1<=mx
    )
    
    select
    coltype,mn
    from numbers
    left outer join
    data
    partition by (coltype)
    on
    mn=colnumber
    where
    colnumber is null
    order by coltype, mn
    
    COLTYPE MN 
    A 100005 
    AA 100003 
  • 8. Re: Looking for gaps (SQL, not PL/SQL)
    chris227 Guru
    Currently Being Moderated
    Another one
    with data as ( 
    select 'AA' COLtype, 100001 COLnumber from dual union all
    select 'AA', 100002 from dual union all
    select 'AA', 100004 from dual union all
    select 'AA', 100005 from dual
    )
    
    select
     COLTYPE
    ,C
    from (
    select 
    *
    from data 
    model
    partition by (COLtype)
    dimension by (COLnumber c)
    measures( COLnumber)
    rules (
    COLnumber[for c from 100000 to 100005 increment 1]=
    COLnumber[cv()]
    ))
    where colnumber is null
    
    COLTYPE     C
    AA     100000
    AA     100003

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points