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.

I've tried to solve this problem using a set-based approach. However, since I need to look at each row I think I must use a cursor; please correct me if I'm wrong.

The table:

Project, item, method, start, end

The table contains multiple projects, multiple items, but I've reduced it here to a single project, one item, for simplicity:

The data looks like this:

ABC, widget1, XY, 1000, 1033
ABC, widget1, XY, 1033, 1062
ABC, widget1, XY, 1062, 1112
ABC, widget1, XY, 1112, 1163
ABC, widget1, WW, 1163, 1223
ABC, widget1, WW, 1223, 1288
ABC, widget1, WW, 1288, 1334
ABC, widget1, XY, 1334, 1383
ABC, widget1, XY, 1383, 1425

I'd like to write a query that returns this result:

ABC, widget1, XY, 1000, 1163
ABC, widget1, WW, 1163, 1334
ABC, widget1, XY, 1334, 1425

What is the best way to do this?

share|improve this question
1  
You'll need a recursive CTE. What platform are you using? –  Nick Chammas May 2 '12 at 23:12
    
It would be very useful for you to specify the RDBMS and the version. "sql" isn't specific enough to answer your question, though I hope @Nick guessed right, otherwise it's a shame to waste that time and effort. –  Aaron Bertrand May 3 '12 at 0:28
    
Do you really need to do it in RDBMS? It might be faster to write it on the client, and it might perform better too. –  AlexKuznetsov May 3 '12 at 0:34
    
I do not understand your post. As far as I can see you are calculating min(start),max(end) for each project,item,method group. Where in your test data are the gaps you are talking about and how are they removed? can you clarify that? –  miracle173 Sep 20 '12 at 5:16
    
This question is similar: dba.stackexchange.com/questions/1334/… –  Leigh Riffel Sep 20 '12 at 19:51

3 Answers 3

You can store pre-calculated gaps, and use constraints to make sure that your pre-calcualted data is always up-to-date:

Here is the table and the first interval

CREATE TABLE dbo.IntegerSettings(SettingID INT NOT NULL,

  IntValue INT NOT NULL,

  StartedAt DATETIME NOT NULL,

  FinishedAt DATETIME NOT NULL,

  PreviousFinishedAt DATETIME NULL,

  CONSTRAINT PK_IntegerSettings_SettingID_FinishedAt PRIMARY KEY(SettingID, FinishedAt),

  CONSTRAINT UNQ_IntegerSettings_SettingID_PreviousFinishedAt UNIQUE(SettingID, PreviousFinishedAt),

  CONSTRAINT FK_IntegerSettings_SettingID_PreviousFinishedAt

    FOREIGN KEY(SettingID, PreviousFinishedAt)

    REFERENCES dbo.IntegerSettings(SettingID, FinishedAt),

  CONSTRAINT CHK_IntegerSettings_PreviousFinishedAt_NotAfter_StartedAt CHECK(PreviousFinishedAt <= StartedAt),

  CONSTRAINT CHK_IntegerSettings_StartedAt_Before_FinishedAt CHECK(StartedAt < FinishedAt)

);

GO

INSERT INTO dbo.IntegerSettings(SettingID, IntValue, StartedAt, FinishedAt, PreviousFinishedAt)

  VALUES(1, 1, '20070101', '20070103', NULL);

It has five constraints which work together to implement the business rule. Let me demonstrate how the more complex ones work. Of course, some constraints are simple and as such do not need any explanations.

**

  • There can be only one first interval for a setting

**

The constraint UNQ_IntegerSettings_SettingID_PreviousFinishedAt ensures exactly that. The first interval does not have a previous one, which means that PreviousFinishedAt IS NULL. The UNIQUE constraint guarantees that there can be only one such row per setting. See for yourself:

INSERT INTO dbo.IntegerSettings(SettingID, IntValue, StartedAt, FinishedAt, PreviousFinishedAt)

  VALUES(1, 1, '20070104', '20070105', NULL);

/*

Server: Msg 2627, Level 14, State 2, Line 1

Violation of UNIQUE KEY constraint 'UNQ_IntegerSettings_SettingID_PreviousFinishedAt'. Cannot insert duplicate key in object 'dbo.IntegerSettings'.

The statement has been terminated.

*/

**

  • Next window must begin after the end of the previous one.

**

The constraint CHK_IntegerSettings_PreviousFinishedAt_NotAfter_StartedAt guarantees exactly that. See for yourself:

INSERT INTO dbo.IntegerSettings(SettingID, IntValue, StartedAt, FinishedAt, PreviousFinishedAt)

  VALUES(1, 2, '20070104', '20070109', '20070105')

/*

Server: Msg 547, Level 16, State 1, Line 1

INSERT statement conflicted with TABLE CHECK constraint 'CHK_IntegerSettings_PreviousFinishedAt_NotAfter_StartedAt'. The conflict occurred in database 'RiskCenter', table 'IntegerSettings'.

The statement has been terminated.

*/

**

  • Two different windows cannot refer to one and the same window as their previous one.

**

Again, the same constraint UNQ_IntegerSettings_SettingID_PreviousFinishedAt guarantees precisely that, as demonstrated below:

INSERT INTO dbo.IntegerSettings(SettingID, IntValue, StartedAt, FinishedAt, PreviousFinishedAt)

  VALUES(1, 3, '20070104', '20070115', '20070103')



Msg 2627, Level 14, State 1, Line 1

Violation of UNIQUE KEY constraint 'UNQ_IntegerSettings_SettingID_PreviousFinishedAt'. Cannot insert duplicate key in object 'dbo.IntegerSettings'.

The statement has been terminated.

This means that there can be no overlaps.

As you have seen, for every time window, there can be at most one preceding it, and at most one following it. The following interval cannot begin before the end of its previous one. Together these two statements mean that there can be no overlaps.

**

  • Working with gaps.

**

You can prohibit gaps altogether, just replace the following constraint:

  CONSTRAINT CHK_IntegerSettings_PreviousFinishedAt_NotAfter_StartedAt CHECK(PreviousFinishedAt <= StartedAt),

With a stricter one, as follows:

 CONSTRAINT CHK_IntegerSettings_PreviousFinishedAt_EqualTo_StartedAt CHECK(PreviousFinishedAt = StartedAt),

But if you allow gaps, the query to retrieve them is very simple and performant, as follows:

SELECT PreviousFinishedAt AS GapStart, StartedAt AS GapEnd
  FROM dbo.IntegerSettings
  WHERE StartedAt > PreviousFinishedAt;
share|improve this answer

Recursive CTEs are perfect for this job.

You don't need cursors in this case, and I bet a CTE will perform much better than any cursor- or loop-based approach to solving this problem.

The following query gives you exactly what you need. I tested it on SQL Server 2008, but if you ignore the setup block and replace @table with the name of your target table, you should be able to run this against any platform that supports CTEs like Oracle, SQL Server, or PostgreSQL.

-- setup
DECLARE @table TABLE (
      project   VARCHAR(10) NOT NULL
    , item      VARCHAR(20) NOT NULL
    , method    CHAR(2)     NOT NULL
    , start     INT         NOT NULL
    , [end]     INT         NOT NULL
);

INSERT INTO @table
VALUES
      ('ABC', 'widget1', 'XY', 1000, 1033)
    , ('ABC', 'widget1', 'XY', 1033, 1062)
    , ('ABC', 'widget1', 'XY', 1062, 1112)
    , ('ABC', 'widget1', 'XY', 1112, 1163)
    , ('ABC', 'widget1', 'WW', 1163, 1223)
    , ('ABC', 'widget1', 'WW', 1223, 1288)
    , ('ABC', 'widget1', 'WW', 1288, 1334)
    , ('ABC', 'widget1', 'XY', 1334, 1383)
    , ('ABC', 'widget1', 'XY', 1383, 1425)
;

-- query
WITH connected_ranges AS (
    SELECT
          right_range.project
        , right_range.method
        , right_range.item
        , right_range.start
        , right_range.[end]
    FROM
                            @table  left_range
        RIGHT OUTER JOIN    @table  right_range
            ON  right_range.project = left_range.project
            AND right_range.item    = left_range.item
            AND right_range.method  = left_range.method
            AND right_range.start   = left_range.[end]
    WHERE left_range.project IS NULL

    UNION ALL

    SELECT
          right_range.project
        , right_range.method
        , right_range.item
        , left_range.start
        , right_range.[end]
    FROM
                    connected_ranges    left_range
        INNER JOIN  @table              right_range
            ON  right_range.project = left_range.project
            AND right_range.item    = left_range.item
            AND right_range.method  = left_range.method
            AND right_range.start   = left_range.[end] 
)
--SELECT *
--FROM connected_ranges
--ORDER BY
--    project
--  , method
--  , item
--  , start
--  , [end]
--;
SELECT
      project
    , method
    , item
    , start
    , MAX([end])    AS [end]
FROM connected_ranges
GROUP BY
      project
    , method
    , item
    , start
;

To summarize what I've done: I use a recursive CTE to join all the contiguous segments together, starting from the left-most edge and building up to the right. Then, in the final SELECT I pull only the largest, non-overlapping segments.

share|improve this answer
    
Nick, +1 but on Oracle I would just write a cursor - it would be very simple and perform very fast, at least as fast as any set- based query. –  AlexKuznetsov May 3 '12 at 1:20
1  
@Alex - I typically shy away from cursors as I'm used to thinking in SQL Server terms, though I understand that they are more commonly used on Oracle. Do you really think a cursor-based approach to this problem on Oracle would scale as gracefully as the recursive CTE as the source table grew? I find that hard to believe. –  Nick Chammas May 3 '12 at 1:28
    
In Oracle, cursors are usually as fast as simple set-based queries. We can update several million rows one by one via a cursor and have exactly the same performance as a set-based update. This means that when the optimizer does not get it, we can easily write our own execution plan in PL/SQL. With time series related queries on SQL Server, I frequently just load data into a C# dll and write my own plan in C#. It can be a thousand times faster or more than an equivalent T-SQL set based query. –  AlexKuznetsov May 3 '12 at 13:20

