Overlapping time in SQL server

Question

I am having a table like this

ColumnId Intime                   Outtime
1        01/02/2009 10.00.000    01/02/2009 20.00.0000  
2        01/02/2009 2.00.000    01/02/2009 2.00.0000 
3        01/02/2009 2.00.000    01/02/2009 5.00.0000 
4        01/02/2009 3.3.0.000    01/02/2009 5.00.0000 
5        01/02/2009 10.00.000    01/02/2009 22.00.0000 
6        01/02/2009 3.00.000    01/02/2009 4.00.0000 

I am having columns and values like this. I like to find the overlapping records and how many overlapping records for the particular date. Overlapping for time from 1-24 in a day.

Note:- My table has millions of records.

for example in first value login an 10 and logged out 20. and in 5the record login at 10 and logged out at 22 so 5th overlapped with first. No Indices available in the table.

Please get me the answer for my query.

I need the query to execute in SQL Server 2005

Answer 1

Out of the tip of my head, and assuming index on both columns, you could use something like this:

SELECT a.ColumnId
      ,a.InTime
      ,a.OutTime
      ,b.ColumnId AS OverlappingId
      ,b.InTime   AS OverlappingInTime
      ,b.OutTime  AS OverlappingOutTime
  FROM TimeTable  AS a
  JOIN TimeTable  AS b ON ((a.InTime  BETWEEN b.InTime AND b.OutTime)
                       OR  (a.OutTime BETWEEN b.InTime AND b.OutTime) 
                       OR  (a.InTime < b.InTime AND a.OutIme > b.OutTime))
                      AND  (a.ColumnId != b.ColumnId)

But I'm really not sure about the performance this query would have in a table with millions of records as you mention.

Edited to Add, and edited yet again:

After the comments of Vadim K., I noticed that the query I had wrote previously were missing a case when the overlapping were total, that is one range cover the entirely another one. Above is my revised query, and below the original one:

SELECT a.ColumnId 
      ,a.InTime 
      ,a.OutTime 
      ,b.ColumnId AS OverlappingId 
      ,b.InTime   AS OverlappingInTime 
      ,b.OutTime  AS OverlappingOutTime 
  FROM TimeTable  AS a 
  JOIN TimeTable  AS b ON ((a.InTime  BETWEEN b.InTime AND b.OutTime) 
                       OR  (a.OutTime BETWEEN b.InTime AND b.OutTime)) 
                      AND  (a.ColumnId != b.ColumnId) 

Using the question initial data for the a test run:

+--------+------------------+------------------+
|ColumnId| InTime           | OutTime          |
+--------+------------------+------------------+
|      1 | 01/02/2009 10:00 | 01/02/2009 20:00 |   
|      2 | 01/02/2009  2:00 | 01/02/2009  2:00 |  
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |  
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |  
|      5 | 01/02/2009 10:00 | 01/02/2009 22:00 |  
|      6 | 01/02/2009  3:00 | 01/02/2009  4:00 |  
+--------+------------------+------------------+

Running the original query we have the following result:

+--------+------------------+------------------+-------------+
|ColumnId| InTime           | OutTime          |OverlappingId|
+--------+------------------+------------------+-------------+
|      1 | 01/02/2009 10:00 | 01/02/2009 20:00 |           5 |
|      2 | 01/02/2009  2:00 | 01/02/2009  2:00 |           3 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           2 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           4 |
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |           3 |
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |           6 |
|      5 | 01/02/2009 10:00 | 01/02/2009 22:00 |           1 |
|      6 | 01/02/2009  3:00 | 01/02/2009  4:00 |           3 |
|      6 | 01/02/2009  3:00 | 01/02/2009  4:00 |           4 |
+--------+------------------+------------------+-------------+

Running the updated query we have the following result:

+--------+------------------+------------------+-------------+
|ColumnId| InTime           | OutTime          |OverlappingId|
+--------+------------------+------------------+-------------+
|      1 | 01/02/2009 10:00 | 01/02/2009 20:00 |           5 |
|      2 | 01/02/2009  2:00 | 01/02/2009  2:00 |           3 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           2 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           4 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           6 | << missing row
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |           3 |
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |           6 |
|      5 | 01/02/2009 10:00 | 01/02/2009 22:00 |           1 |
|      6 | 01/02/2009  3:00 | 01/02/2009  4:00 |           3 |
|      6 | 01/02/2009  3:00 | 01/02/2009  4:00 |           4 |
+--------+------------------+------------------+-------------+

Yes, there are some IDs that are repeated, but that's because they overlaps with different records.

The question also asks for the number of overlapping rows. I'm not sure, and the question isn't clear enough, if it wants the number of overlapping rows regarding the original table.

Some people have suggested using the a.ColumnId < b.ColumnId or a.ColumnId > b.ColumnId in order to avoid repetition, however, it still doesn't work because if we did the first comparison we'd get the following result:

+--------+------------------+------------------+-------------+
|ColumnId| InTime           | OutTime          |OverlappingId|
+--------+------------------+------------------+-------------+
|      1 | 01/02/2009 10:00 | 01/02/2009 20:00 |           5 |
|      2 | 01/02/2009  2:00 | 01/02/2009  2:00 |           3 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           4 |
|      3 | 01/02/2009  2:00 | 01/02/2009  5:00 |           6 | 
|      4 | 01/02/2009  3:03 | 01/02/2009  5:00 |           6 |
+--------+------------------+------------------+-------------+

If you notice all the 6 rows of the sample data are referenced in the results, although it has only 5 lines. I believe that, with this data, where all the rows are overlapping each other at one point or another, the number of overlapping rows is 6.

And in order to get this result, the query below could be used:

SELECT COUNT (DISTINCT a.ColumnId)
  FROM TimeTable  AS a
  JOIN TimeTable  AS b ON ((a.InTime  BETWEEN b.InTime AND b.OutTime)
                       OR  (a.OutTime BETWEEN b.InTime AND b.OutTime) 
                       OR  (a.InTime < b.InTime AND a.OutIme > b.OutTime))
                      AND  (a.ColumnId != b.ColumnId)

Which returns the count of all 6 rows.

Answer 2

Test the solutions carefully, I've found that the answers posted so far either get the overlap check wrong or return too many results (two rows for each overlap).

select
    aa.ColumnId as ColumnIdA, aa.InTime as InTimeA, aa.OutTime as OutTimeA,
    bb.ColumnId as ColumnIdB, bb.InTime as InTimeB, bb.OutTime as OutTimeB
from
    MyTable aa
    join
    MyTable bb on aa.ColumnId < bb.ColumnId
where
    aa.InTime < bb.OutTime
    and
    aa.OutTime > bb.InTime

One must be careful in defining "overlap". I assume that if the first period is 3am-to-4am and the second period is 4am-to-5am that these ranges don't overlap. If one truly wishes this case to be considered an overlap, change the <-to-<= and the >-to->= in the where clause.

Performance is proportional to the square of the number of rows. Faster solutions are possible for large data sets, but are much more involved than this one.