how to find non overlapping range

• Question

• hi,

create table t ( b decimal(13,4) not null, c decimal(13,4) not null);
Insert into T (B,C) values ( 1,200);
Insert into T (B,C) values (   200   ,400);
Insert into T (B,C) values (  600,   900);

create table t1 (b decimal(13,4) not null, c decimal(13,4) not null);
Insert into t1 (B,C) values ( 1,100);
Insert into t1 (B,C) values (  200   ,500);
Insert into t1 (B,C) values (  800,   1000);

-- "t" and "t1" table holds ranges which could be any thing where b<c, i have to find out where "t" has range but "t1" does not?
--ex "t"  has 1,200 , "t1"  1,100 means i want to see 100 to 200 t2 does not have any thing.

Q) i have to find out the range where "t" has got range but "t1" does not? that means start range and end range will be passed

and i have to find out the range where "t1" is not done but "t" is done

--case 1 table "t" and "t1" will have no overlap  with in the table

--case 2 they will have overlap with in the table.

yours sincerley

• Edited by Sunday, January 12, 2020 7:10 AM
Tuesday, January 7, 2020 12:28 PM

All replies

• Can we assume that there are no overlaps in the same table? That is, B for the second row is always >= C for the first row etc?

You have used decimal(13,4) here. In your actual use case, what range are the values? Are they really decimal? Or are the integer? In which range approxamitely? (I'm asking, because that could possibly permit for a shortcut.)

From the sample you have posted, the result you want is
100-200
400-500
600-800

Right? Or something else?

It could also help if you could add more test cases with desired result.

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Tuesday, January 7, 2020 11:03 PM
• Hi,

Would you like this one ?

drop table t
drop table t1
go
create table t ( b decimal(13,4) not null, c decimal(13,4) not null);
Insert into T (B,C) values ( 1,200);
Insert into T (B,C) values (   200   ,400);
Insert into T (B,C) values (  600,   900);

create table t1 (b decimal(13,4) not null, c decimal(13,4) not null);
Insert into t1 (B,C) values ( 1,100);
Insert into t1 (B,C) values (  200   ,500);
Insert into t1 (B,C) values (  800,   1000);

--100-199
--600-799
DECLARE @sql_str VARCHAR(8000)
DECLARE @sql_col1 VARCHAR(8000)
DECLARE @sql_col2 VARCHAR(8000)
SELECT @sql_col1 = ISNULL(@sql_col1 + '
or ','') +'(number >= '+ cast(B as varchar(13))+' and number < '+cast(C as varchar(13))+')' FROM t
SELECT @sql_col2 = ISNULL(@sql_col2 + '
or ','') +'(number >=  '+ cast(B as varchar(13))+' and number <'+cast(C as varchar(13))+')' FROM t1

SET @sql_str = '
;with cte1 as(
SELECT number FROM master..spt_values WHERE type=''p''
) ,cte2 as(
select distinct number from t cross join cte1 where '+@sql_col1+'
),cte3 as(
select distinct number from t1 cross join cte1 where '+@sql_col2+'
),cte4 as (
select  cte2.number,cte2.number-row_number()over(order by cte2.number) rn
from cte2 left join cte3 on cte2.number =cte3.number where cte3.number is null
)
select min(number) B, max(number) C from cte4 group by rn '
PRINT (@sql_str)
execute(@sql_str)
/*
;with cte1 as(
SELECT number FROM master..spt_values WHERE type='p'
) ,cte2 as(
select distinct number from t cross join cte1 where (number >= 1.0000 and number < 200.0000)
or (number >= 200.0000 and number < 400.0000)
or (number >= 600.0000 and number < 900.0000)
),cte3 as(
select distinct number from t1 cross join cte1 where (number >=  1.0000 and number <100.0000)
or (number >=  200.0000 and number <500.0000)
or (number >=  800.0000 and number <1000.0000)
),cte4 as (
select  cte2.number,cte2.number-row_number()over(order by cte2.number) rn
from cte2 left join cte3 on cte2.number =cte3.number where cte3.number is null
)
select min(number) B, max(number) C from cte4 group by rn
B           C
----------- -----------
100         199
600         799
*/

Best Regards,

Rachel

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

Wednesday, January 8, 2020 5:41 AM
• Hi ,

I am writing to follow up this thread with you. Have you solved your issue? If you have solved your issue ,in order to close this thread, please kindly mark helpful replies as answers. By doing so, it will benefit all community members who are having this similar issue.  Your contribution is highly appreciated.

Best Regards,

Rachel

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

Friday, January 10, 2020 9:03 AM
• pls answer for both one for overlap and other for non overlap.

and decimal is possible like u can have 400.2345

and result is just example.

the question is,

Q) i have to find out the range where "t" has got range but "t1" does not? that means start range and end range will be passed

and i have to find out the range where "t1" is not done but "t" is done

--case 1 table "t" and "t1" will have no overlap  with in the table

--case 2 they will have overlap with in the table.

• Edited by Saturday, January 11, 2020 7:44 AM
Saturday, January 11, 2020 7:17 AM

Saturday, January 11, 2020 7:29 AM
• pls answer for both one for overlap and other for non overlap.

and decimal is possible like u can have 400.2345

OK, I know that there are no shortcuts to be found there.

the question is,

Q) i have to find out the range where "t" has got range but "t1" does not? that means start range and end range will be passed

and i have to find out the range where "t1" is not done but "t" is done

--case 1 table "t" and "t1" will have no overlap  with in the table

--case 2 they will have overlap with in the table.

But for the rest of my questions, I did not get much clarity. What is expected result given the sample data. And you provide more sample data?

As this appears to a difficult problem, I'm not inclined to work on it without full understanding of the presumptions.

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Saturday, January 11, 2020 11:26 AM
• create table t ( b decimal(13,4) not null, c decimal(13,4) not null);
Insert into T (B,C) values ( 1,200);
Insert into T (B,C) values (   200   ,400);
Insert into T (B,C) values (  600,   900);

create table t1 (b decimal(13,4) not null, c decimal(13,4) not null);
Insert into t1 (B,C) values ( 1,100);
Insert into t1 (B,C) values (  200   ,500);
Insert into t1 (B,C) values (  800,   1000);

result ( pls find where t has range and t1 does not)

100 200

600 800

Sunday, January 12, 2020 7:18 AM
• The amount of effort that you put into this question is not startling. If you are not willing to spend more time on this, well nor am I. I give it one more try. With the data below, what result do you want:

create table T ( B decimal(13,4) not null, C decimal(13,4) not null);
Insert into T (B,C) values (   1,  200);
Insert into T (B,C) values ( 200,  400);
Insert into T (B,C) values ( 600,  900);
Insert into T (B,C) values (1200, 1300);
Insert into T (B,C) values (1500.234, 1999.1234);
Insert into T (B,C) values (3100, 3300);
Insert into T (B,C) values (3400, 3600)

create table t1 (B decimal(13,4) not null, C decimal(13,4) not null);
Insert into t1 (B,C) values (    1, 100);
Insert into t1 (B,C) values (  200, 500);
Insert into t1 (B,C) values (  800, 1000)
Insert into t1 (B,C) values (1100,  1400)
Insert into t1 (B,C) values (1600,  1701.111)
Insert into t1 (B,C) values (1800,  1990.123)
Insert into t1 (B,C) values (3000,  3150)
Insert into t1 (B,C) values (3250,  3500)

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Sunday, January 12, 2020 11:08 AM
• first thing i have tried to keep things simple. and if u see comment above than your post

i have written the result also.

u have to little bit specific in your question. just tell me how do i know what u want.

unless u tel me.

1) two tables store range data related to two activities , but for simplecity i have removed other cols.

