Missing numbers in a series

Question

Post reply

Missing numbers in a series

Viewing 15 posts - 16 through 30 (of 61 total)

You must be logged in to reply to this topic. Login to reply

Eric M Russell SSC Guru Points: 125522 More actions · Answer 1

-- create and insert a table variable containing missing numbers.

declare @missingnumbers table (n int not null primary key);

insert into @missingnumbers

select 1 union select 2 union select 4 union select 5 union

select 7 union select 8 union select 11 union select 12 union

select 13 union select 15 union select 17 union select 19 union select 20;

-- create and insert a table variable containing all numbers

-- between min(n) and max(n).

declare @allnumbers table (n int not null primary key);

declare @n int, @nmax int;

select @n = min(n), @nmax = max(n) from @missingnumbers;

while @n < @nmax

begin

select @n = @n + 1;

insert into @allnumbers (n) values (@n);

end;

-- left join the 2 tables and return those numbers

-- not contained in the @missingnumbers table.

select a.n

from @allnumbers a

left join @missingnumbers m on m.n = a.n

where m.n is null;

n

-----------

3

6

9

10

14

16

18

"Do not seek to follow in the footsteps of the wise. Instead, seek what they sought." - Matsuo Basho

gurukiran.bhat SSC Veteran Points: 262 More actions · Answer 2

following method worked out for me

for this example i have used table called table1 which has single column column1.

create table table1

(column1 int)

I have inserted values 1,2,3,5,9 in to this table using following query

insert into table1

select 1 union all

select 2 union all

select 3 union all

select 5 union all

select 9 union all

select 10

In the above sequence 0,4,6,7,8 are missing. to find out missed values i have used following method

1. create a temporary table temp_table(later we can drop it)

create table temp_table

(column2 int)

2. following query will insert all the values from 0 to 10 into temp_table

DECLARE @val1 int;

set @val1 = 0;

while (@val1 < (select max(column1) from table1))

begin

insert into temp_table

select @val1

set @val1 = @val1+1

end

3. use exept function of SQl server 2005 to get missed values

select * from temp_table

except

select * from table1

4.delete temp_table

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 3

gurukiran.bhat (5/3/2010)
following method worked out for me
for this example i have used table called table1 which has single column column1.
create table table1
(column1 int)
I have inserted values 1,2,3,5,9 in to this table using following query
insert into table1
select 1 union all
select 2 union all
select 3 union all
select 5 union all
select 9 union all
select 10
In the above sequence 0,4,6,7,8 are missing. to find out missed values i have used following method
1. create a temporary table temp_table(later we can drop it)
create table temp_table
(column2 int)
2. following query will insert all the values from 0 to 10 into temp_table
DECLARE @val1 int;
set @val1 = 0;
while (@val1 < (select max(column1) from table1))
begin
insert into temp_table
select @val1
set @val1 = @val1+1
end
3. use exept function of SQl server 2005 to get missed values
select * from temp_table
except
select * from table1
4.delete temp_table

Yep... that works for gaps of ten rows. Try it on a gap that jumps from 1000000 to 2000000 because some manager decided to use ranges of numbers to isolate customers from different countries.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 4

Folks, I think that just about anything with any form of a Tally table is the wrong way to do it here especially if you have very large gaps for the reasons like the one in my response in the post above. I've got a very old but fast method of doing this and I'll try to remember to post it tonight after work...

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 5

Ok... here's a test table with some huge gaps over a huge range of numbers along with some single row gaps. The code takes about 12 seconds to run on my 8 year old machine. Details are in the comments, as usual...

DROP TABLE #MyTest

GO

--===== Create and populate a 2,000,000 row test table.

-- This first SELECT creates a range of 1 to 1,000,000 unique numbers starting at 10,000,001

SELECT TOP 1000000

MyID = ISNULL(CAST(ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) + 10000000 AS BIGINT),0)

INTO #MyTest

FROM Master.sys.All_Columns ac1,

Master.sys.All_Columns ac2

-- This second SELECT creates a range of 1 to 1,000,000 unique numbers starting at 82,011,000,000,001

UNION ALL

SELECT TOP 1000000

MyID = ISNULL(CAST(ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) + 82011000000000 AS BIGINT),0)

FROM Master.sys.All_Columns ac1,

Master.sys.All_Columns ac2

--===== Create the quintessential Primary Key

-- Takes about 3 seconds to execute.

ALTER TABLE #MyTest

ADD PRIMARY KEY CLUSTERED (MyID)

--===== Delete some know rows to demo the gap detection code

-- This deletes 50 rows spaced 2000 apart in the given range

-- to demo small gaps

DELETE #MyTest

WHERE MyID BETWEEN 82011000400001 AND 82011000500000

AND MyID %2000 = 0

-- This deletes 100,000 rows in a given range to demo large gaps

DELETE #MyTest

WHERE MyID BETWEEN 82011000600001 AND 82011000700000

Here's the gap detection code I spoke of. It takes about 3 seconds to run on that same 8 year old machine. I'm thinking that because of the very large ranges of numbers that a Tally table just isn't going to cut it for stuff like this...

--===== Find the "gap ranges" --This takes 3 seconds on my 8 year old machine

-- Finds trailing edge of "islands" and then computes the gaps

-- This assumes that gaps include any whole number greater than 0

SELECT GapStart = (SELECT ISNULL(MAX(lo.MyID),0)+1

FROM #MyTest lo

WHERE lo.MyID < hi.MyID),

