Luki i wyspy: rozwiązanie klienta a zapytanie T-SQL

Czy rozwiązanie T-SQL dla luk i wysp może działać szybciej niż rozwiązanie C # działające na kliencie?

Aby być konkretnym, podajmy dane testowe:

CREATE TABLE dbo.Numbers
  (
    n INT NOT NULL
          PRIMARY KEY
  ) ; 
GO 

INSERT  INTO dbo.Numbers
        ( n )
VALUES  ( 1 ) ; 
GO 
DECLARE @i INT ; 
SET @i = 0 ; 
WHILE @i < 21 
  BEGIN 
    INSERT  INTO dbo.Numbers
            ( n 
            )
            SELECT  n + POWER(2, @i)
            FROM    dbo.Numbers ; 
    SET @i = @i + 1 ; 
  END ;  
GO

CREATE TABLE dbo.Tasks
  (
    StartedAt SMALLDATETIME NOT NULL ,
    FinishedAt SMALLDATETIME NOT NULL ,
    CONSTRAINT PK_Tasks PRIMARY KEY ( StartedAt, FinishedAt ) ,
    CONSTRAINT UNQ_Tasks UNIQUE ( FinishedAt, StartedAt )
  ) ;
GO

INSERT  INTO dbo.Tasks
        ( StartedAt ,
          FinishedAt
        )
        SELECT  DATEADD(MINUTE, n, '20100101') AS StartedAt ,
                DATEADD(MINUTE, n + 2, '20100101') AS FinishedAt
        FROM    dbo.Numbers
        WHERE   ( n < 500000
                  OR n > 500005
                )
GO

Ten pierwszy zestaw danych testowych ma dokładnie jedną lukę:

SELECT  StartedAt ,
        FinishedAt
FROM    dbo.Tasks
WHERE   StartedAt BETWEEN DATEADD(MINUTE, 499999, '20100101')
                  AND     DATEADD(MINUTE, 500006, '20100101')

Drugi zestaw danych testowych ma przerwy 2M -1, odstęp między każdym z dwóch sąsiednich przedziałów:

TRUNCATE TABLE dbo.Tasks;
GO

INSERT  INTO dbo.Tasks
        ( StartedAt ,
          FinishedAt
        )
        SELECT  DATEADD(MINUTE, 3*n, '20100101') AS StartedAt ,
                DATEADD(MINUTE, 3*n + 2, '20100101') AS FinishedAt
        FROM    dbo.Numbers
        WHERE   ( n < 500000
                  OR n > 500005
                )
GO

Obecnie korzystam z 2008 R2, ale rozwiązania z 2012 roku są bardzo mile widziane. W odpowiedzi opublikowałem moje rozwiązanie C #.

I 1 sekundowe rozwiązanie ...

;WITH cteSource(StartedAt, FinishedAt)
AS (
    SELECT      s.StartedAt,
            e.FinishedAt
    FROM        (
                SELECT  StartedAt,
                    ROW_NUMBER() OVER (ORDER BY StartedAt) AS rn
                FROM    dbo.Tasks
            ) AS s
    INNER JOIN  (
                SELECT  FinishedAt,
                    ROW_NUMBER() OVER (ORDER BY FinishedAt) + 1 AS rn
                FROM    dbo.Tasks
            ) AS e ON e.rn = s.rn
    WHERE       s.StartedAt > e.FinishedAt

    UNION ALL

    SELECT  MIN(StartedAt),
        MAX(FinishedAt)
    FROM    dbo.Tasks
), cteGrouped(theTime, grp)
AS (
    SELECT  u.theTime,
        (ROW_NUMBER() OVER (ORDER BY u.theTime) - 1) / 2
    FROM    cteSource AS s
    UNPIVOT (
            theTime
            FOR theColumn IN (s.StartedAt, s.FinishedAt)
        ) AS u
)
SELECT      MIN(theTime),
        MAX(theTime)
FROM        cteGrouped
GROUP BY    grp
ORDER BY    grp

Poniższy kod C # rozwiązuje problem:

    var connString =
        "Initial Catalog=MyDb;Data Source=MyServer;Integrated Security=SSPI;Application Name=Benchmarks;";

    var stopWatch = new Stopwatch();
    stopWatch.Start();

    using (var conn = new SqlConnection(connString))
    {
        conn.Open();
        var command = conn.CreateCommand();
        command.CommandText = "dbo.GetAllTaskEvents";
        command.CommandType = CommandType.StoredProcedure;
        var gaps = new List<string>();
        using (var dr = command.ExecuteReader())
        {
            var currentEvents = 0;
            var gapStart = new DateTime();
            var gapStarted = false;
            while (dr.Read())
            {
                var change = dr.GetInt32(1);
                if (change == -1 && currentEvents == 1)
                {
                    gapStart = dr.GetDateTime(0);
                    gapStarted = true;
                }
                else if (change == 1 && currentEvents == 0 && gapStarted)
                {
                    gaps.Add(string.Format("({0},{1})", gapStart, dr.GetDateTime(0)));
                    gapStarted = false;
                }
                currentEvents += change;
            }
        }
        File.WriteAllLines(@"C:\Temp\Gaps.txt", gaps);
    }

    stopWatch.Stop();
    System.Console.WriteLine("Elapsed: " + stopWatch.Elapsed);

