Kesenjangan dan pulau: solusi klien vs kueri T-SQL

Bisakah solusi T-SQL untuk kesenjangan dan pulau berjalan lebih cepat daripada solusi C # yang berjalan pada klien?

Untuk lebih spesifik, mari kita berikan beberapa data pengujian:

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

Rangkaian data uji pertama ini memiliki tepat satu celah:

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

Set kedua data uji memiliki kesenjangan 2M -1, kesenjangan antara masing-masing dua interval yang berdekatan:

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

Saat ini saya menjalankan 2008 R2, tetapi solusi 2012 sangat disambut. Saya telah memposting solusi C # saya sebagai jawaban.

Dan solusi 1 detik ...

;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

Kode C # berikut memecahkan masalah:

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

Kode ini menjalankan prosedur tersimpan ini:

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

Ia menemukan dan mencetak satu celah dalam interval 2M di waktu berikut, cache hangat:

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

Ia menemukan dan mencetak celah 2M-1 dalam interval 2M di waktu berikut, cache hangat:

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

Ini adalah solusi yang sangat sederhana - saya butuh 10 menit untuk berkembang. Lulusan perguruan tinggi baru-baru ini dapat memunculkannya. Di sisi basis data, rencana eksekusi adalah penggabungan sepele yang menggunakan sangat sedikit CPU dan memori.

Sunting: agar realistis, saya menjalankan klien dan server pada kotak terpisah.

Saya pikir saya telah kehabisan batas pengetahuan saya di SQL server yang satu ini ....

Untuk menemukan celah di SQL server (apa kode C # tidak), dan Anda tidak peduli memulai atau mengakhiri kesenjangan (yang sebelum mulai pertama, atau setelah selesai terakhir), maka kueri berikut (atau varian) adalah tercepat yang bisa saya temukan:

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

Yang bekerja dengan sedikit tangan untuk setiap set start-finish, Anda dapat memperlakukan start dan finish sebagai urutan yang terpisah, mengimbangi finish dengan satu dan celah ditampilkan.

mis. ambil (S1, F1), (S2, F2), (S3, F3), dan pesan sebagai: {S1, S2, S3, null} dan {null, F1, F2, F3} Kemudian bandingkan baris n ke baris n di setiap set, dan kesenjangan adalah di mana nilai set F kurang dari nilai set S ... masalahnya saya pikir adalah bahwa dalam SQL server tidak ada cara untuk bergabung atau membandingkan dua set terpisah murni pada urutan nilai-nilai di set ... maka penggunaan fungsi row_number untuk memungkinkan kita untuk menggabungkan berdasarkan murni pada nomor baris ... tetapi tidak ada cara untuk memberitahu SQL server bahwa nilai-nilai ini unik (tanpa memasukkannya ke dalam tabel var dengan indeks) di atasnya - yang membutuhkan waktu lebih lama - saya mencobanya), jadi saya pikir gabungan gabung kurang optimal? (Meskipun sulit untuk dibuktikan ketika itu lebih cepat daripada hal lain yang bisa saya lakukan)

Saya bisa mendapatkan solusi menggunakan fungsi 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

(yang omong-omong, saya tidak menjamin hasilnya - tampaknya berfungsi, tapi saya pikir mengandalkan BeginAt agar dalam urutan di tabel Tugas ... dan itu lebih lambat)

Menggunakan perubahan jumlah:

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

(tidak mengherankan, juga lebih lambat)

Saya bahkan mencoba fungsi agregat CLR (untuk mengganti jumlah - itu lebih lambat dari jumlah dan mengandalkan row_number () untuk menjaga urutan data), dan CLR fungsi tabel yang dihargai (untuk membuka dua set hasil dan membandingkan nilai berdasarkan murni pada urutan) ... dan itu juga lebih lambat. Saya membenturkan kepala saya berkali-kali pada SQL, dan keterbatasan CLR, mencoba banyak metode lain ...

Dan untuk apa?

Berjalan di mesin yang sama, dan meludahkan data C #, dan SQL memfilter data ke dalam file (sesuai kode C # asli), waktunya hampir sama .... kira-kira 2 detik untuk data 1 gap (C # biasanya lebih cepat ), 8-10 detik untuk set data multi-gap (SQL biasanya lebih cepat).

CATATAN : Jangan gunakan Lingkungan Pengembangan SQL Server untuk perbandingan waktu, karena tampilan ke grid membutuhkan waktu. Seperti yang diuji dengan profil klien SQL 2012, VS2010, .net 4.0

Saya akan menunjukkan bahwa kedua solusi melakukan cukup banyak pengurutan data yang sama pada server SQL sehingga beban server untuk fetch-sort akan serupa, solusi mana pun yang Anda gunakan, satu-satunya perbedaan adalah pemrosesan pada klien (bukan server) , dan transfer melalui jaringan.

Saya tidak tahu apa bedanya ketika dipartisi oleh anggota staf yang berbeda mungkin, atau ketika Anda mungkin membutuhkan data tambahan dengan informasi kesenjangan (meskipun saya tidak bisa memikirkan banyak hal selain id staf), atau tentu saja jika ada koneksi data yang lambat antara server SQL dan mesin klien (atau klien lambat ) ... Saya juga belum membuat perbandingan waktu-kunci, atau masalah pertikaian, atau masalah CPU / JARINGAN untuk banyak pengguna ... Jadi saya tidak tahu mana yang lebih mungkin menjadi hambatan dalam kasus ini.

Yang saya tahu, adalah ya, SQL server tidak pandai mengatur perbandingan ini, dan jika Anda tidak menulis kueri dengan benar, Anda akan membayar mahal.

Apakah lebih mudah atau lebih sulit daripada menulis versi C #? Saya tidak sepenuhnya yakin, Perubahan +/- 1, menjalankan solusi total tidak sepenuhnya intuitif juga, dan saya tetapi itu bukan solusi pertama lulusan rata-rata akan datang ke ... sekali selesai cukup mudah untuk menyalin, tetapi dibutuhkan wawasan untuk menulis di tempat pertama ... sama dapat dikatakan untuk versi SQL. Mana yang lebih sulit? Mana yang lebih kuat untuk data jahat? Mana yang lebih berpotensi untuk operasi paralel? Apakah penting ketika perbedaannya sangat kecil dibandingkan dengan upaya pemrograman?

Satu not terakhir; ada batasan yang tidak disebutkan pada data - StartingAt harus lebih kecil dari FinishedAt, atau Anda akan mendapatkan hasil yang buruk.

Inilah solusi yang berjalan dalam 4 detik.

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;