Lacunes et îles: solution client vs requête T-SQL

Une solution T-SQL pour les lacunes et les îles peut-elle s'exécuter plus rapidement qu'une solution C # exécutée sur le client?

Pour être précis, fournissons quelques données de test:

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

Ce premier ensemble de données de test présente exactement une lacune:

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

Le deuxième ensemble de données de test a 2M -1 espaces, un espace entre chacun des deux intervalles adjacents:

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

Actuellement, je lance 2008 R2, mais les solutions 2012 sont les bienvenues. J'ai publié ma solution C # comme réponse.

Et une solution d'une seconde ...

;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

Le code C # suivant résout le problème:

    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);

Ce code appelle cette procédure stockée:

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

Il trouve et imprime un intervalle à 2 M d'intervalle dans les moments suivants, cache chaud:

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

Il trouve et imprime 2M-1 intervalles à 2M dans les moments suivants, cache chaud:

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

C'est une solution très simple - il m'a fallu 10 minutes pour développer. Un récent diplômé d'université peut le proposer. Du côté de la base de données, le plan d'exécution est une jointure de fusion triviale qui utilise très peu de CPU et de mémoire.

Edit: pour être réaliste, j'exécute le client et le serveur sur des boîtes séparées.

Je pense avoir épuisé les limites de mes connaissances en serveur SQL sur celui-ci ....

Pour trouver un écart dans SQL Server (ce que fait le code C #), et vous ne vous souciez pas du début ou de la fin des écarts (ceux avant le premier démarrage ou après la dernière fin), la requête (ou variantes) suivante est la le plus vite que j'ai pu trouver:

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

Ce qui fonctionne bien à la main que pour chaque ensemble de départ-arrivée, vous pouvez traiter le début et la fin comme des séquences distinctes, décaler la fin d'une unité et des espaces sont affichés.

par exemple prendre (S1, F1), (S2, F2), (S3, F3), et ordonner comme: {S1, S2, S3, null} et {null, F1, F2, F3} Ensuite, comparer la ligne n à la ligne n dans chaque ensemble, et les écarts sont là où la valeur de l'ensemble F est inférieure à la valeur de l'ensemble S ... le problème, je pense, est que dans SQL Server, il n'y a aucun moyen de joindre ou de comparer deux ensembles distincts uniquement sur l'ordre des valeurs dans l'ensemble ... d'où l'utilisation de la fonction row_number pour nous permettre de fusionner uniquement sur la base du numéro de ligne ... mais il n'y a aucun moyen de dire au serveur SQL que ces valeurs sont uniques (sans les insérer dans une table var avec un index dessus - qui prend plus de temps - je l'ai essayé), donc je pense que la jointure de fusion est moins qu'optimale? (bien que difficile à prouver quand c'est plus rapide que tout ce que je pourrais faire)

J'ai pu obtenir des solutions en utilisant les fonctions 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

(ce qui, soit dit en passant, je ne garantis pas les résultats - cela semble fonctionner, mais je pense que je compte sur StartedAt pour être en ordre dans le tableau des tâches ... et c'était plus lent)

En utilisant le changement de somme:

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

(pas de surprise, aussi plus lent)

J'ai même essayé une fonction d'agrégation CLR (pour remplacer la somme - elle était plus lente que la somme et je comptais sur row_number () pour conserver l'ordre des données), et CLR une fonction de valeur de table (pour ouvrir deux jeux de résultats et comparer des valeurs basées uniquement sur sur séquence) ... et c'était aussi plus lent. Je me suis cogné la tête tellement de fois sur les limitations SQL et CLR, en essayant de nombreuses autres méthodes ...

Et pour quoi?

En cours d'exécution sur la même machine et en répartissant à la fois les données C # et les données filtrées SQL dans un fichier (selon le code C # d'origine), les temps sont pratiquement les mêmes .... environ 2 secondes pour les 1 données d'écart (C # généralement plus rapide ), 8 à 10 secondes pour l'ensemble de données à intervalles multiples (SQL généralement plus rapide).

REMARQUE : n'utilisez pas l'environnement de développement SQL Server pour la comparaison de synchronisation, car son affichage sur la grille prend du temps. Testé avec SQL 2012, VS2010, .net 4.0 Profil client

Je soulignerai que les deux solutions effectuent à peu près le même tri des données sur le serveur SQL, de sorte que la charge du serveur pour le fetch-sort sera similaire, quelle que soit la solution que vous utilisez, la seule différence étant le traitement sur le client (plutôt que sur le serveur) et le transfert sur le réseau.

Je ne sais pas quelle pourrait être la différence lors du partitionnement par différents membres du personnel, ou quand vous pourriez avoir besoin de données supplémentaires avec les informations sur l'écart (bien que je ne puisse pas penser à autre chose qu'un identifiant du personnel), ou bien sûr si il y a une connexion de données lente entre le serveur SQL et la machine cliente (ou un client lent ) ... Je n'ai pas non plus comparé les temps de verrouillage, ou les problèmes de contention, ou les problèmes de CPU / RESEAU pour plusieurs utilisateurs ... Donc, je Je ne sais pas lequel est le plus susceptible d'être un goulot d'étranglement dans ce cas.

Ce que je sais, c'est oui, le serveur SQL n'est pas bon dans ce genre de comparaisons d'ensemble, et si vous n'écrivez pas correctement la requête, vous en paierez le prix fort.

Est-ce plus facile ou plus difficile que d'écrire la version C #? Je ne suis pas tout à fait sûr, le changement +/- 1, la solution totale en cours d'exécution n'est pas entièrement intuitif non plus, et moi, mais ce n'est pas la première solution à laquelle un diplômé moyen viendrait ... une fois terminé, il est assez facile de copier, mais il faut un aperçu pour écrire en premier lieu ... il en va de même pour la version SQL. Quel est le plus difficile? Qu'est-ce qui est plus robuste pour les données frauduleuses? Lequel a le plus de potentiel pour les opérations parallèles? Est-ce vraiment important lorsque la différence est si faible par rapport à l'effort de programmation?

Une dernière note; il y a une contrainte non déclarée sur les données - le StartedAt doit être inférieur au FinishedAt, sinon vous obtiendrez de mauvais résultats.

Voici une solution qui s'exécute en 4 secondes.

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;