2) any range could be entered as long as decimal(13,4) supports.

3) i have to find out the range where  "t1" activity is not done  but "t" activity is done?

• Edited by Monday, January 13, 2020 5:33 AM
Monday, January 13, 2020 5:24 AM
• Hi rajemessage,

I have a simple question , in your table you have data like 200 ,400. What is the range ? B>=200 and C<=400 ? Or B>=200 or C<400?......

If it is  B>=200 or C<400, I think my script will satisfy your requirement . Could you please explain more ?

Best Regards,

Rachel

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

Monday, January 13, 2020 8:26 AM
• as i have written range could be any thing  which u can store in decimal(13,4)
Monday, January 13, 2020 9:45 AM
• first thing i have tried to keep things simple. and if u see comment above than your post

Well, if you want to keep things simple, I can also keep it simple. And the simplest I can do is to nothing at all. Which is what I'm starting to lean at.

i have written the result also.

u have to little bit specific in your question. just tell me how do i know what u want.

I extended your sample data with more cases. I want to know what your expected results are, so that anyone who takes a stab at your case and verify that his or her solution is correct.

But if you are not interested in helping us to help you, well, guess how interested we are...

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Monday, January 13, 2020 11:06 PM
• Good day rajemessage,

It is clear that you do not read my blog 😕 or you probably could have a simple solution long time ago.

