Solved

SQL find gaps

Posted on 2014-12-11
15
104 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
Microsoft Certification Exam 74-409

Veeam® is happy to provide the Microsoft community with a study guide prepared by MVP and MCT, Orin Thomas. This guide will take you through each of the exam objectives, helping you to prepare for and pass the examination.

 
LVL 22

Expert Comment

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

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 53

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 53

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 53

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 53

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 53

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

NEW Veeam Agent for Microsoft Windows

Backup and recover physical and cloud-based servers and workstations, as well as endpoint devices that belong to remote users. Avoid downtime and data loss quickly and easily for Windows-based physical or public cloud-based workloads!

Question has a verified solution.

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

Ever wondered why sometimes your SQL Server is slow or unresponsive with connections spiking up but by the time you go in, all is well? The following article will show you how to install and configure a SQL job that will send you email alerts includ…
In the first part of this tutorial we will cover the prerequisites for installing SQL Server vNext on Linux.
Via a live example, show how to extract insert data into a SQL Server database table using the Import/Export option and Bulk Insert.
Viewers will learn how the fundamental information of how to create a table.

734 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