Answered by:
how to find gap ranges in range based entry.

Hi !
i have a table "bridgeP"
with cols bridgePid int, fromlen decimal(10,2) , tolen decimal(10,2)
bridgePid is autogenerated, and fromlen and tolen has lenght of painting done of bridge.
ex if bridge is of 100 metere and painting of bridge is done from 10 m to 20 m , 40 m to 50 m etc.
so i would like to find the gaps for which painting is not done.
the problem is entry in table has overlap as shown below.
bridgepid , fromlen , tolen
1 , 10 ,20
2 ,18 ,21
3 ,11 ,20
4 ,40 ,50
5 ,19 ,35
so please find solution , with overlaps , i have found a solution by using loop.looping through the record of bridgeP
table one by one in asceding order of fromlen and finding out gap and inserting it into new table.
so please provide me solution with out loop.
yours sincerely
 Edited by rajemessage Wednesday, August 22, 2012 3:39 AM
Question
Answers

Declare @BridgeP Table(BridgePID int, FromLen Int, ToLen Int); Declare @MaxBridgeLenght int = 100; Insert into @BridgeP Values (1,10,20) , (2,18,21) , (3,11,20) , (4,40,50) , (5,19,35) ;With CTE1 As ( Select BridgePID, FromLen AS MyLength, 1 As indicator , Null As ToRN , Row_Number() Over(Order by FromLen, BridgePID) As FromRN From @BridgeP Union All Select BridgePID, ToLen AS MyLength, 1 As indicator , Row_Number() Over(Order by ToLen, BridgePID) As ToRN , NULL As FromRN From @BridgeP ) , CTE2 As ( Select * , Row_Number() Over(Order by MyLength, Indicator Desc, BridgePID) As FromToRN From CTE1 ) , CTE3 As ( Select MyLength , Row_Number() Over(Order by MyLength) As MyRN From CTE2 Where Coalesce(FromRn  (FromToRN  FromRN)  1, (FRomToRN  ToRN)  ToRN) = 0 ) , CTE4 As ( Select BridgeLength , (Row_Number() Over(Order by BridgeLength)  1) / 2 As MyGroup From ( Select B.BridgeLength From (Values (0), (@MaxBridgeLenght)) B(BridgeLength) Union All Select Case When MyRN % 2 = 1 and MyLength > 0 Then MyLength  1 When MyRN % 2 = 0 and MyLength < @MaxBridgeLenght Then MyLength + 1 When MyRN % 2 = 1 and MyLength = 0 Then 0 When MyRN % 2 = 0 and MyLength = @MaxBridgeLenght Then @MaxBridgeLenght End From CTE3 ) X ) Select Min(Bridgelength) As GapStart, Max(Bridgelength) As GapEnd From CTE4 Group By MyGroup Having Min(Bridgelength) <> Max(Bridgelength)
 Blog: MSBICOE.com  MCITP  BI, SQL Developer & DBA
Hate to mislead others, if I'm wrong slap me. Thanks!
 Marked as answer by rajemessage Saturday, August 25, 2012 5:13 AM

I see here two problems in one. The first one would be packing overlapping ranges, and then identifying gaps.
Itzik BenGan included these two problems in his last book about window functions. He explains the solutions for SQL Server 2012 and also for previous versions.
Microsoft® SQL Server® 2012 HighPerformance TSQL Using Window Functions
http://shop.oreilly.com/product/0790145323088.doI am going to use his approach to tackle your question.
SET NOCOUNT ON; USE tempdb; GO Declare @BridgeP Table( BridgePID int, FromLen Decimal(14,4), ToLen Decimal(14,4) ); Declare @MaxBridgeLenght Decimal(14,4) = 100.0000; Insert into @BridgeP Values (1,10.0002,20.0004) , (2,18.0000,21.0004) , (3,11.12345,20.0002) , (4,40.0000,50.0003) , (5,19.1100,35.0000) ; WITH C0 AS ( SELECT FromLen, ToLen FROM @BridgeP UNION ALL SELECT FromLen, ToLen FROM (VALUES (0, 0), (100, 100) ) AS T(FromLen, ToLen) ) , C1 AS ( SELECT FromLen AS ln, +1 AS [type], 1 AS sub FROM C0 UNION ALL SELECT ToLen AS ln, 1 AS [type], 0 AS sub FROM C0 ) , C2 AS ( SELECT ln, SUM([type]) OVER( ORDER BY ln, [type] DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW )  sub AS cnt FROM C1 ) , C3 AS ( SELECT ln, ((ROW_NUMBER() OVER(ORDER BY ln)  1) / 2) + 1 AS grp FROM C2 WHERE cnt = 0 ) , C4 AS ( SELECT MIN(ln) AS FromLen, MAX(ln) AS ToLen FROM C3 GROUP BY grp ) , C5 AS ( SELECT *, LEAD(FromLen, 1, ToLen) OVER(ORDER BY FromLen) AS nxt_FromLen FROM C4 ) SELECT ToLen AS GapStart, nxt_FromLen AS GapEnd FROM C5 WHERE nxt_FromLen  ToLen > 0.0001; GO /* GapStart GapEnd 0.0000 10.0002 35.0000 40.0000 50.0003 100.0000 */
The beauty of this approach is that it could easily be adapted to report on multiple bridges or roads, whatever it is that you are painting.
SET NOCOUNT ON; USE tempdb; GO DECLARE @BridgeP TABLE ( BridgeID int NOT NULL, BridgePID int, FromLen Decimal(14,4), ToLen Decimal(14,4) ); Insert into @BridgeP Values (1, 1,10.0002,20.0004) , (1, 2,18.0000,21.0004) , (1, 3,11.12345,20.0002) , (1, 4,40.0000,50.0003) , (1, 5,19.1100,35.0000) , (2, 1,10.0002,20.0004) , (2, 2,18.0000,21.0004) , (2, 3,11.12345,20.0002) , (2, 4,40.0000,50.0003) , (2, 5,25.1100,35.0000) ;  Itzik's approach WITH C0 AS ( SELECT BridgeID, FromLen, ToLen FROM @BridgeP UNION ALL SELECT B.BridgeID, T.FromLen, T.ToLen FROM (SELECT DISTINCT BridgeID FROM @BridgeP) AS B CROSS JOIN (VALUES (0, 0), (100, 100) ) AS T(FromLen, ToLen) ) , C1 AS ( SELECT BridgeID, FromLen AS ln, +1 AS [type], 1 AS sub FROM C0 UNION ALL SELECT BridgeID, ToLen AS ln, 1 AS [type], 0 AS sub FROM C0 ) , C2 AS ( SELECT BridgeID, ln, SUM([type]) OVER( PARTITION BY BridgeID ORDER BY ln, [type] DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW )  sub AS cnt FROM C1 ) , C3 AS ( SELECT BridgeID, ln, ((ROW_NUMBER() OVER(PARTITION BY BridgeID ORDER BY ln)  1) / 2) + 1 AS grp FROM C2 WHERE cnt = 0 ) , C4 AS ( SELECT BridgeID, MIN(ln) AS FromLen, MAX(ln) AS ToLen FROM C3 GROUP BY BridgeID, grp ) , C5 AS ( SELECT BridgeID, FromLen, ToLen, LEAD(FromLen, 1, ToLen) OVER(PARTITION BY BridgeID ORDER BY FromLen) AS nxt_FromLen FROM C4 ) SELECT BridgeID, ToLen AS GapStart, nxt_FromLen AS GapEnd FROM C5 WHERE nxt_FromLen  ToLen > 0.0001; GO /* BridgeID GapStart GapEnd 1 0.0000 10.0002 1 35.0000 40.0000 1 50.0003 100.0000 2 0.0000 10.0002 2 21.0004 25.1100 2 35.0000 40.0000 2 50.0003 100.0000 */
I didn't include an ORDER BY clause for presentation purpose, neither setup proper indexes to support the OVER clause.
AMB
Some guidelines for posting questions...
 Edited by HunchbackMVP, Moderator Monday, September 03, 2012 4:54 PM
 Marked as answer by Naomi NModerator Monday, September 03, 2012 7:52 PM
All replies

 Sample data Declare @Bridge Table(BridgePID int, fromlen int, tolen int); Insert @Bridge(BridgePID, fromlen, tolen) Values (1 , 10 ,20), (2 ,18 ,2), (3 ,11 ,20), (4 ,40 ,50), (5 ,19 ,35); ;With N2 As (Select 1 As Number Union All Select 1), N4 As (Select na.Number From N2 na Cross Join N2 nb), N16 As (Select na.Number From N4 na Cross Join N4 nb), N256 As (Select na.Number From N16 na Cross Join N16 nb), Numbers As (Select Row_Number() Over (Order By n.Number) As Number From N256 n), MissingNumbers As (Select n.Number, Row_Number() Over (Order By n.Number) As SeqNbr From Numbers n Where n.Number <= 100 And Not Exists(Select * From @Bridge b Where n.Number Between b.fromlen And b.tolen)) Select Min(m.Number) As GapStart, Max(m.Number) As GapEnd From MissingNumbers m Group By m.Number  m.SeqNbr;
