8 Replies Latest reply on Feb 2, 2013 12:37 AM by chris227

# Looking for gaps (SQL, not PL/SQL)

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

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

Any other solutions, ideas?

Gaspar

Edited by: 985540 on 2013-02-01 02:59
• ###### 1. Re: Looking for gaps (SQL, not PL/SQL)
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)
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)
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)
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)
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)
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.

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)
``````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)
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``````