how to find gap ranges in range based entry.

# how to find gap ranges in range based entry.

• 2012年8月22日 上午 03:37

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

• 已編輯 2012年8月22日 上午 03:39
•

### 所有回覆

• 2012年8月22日 上午 05:07

```-- 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
• 2012年8月22日 上午 06:15

```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!

• 已標示為解答 2012年8月25日 上午 05:13
•
• 2012年8月22日 上午 06:45

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!

• 2012年8月22日 上午 08:44

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"

• 2012年8月22日 上午 09:59

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
• 2012年8月22日 上午 10:01

I don't like nor appreciate to be mislead!

N 56°04'39.26"
E 12°55'05.63"

• 2012年8月22日 上午 11:03

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.

• 已編輯 2012年8月22日 上午 11:23
•
• 2012年8月24日 上午 10:20

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!

• 2012年9月3日 下午 04:52
版主

I see here two problems in one. The first one would be packing overlapping ranges, and then identifying gaps.

Itzik Ben-Gan 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 High-Performance T-SQL Using Window Functions
http://shop.oreilly.com/product/0790145323088.do

I 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...