T-SQL query - row iteration without cursor

Question

I have a table

T (variable_name, start_no, end_no)

that holds values like:

(x, 10, 20)
(x, 30, 50)
(x, 60, 70)
(y, 1, 3)
(y, 7, 8)

All intervals are guaranteed to be disjoint.

I want to write a query in T-SQL that computes the intervals where a variable is not searched:

(x, 21, 29)
(x, 51, 59)
(y, 4, 6)

Can I do this without a cursor?

I was thinking of partitioning by variable_name and then ordering by start_no. But how to proceed next? Given the current row in the rowset, how to access the "next" one?

So the range for each variable is implicitly bounded by the lowest of the low ranges and the highest of the high ranges, correct? — David W
– David W, Commented Jun 16, 2015 at 15:03
Are you using SQL Server 2012 or newer? Lag / Lead could help you — James Z
– James Z, Commented Jun 16, 2015 at 15:03
Yes, that's correct David W. E.g., for x I'm excluding (-inf, 10) and (70, +inf). — cloudy
– cloudy, Commented Jun 16, 2015 at 15:09
JamesZ, SQL Server 2014, I'd rather have it working on 2008 as well. — cloudy
– cloudy, Commented Jun 16, 2015 at 15:10

Stephan · Accepted Answer · 2015-06-16 23:23:16Z

8

Since you didn't specify which version of SQL Server, I have multiple solutions. If you have are still rocking SQL Server 2005, then Giorgi's uses CROSS APPLY quite nicely.

Note: For both solutions, I use the where clause to filter out improper values so even if the the data is bad and the rows overlap, it will ignore those values.

My Version of Your Table

DECLARE @T TABLE (variable_name CHAR, start_no INT, end_no INT) 
INSERT INTO @T
VALUES  ('x', 10, 20),
        ('x', 30, 50),
        ('x', 60, 70),
        ('y', 1, 3),
        ('y', 7, 8);

Solution for SQL Server 2012 and Above

SELECT *
FROM
(
    SELECT  variable_name,
            LAG(end_no,1) OVER (PARTITION BY variable_name ORDER BY start_no) + 1 AS start_range,
            start_no - 1 AS end_range
    FROM @T
) A
WHERE end_range > start_range

Solution for SQL 2008 and Above

WITH CTE
AS
(
    SELECT  ROW_NUMBER() OVER (PARTITION BY variable_name ORDER BY start_no) row_num,
            *
    FROM @T
)

SELECT  A.variable_name,
        B.end_no + 1 AS start_range,
        A.start_no - 1 AS end_range
FROM CTE AS A
INNER JOIN CTE AS B
ON      A.variable_name = B.variable_name
    AND A.row_num = B.row_num + 1
WHERE A.start_no - 1 /*end_range*/ > B.end_no + 1 /*start_range*/

edited Jun 16, 2015 at 23:23

answered Jun 16, 2015 at 15:08

Stephan

6,0581 gold badge19 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ionic Over a year ago

This will work just on 2012+. But it will give you the result. :-)

Stephan Over a year ago

Yeah I was working on the my solution with ROW_NUMBER() as you commented this. See edited answer.

Ionic Over a year ago

Yes this looks quite better on older versions. :-)

cloudy Over a year ago

Thanks for both solutions.

Giorgi Nakeuri · Accepted Answer · 2015-06-16 15:41:39Z

3

Here is another version with cross apply:

DECLARE @t TABLE ( v CHAR(1), sn INT, en INT )
INSERT  INTO @t
VALUES  ( 'x', 10, 20 ),
        ( 'x', 30, 50 ),
        ( 'x', 60, 70 ),
        ( 'y', 1, 3 ),
        ( 'y', 7, 8 );

SELECT t.v, t.en + 1, c.sn - 1 FROM @t t
CROSS APPLY(SELECT TOP 1 * FROM @t WHERE v = t.v AND sn > t.sn ORDER BY sn)c
WHERE t.en + 1 < c.sn

Fiddle http://sqlfiddle.com/#!3/d6458/3

edited Jun 16, 2015 at 15:41