Tom Proposed as answer by Naomi NModerator Wednesday, August 22, 2012 5:18 AM

Declare @BridgeP Table(BridgePID int, FromLen Int, ToLen Int); Declare @MaxBridgeLenght int = 100; Insert into @BridgeP Values (1,10,20) , (2,18,21) , (3,11,20) , (4,40,50) , (5,19,35) ;With CTE1 As ( Select BridgePID, FromLen AS MyLength, 1 As indicator , Null As ToRN , Row_Number() Over(Order by FromLen, BridgePID) As FromRN From @BridgeP Union All Select BridgePID, ToLen AS MyLength, 1 As indicator , Row_Number() Over(Order by ToLen, BridgePID) As ToRN , NULL As FromRN From @BridgeP ) , CTE2 As ( Select * , Row_Number() Over(Order by MyLength, Indicator Desc, BridgePID) As FromToRN From CTE1 ) , CTE3 As ( Select MyLength , Row_Number() Over(Order by MyLength) As MyRN From CTE2 Where Coalesce(FromRn  (FromToRN  FromRN)  1, (FRomToRN  ToRN)  ToRN) = 0 ) , CTE4 As ( Select BridgeLength , (Row_Number() Over(Order by BridgeLength)  1) / 2 As MyGroup From ( Select B.BridgeLength From (Values (0), (@MaxBridgeLenght)) B(BridgeLength) Union All Select Case When MyRN % 2 = 1 and MyLength > 0 Then MyLength  1 When MyRN % 2 = 0 and MyLength < @MaxBridgeLenght Then MyLength + 1 When MyRN % 2 = 1 and MyLength = 0 Then 0 When MyRN % 2 = 0 and MyLength = @MaxBridgeLenght Then @MaxBridgeLenght End From CTE3 ) X ) Select Min(Bridgelength) As GapStart, Max(Bridgelength) As GapEnd From CTE4 Group By MyGroup Having Min(Bridgelength) <> Max(Bridgelength)
 Blog: MSBICOE.com  MCITP  BI, SQL Developer & DBA
Hate to mislead others, if I'm wrong slap me. Thanks!
 Marked as answer by rajemessage Saturday, August 25, 2012 5:13 AM

The below solution is the easy to understand solution but may have performance issue if you have a large volume of data:
Declare @BridgeP Table(BridgePID int, FromLen Int, ToLen Int); Declare @MaxBridgeLenght int = 100; Insert into @BridgeP Values (1,10,20) , (2,18,21) , (3,11,20) , (4,40,50) , (5,19,35) ;With RangeStart As ( Select Distinct A.FromLen As RangeSTart From @BridgeP A Where Not Exists (Select * From @BridgeP B Where B.FromLen < A.FromLen And B.ToLen >= A.FromLen) ) , RangeEnd As ( Select Distinct A.ToLen As RangeEnd From @BridgeP A Where Not Exists (Select * From @BridgeP B Where B.ToLen > A.ToLen And B.FromLen <= A.ToLen) ) , GapValue As ( Select GapStart , (Row_Number() Over(Order by GapStart)  1) / 2 As MyGroup From ( Select 0 As GapStart Union All Select Case When RangeStart  1 < 0 Then 0 Else RangeStart  1 End From RangeStart S Union All Select Case When RangeEnd + 1 > @MaxBridgeLenght Then @MaxBridgeLenght Else RangeEnd + 1 End From RangeEnd E Union All Select @MaxBridgeLenght ) X ) Select Min(GapStart) As GapStart, Max(GapStart) As GapEnd From GapValue Group By MyGroup Having Min(GapStart) <> Max(GapStart)
 Blog: MSBICOE.com  MCITP  BI, SQL Developer & DBA
Hate to mislead others, if I'm wrong slap me. Thanks!
 Proposed as answer by Samuel Lester  MSFTMicrosoft employee, Moderator Wednesday, August 22, 2012 5:42 PM

