how to find gap ranges in range based entry.

Question

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

   

Answer 1

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

Answer 2

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!

Answer 3

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!

Answer 4

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"

Answer 5

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

Answer 6

I don't like nor appreciate to be mislead!
Why should we help you again, when we already have spent some time on your [fake] fictitious problem statement?

---

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

Answer 7

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.

Answer 8

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!

Answer 9

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