?
Solved

SQL find gaps

Posted on 2014-12-11
15
Medium Priority
?
106 Views
Last Modified: 2014-12-19
Hi found a solution for finding gaps in a squence of numbers. But it only Works for a small range.
Tried it for a sequence of 500 number and it worked great and fast.
But when I go up to 1500 the error comes
"An error occurred while executing batch. Error message is: There is not enough space on the disk."
"
Declare @StartNo BIgInt  = 1111000
DECLARE @EndNo BigInt = 1111500

;with data as (
  select ObservationNO
       , row_number() over ( order by ObservationNo desc ) rx
  from Observation
  where CompanyID = 2 and (ObservationNO >=  @StartNo and ObservationNO <=  @EndNo)
)
select tc.ObservationNO + 1 start_gap
        , tn.ObservationNO - 1 end_gap
        , row_number() over (order by tc.ObservationNO asc) rn
from data tc
left join data tn on tn.rx = tc.rx -1
where ( tn.ObservationNO <> tc.ObservationNO + 1 and tc.rx > 1  )
order by tc.rx desc
"


How do I solve this for large number sequences?
0
Comment
Question by:staleb
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 3
  • 2
  • +4
15 Comments
 
LVL 22

Expert Comment

by:plusone3055
ID: 40493807
not enough space on the disk means exactly that
I would try the following in a Development environment

1. back up the database
2. restore it
3. convert the database to simple
4. reduce the size of the transaction logs
 and try again.

Alternatively there is also  2 great articles on SLQ gaps you should check out

https://www.simple-talk.com/sql/t-sql-programming/the-sql-of-gaps-and-islands-in-sequences/

http://technet.microsoft.com/en-us/library/aa175780(v=sql.80).aspx
0
 
LVL 35

Expert Comment

by:ste5an
ID: 40493872
First of all: Your algorithm is not correct. E.g.

USE tempdb;
GO

CREATE TABLE dbo.Numbers ( Number INT );
CREATE CLUSTERED INDEX CIX_Numbers ON dbo.Numbers ( Number );
GO

INSERT  INTO dbo.Numbers
        ( Number )
VALUES  ( RAND() * 100 );
GO 100		 

DECLARE @StartNo BIGINT = 0;
DECLARE @EndNo BIGINT = 25;

WITH    Data
          AS ( SELECT   Number ,
                        ROW_NUMBER() OVER ( ORDER BY Number DESC ) rx
               FROM     dbo.Numbers
               WHERE    Number >= @StartNo
                        AND Number <= @EndNo
             ),
        Gaps
          AS ( SELECT   tc.Number + 1 start_gap ,
                        tn.Number - 1 end_gap ,
                        ROW_NUMBER() OVER ( ORDER BY tc.Number ASC ) rn
               FROM     Data tc
                        LEFT JOIN Data tn ON tn.rx = tc.rx - 1
               WHERE    ( tn.Number <> tc.Number + 1
                          AND tc.rx > 1
                        )
             )
    SELECT  *
    FROM    dbo.Numbers N
            LEFT JOIN Gaps G ON N.Number = G.start_gap
    WHERE   N.Number >= @StartNo
            AND Number <= @EndNo
    ORDER BY N.Number;
GO

DROP TABLE dbo.Numbers;
GO 

Open in new window


The easiast approach would be a number tally to avoid the massiv spill to tempdb.
0
 
LVL 143

Expert Comment

by:Guy Hengel [angelIII / a3]
ID: 40493959
0
NFR key for Veeam Agent for Linux

Veeam is happy to provide a free NFR license for one year.  It allows for the non‑production use and valid for five workstations and two servers. Veeam Agent for Linux is a simple backup tool for your Linux installations, both on‑premises and in the public cloud.

 
LVL 22

Expert Comment

by:plusone3055
ID: 40493990
*kneels before angellll*
0
 
LVL 57

Expert Comment

by:HainKurt
ID: 40494006
may be useful... finds first number in gap... do you need all id's in a gap? for example if id = 6,7,8 missing, do you need all, or just 6 is enough?

declare @StartNo as int=3;
declare @EndNo as int=12;
with t as (
select 1 id
union select 2 union select 3 union select 5 union select 7 union select 10 
union select 11  union select 12 union select 13
)
select t1.id+1 missing from t t1 full join t t2 on t1.id=t2.id-1
where t2.id is null
and t1.id between @StartNo and @EndNo;

missing
4
6
8

Open in new window


also, what is you max id? 3 digits? 4 digits? 6 digits?
0
 
LVL 57

Expert Comment

by:HainKurt
ID: 40494042
here is another approach to find all gaps...

declare @StartNo as int=3;
declare @EndNo as int=12;

with t as (
select 1 id
union select 2 union select 3 union select 5 union select 7 union select 10 
union select 11  union select 12 union select 13
),
n as (select 0 n union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9),
nx6 as (select n5.n*100000+n4.n*10000+n3.n*1000+n2.n*100+n1.n*10+n0.n n from n n0, n n1, n n2, n n3, n n4, n n5)
select nx6.n 
from nx6
left join t on nx6.n=t.id 
where t.id is null and nx6.n between @StartNo and @EndNo