http://ariely.info/Blog/tabid/83/EntryId/228/Grouping-continuous-Ranges-together-Part-2-Using-geometry-Data-type.aspx

Using the same logic we can get a solution that cover all options including cases that you have overlap ranges in the same table and so on. This is a general solution which might be too general if your case is simpler like in your sample data.

Anyhow, let's go over the solution

1. Using the logic I present in the post, you can convert the "start point" and "end point" of each row in each table into a line geometry Data Type. This line include the range.

2. Next, you combine all the lines in each table into one geometry Data Type value, as presented in the post (this cover cases that you have overlap ranges in the same table)

Now you need to do some more work...
At this time you have simple way to get one geometry value from each table

3. All you need to do next is to use the built-in function STDifference in order to get the ranges that exists in one value (table t for example) and not in the other value (which is the ranges from table t1), and WALLA... you have the solution

THIS SOLUTION as I mentioned MIGHT BE OVER-KILLING of what you actually need and it cover all options. Therefore, it might not be the best performance solution for your specific case if you do not need the full solution for all cases. But since you provided only 3 rows we do not have a lot to work on in order to be sure that we cover all the options, so this will give the solution

* Can you implement the last step yourself, or do you need more help? Please check the post in my blog first and read it fully. Come back only after you fully understand it, if you need help for the last step.

NOTE! If you want a solution that best fit your specific needs then we need more sample data to work with in order to understand your full case. This is basically what Erland ask you. In this case please provide at least 15 rows in each table which cover all options (for example if we need to covber overlap ranges then we need a sample data for this and so on)

Tuesday, January 14, 2020 2:35 AM
• I have read many books articals and one of them is jeo celkos, why i have posted here is because sometimes u get more optimized solution and with latest functions or ready made solutions.

like in sqlserver u have pivote now u do not have to wirte the whole query. similry we have lead,lag last and first analytical function.

1) as far as the entry is concerned u can enter any thing into it, considering that it is an range based entry of an activity in one table and other table has other activity which is also range based.

which could be lets say  between -99999999.9999 to 99999999.9999

it can overlap with in the table. but still if u want some more data then i will provide u.

Q) i have to find out the range where  "t1" activity is not done  but "t" activity is done?

so out put will be like(this is only on rec , there could me many )

100 200 ( this means t1 is not done for this range and  t is done for it, becasue we would write query in that way)

yes one thing i knowingly removed because it  could make the question complex but i am writing it know

1. u can assume that to params are passed lest say 10000 to 20000 which means u have to to get data from these two tables which falls in between then u have to find out were "t1" is not done and "t" is done. and if anything crosses the passed limit that could be cut of. like if there is an entry in table "t" which starts from 9000 to 11000 then u have to consider only 10000 to 11000 form this entry and likewise.
2. i will send some more data

• Edited by Tuesday, January 14, 2020 2:00 PM
Tuesday, January 14, 2020 1:36 PM
• It is clear that you do not read my blog ? or you probably could have a simple solution long time ago.

http://ariely.info/Blog/tabid/83/EntryId/228/Grouping-continuous-Ranges-together-Part-2-Using-geometry-Data-type.aspx