Something like this?
 Prepare sample data DECLARE @Bridges TABLE ( Bridge INT NOT NULL, [Length] INT NOT NULL ); DECLARE @Work TABLE ( Bridge INT NOT NULL, StartMarker INT NOT NULL, EndMarker INT NOT NULL );  Populate sample data INSERT @Bridges ( Bridge, [Length] ) VALUES (1, 112), (2, 100), (3, 75); INSERT @Work ( Bridge, StartMarker, EndMarker ) VALUES (1, 10, 20), (1, 18, 2), (2, 11, 20), (3, 40, 50), (3, 19, 35);  Solution starts here CREATE TABLE #Missing ( Bridge INT NOT NULL, Marker INT NOT NULL ); INSERT #Missing ( Bridge, Marker ) SELECT b.Bridge, v.Number FROM @Bridges AS b INNER JOIN MASTER.dbo.spt_values AS v ON v.Type = 'P' AND v.Number BETWEEN 0 AND b.[Length] LEFT JOIN @Work AS w ON w.Bridge = b.Bridge GROUP BY b.Bridge, v.Number HAVING MAX(CASE WHEN v.Number BETWEEN w.StartMarker AND w.EndMarker THEN 1 WHEN v.Number BETWEEN w.EndMarker AND w.StartMarker THEN 1 ELSE 0 END) = 0; CREATE UNIQUE CLUSTERED INDEX UCX_Missing ON #Missing (Bridge, Marker); ;WITH cteSource(Bridge, Marker, SeqID) AS ( SELECT Bridge, Marker, Marker  ROW_NUMBER() OVER (PARTITION BY Bridge ORDER BY Marker) AS SeqID FROM #Missing ) SELECT s.Bridge, CASE WHEN MIN(s.Marker) < 1 THEN 0 ELSE MIN(s.Marker)  1 END AS FromMarker, CASE WHEN MAX(s.Marker) >= MIN(b.[Length]) THEN MIN(b.[Length]) ELSE MAX(s.Marker) + 1 END AS ToMarker FROM cteSource AS s INNER JOIN @Bridges AS b ON b.Bridge = s.Bridge GROUP BY s.Bridge, s.SeqID ORDER BY s.Bridge, s.SeqID;  Clean up DROP TABLE #Missing;
N 56°04'39.26"
E 12°55'05.63" Proposed as answer by Samuel Lester  MSFTMicrosoft employee, Moderator Wednesday, August 22, 2012 5:42 PM

Thank u,
thing is i am keeping decimal (14,4) for from length and to length,
and it is not bridge it is road where paiting is going on.
will the query be able to accomadate this much of lenght.
and overlaps are there but we need to show only gaps in points.
yours sincerely 

Dear sir/madam and friends
problem is correct just consider that in lenght col i have decimal(14,4)
and data is in decimal (points).
and need to show gaps in decimals also.because entry can be done in from lenght and to lenght like following.
900000.0000 to 1000000.0001,1000000.0005 to 1000100.0000 so there is gap of .0004.
and we want to show 1000000.0001(start gap),1000000.0005 (end gap)
yours sincerely.
 Edited by rajemessage Wednesday, August 22, 2012 11:23 AM

there is really no difference as the concept is same. try this:
Declare @BridgeP Table(BridgePID int, FromLen Decimal(14,4), ToLen Decimal(14,4)); Declare @MaxBridgeLenght Decimal(14,4) = 100.0000; Insert into @BridgeP Values (1,10.0002,20.0004) , (2,18.0000,21.0004) , (3,11.12345,20.0002) , (4,40.0000,50.0003) , (5,19.1100,35.0000) ;
The solution starts there
;With RangeStart As ( Select Distinct A.FromLen As RangeSTart From @BridgeP A Where Not Exists (Select * From @BridgeP B Where B.FromLen < A.FromLen And B.ToLen >= A.FromLen) ) , RangeEnd As ( Select Distinct A.ToLen As RangeEnd From @BridgeP A Where Not Exists (Select * From @BridgeP B Where B.ToLen > A.ToLen And B.FromLen <= A.ToLen) ) , GapValue As ( Select GapStart , (Row_Number() Over(Order by GapStart)  1) / 2 As MyGroup From ( Select 0 As GapStart Union All Select RangeStart From RangeStart S Union All Select RangeEnd From RangeEnd E Union All Select @MaxBridgeLenght ) X ) Select Min(GapStart) As GapStart, Max(GapStart) As GapEnd From GapValue Group By MyGroup Having Min(GapStart) <> Max(GapStart);
 Blog: MSBICOE.com  MCITP  BI, SQL Developer & DBA
Hate to mislead others, if I'm wrong slap me. Thanks!
 Edited by Steven Wang  Shangzhou Friday, August 24, 2012 10:22 AM

