Solved

SQL find gaps

Posted on 2014-12-11
15
99 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
  • 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 32

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 142

Expert Comment

by:Guy Hengel [angelIII / a3]
ID: 40493959
0
 
LVL 22

Expert Comment

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

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 51

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 51

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
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 69

Expert Comment

by:ScottPletcher
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 51

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 51

Accepted Solution

by:
HainKurt 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 51

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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
SQL Query Syntax Error 9 32
MS SQL 2014 get SPIDs of users 6 25
separate column 24 20
Trouble connecting to SqlServer database 4 31
In this article I will describe the Backup & Restore method as one possible migration process and I will add the extra tasks needed for an upgrade when and where is applied so it will cover all.
The Delta outage: 650 cancelled flights, more than 1200 delayed flights, thousands of frustrated customers, tens of millions of dollars in damages – plus untold reputational damage to one of the world’s most trusted airlines. All due to a catastroph…
Via a live example, show how to backup a database, simulate a failure backup the tail of the database transaction log and perform the restore.
Using examples as well as descriptions, and references to Books Online, show the documentation available for datatypes, explain the available data types and show how data can be passed into and out of variables.

707 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now