Skip to Main Content
  • Questions
  • Find the number in list which is not present in Database column

Breadcrumb

May 4th

Question and Answer

Connor McDonald

Thanks for the question, Nitin.

Asked: January 13, 2017 - 3:13 pm UTC

Last updated: January 18, 2017 - 1:42 am UTC

Version: 11g

Viewed 1000+ times

You Asked

I have one requirement where I need to find the first missing number in the List which is not there in Database(Oracle) column.

Scenario is like this :

Table 1:

Link to table image is here :-
https://i.stack.imgur.com/iXm6N.png


From the above table I am thinking to make 3 lists

List<Integer> lst1 = new ArrayList<Integer>();
List<Integer> lst2 = new ArrayList<Integer>();
List<Integer> lst3 = new ArrayList<Integer>();
lst1 -> [0,1,2,3,4,5,6....1000]

lst2 -> [a0,a1,a2,a3,a4,a5,a6....a1000]

lst3 -> [b0,b1,b2,b3,b4,b5,b6....b1000]

As of now the lists contains approx 1000 values in the serial order.

Now I have a Database table as below

Link to table image :-
https://i.stack.imgur.com/OvAmW.png


How can I match the lsts with Range column. I need to find what value from lsts is not present in this table ?

Like in this case, if we see from the "lst1" the first available value which is not there in the table is "1" then next available value is "3" and then 5.6...so on. Similarly for "lst2" the first missing value is "a3"

Is there any way to do ?


-----------------------------------------------------------------

Someone suggested a solution on stackoverflow as below:-
-----------------------------------------------------------------

The below query obtains a prefix and numeric valuest of range_start and range_end.
For simplicity of examples I limited ranges to 0-5
SELECT  lstname,
        regexp_substr( rangestart, '[^0-9]') AS Prefix,
        regexp_substr( rangestart, '[0-9]') AS r_start,
        regexp_substr( rangeend, '[0-9]') AS r_end
FROM table_1

LSTNAME |PREFIX |R_START |R_END |
--------|-------|--------|------|
Lst1    |       |0       |5     |
Lst2    |a      |0       |5     |
Lst3    |b      |0       |5     |


The below query will generate all values for ranges using the above query as a subquery.
Please note that CROSS JOIN LATERAL works on version Oracle 12c and later, if you are using earlier version then this query must be rewriten.

SELECT lstname, prefix || val AS val
FROM (
        SELECT  lstname,
                regexp_substr( rangestart, '[^0-9]') AS Prefix,
                regexp_substr( rangestart, '[0-9]') AS r_start,
                regexp_substr( rangeend, '[0-9]') AS r_end
        FROM table_1
) x
CROSS JOIN LATERAL (
   SELECT LEVEL - 1 + x.r_start AS val
   FROM dual
   CONNECT BY LEVEL <= x.r_end - x.r_start + 1
)

LSTNAME |VAL |
--------|----|
Lst1    |0   |
Lst1    |1   |
Lst1    |2   |
Lst1    |3   |
Lst1    |4   |
Lst1    |5   |
Lst2    |a0  |
Lst2    |a1  |
Lst2    |a2  |
Lst2    |a3  |
Lst2    |a4  |
Lst2    |a5  |
Lst3    |b0  |
Lst3    |b1  |
Lst3    |b2  |
Lst3    |b3  |
Lst3    |b4  |
Lst3    |b5  |

And now say that table_2 contains the following values:

SELECT * FROM table_2

RANGE |
------|
3     |
a0    |
a1    |
a5    |
b3    |
b4    |
b5    |


To find missing values just LEFT JOIN the above queries to this table and filter out not null values.
Please note that I am using "RANGE" within quotes as a column name in this example because RANGE is reserved word in Oracle

SELECT lstname, val
FROM (
        SELECT lstname, prefix || val AS val
        FROM (
                SELECT  lstname,
                        regexp_substr( rangestart, '[^0-9]') AS Prefix,
                        regexp_substr( rangestart, '[0-9]') AS r_start,
                        regexp_substr( rangeend, '[0-9]') AS r_end
                FROM table_1
        ) x
        CROSS JOIN LATERAL (
           SELECT LEVEL - 1 + x.r_start AS val
           FROM dual
           CONNECT BY LEVEL <= x.r_end - x.r_start + 1
        )
) XX
LEFT JOIN table_2 t2
ON t2."RANGE" = xx.val
WHERE t2."RANGE" IS NULL
ORDER BY 1, 2;

