Joining sequential records in TSQL

I've got a database of messages which contain various pieces of information that come in. One such piece is a state change messages so my table looks like the following.

    +-----------+--------------+---------+
    | MessageId | RecievedUTC  |  State  |
    +-----------+--------------+---------+
    |    1      | 1/1/2010 5pm |   Off   |
    +-----------+--------------+---------+
    |    2      | 1/2/2010 8am |   Idle  |
    +-----------+--------------+---------+
    |    3      | 1/2/2010 9am | Working |
    +-----------+----------开发者_如何学Go----+---------+

I'd like get a list of records which state how long I was in each state something like for a report and a maybe a pretty bar chart of how time was spent.

    +---------+---------------+--------------+
    |  State  |    StartUTC   |    StopUTC   |
    +---------+---------------+--------------+
    |   Off   | 1/1/2010 5pm  | 1/2/2010 8am |
    +---------+---------------+--------------+
    |   Idle  | 1/1/2010 8am  | 1/2/2010 9am |
    +---------+---------------+--------------+

etc. In my mind its no harder than a join of the table with itself, offset by 1 record ordered by the RecievedUTC.

The best TSQL I could come up with is something to the effect of

SELECT m1.State, m1.RecievedUTC as StartUTC, MIN(m2.RecievedUTC) as StopUTC
FROM MessageStates as m1
  INNER JOIN MessageStates as m2 ON MessageStates ON m2.RecievedUTC > m1.RecievedUTC
GROUP BY m1.MessageId, m1.State, m1.RecievedUTC

Or as a sub query to get StopUTC but both perform horribly with only 30-40k records taking almost 5 minutes to do this join.

If I wrote this in C# I would keep the track of the previous RecievedUTC and state so when I saw the next record I could combine the next RecievedUTC with it and in linear time have the data as I wanted it.

Try this:

WITH MsgStates AS 
(
  SELECT a.*, ROW_NUMBER() OVER(ORDER BY RecievedUTC ) RN
    FROM MessageStates a
)
SELECT a.State, a.RecievedUTC StartUTC, b.RecievedUTC StartUTC
  FROM MsgStates a, MsgStates b
 WHERE a.rn = b.rn+1