Here are three methods of solving this in Oracle. The first is an Analytic SQL solution that only has to do one full table scan (assuming no indexes). The second is Nick Chammas's CTE solution converted to Oracle syntax and the third is a solution using a PL/SQL cursor FOR loop inside a Pipelined function. The solutions all produce the results expected. For these few rows the analytic solution performs best followed by the recursive CTE. Which is easiest to work with will be in the eye of the beholder.

Analytic Solution

SELECT Project, Item, Method, Min("Start") "Start", Max("End") "End" FROM (
   SELECT Project, Item, Method, "Start", "End"
      , MAX(Change) OVER (PARTITION BY Project, Item ORDER BY "Start", "End") ChangeGroup
   FROM (
         SELECT Project, Item, Method, "Start", "End"
            , CASE WHEN Method = 
                 LAG(Method) OVER (PARTITION BY Project, Item ORDER BY "Start", "End") THEN NULL
              ELSE Row_Number() OVER (ORDER BY Project, Item, "Start", "End")
              END Change
         FROM T1
   )
) 
GROUP BY Project, Item, Method, ChangeGroup
ORDER BY 1, 2, 4, 5;

CTE Solution

WITH connected_ranges (Project, Method, Item, "Start", "End") AS (
    SELECT right_range.project, right_range.method, right_range.item, right_range."Start"
       , right_range."End"
    FROM T1  left_range
    RIGHT OUTER JOIN    T1  right_range
       ON  right_range.project = left_range.project
       AND right_range.item    = left_range.item
       AND right_range.method  = left_range.method
       AND right_range."Start" = left_range."End"
    WHERE left_range.project IS NULL
    UNION ALL
    SELECT right_range.project, right_range.method, right_range.item, left_range."Start"
       , right_range."End"
    FROM connected_ranges left_range
    INNER JOIN  T1 right_range
       ON  right_range.project = left_range.project
       AND right_range.item    = left_range.item
       AND right_range.method  = left_range.method
       AND right_range."Start" = left_range."End"
)
SELECT project, item, Method, "Start", MAX("End") AS "End"
FROM connected_ranges
GROUP BY project, method, item, "Start"
ORDER BY 1, 2, 4, 5;

PL/SQL Cursor FOR Loop Solution

CREATE OR REPLACE 
CREATE OR REPLACE FUNCTION PipeResult Return 
BEGIN
   For vLoop In (
      SELECT Project, Item, Method, "Start", "End"
         , LAG(Method) OVER (PARTITION BY Project, Item ORDER BY "Start", "End") LagMethod
   ) Loop
      Pipe Row 
   End Loop;
END;
/


CREATE OR REPLACE PACKAGE Example AUTHID DEFINER AS
   Type tRow Is Record (
        Project Varchar2(3)
      , Item    Varchar2(7)
      , Method  Varchar2(2)
      , "Start" Number(4)
      , "End"   Number(4)
      );
   Type tTable Is Table of tRow;
   Function PipelineResult(pDate In Date DEFAULT sysdate) Return tTable Pipelined;
END Example;
/

CREATE OR REPLACE PACKAGE BODY Example AS
   Function PipelineResult(pDate In Date DEFAULT sysdate) Return tTable Pipelined AS
      vSavedRow tRow;
   Begin
      For vRow IN (
         SELECT Project, Item, Method, "Start", "End"
            , LEAD(Method) OVER (PARTITION BY Project, Item ORDER BY "Start", "End") LeadMethod
         FROM T1
         ORDER BY Project, Item, "Start", "End"
      )
      Loop
         If (vSavedRow.Method IS NULL) Then
            vSavedRow.Project := vRow.Project;
            vSavedRow.Item := vRow.Item;
            vSavedRow.Method := vRow.Method;
            vSavedRow."Start" := vRow."Start";
         End If;

         vSavedRow."End" := vRow."End";

         If (vRow.Method <> vRow.LeadMethod OR vRow.LeadMethod IS NULL) Then
            Pipe Row(vSavedRow);
            vSavedRow.Method := NULL;
         End If;
      End Loop;
   End;
END Example;
/


SELECT * FROM TABLE(Example.PipelineResult);

Demonstration Environment:

DROP TABLE T1;
CREATE TABLE T1 AS (
   SELECT 'ABC' Project, 'widget1' Item, 'XY' Method, 1000 "Start", 
      1033 "End"FROM dual);
INSERT INTO T1 VALUES ('ABC','widget1','XY',1033,1062);
INSERT INTO T1 VALUES ('ABC','widget1','XY',1062,1112);
INSERT INTO T1 VALUES ('ABC','widget1','XY',1112,1163);
INSERT INTO T1 VALUES ('ABC','widget1','WW',1163,1223);
INSERT INTO T1 VALUES ('ABC','widget1','WW',1223,1288);
INSERT INTO T1 VALUES ('ABC','widget1','WW',1288,1334);
INSERT INTO T1 VALUES ('ABC','widget1','XY',1334,1383);
INSERT INTO T1 VALUES ('ABC','widget1','XY',1383,1425);
COMMIT;
share|improve this answer

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.