LSTNAME |VAL |
--------|----|
Lst1    |0   |
Lst1    |1   |
Lst1    |2   |
Lst1    |4   |
Lst1    |5   |
Lst2    |a2  |
Lst2    |a3  |
Lst2    |a4  |
Lst3    |b0  |
Lst3    |b1  |
Lst3    |b2  |



---------------
I think above solution should work. But the problem is "CROSS JOIN LATERAL" thing. I am using Oracle 11g and this keyword is not working in 11g.

Does anyone knows what will be the alternative of this in 11g or any other alternative solution to the whole problem ?

Thanks
Nitin

and Chris said...

The commenters on SO already gave you the "correct" solution:

Create a table storing all the values in the ranges for your "lsts". Then do a not exists between them:

create table vals (
  val varchar2(10)
);

create table t (
  rnge varchar2(10)
);

insert into vals 
  select rownum from dual connect by level <= 10;
 
insert into t values ('0');
insert into t values ('2');
insert into t values ('4');
commit;

select * from vals v
where  not exists (
  select * from t
  where  t.rnge = v.val
);

VAL  
1    
6    
10   
3    
5    
9    
7    
8  

Rating

  (3 ratings)

Is this answer out of date? If it is, please let us know via a Comment

Comments

Why generate all the values?

Stew Ashton, January 13, 2017 - 7:02 pm UTC

You can calculate a number range, so find the lowest free number within that range.

Notice the WHERE clause in the LOOKUP subquery that limits the lookup table to whatever you want it to be.
drop table t1 purge;
create table t1(lstname, range_start, range_end) as
select 1, '1', '100' from dual
union all
select 2, 'a1', 'a100' from dual
union all
select 3, 'b1', 'b100' from dual;

drop table t2 purge;
create table t2(rnge, status, nbr) as
select null||(level*2), 'Assigned', 'M12'
from dual
connect by level <= 100000;

with lookup as (
  select regexp_substr(range_start, '[^0-9]') prefix,
  to_number(regexp_replace(range_start, '[^0-9]')) range_start,
  to_number(regexp_replace(range_end, '[^0-9]')) range_end
  from t1
  where lstname between 1 and 2
)
, data as (
  select t.prefix, t.prev_range_num from (
    select prefix,
    range_num,
    lag(range_num,1,0) over(partition by prefix order by range_num) prev_range_num
    from (
      select regexp_substr(rnge, '[^0-9]') prefix,
      to_number(regexp_replace(rnge, '[^0-9]')) range_num
      from t2
    )
  ) t
  join lookup l on decode(l.prefix, t.prefix, 0, 1) = 0
  and prev_range_num < range_num - 1
  and prev_range_num+1 between range_start and range_end
)
select prefix||(prev_range_num+1) free_range
from data
where rownum = 1;

FREE_RANGE
----------
1

Connor McDonald
January 14, 2017 - 7:51 am UTC

Thanks Stew

Correction

Stew Ashton, January 14, 2017 - 7:31 am UTC

My previous effort fails if the first free "number" is after the last one already in use.
with lookup as (
  select regexp_substr(range_start, '[^0-9]') prefix,
  to_number(regexp_replace(range_start, '[^0-9]')) range_start,
  to_number(regexp_replace(range_end, '[^0-9]')) range_end
  from t1
  where lstname between 1 and 1
)
, data as (
  select t.prefix, t.prev_range_num from (
    select prefix,
    range_num,
    lag(range_num,1,0) over(partition by prefix order by range_num) prev_range_num
    from (
      select regexp_substr(rnge, '[^0-9]') prefix,
      to_number(regexp_replace(rnge, '[^0-9]')) range_num
      from t2
      union all
      select prefix, range_end+1 from lookup -- correction
    )
  ) t
  join lookup l on decode(l.prefix, t.prefix, 0, 1) = 0
  and prev_range_num < range_num - 1
  and prev_range_num+1 between range_start and range_end
)
select prefix||(prev_range_num+1) free_range
from data
where rownum = 1;

Nitin, January 17, 2017 - 1:43 am UTC

Thanks Guys.

But if there are 10K of rows in both tables then joining them will decrease the performance.

What can we do about that ?


Nitin
Connor McDonald
January 18, 2017 - 1:42 am UTC

You have 10,000 lists ?

In any event, just try a benchmark with Stew's final solution.