n
4
6
8
9

Open in new window

0
 
LVL 57

Expert Comment

by:HainKurt
ID: 40494058
you can create some views like

create view n as (select 0 n union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9)
-- 0,1,2,...,9

create view nx2 as (select n1.n*10+n0.n n from n n0, n n1)
--0,1,2,...,99

...

create view nx6 as (select n5.n*100000+n4.n*10000+n3.n*1000+n2.n*100+n1.n*10+n0.n n from n n0, n n1, n n2, n n3, n n4, n n5)
--0,1,2,...,999999

then just this will give you gaps:

declare @StartNo as int=3;
declare @EndNo as int=12;

select nx6.n 
from nx6 left join MyTable t on nx6.n=t.id 
where t.id is null and nx6.n between @StartNo and @EndNo

Open in new window

0
 
LVL 69

Expert Comment

by:Scott Pletcher
ID: 40494601
Itzik Ben-Gan did the definitive "Gaps and Islands" sql performance-wise.  You can find it on the web and/or in his books.
0
 
LVL 23

Expert Comment

by:Racim BOUDJAKDJI
ID: 40496597
Perhaps below could help...at least logically...

If you can create a clustered index on the values
for numbers...(make sure there is at least one index including the column)
create clustered index IX_Number on Numbers(Number);

select A.Number as current, B.Number as next, B.Number-A.Number as gap
from Numbers A inner join (select top 1 Number from Numbers) B on B.Number > A.Number
where (B.Number-A.Number) > 1

Open in new window


for datetime...
create clustered index IX_Dates on Dates(DateR);

select A.DateR as current, B.DateR as next, datediff(d, A.DateR, B.DateR) as gap
from Dates A inner join (select top 1 DateR from Dates) B on B.DateR > A.DateR
where datediff(d, A.DateR, B.DateR) > 1

Open in new window


If you can't create a clustered index...
select A.Number as current, min(B.Number-A.Number) as gap
from Numbers A inner join Numbers B on B.Number > A.Number
group by A.Number
having min(B.Number-A.Number)  > 1

Open in new window

0
 

Author Comment

by:staleb
ID: 40498784
Hi
Will look through the different solutions tomorrow.
Was hit by the flu, so havent been able to work.

Some have asked for how many digits in the ID, and it can be up to 10digits.
And therfore I need  the gaps in range:
so if 102000 through 102050 it should say 102000 - 102050  as the sql I found does (start_gap, end-Gap)
0
 
LVL 57

Expert Comment

by:HainKurt
ID: 40505941
i will help you :)

here it is:

with t as (
select 10 ObservationNO 
union select 11 union select 12 union select 14 union select 16 union select 19
union select 20 union select 23 union select 24 union select 26 union select 28 union select 29
union select 30 union select 31 union select 34 union select 38 union select 39
),
x as (select t.ObservationNO, row_number() over (order by ObservationNO) rn from t)
select x1.ObservationNO+1 gap_start, x2.ObservationNO-1 gap_end
from x x1 inner join x x2 on x1.rn=x2.rn-1
where x1.ObservationNO != x2.ObservationNO-1
and x1.ObservationNO between 20 and 36

gap_start	gap_end
21	22
25	25
27	27
32	33
35	37

Open in new window


have fun...
0
 
LVL 57

Accepted Solution

by:
HainKurt earned 2000 total points
ID: 40505955
solution embedded into yours

DECLARE @StartNo BIgInt  = 1111000;
DECLARE @EndNo BigInt = 1111500;

with
x as (
  select ObservationNO, row_number() over (order by ObservationNO) rn
    from Observation t
   where CompanyID = 2 and ObservationNO >=  @StartNo and ObservationNO <=  @EndNo
)
select x1.ObservationNO+1 gap_start, x2.ObservationNO-1 gap_end
  from x x1 inner join x x2 on x1.rn=x2.rn-1
 where x1.ObservationNO != x2.ObservationNO-1

Open in new window

0
 

Author Comment

by:staleb
ID: 40506422
Thanks HainKurt
I will look into it, it seems to work perfectøy for my purpose
0
 
LVL 57

Expert Comment

by:HainKurt
ID: 40507145
just make sure you have a index starting with ObservationNO column on this table...
just for performance thing...
0
 

Author Closing Comment

by:staleb
ID: 40509187
Just what I was looking for
0

Featured Post

Get MongoDB database support online, now!

At Percona’s web store you can order your MongoDB database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card. Handle your MongoDB database support now!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article explains how to reset the password of the sa account on a Microsoft SQL Server.  The steps in this article work in SQL 2005, 2008, 2008 R2, 2012, 2014 and 2016.
Load balancing is the method of dividing the total amount of work performed by one computer between two or more computers. Its aim is to get more work done in the same amount of time, ensuring that all the users get served faster.
Via a live example, show how to setup several different housekeeping processes for a SQL Server.
Viewers will learn how to use the SELECT statement in SQL to return specific rows and columns, with various degrees of sorting and limits in place.
Suggested Courses

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question