8 Replies Latest reply: Feb 1, 2013 6:37 PM by chris227 RSS

    Looking for gaps (SQL, not PL/SQL)

    988543
      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
          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
            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
              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
                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
                  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
                    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
                      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
                        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