GapEnd = hi.MyID - 1

FROM #MyTest hi

WHERE hi.MyID NOT IN (SELECT MyID + 1 FROM #MyTest)

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

ralm Hall of Fame Points: 3156 More actions · Answer 6

DECLARE @Numbers TABLE (N INT)

DECLARE @MissingNumbers TABLE (N INT)

Declare @vMax int

Declare @vMIn int

INSERT INTO @Numbers

VALUES (50000001),(50000002),(50000019),(51000000)

--VALUES (1),(2),(19),(20)

Set @vMax = (Select MAX(N) from @Numbers)

Set @vMin = (Select MIN(N) from @Numbers)

while(@vMax > @vMIn)

begin

If NOT Exists( Select 1 from @Numbers Where N = @vMIn)

BEGIN

Insert into @MissingNumbers

Select @vMIn

END

Set @vMIn = @vMIn + 1

end

Select * from @MissingNumbers

^{[font="Verdana"]Regards,
Rals[/font].}

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 7

rajesh.subramanian (5/4/2010)
DECLARE @Numbers TABLE (N INT)
DECLARE @MissingNumbers TABLE (N INT)
Declare @vMax int
Declare @vMIn int
INSERT INTO @Numbers
VALUES (50000001),(50000002),(50000019),(51000000)
--VALUES (1),(2),(19),(20)
Set @vMax = (Select MAX(N) from @Numbers)
Set @vMin = (Select MIN(N) from @Numbers)
while(@vMax > @vMIn)
begin
If NOT Exists( Select 1 from @Numbers Where N = @vMIn)
BEGIN
Insert into @MissingNumbers
Select @vMIn
END
Set @vMIn = @vMIn + 1
end
Select * from @MissingNumbers

Uh huh... try that on the data example I posted above and tell me how long it takes to run. Shoot, for that matter, just insert the values you have commented out along with the ones that you're currently using in your code. A While loop just isn't the answer for something like this (or most anything else), Rajesh.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

ralm Hall of Fame Points: 3156 More actions · Answer 8

Yes jeff you are right. Just started to use this forum... I have just posted what I have tried first when I read that.

I know even in our product we have slot ranges for each customers (but luckily we don't have a requirement to find the missing sequence). I agree your point on using the while in queries.. Thanks..

regards,

Rajesh Subramanian

^{[font="Verdana"]Regards,
Rals[/font].}

Paul White SSC Guru Points: 150467 More actions · Answer 9

Jeff Moden (5/3/2010)
...Here's the gap detection code I spoke of. It takes about 3 seconds to run on that same 8 year old machine. I'm thinking that because of the very large ranges of numbers that a Tally table just isn't going to cut it for stuff like this...

I like this code a lot. It is even slightly faster than the ROW_NUMBER() code I usually use for gaps problems.

It wouldn't be me if I didn't pick at something, so here it is: although it is safe here since MyID is a PRIMARY KEY and therefore NOT NULL, I don't like to see NOT IN because of the weirdness that happens if the IN list contains a NULL. Rewriting with NOT EXISTS or something equivalent would seem to be a happier idea.

Hey, would anyone like to see the SQLCLR solution to this same problem? 😉

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

ColdCoffee SSC-Dedicated Points: 39971 More actions · Answer 10

Paul White NZ (5/4/2010)
Hey, would anyone like to see the SQLCLR solution to this same problem? 😉

I would love to, Mr.BlackCap! Please shoot it out!

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 11

rajesh.subramanian (5/4/2010)
Yes jeff you are right. Just started to use this forum... I have just posted what I have tried first when I read that.
I know even in our product we have slot ranges for each customers (but luckily we don't have a requirement to find the missing sequence). I agree your point on using the while in queries.. Thanks..
regards,
Rajesh Subramanian

Thanks for the feedback, Rajesh... and welcome aboard!

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003870 More actions · Answer 12

Paul White NZ (5/4/2010)
Hey, would anyone like to see the SQLCLR solution to this same problem? 😉

Absolutely. You know me... I never turn down knowledge. Thanks, Paul.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 13

Jeff Moden (5/4/2010)
Absolutely. You know me... I never turn down knowledge. Thanks, Paul.

Hey Jeff and Mr Coffee - I'm not saying a SQLCLR solution won't suck (it might do!) but since there is interest, I'll have a go later. Just a bit busy with QotD at the moment 😀

My objective would be to get close to Jeff's rocket code performance here, I don't think there's much chance of a win...but hey I am awesome so anything's possible :laugh:

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

WayneS SSC Guru Points: 95409 More actions · Answer 14

Paul White NZ (5/4/2010)
My objective would be to get close to Jeff's rocket code performance here, I don't think there's much chance of a win...but hey I am awesome so anything's possible :laugh:

I've always been impressed with how humble Paul is... :-D:-P

Wayne
Microsoft Certified Master: SQL Server 2008
Author - SQL Server T-SQL Recipes

If you can't explain to another person how the code that you're copying from the internet works, then DON'T USE IT on a production system! After all, you will be the one supporting it!

Links:
For better assistance in answering your questions
Performance Problems
Common date/time routines
Understanding and Using APPLY Part 1 & Part 2

Paul White SSC Guru Points: 150467 More actions · Answer 15

WayneS (5/4/2010)
I've always been impressed with how humble Paul is... :-D:-P

Yeah - I'm especially awesomely brilliant at being humble :w00t:

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi