Bagaimana saya bisa menulis kueri windowing yang meringkas kolom untuk membuat ember terpisah?

11

Saya memiliki tabel yang menyertakan kolom nilai desimal, seperti ini:

id value size
-- ----- ----
 1   100  .02
 2    99  .38
 3    98  .13
 4    97  .35
 5    96  .15
 6    95  .57
 7    94  .25
 8    93  .15

Apa yang perlu saya capai sedikit sulit untuk dijelaskan, jadi tolong tahan dengan saya. Apa yang saya coba lakukan adalah membuat nilai agregat sizekolom yang bertambah 1 setiap kali baris sebelumnya berjumlah 1, ketika dalam urutan menurun menurut value. Hasilnya akan terlihat seperti ini:

id value size bucket
-- ----- ---- ------
 1   100  .02      1
 2    99  .38      1
 3    98  .13      1
 4    97  .35      1
 5    96  .15      2
 6    95  .57      2
 7    94  .25      2
 8    93  .15      3

Upaya naif pertama saya adalah tetap berjalan SUMdan kemudian CEILINGnilai itu, namun itu tidak menangani kasus di mana beberapa catatan sizeakhirnya berkontribusi terhadap total dua ember terpisah. Contoh di bawah ini dapat menjelaskan hal ini:

id value size crude_sum crude_bucket distinct_sum bucket
-- ----- ---- --------- ------------ ------------ ------
 1   100  .02       .02            1          .02      1
 2    99  .38       .40            1          .40      1
 3    98  .13       .53            1          .53      1
 4    97  .35       .88            1          .88      1
 5    96  .15      1.03            2          .15      2
 6    95  .57      1.60            2          .72      2
 7    94  .25      1.85            2          .97      2
 8    93  .15      2.00            2          .15      3

Seperti yang Anda lihat, jika saya hanya menggunakan CEILINGpada crude_sumrecord # 8 akan ditugaskan ke bucket 2. Ini disebabkan oleh sizerecord # 5 dan # 8 yang dibagi menjadi dua ember. Sebagai gantinya, solusi ideal adalah mengatur ulang jumlah setiap kali mencapai 1, yang kemudian menambah bucketkolom dan memulai SUMoperasi baru mulai dari sizenilai catatan saat ini. Karena urutan catatan penting untuk operasi ini, saya telah memasukkan valuekolom, yang dimaksudkan untuk diurutkan dalam urutan menurun.

Upaya awal saya telah melibatkan membuat beberapa melewati data, sekali untuk melakukan SUMoperasi, sekali lagi untuk CEILINGitu, dll. Berikut adalah contoh dari apa yang saya lakukan untuk membuat crude_sumkolom:

SELECT
  id,
  value,
  size,
  (SELECT TOP 1 SUM(size) FROM table t2 WHERE t2.value<=t1.value) as crude_sum
FROM
  table t1

Yang digunakan dalam UPDATEoperasi untuk memasukkan nilai ke dalam tabel untuk dikerjakan nanti.

Sunting: Saya ingin mengambil langkah lain dalam menjelaskan ini, jadi begini. Bayangkan setiap catatan adalah benda fisik. Item itu memiliki nilai yang terkait dengannya, dan ukuran fisiknya kurang dari satu. Saya memiliki serangkaian ember dengan kapasitas volume tepat 1, dan saya perlu menentukan berapa banyak ember yang akan saya butuhkan dan ember mana yang dimasukkan setiap item sesuai dengan nilai item, diurutkan dari tertinggi ke terendah.

Item fisik tidak dapat ada di dua tempat sekaligus, jadi item tersebut harus berada dalam satu ember atau lainnya. Inilah sebabnya saya tidak dapat menjalankan CEILINGsolusi total + berjalan , karena itu akan memungkinkan catatan berkontribusi ukurannya menjadi dua ember.

Zikes
sumber
Anda harus menambahkan SQL Anda untuk menjelaskan apa yang termasuk dalam upaya awal Anda.
mdahlman
Apakah Anda akan menjumlahkan data sesuai dengan bucket yang Anda hitung, atau apakah nomor bucket adalah jawaban terakhir yang Anda cari?
Jon Seigel
2
Ack. Saya mungkin akan menggunakan aplikasi sisi klien karena itu akan mendukung streaming yang lebih baik dari catatan sebagai lawan dari loop kursor yang mengambil satu baris pada satu waktu. Saya pikir selama semua pembaruan dilakukan dalam batch, itu harus berkinerja cukup baik.
Jon Seigel
1
Seperti yang lain telah disebutkan, persyaratan untuk menangani distinct_counthal-hal yang rumit. Aaron Bertrand memiliki ringkasan opsi Anda di SQL Server untuk jenis pekerjaan windowing ini. Saya telah menggunakan metode "pembaruan unik" untuk menghitung distinct_sum, yang dapat Anda lihat di sini di SQL Fiddle , tetapi ini tidak dapat diandalkan.
Nick Chammas
1
@ JonSeigel Kita harus mencatat bahwa masalah menempatkan item X dalam jumlah minimal ember tidak dapat diselesaikan secara efisien menggunakan algoritma baris demi baris dari bahasa SQL. Misalnya item ukuran 0,7; 0,8; 0,3 akan membutuhkan 2 ember, tetapi jika diurutkan berdasarkan id mereka akan membutuhkan 3 ember.
Stoleg

Jawaban:

9

Saya tidak yakin jenis kinerja apa yang Anda cari, tetapi jika CLR atau aplikasi eksternal bukan pilihan, hanya kursor yang tersisa. Di laptop saya yang sudah tua, saya dapat melewati 1.000.000 baris dalam waktu sekitar 100 detik menggunakan solusi berikut. Hal yang menyenangkan tentang itu adalah skala secara linear, jadi saya akan melihat sekitar 20 menit untuk menjalankan seluruh hal. Dengan server yang layak Anda akan lebih cepat, tetapi bukan urutan besarnya, sehingga masih akan memakan waktu beberapa menit untuk menyelesaikan ini. Jika ini adalah proses satu kali saja, Anda mungkin dapat memperlambatnya. Jika Anda perlu menjalankan ini sebagai laporan atau serupa secara teratur, Anda mungkin ingin menyimpan nilai dalam tabel yang sama dan tidak memperbaruinya saat baris baru ditambahkan, misalnya dalam pemicu.

Bagaimanapun, ini kodenya:

IF OBJECT_ID('dbo.MyTable') IS NOT NULL DROP TABLE dbo.MyTable;

CREATE TABLE dbo.MyTable(
 Id INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
 v NUMERIC(5,3) DEFAULT ABS(CHECKSUM(NEWID())%100)/100.0
);


MERGE dbo.MyTable T
USING (SELECT TOP(1000000) 1 X FROM sys.system_internals_partition_columns A,sys.system_internals_partition_columns B,sys.system_internals_partition_columns C,sys.system_internals_partition_columns D)X
ON(1=0)
WHEN NOT MATCHED THEN
INSERT DEFAULT VALUES;

--SELECT * FROM dbo.MyTable

DECLARE @st DATETIME2 = SYSUTCDATETIME();
DECLARE cur CURSOR FAST_FORWARD FOR
  SELECT Id,v FROM dbo.MyTable
  ORDER BY Id;

DECLARE @id INT;
DECLARE @v NUMERIC(5,3);
DECLARE @running_total NUMERIC(6,3) = 0;
DECLARE @bucket INT = 1;

CREATE TABLE #t(
 id INT PRIMARY KEY CLUSTERED,
 v NUMERIC(5,3),
 bucket INT,
 running_total NUMERIC(6,3)
);

OPEN cur;
WHILE(1=1)
BEGIN
  FETCH NEXT FROM cur INTO @id,@v;
  IF(@@FETCH_STATUS <> 0) BREAK;
  IF(@running_total + @v > 1)
  BEGIN
    SET @running_total = 0;
    SET @bucket += 1;
  END;
  SET @running_total += @v;
  INSERT INTO #t(id,v,bucket,running_total)
  VALUES(@id,@v,@bucket, @running_total);
END;
CLOSE cur;
DEALLOCATE cur;
SELECT DATEDIFF(SECOND,@st,SYSUTCDATETIME());
SELECT * FROM #t;

GO 
DROP TABLE #t;

Ini menjatuhkan dan membuat ulang tabel MyTable, mengisinya dengan 1000000 baris dan kemudian mulai bekerja.

Kursor menyalin setiap baris ke tabel temp saat menjalankan perhitungan. Pada akhirnya pilih mengembalikan hasil yang dihitung. Anda mungkin sedikit lebih cepat jika Anda tidak menyalin data sekitar tetapi lakukan pembaruan di tempat.

Jika Anda memiliki opsi untuk memutakhirkan ke SQL 2012, Anda dapat melihat agregat jendela bergerak yang didukung kumparan jendela baru, yang seharusnya memberi Anda kinerja yang lebih baik.

Sebagai catatan, jika Anda memiliki rakitan yang diinstal dengan izin_set = aman, Anda dapat melakukan lebih banyak hal buruk ke server dengan T-SQL standar daripada dengan rakitan, jadi saya akan terus bekerja untuk menghilangkan penghalang itu - Anda harus menggunakan dengan baik kasus di sini di mana CLR benar-benar akan membantu Anda.

Sebastian Meine
sumber
Saya menerima yang ini karena betapa mudahnya untuk mengimplementasikan, dan betapa mudahnya saya dapat mengubah dan men-debug itu nanti ketika diperlukan. @Jawaban NickChammas juga benar dan mungkin berjalan lebih efisien, jadi saya kira ini masalah preferensi bagi orang lain yang menghadapi masalah serupa.
Zikes
9

Tidak ada fungsi windowing baru di SQL Server 2012, windowing kompleks dapat dicapai dengan menggunakan CTE rekursif. Saya bertanya-tanya seberapa baik ini akan bekerja terhadap jutaan baris.

Solusi berikut mencakup semua kasus yang Anda jelaskan. Anda dapat melihatnya beraksi di sini di SQL Fiddle .

-- schema setup
CREATE TABLE raw_data (
    id    INT PRIMARY KEY
  , value INT NOT NULL
  , size  DECIMAL(8,2) NOT NULL
);

INSERT INTO raw_data 
    (id, value, size)
VALUES 
   ( 1,   100,  .02) -- new bucket here
 , ( 2,    99,  .99) -- and here
 , ( 3,    98,  .99) -- and here
 , ( 4,    97,  .03)
 , ( 5,    97,  .04)
 , ( 6,    97,  .05)
 , ( 7,    97,  .40)
 , ( 8,    96,  .70) -- and here
;

Sekarang ambil napas dalam-dalam. Ada dua CTE utama di sini, masing-masing didahului oleh komentar singkat. Sisanya hanyalah "pembersihan" CTE, misalnya, untuk menarik baris yang tepat setelah kami memberi peringkat.

-- calculate the distinct sizes recursively
WITH distinct_size AS (
  SELECT
      id
    , size
    , 0 as level
  FROM raw_data

  UNION ALL

  SELECT 
      base.id
    , CAST(base.size + tower.size AS DECIMAL(8,2)) AS distinct_size
    , tower.level + 1 as level
  FROM 
                raw_data AS base
    INNER JOIN  distinct_size AS tower
      ON base.id = tower.id + 1
  WHERE base.size + tower.size <= 1
)
, ranked_sum AS (
  SELECT 
      id
    , size AS distinct_size
    , level
    , RANK() OVER (PARTITION BY id ORDER BY level DESC) as rank
  FROM distinct_size  
)
, top_level_sum AS (
  SELECT
      id
    , distinct_size
    , level
    , rank
  FROM ranked_sum
  WHERE rank = 1
)
-- every level reset to 0 means we started a new bucket
, bucket AS (
  SELECT
      base.id
    , COUNT(base.id) AS bucket
  FROM 
               top_level_sum base
    INNER JOIN top_level_sum tower
      ON base.id >= tower.id
  WHERE tower.level = 0
  GROUP BY base.id
)
-- join the bucket info back to the original data set
SELECT
    rd.id
  , rd.value
  , rd.size
  , tls.distinct_size
  , b.bucket
FROM 
             raw_data rd
  INNER JOIN top_level_sum tls
    ON rd.id = tls.id
  INNER JOIN bucket   b
    ON rd.id = b.id
ORDER BY
  rd.id
;

Solusi ini mengasumsikan bahwa itu idadalah urutan tanpa celah. Jika tidak, Anda harus membuat urutan gapless Anda sendiri dengan menambahkan CTE tambahan di awal yang memberi nomor baris dengan ROW_NUMBER()sesuai dengan urutan yang diinginkan (misalnya ROW_NUMBER() OVER (ORDER BY value DESC)).

Untungnya, ini sangat bertele-tele.

Nick Chammas
sumber
1
Solusi ini tampaknya tidak menangani kasus di mana baris dapat berkontribusi ukurannya ke beberapa ember. Jumlah bergulir cukup mudah, tetapi saya membutuhkan jumlah itu untuk mengatur ulang setiap kali mencapai 1. Lihat tabel contoh terakhir dalam pertanyaan saya dan bandingkan crude_sumdengan distinct_sumdan bucketkolom terkait untuk melihat apa yang saya maksud.
Zikes
2
@Zikes - Saya telah membahas kasus ini dengan solusi saya yang diperbarui.
Nick Chammas
Sepertinya itu seharusnya berfungsi sekarang. Saya akan bekerja mengintegrasikannya ke dalam basis data saya untuk mengujinya.
Zikes
@Zikes - Hanya ingin tahu, bagaimana kinerja berbagai solusi yang diposting di sini terhadap kumpulan data besar Anda? Saya menduga Andriy adalah yang tercepat.
Nick Chammas
5

