Solved

SQL find gaps

Posted on 2014-12-11
15
105 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 34

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
What Is Transaction Monitoring and who needs it?

Synthetic Transaction Monitoring that you need for the day to day, which ensures your business website keeps running optimally, and that there is no downtime to impact your customer experience.

 
LVL 22

Expert Comment

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

Expert Comment

by:Huseyin KAHRAMAN
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 55

Expert Comment

by:Huseyin KAHRAMAN
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 55

Expert Comment

by:Huseyin KAHRAMAN
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 55

Expert Comment

by:Huseyin KAHRAMAN
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 55

Accepted Solution

by:
Huseyin KAHRAMAN earned 500 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 55

Expert Comment

by:Huseyin KAHRAMAN
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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.
I have a large data set and a SSIS package. How can I load this file in multi threading?
Via a live example, show how to shrink a transaction log file down to a reasonable size.
Viewers will learn how the fundamental information of how to create a table.

688 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