Ten kod wywołuje tę procedurę przechowywaną:

CREATE PROCEDURE dbo.GetAllTaskEvents
AS 
  BEGIN ;
    SELECT  EventTime ,
            Change
    FROM    ( SELECT  StartedAt AS EventTime ,
                      1 AS Change
              FROM    dbo.Tasks
              UNION ALL
              SELECT  FinishedAt AS EventTime ,
                      -1 AS Change
              FROM    dbo.Tasks
            ) AS TaskEvents
    ORDER BY EventTime, Change DESC ;
  END ;
GO

Wyszukuje i drukuje jedną przerwę w odstępach 2M w następujących okresach: ciepła pamięć podręczna:

1 gap: Elapsed: 00:00:01.4852029 00:00:01.4444307 00:00:01.4644152

Wyszukuje i drukuje przerwy 2M-1 w odstępach 2M w następujących czasach, ciepła pamięć podręczna:

2M-1 gaps Elapsed: 00:00:08.8576637 00:00:08.9123053 00:00:09.0372344 00:00:08.8545477

To bardzo proste rozwiązanie - opracowanie zajęło mi 10 minut. Niedawny absolwent college'u może to wymyślić. Po stronie bazy danych plan wykonania jest trywialnym połączeniem scalającym, które zużywa bardzo mało procesora i pamięci.

Edycja: aby być realistą, uruchamiam klienta i serwer na osobnych polach.

Myślę, że wyczerpałem granice mojej wiedzy na temat serwera SQL na tym ...

