Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

In the main, I've got two kinds of time intervals:

presence time and absence time

absence time can be of different types (eg breaks, absences, special day and so on) and time intervals may overlap and / or intersect.

It is not for sure, that only plausible combinations of intervals exist in raw data, eg. overlapping presence-intervals don't make sense, but may exist. I've tried to identify resulting presence-time intervals in many ways now - for me, the most comfortable seems to be the follwing one.

;with "timestamps"
as
(
    select
        "id" = row_number() over ( order by "empId", "timestamp", "opening", "type" )
        , "empId"
        , "timestamp"
        , "type"
        , "opening"
    from
    (
        select "empId", "timestamp", "type", case when "types" = 'starttime' then 1 else -1 end as "opening" from
        ( select "empId", "starttime", "endtime", 1 as "type" from "worktime" ) as data
        unpivot ( "timestamp" for "types" in ( "starttime", "endtime" ) ) as pvt
        union all
        select "empId", "timestamp", "type", case when "types" = 'starttime' then 1 else -1 end as "opening" from
        ( select "empId", "starttime", "endtime", 2 as "type" from "break" ) as data
        unpivot ( "timestamp" for "types" in ( "starttime", "endtime" ) ) as pvt
        union all
        select "empId", "timestamp", "type", case when "types" = 'starttime' then 1 else -1 end as "opening" from
        ( select "empId", "starttime", "endtime", 3 as "type" from "absence" ) as data
        unpivot ( "timestamp" for "types" in ( "starttime", "endtime" ) ) as pvt
    ) as data
)
select 
      T1."empId"
    , "starttime"   = T1."timestamp"
    , "endtime"     = T2."timestamp"
from 
    "timestamps" as T1
    left join "timestamps" as T2
        on T2."empId" = T1."empId"
        and T2."id" = T1."id" + 1
    left join "timestamps" as RS
        on RS."empId" = T2."empId"
        and RS."id" <= T1."id"      
group by
    T1."empId", T1."timestamp", T2."timestamp"
having
    (sum( power( 2, RS."type" ) * RS."opening" ) = 2)
order by 
    T1."empId", T1."timestamp";

see SQL-Fiddle for some demo data.

The raw data exist in different tables in form of "starttime" - "endtime" or "starttime" - "duration".

The idea was to get an ordered list of every timestamp with a "bitmasked" rolling sum of open intervals at each time to estimate presence time.

The fiddle works and gives estimated results, even if startimes of different intervals are equal. No indices are used in this example.

Is this the right way to achieve questioned task or is there a more elegant way for this?

If relevant for answering: amount of data will be up to several ten-thousand datasets per employee per table. sql-2012 is not available to calculate a rolling sum of predecessors inline in aggregate.


edit:

Just executed the query against larger amount of testdata ( 1000, 10.000, 100.000, 1 million) and can see that runtime increases exponentially. Obviously a warning flag, right?

I changed the query and removed aggregation of rolling sum by a quirky update.

I've added an auxiliary table:

create table timestamps
(
  "id" int
  , "empId" int
  , "timestamp" datetime
  , "type" int
  , "opening" int
  , "rolSum" int
)

create nonclustered index "idx" on "timestamps" ( "rolSum" ) include ( "id", "empId", "timestamp" )

and I moved calculating rolling sum to this place:

declare @rolSum int = 0
update "timestamps" set @rolSum = "rolSum" = @rolSum + power( 2, "type" ) * "opening" from "timestamps"

see SQL-Fiddle here

The runtime decreased to 3 sec regarding 1 million entries in the "worktime"-table.

Question stays the same: What's the most effective way to solve this?

share|improve this question

migrated from stackoverflow.com Dec 24 '12 at 15:04

This question came from our site for professional and enthusiast programmers.

    
I'm sure there will be contention on this, but you might try not doing it in a CTE. Use temp tables instead, and see if it is faster. –  Amanda Feb 8 '13 at 20:35
    
Just a style question: I have never seen anyone put all their column names and table names in double quotes. Is this the practice of your whole company? I definitely find it uncomfortable. It is not necessary in my view, and thus increases the noise over the signal... –  ErikE Feb 9 '13 at 6:49
    
@ErikE Above method is part of a huge addon. Some of the objects are created dynamically and depend on end-user-input-choice. So eg blanks could come up in table- or view-names. double-quotes around those won't let the query crash...! –  Nico Feb 10 '13 at 12:14
    
@Nico in my world that's usually done with square brackets then like [this]. I just like that better than double quotes, I guess. –  ErikE Feb 12 '13 at 20:59
    
