Brechas e islas: solución de cliente vs consulta T-SQL

¿Puede una solución T-SQL para huecos e islas ejecutarse más rápido que una solución C # que se ejecuta en el cliente?

Para ser específicos, proporcionemos algunos datos de prueba:

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

Este primer conjunto de datos de prueba tiene exactamente una brecha:

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

El segundo conjunto de datos de prueba tiene espacios de 2M -1, un espacio entre cada dos intervalos adyacentes:

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

Actualmente estoy ejecutando 2008 R2, pero las soluciones de 2012 son muy bienvenidas. He publicado mi solución C # como respuesta.

Y una solución de 1 segundo ...

;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

El siguiente código C # resuelve el problema:

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

Este código invoca este procedimiento almacenado:

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

Encuentra e imprime un espacio en intervalos de 2M en los siguientes tiempos, caché cálido:

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

Encuentra e imprime espacios de 2M-1 en intervalos de 2M en los siguientes tiempos, caché cálido:

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

Esta es una solución muy simple: me llevó 10 minutos desarrollarla. Un recién graduado de la universidad puede pensarlo. En el lado de la base de datos, el plan de ejecución es una combinación trivial de fusión que utiliza muy poca CPU y memoria.

Editar: para ser realista, estoy ejecutando cliente y servidor en cajas separadas.

Creo que he agotado los límites de mi conocimiento en el servidor SQL en este ...

Para encontrar una brecha en el servidor SQL (lo que hace el código C #), y no le importa comenzar o terminar las brechas (las que se encuentran antes del primer inicio o después del último final), la siguiente consulta (o variantes) es más rápido que pude encontrar:

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

Lo que funciona, aunque con poca mano, para cada conjunto de inicio-fin, puede tratar el inicio y el final como secuencias separadas, compensar el final en uno y se muestran los espacios.

Por ejemplo, tome (S1, F1), (S2, F2), (S3, F3) y ordene como: {S1, S2, S3, nulo} y {nulo, F1, F2, F3} Luego compare la fila n con la fila n en cada conjunto, y las brechas son donde el valor del conjunto F es menor que el valor del conjunto S ... el problema creo que es que en el servidor SQL no hay forma de unir o comparar dos conjuntos separados únicamente en el orden de los valores en el conjunto ... de ahí el uso de la función row_number para permitirnos fusionarnos basados ​​únicamente en el número de fila ... pero no hay forma de decirle al servidor SQL que estos valores son únicos (sin insertarlos en una tabla var con un índice en él, lo que lleva más tiempo, lo probé), ¿así que creo que la combinación de combinación es menos que óptima? (aunque difícil de probar cuando es más rápido que cualquier otra cosa que pueda hacer)

Pude obtener soluciones usando las funciones 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

(que por cierto, no garantizo los resultados, parece funcionar, pero creo que depende de que StartedAt esté en orden en la tabla Tareas ... y fue más lento)

Usando cambio de suma:

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

(no es de extrañar, también más lento)

Incluso probé una función agregada CLR (para reemplazar la suma; era más lenta que la suma y dependía de row_number () para mantener el orden de los datos), y CLR una función con valores de tabla (para abrir dos conjuntos de resultados y comparar valores basados ​​puramente en secuencia) ... y también fue más lento. Me golpeé la cabeza muchas veces con las limitaciones de SQL y CLR, probando muchos otros métodos ...

¿Y para qué?

Al ejecutarse en la misma máquina y escupir tanto los datos de C # como los datos filtrados por SQL en un archivo (según el código de C # original), los tiempos son prácticamente los mismos ... aproximadamente 2 segundos para los datos de 1 gap (C # generalmente más rápido ), 8-10 segundos para el conjunto de datos de espacio múltiple (SQL generalmente más rápido)

NOTA : No utilice el entorno de desarrollo de SQL Server para la comparación de tiempos, ya que su visualización en la cuadrícula lleva tiempo. Según lo probado con SQL 2012, VS2010, .net 4.0 Perfil del cliente

Señalaré que ambas soluciones realizan más o menos la misma clasificación de datos en el servidor SQL, por lo que la carga del servidor para fetch-sort será similar, cualquiera que sea la solución que use, la única diferencia es el procesamiento en el cliente (en lugar del servidor) y la transferencia a través de la red.

No sé cuál podría ser la diferencia al dividir por diferentes miembros del personal, tal vez, o cuando pueda necesitar datos adicionales con la información de brecha (aunque no puedo pensar en otra cosa que no sea una identificación del personal), o por supuesto si hay una conexión de datos lenta entre el servidor SQL y la máquina del cliente (o un cliente lento ) ... Tampoco he hecho una comparación de los tiempos de bloqueo o problemas de contención, o problemas de CPU / RED para múltiples usuarios ... Entonces No sé cuál es más probable que sea un cuello de botella en este caso.

Lo que sí sé es que sí, el servidor SQL no es bueno en este tipo de comparaciones de conjuntos, y si no escribe la consulta correctamente, la pagará caro.

¿Es más fácil o más difícil que escribir la versión de C #? No estoy completamente seguro, el cambio +/- 1, ejecutar la solución total tampoco es del todo intuitivo, y yo, pero no es la primera solución a la que llegaría un graduado promedio ... una vez hecho, es bastante fácil de copiar, pero se necesita una idea para escribir en primer lugar ... lo mismo se puede decir de la versión SQL. ¿Qué es más difícil? ¿Cuál es más robusto para rogue datos? ¿Cuál tiene más potencial para operaciones paralelas? ¿Realmente importa cuando la diferencia es tan pequeña en comparación con el esfuerzo de programación?

Una última nota; hay una restricción no declarada en los datos: StartedAt debe ser menor que FinishedAt o obtendrá malos resultados.

Aquí hay una solución que se ejecuta en 4 segundos.

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;