Using the same logic we can get a solution that cover all options including cases that you have overlap ranges in the same table and so on. This is a general solution which might be too general if your case is simpler like in your sample data.

Hey, that's cool, Ronen!

I will have to admit that I have not given the special, eh, spatial data types much attention. Largely, they have gone over my head, and I don't do things where I need them. But it's interesting to see a non-spatial use case for them.

I definitely think that Raj should consider this approach. A pure SQL solution will be fairly complicated.

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Tuesday, January 14, 2020 10:53 PM
• Hey, that's cool, Ronen!

I will have to admit that I have not given the special, eh, spatial data types much attention. Largely, they have gone over my head, and I don't do things where I need them. But it's interesting to see a non-spatial use case for them.

I definitely think that Raj should consider this approach. A pure SQL solution will be fairly complicated.

Erland Sommarskog, SQL Server MVP, esquel@sommarskog.se

Thanks Erland for the nice words :-)

By the way, don't tell rajemessage but when I posted my answer here it was after I already wrote the final script to get the requested result and I started a part two of the blog which will present it together with several more combination of ranges like

-- return all ranges that in one table but not in the other (both directions)
-- return all ranges that in both tables
-- Ranges in table 1 and not table 2
-- get specific line in the MULTILINESTRING

I did not posted yet since I do not want that rajemessag will copy-paste it without understand (learning) the basic approach and try to implement it by himself first :-)

I prefer to know that we teach someone and provided "free support" and not just provide "free work"

Thursday, January 16, 2020 12:51 AM
• I have read many books articals and one of them is jeo celkos, why i have posted here is because sometimes u get more optimized solution and with latest functions or ready made solutions.

like in sqlserver u have pivote now u do not have to wirte the whole query. similry we have lead,lag last and first analytical function.

1) as far as the entry is concerned u can enter any thing into it, considering that it is an range based entry of an activity in one table and other table has other activity which is also range based.

which could be lets say  between -99999999.9999 to 99999999.9999

it can overlap with in the table. but still if u want some more data then i will provide u.

Q) i have to find out the range where  "t1" activity is not done  but "t" activity is done?

so out put will be like(this is only on rec , there could me many )

100 200 ( this means t1 is not done for this range and  t is done for it, becasue we would write query in that way)

yes one thing i knowingly removed because it  could make the question complex but i am writing it know

1. u can assume that to params are passed lest say 10000 to 20000 which means u have to to get data from these two tables which falls in between then u have to find out were "t1" is not done and "t" is done. and if anything crosses the passed limit that could be cut of. like if there is an entry in table "t" which starts from 9000 to 11000 then u have to consider only 10000 to 11000 form this entry and likewise.
2. i will send some more data

Hi,

Did you responded to me or to someone else?

I cannot understand the context in your response.

1. Please check my post in the link I provided you and try to implement the final solution based on that approach

2. please provide more sample data as you was asked to do several times by Erland and myself. Do your part in helping you!

>> I have read many books articals and one of them is jeo celkos

I am sorry to hear that CELKO got to you. My personal feeling is that he come to the forum only in order to promote his book(s). According to his responses in the forum I would not recommend to any newbie to pay one cent to read his book, but to be fair let me clarify that I did not read any of his book and I only say what I say as conclusion of his responses in the forum.

I think that what people needs first in order to learn T-SQL, is ordered course which is relevant to practical result and not to read about irrelevant standards and theory which is not necessarily implemented it SQL Server.

>> why i have posted here is because sometimes u get more optimized solution and with latest functions or ready made solutions.
You don't have to justify or explain why you ask for help. I am not CELKO :-), and we will not judge as long as you will help us to help you and do what people ask you to do, which you did not done yet.

>> Q) i have to find out the range where  "t1" activity is not done  but "t" activity is done?

And we try to help you but you do not do your part - do what we guide you to do.

Check point 1 and 2 in this message

>> i will send some more data

This will help to clarify your needs :-)