@ErikE square brackets is tsql. standard is double quotes! anyway, i learned it that way and so somehow am used to it! –  Nico Feb 12 '13 at 22:12

1 Answer 1

I can't answer your question as to the absolutely best way. But I can offer a different way of solving the problem, which may or may not be better. It has a reasonably flat execution plan, and I think it will perform well. (I'm eager to know so share the results!)

I apologize for using my own syntax style instead of yours--it helps query wizardry come to me when everything lines up in its usual place.

The query is available in a SqlFiddle. I threw in an overlap for EmpID 1 just to be sure I had that covered. If you eventually find that overlaps cannot occur in presence data, then you can remove the final query and the Dense_Rank calculations.

WITH Points AS (
  SELECT DISTINCT
    T.EmpID,
    P.TimePoint
  FROM
    (
      SELECT * FROM dbo.WorkTime
      UNION SELECT * FROM dbo.BreakTime
      UNION SELECT * FROM dbo.Absence
    ) T
    CROSS APPLY (VALUES (StartTime), (EndTime)) P (TimePoint)
), Groups AS (
  SELECT
    P.EmpID,
    P.TimePoint,
    Grp =
      Row_Number()
      OVER (PARTITION BY P.EmpID ORDER BY P.TimePoint, X.Which) / 2
  FROM
    Points P
    CROSS JOIN (VALUES (1), (2)) X (Which)
), Ranges AS (
  SELECT
    G.EmpID,
    StartTime = Min(G.TimePoint),
    EndTime = Max(G.TimePoint)
  FROM Groups G
  GROUP BY
    G.EmpID,
    G.Grp
  HAVING Count(*) = 2
), Presences AS (
  SELECT
    R.*,
    P.Present,
    Grp =
       Dense_Rank() OVER (PARTITION BY R.EmpID ORDER BY R.StartTime)
       - Dense_Rank() OVER (PARTITION BY R.EmpID, P.Present ORDER BY R.StartTime)
  FROM
    Ranges R
    CROSS APPLY (
      SELECT
        CASE WHEN EXISTS (
          SELECT *
          FROM dbo.WorkTime W
          WHERE
            R.EmpID = W.EmpID
            AND R.StartTime < W.EndTime
            AND W.StartTime < R.EndTime
        ) AND NOT EXISTS (
          SELECT *
          FROM dbo.BreakTime B
          WHERE
            R.EmpID = B.EmpID
            AND R.StartTime < B.EndTime
            AND B.StartTime < R.EndTime
        ) AND NOT EXISTS (
          SELECT *
          FROM dbo.Absence A
          WHERE
            R.EmpID = A.EmpID
            AND R.StartTime < A.EndTime
            AND A.StartTime < R.EndTime
        ) THEN 1 ELSE 0 END
    ) P (Present)
)
SELECT
  EmpID,
  StartTime = Min(StartTime),
  EndTime = Max(EndTime)
FROM Presences
WHERE Present = 1
GROUP BY
  EmpID,
  Grp
ORDER BY
  EmpID,
  StartTime;

Note: performance of this query would be improved you combined the three tables and added a column to indicate what kind of time it was: work, break, or absence.

And why all the CTEs, you ask? Because each one is forced by what I need to do to the data. There's an aggregate, or I need to put a WHERE condition on a windowing function or use it in a clause where windowing functions aren't allowed.

Now I'm going to go off and see if I can't think up another strategy for accomplishing this. :)

For amusement I include here a "diagram" I made to help solve the problem:

------------
   -----------------
                ---------------
                           -----------

    ---    ------   ------       ------------

----   ----      ---      -------

The three sets of dashes (separated by spaces) represent, in order: presence data, absence data, and the desired result.

share|improve this answer
    
Thanks for this approach. I'll check it out when back in office and give you runtime-results with larger data-base. –  Nico Feb 10 '13 at 12:17
    
Runtime is definetely much higher than 1st approach. I had no time to check if further indices may decrease it yet. Will check as soon as possible! –  Nico Feb 12 '13 at 15:23
    
I have another idea I haven't had time to get working. For what it's worth, your query returns wrong results with overlapping ranges in all tables. –  ErikE Feb 12 '13 at 16:04
    
I checked this out again, see this fiddle which has completely overlapping intervals in all three tables. it returns correct results, as i can see. could you provide a case in which wrong results are returned? feel free to adjust demo data in fiddle! –  Nico Feb 12 '13 at 19:31
    
alright, i got your point. in case of intersecting intervals in one table, results got mad. will check this. –  Nico Feb 12 '13 at 19:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.