Ini terasa seperti solusi konyol, dan mungkin tidak akan menskala dengan baik, jadi uji dengan hati-hati jika Anda menggunakannya. Karena masalah utama berasal dari "ruang" yang tersisa di ember, pertama-tama saya harus membuat catatan pengisi untuk menyatukan ke dalam data.

with bar as (
select
  id
  ,value
  ,size
  from foo
union all
select
  f.id
  ,value = null
  ,size = 1 - sum(f2.size) % 1
  from foo f
  inner join foo f2
    on f2.id < f.id
  group by f.id
    ,f.value
    ,f.size
  having cast(sum(f2.size) as int) <> cast(sum(f2.size) + f.size as int)
)
select
  f.id
  ,f.value
  ,f.size
  ,bucket = cast(sum(b.size) as int) + 1
  from foo f
  inner join bar b
    on b.id <= f.id
  group by f.id
    ,f.value
    ,f.size

http://sqlfiddle.com/#!3/72ad4/14/0

SQLFox
sumber
1
+1 Saya pikir ini berpotensi jika ada indeks yang sesuai.
Jon Seigel
3

Berikut ini adalah solusi CTE rekursif lain, meskipun saya akan mengatakan itu lebih mudah daripada saran @ Nick . Ini sebenarnya lebih dekat dengan kursor @ Sebastian , hanya saya yang menggunakan menjalankan perbedaan daripada menjalankan total. (Awalnya saya bahkan berpikir bahwa jawaban Nick akan sesuai dengan apa yang saya sarankan di sini, dan setelah mengetahui bahwa jawabannya sebenarnya adalah pertanyaan yang sangat berbeda yang saya putuskan untuk menawarkan milik saya.)

WITH rec AS (
  SELECT TOP 1
    id,
    value,
    size,
    bucket        = 1,
    room_left     = CAST(1.0 - size AS decimal(5,2))
  FROM atable
  ORDER BY value DESC
  UNION ALL
  SELECT
    t.id,
    t.value,
    t.size,
    bucket        = r.bucket + x.is_new_bucket,
    room_left     = CAST(CASE x.is_new_bucket WHEN 1 THEN 1.0 ELSE r.room_left END - t.size AS decimal(5,2))
  FROM atable t
  INNER JOIN rec r ON r.value = t.value + 1
  CROSS APPLY (
    SELECT CAST(CASE WHEN t.size > r.room_left THEN 1 ELSE 0 END AS bit)
  ) x (is_new_bucket)
)
SELECT
  id,
  value,
  size,
  bucket
FROM rec
ORDER BY value DESC
;

Catatan: kueri ini mengasumsikan bahwa valuekolom terdiri dari nilai unik tanpa celah. Jika bukan itu masalahnya, Anda harus memperkenalkan kolom peringkat yang dihitung berdasarkan urutan menurun valuedan menggunakannya dalam CTE rekursif alih-alih valuebergabung dengan bagian rekursif dengan jangkar.

Demo SQL Fiddle untuk kueri ini dapat ditemukan di sini .

Andriy M
sumber
Ini jauh lebih pendek dari apa yang saya tulis. Kerja bagus. Apakah ada alasan Anda menghitung mundur ruangan yang tersisa di ember daripada menghitung?
Nick Chammas
Ya, ada, tidak yakin apakah itu masuk akal untuk versi yang akhirnya saya posting di sini. Lagi pula, alasannya adalah bahwa tampaknya lebih mudah / lebih alami untuk membandingkan nilai tunggal dengan nilai tunggal ( sizedengan room_left) dibandingkan dengan membandingkan nilai tunggal dengan ekspresi ( 1dengan running_size+ size). Saya tidak menggunakan is_new_bucketbendera pada awalnya tetapi beberapa CASE WHEN t.size > r.room_left ...sebagai gantinya ("beberapa" karena saya juga sedang menghitung (dan mengembalikan) ukuran total, tetapi kemudian berpikir menentangnya demi kesederhanaan), jadi saya pikir itu akan lebih elegan seperti itu.
Andriy M