answered Jun 16, 2015 at 15:34

Giorgi Nakeuri

35.9k8 gold badges50 silver badges78 bronze badges

2 Comments

Stephan Over a year ago

One issue with this. What if there is no gap? Lets say the second row is ('x',21,50). Then you will return a row with ('x',21,20) which is improper. You should add a where clause WHERE t.en + 1 < c.sn - 1

cloudy Over a year ago

Excellent, thank you! I didn't mark yours as t-h-e answer since indeed I didn't specify the SQL Server version in initial post.

Community · Accepted Answer · 2017-05-23 11:51:15Z

0

For each end_no you should find the nearest start_no > end_no then exclude rows without nearest start_no (last rows for the variable_name)

WITH A AS
(
SELECT variable_name, end_no+1 as x1, 
              (SELECT MIN(start_no)-1 FROM t 
                     WHERE t.variable_name = t1.variable_name
                     AND t.start_no>t1.end_no) as x2
FROM t as t1 )
SELECT * FROM A WHERE x2 IS NOT NULL 
ORDER BY variable_name,x1

SQLFiddle demo

Also here is my old answer to the similar question:

Allen's Interval Algebra operations in SQL

edited May 23, 2017 at 11:51

CommunityBot

11 silver badge

answered Jun 16, 2015 at 15:17

valex

24.2k7 gold badges47 silver badges62 bronze badges

Comments

David W · Accepted Answer · 2015-06-16 15:30:31Z

0

Here's a non-CTE version that seems to work: http://sqlfiddle.com/#!9/4fdb4/1

Given the guaranteed disjoint ranges, I just joined T to itself, computed the next range as the increment/decrement of the adjoining range, then ensuring the new range didn't overlap any existing ranges.

select t1.variable_name, t1.end_no+1, t2.start_no-1
  from t t1
  join t t2
     on t1.variable_name=t2.variable_name
where t1.start_no < t2.start_no
  and t1.end_no < t2.end_no
  and not exists (select *
                    from t 
                   where ((t2.start_no-1< t.end_no
                     and t1.end_no+1 > t.start_no) or
                         (t1.end_no + 1 < t.end_no and
                          t2.start_no-1 > t.end_no))
                          and t.variable_name=t1.variable_name)

answered Jun 16, 2015 at 15:30

David W

10.2k38 silver badges60 bronze badges

3 Comments

shawnt00 Over a year ago

The join will be one to many, won't it? Does the not exists query handle the extra rows?

David W Over a year ago

The intent is for the not exists to handle edge cases where one end of a new possible unsearched range overlaps an existing one; as for generating too many rows, I did not see that in my testing, but perhaps I overlooked a condition.

shawnt00 Over a year ago

I just looked at the fiddle. It does generate extra rows that do end up overlapping so ultimately they are culled.

shawnt00 · Accepted Answer · 2015-06-16 23:36:18Z

0

This is very portable as it doesn't require CTEs or analytic functions. I could also easily be rewritten without the derived table if that were ever necessary.

select * from (
    select
        variable_name,
        end_no + 1 as start_no,
        (
            select min(start_no) - 1
            from T as t2
            where t2.variable_name = t1.variable_name and t2.start_no > t1.end_no
        ) as end_no
    from T as t1
) as intervals
where start_no <= end_no

The number of complemented intervals will be at maximum one fewer than the what you start with. (Some will be eliminated if two ranges were actually consecutive.) So it's easy to take each separate intervals and calculate the one just to its right (or left if you wanted to reverse some of the logic.)

edited Jun 16, 2015 at 23:36

answered Jun 16, 2015 at 15:19

shawnt00

18.1k3 gold badges23 silver badges25 bronze badges

Collectives™ on Stack Overflow

T-SQL query - row iteration without cursor

5 Answers 5

My Version of Your Table

Solution for SQL Server 2012 and Above

Solution for SQL 2008 and Above

4 Comments

2 Comments

Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

My Version of Your Table

Solution for SQL Server 2012 and Above

Solution for SQL 2008 and Above

4 Comments

2 Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related