Aby znaleźć lukę w serwerze SQL (co robi kod C #), a nie przejmujesz się początkowymi lub końcowymi lukami (tymi przed pierwszym uruchomieniem lub po ostatnim zakończeniu), to następujące zapytanie (lub warianty) to najszybciej mogłem znaleźć:

SELECT e.FinishedAt as GapStart, s.StartedAt as GapEnd
FROM 
(
    SELECT StartedAt, ROW_NUMBER() OVER (ORDER BY StartedAt) AS rn
    FROM dbo.Tasks
) AS s
INNER JOIN  
(
    SELECT  FinishedAt, ROW_NUMBER() OVER (ORDER BY FinishedAt) + 1 AS rn
    FROM    dbo.Tasks
) AS e ON e.rn = s.rn and s.StartedAt > e.FinishedAt

To działa, choć nieznacznie z ręki, że dla każdego zestawu start-meta możesz traktować początek i koniec jako osobne sekwencje, przesunąć wykończenie o jeden i pokazywane są przerwy.

np. weź (S1, F1), (S2, F2), (S3, F3) i uporządkuj jako: {S1, S2, S3, null} i {null, F1, F2, F3} Następnie porównaj wiersz n do rzędu n w każdym zestawie, a luki są tam, gdzie wartość zestawu F jest mniejsza niż wartość zestawu S ... Problemem myślę, że w serwerze SQL nie ma możliwości połączenia lub porównania dwóch oddzielnych zestawów wyłącznie w kolejności wartości w zestaw ... stąd użycie funkcji numer_wiersza, aby umożliwić nam scalanie oparte wyłącznie na numerze wiersza ... ale nie ma sposobu, aby powiedzieć serwerowi SQL, że te wartości są unikalne (bez wstawiania ich do zmiennej var z indeksem na to - co trwa dłużej - próbowałem), więc myślę, że łączenie scalające jest mniej niż optymalne? (choć trudno udowodnić, kiedy jest szybszy niż cokolwiek innego, co mógłbym zrobić)

Udało mi się uzyskać rozwiązania za pomocą funkcji LAG / LEAD:

select * from
(
    SELECT top (100) percent StartedAt, FinishedAt, LEAD(StartedAt, 1, null) OVER (Order by FinishedAt) as NextStart
    FROM dbo.Tasks
) as x
where NextStart > FinishedAt

(które, nawiasem mówiąc, nie gwarantuję wyników - wydaje się, że działa, ale myślę, że polega na tym, że StartedA jest w porządku w tabeli Zadań ... i było wolniej)

Za pomocą zmiany sumy:

select * from
(
    SELECT EventTime, Change, SUM(Change) OVER (ORDER BY EventTime, Change desc ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) as RunTotal --, x.*
    FROM    
    ( 
        SELECT StartedAt AS EventTime, 1 AS Change
        FROM dbo.Tasks
    UNION ALL
        SELECT  FinishedAt AS EventTime, -1 AS Change
        FROM dbo.Tasks
    ) AS TaskEvents
) as x
where x.RunTotal = 0 or (x.RunTotal = 1 and x.Change = 1)
ORDER BY EventTime, Change DESC

(bez zaskoczenia, również wolniej)

Próbowałem nawet funkcji agregującej CLR (w celu zastąpienia sumy - była wolniejsza od sumy i polegałem na row_number () w celu zachowania kolejności danych), a CLR to funkcja o wartościach w tabeli (aby otworzyć dwa zestawy wyników i porównać wartości oparte wyłącznie sekwencyjnie) ... i to też było wolniejsze. Wielokrotnie waliłem głową w ograniczenia SQL i CLR, próbując wielu innych metod ...

I po co?

Działa na tym samym komputerze i pluje zarówno dane C #, jak i dane filtrowane SQL do pliku (zgodnie z oryginalnym kodem C #), czasy są praktycznie takie same .... około 2 sekund dla danych 1 luki (C # zwykle szybciej ), 8–10 sekund dla zestawu danych z wieloma przerwami (SQL zwykle szybciej).

UWAGA : Nie używaj środowiska programistycznego SQL Server do porównywania czasu, ponieważ jego wyświetlanie do siatki wymaga czasu. Testowany z SQL 2012, VS2010, profil klienta .net 4.0

Zwrócę uwagę, że oba rozwiązania wykonują prawie takie same sortowanie danych na serwerze SQL, więc obciążenie serwera dla pobierania i sortowania będzie podobne, niezależnie od tego, które rozwiązanie zastosujesz, jedyną różnicą jest przetwarzanie na kliencie (a nie na serwerze) oraz transfer przez sieć.

Nie wiem, jaka może być różnica podczas partycjonowania przez różnych członków personelu, lub kiedy możesz potrzebować dodatkowych danych z informacjami o luce (chociaż nie mogę wymyślić nic innego niż identyfikator personelu), lub oczywiście, jeśli jest powolne połączenie danych pomiędzy serwerem SQL i komputerze klienta (lub powolnego klienta) ... ani nie zrobiłem porównanie czasów blokady lub problemów rywalizacji lub CPU / problemów sieciowych dla wielu użytkowników ... Więc ja nie wiem, który z nich może być w tym przypadku wąskim gardłem.

Wiem, że tak, serwer SQL nie jest dobry w tego rodzaju zestawieniach porównań, a jeśli nie napiszesz poprawnie zapytania, słono za to zapłacisz.

Czy jest to łatwiejsze czy trudniejsze niż pisanie wersji C #? Nie jestem do końca pewien, czy zmiana +/- 1, uruchamianie kompleksowego rozwiązania, nie jest również całkowicie intuicyjna, ale ja, ale nie jest to pierwsze rozwiązanie, do którego wpadłby przeciętny absolwent ... po wykonaniu można łatwo skopiować, ale przede wszystkim potrzeba wglądu ... to samo można powiedzieć o wersji SQL. Co jest trudniejsze? Który jest bardziej odporny na nieuczciwe dane? Który ma większy potencjał dla operacji równoległych? Czy to naprawdę ma znaczenie, gdy różnica jest tak mała w porównaniu do wysiłku programowania?

Ostatnia uwaga; istnieje nieokreślone ograniczenie danych - wartość StartedAt musi być mniejsza niż wartość FinishedAt, w przeciwnym razie otrzymasz złe wyniki.

Oto rozwiązanie, które działa za 4 sekundy.

WITH cteRaw(ts, type, e, s)
AS (
    SELECT  StartedAt,
        1 AS type,
        NULL,
        ROW_NUMBER() OVER (ORDER BY StartedAt)
    FROM    dbo.Tasks

    UNION ALL

    SELECT  FinishedAt,
        -1 AS type, 
        ROW_NUMBER() OVER (ORDER BY FinishedAt),
        NULL
    FROM    dbo.Tasks
), cteCombined(ts, e, s, se)
AS (
    SELECT  ts,
        e,
        s,
        ROW_NUMBER() OVER (ORDER BY ts, type DESC)
    FROM    cteRaw
), cteFiltered(ts, grpnum)
AS (
    SELECT  ts, 
        (ROW_NUMBER() OVER (ORDER BY ts) - 1) / 2 AS grpnum
    FROM    cteCombined
    WHERE   COALESCE(s + s - se - 1, se - e - e) = 0
)
SELECT      MIN(ts) AS starttime,
        MAX(ts) AS endtime
FROM        cteFiltered
GROUP BY    grpnum;