• Edited by Thursday, January 16, 2020 1:11 AM
Thursday, January 16, 2020 1:08 AM
• -- b and e could be reversed

-- and show only latest tid from #t table in case of overlap

-- b and e could be reversed
-- and show only latest tid from #t table in case of overlap
DECLARE
@decBeginStation DECIMAL(13,4)=-2,
@decEndStation DECIMAL(13,4)=10

CREATE table #t ( tid int, b decimal(13,4) not null, E decimal(13,4) not null);

Insert into #T (tid,B,E)
VALUES (1, -12, -2),
(2, -10, 0),
(3, -2, 8),
(4, 10, 0),
(5, 8, 18),
(6, 10, 20),
(7, 21, 11),
(8, 0, 3),
(9, 2, 4),
(10, 3, 10),
(11, -1, 10),
(12, -1, 11),
(13, 0, 11)
;

create table #t1 (t1id int,b decimal(13,4) not null, E decimal(13,4) not null);

Insert into #t1 (t1id,B,E)
VALUES (1, -12, -2),
(2, -10, 0),
(3, 5, -2)
--(4, 0, 10),
--(5, 8, 18),
--(6, 10, 20),
-- (7, 11, 21),
-- (8, 0, 3),
-- (9, 2, 4),
-- (10, 3, 10),
-- (11, -1, 10),
-- (12, -1, 11),
-- (13, 0, 11)
;

/****
This method uses half-closed intervals.
****/

select * into
#tt from #t AS t
WHERE  (
NOT (
@decBeginStation >= t.b
AND @decBeginStation >= t.E
AND @decEndStation >= t.b
AND @decEndStation >= t.E
)
AND NOT (
@decBeginStation <= t.b
AND @decBeginStation <= t.E
AND @decEndStation <= t.b
AND @decEndStation <= t.E
)
)

SELECT * into #tt1
FROM #t1 AS t
WHERE  (
NOT (
@decBeginStation >= t.b
AND @decBeginStation >= t.E
AND @decEndStation >= t.b
AND @decEndStation >= t.E
)
AND NOT (
@decBeginStation <= t.b
AND @decBeginStation <= t.E
AND @decEndStation <= t.b
AND @decEndStation <= t.E
)
)

; WITH Prices AS
(
SELECT p.price
FROM #tt AS t
CROSS APPLY (VALUES(t.b), (t.E)) p(price)

UNION

SELECT p.price
FROM #tt1 AS t
CROSS APPLY (VALUES(t.b), (t.E)) p(price)

UNION
SELECT @decBeginStation price
UNION
SELECT @decEndStation price

)
, intervals AS
(
SELECT LAG(p.price) OVER(ORDER BY p.price) AS interval_start, p.price AS interval_end
FROM Prices AS p WHERE P.price >=@decBeginStation AND P.price <=@decEndStation
)
--SELECT * FROM INTERVALS ORDER BY INTERVAL_START

SELECT * FROM (
SELECT
ROW_NUMBER() OVER(PARTITION BY I.interval_start ORDER BY t.tid desc ) RN, T.TID,
i.interval_start AS b, i.interval_end AS E
FROM intervals AS i
INNER JOIN #tt AS t
ON i.interval_start < t.E
AND t.b < i.interval_end
LEFT OUTER JOIN #tt1 AS t1
ON i.interval_start < t1.E
AND t1.b < i.interval_end
WHERE t1.b IS NULL
) T
WHERE T.RN =1

drop table #t
drop table #t1

drop table #tt
drop table #tt1
• Edited by Wednesday, January 22, 2020 10:29 AM
Thursday, January 16, 2020 12:00 PM
• You did a much better job than average a posting DDL, but you forgotten that a table must have a key. Here is my guess. You also don't seem to know that SQL Server has the table constructor insertion statements.

Why did you use decimal data types in your DDL, but then showed only integer values in your sample data?

CREATE TABLE T
(b INTEGER NOT NULL,
c INTEGER NOT NULL,
PRIMARY KEY (b, c), -- not a option!!
CHECK (b < c));
b, cB,C)
VALUES (1,200), (200, 400), (600, 900);