I see here two problems in one. The first one would be packing overlapping ranges, and then identifying gaps.
Itzik BenGan included these two problems in his last book about window functions. He explains the solutions for SQL Server 2012 and also for previous versions.
Microsoft® SQL Server® 2012 HighPerformance TSQL Using Window Functions
http://shop.oreilly.com/product/0790145323088.doI am going to use his approach to tackle your question.
SET NOCOUNT ON; USE tempdb; GO Declare @BridgeP Table( BridgePID int, FromLen Decimal(14,4), ToLen Decimal(14,4) ); Declare @MaxBridgeLenght Decimal(14,4) = 100.0000; Insert into @BridgeP Values (1,10.0002,20.0004) , (2,18.0000,21.0004) , (3,11.12345,20.0002) , (4,40.0000,50.0003) , (5,19.1100,35.0000) ; WITH C0 AS ( SELECT FromLen, ToLen FROM @BridgeP UNION ALL SELECT FromLen, ToLen FROM (VALUES (0, 0), (100, 100) ) AS T(FromLen, ToLen) ) , C1 AS ( SELECT FromLen AS ln, +1 AS [type], 1 AS sub FROM C0 UNION ALL SELECT ToLen AS ln, 1 AS [type], 0 AS sub FROM C0 ) , C2 AS ( SELECT ln, SUM([type]) OVER( ORDER BY ln, [type] DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW )  sub AS cnt FROM C1 ) , C3 AS ( SELECT ln, ((ROW_NUMBER() OVER(ORDER BY ln)  1) / 2) + 1 AS grp FROM C2 WHERE cnt = 0 ) , C4 AS ( SELECT MIN(ln) AS FromLen, MAX(ln) AS ToLen FROM C3 GROUP BY grp ) , C5 AS ( SELECT *, LEAD(FromLen, 1, ToLen) OVER(ORDER BY FromLen) AS nxt_FromLen FROM C4 ) SELECT ToLen AS GapStart, nxt_FromLen AS GapEnd FROM C5 WHERE nxt_FromLen  ToLen > 0.0001; GO /* GapStart GapEnd 0.0000 10.0002 35.0000 40.0000 50.0003 100.0000 */
The beauty of this approach is that it could easily be adapted to report on multiple bridges or roads, whatever it is that you are painting.
SET NOCOUNT ON; USE tempdb; GO DECLARE @BridgeP TABLE ( BridgeID int NOT NULL, BridgePID int, FromLen Decimal(14,4), ToLen Decimal(14,4) ); Insert into @BridgeP Values (1, 1,10.0002,20.0004) , (1, 2,18.0000,21.0004) , (1, 3,11.12345,20.0002) , (1, 4,40.0000,50.0003) , (1, 5,19.1100,35.0000) , (2, 1,10.0002,20.0004) , (2, 2,18.0000,21.0004) , (2, 3,11.12345,20.0002) , (2, 4,40.0000,50.0003) , (2, 5,25.1100,35.0000) ;  Itzik's approach WITH C0 AS ( SELECT BridgeID, FromLen, ToLen FROM @BridgeP UNION ALL SELECT B.BridgeID, T.FromLen, T.ToLen FROM (SELECT DISTINCT BridgeID FROM @BridgeP) AS B CROSS JOIN (VALUES (0, 0), (100, 100) ) AS T(FromLen, ToLen) ) , C1 AS ( SELECT BridgeID, FromLen AS ln, +1 AS [type], 1 AS sub FROM C0 UNION ALL SELECT BridgeID, ToLen AS ln, 1 AS [type], 0 AS sub FROM C0 ) , C2 AS ( SELECT BridgeID, ln, SUM([type]) OVER( PARTITION BY BridgeID ORDER BY ln, [type] DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW )  sub AS cnt FROM C1 ) , C3 AS ( SELECT BridgeID, ln, ((ROW_NUMBER() OVER(PARTITION BY BridgeID ORDER BY ln)  1) / 2) + 1 AS grp FROM C2 WHERE cnt = 0 ) , C4 AS ( SELECT BridgeID, MIN(ln) AS FromLen, MAX(ln) AS ToLen FROM C3 GROUP BY BridgeID, grp ) , C5 AS ( SELECT BridgeID, FromLen, ToLen, LEAD(FromLen, 1, ToLen) OVER(PARTITION BY BridgeID ORDER BY FromLen) AS nxt_FromLen FROM C4 ) SELECT BridgeID, ToLen AS GapStart, nxt_FromLen AS GapEnd FROM C5 WHERE nxt_FromLen  ToLen > 0.0001; GO /* BridgeID GapStart GapEnd 1 0.0000 10.0002 1 35.0000 40.0000 1 50.0003 100.0000 2 0.0000 10.0002 2 21.0004 25.1100 2 35.0000 40.0000 2 50.0003 100.0000 */
I didn't include an ORDER BY clause for presentation purpose, neither setup proper indexes to support the OVER clause.
AMB
Some guidelines for posting questions...
 Edited by HunchbackMVP, Moderator Monday, September 03, 2012 4:54 PM
 Marked as answer by Naomi NModerator Monday, September 03, 2012 7:52 PM