The value 200 appears in two of the ranges. But there in the same table! What you want to do about that?

You might want to read what Chris Date has to say about tables with the same structure. Essentially, they should not exist in the same schema because they represent the same set of entities. In my books, I've called it attribute splitting. But let's go ahead and ignore this and continue

CREATE TABLE T1
(b INTEGER NOT NULL,
c INTEGER NOT NULL,
PRIMARY KEY (b,c) -- not a option!!
CHECK (b < c));

INSERT INTO T1(b, c)
VALUES (1,100), (200, 500), (800, 1000);

-- T and T1 table holds ranges which could be anything where (b < c), I have to find out where T has range but T1 does not?
--ex T has (1,200), T1 (1,100) means I want to see (100, 200) T2 does not have anything.
Q) I have to find out the range where T has got range but T1 does not? that means start range and end range will be passed and I have to find out the range where T1 is not done but T is done

--case 1 table T and T1 will have no overlap with in the table
--case 2 they will have overlap with in the table.

Standard SQL has an OVERLAPS predicate. I've tried to transcribe and translate the definition into your situation, but I haven't checked it. You should test it before you use it.

(T.b > T1.b AND NOT (T.b >= T1.c AND T.c  >= T1.c))
OR (T1.b > T.b AND NOT (T1.b >= T.c AND T.c.c >= T.c))
OR (S1 = S2 AND (T.c <> T1.c OR T.c = T1.c))

--CELKO-- Books in Celko Series for Morgan-Kaufmann Publishing: Analytics and OLAP in SQL / Data and Databases: Concepts in Practice Data / Measurements and Standards in SQL SQL for Smarties / SQL Programming Style / SQL Puzzles and Answers / Thinking in Sets / Trees and Hierarchies in SQL

Thursday, January 16, 2020 9:50 PM
• could i get one link of overlaps predicate.

is it this

yours sincerely

• Edited by Friday, January 17, 2020 8:54 AM
Friday, January 17, 2020 5:25 AM
• It might return true and false .

true if the two collections have common elements; otherwise, false.

Monday, January 20, 2020 7:02 AM
• the link I have given is from entity to SQL, so what I wanted to know is, Is there any "overlaps" predicate exists for SQL?

• Edited by Wednesday, January 22, 2020 6:29 AM
Wednesday, January 22, 2020 6:08 AM
• Might be related to .NET.
Wednesday, January 22, 2020 6:38 AM

• -- in following  "#t" table one can enter b as 10 and e as 2 that means e can be smaller than b and b can be smaller than e
-- for that i have used following logic in where clause i want to known is there any short way to do it with out putting small value in "b" and bigger in "e"

DECLARE
@decBeginStation DECIMAL(13,4)=-2,
@decEndStation DECIMAL(13,4)=10

CREATE table #t ( tid int, b decimal(13,4) not null, E decimal(13,4) not null);

Insert into #T (tid,B,E)
VALUES (1, -12, -2),
(2, -10, 0),
(3, -2, 8),
(4, 10, 0),
(5, 8, 18),
(6, 10, 20),
(7, 21, 11),
(8, 0, 3),
(9, 2, 4),
(10, 3, 10),
(11, -1, 10),
(12, -1, 11),
(13, 0, 11)
;

select *  from #t AS t
WHERE  (
NOT (
@decBeginStation >= t.b
AND @decBeginStation >= t.E
AND @decEndStation >= t.b
AND @decEndStation >= t.E
)
AND NOT (
@decBeginStation <= t.b
AND @decBeginStation <= t.E
AND @decEndStation <= t.b
AND @decEndStation <= t.E
)
)

drop table #t
Wednesday, January 22, 2020 10:35 AM
• It is too hard to understand .
Thursday, January 23, 2020 7:21 AM
• do u have any query to find overlaps, where b<c or c > b or b=c
Friday, January 24, 2020 10:48 AM
• where b=<c or c > b ?

Monday, January 27, 2020 8:29 AM
• yes it can be taken in that way.

but my question is how to reduce these clauses.

Wednesday, January 29, 2020 11:47 AM