Wie kann ich eine Fensterabfrage schreiben, die eine Spalte summiert, um diskrete Buckets zu erstellen?

11

Ich habe eine Tabelle, die eine Spalte mit Dezimalwerten enthält, wie diese:

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

Was ich erreichen muss, ist etwas schwierig zu beschreiben. Bitte nehmen Sie Kontakt mit mir auf. Ich versuche, einen Gesamtwert der sizeSpalte zu erstellen, der jedes Mal um 1 erhöht wird, wenn die vorhergehenden Zeilen in absteigender Reihenfolge zu 1 summieren value. Das Ergebnis würde ungefähr so ​​aussehen:

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

Mein naiver erster Versuch war, einen laufenden Wert SUMund dann CEILINGdiesen Wert beizubehalten. Er behandelt jedoch nicht den Fall, in dem einige Datensätze sizezu insgesamt zwei separaten Buckets beitragen. Das folgende Beispiel könnte dies verdeutlichen:

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

Wie Sie sehen können, wenn ich einfach zu bedienen waren CEILINGauf crude_sumRekord # 8 würde 2. zu Eimer zugeordnet werden diese durch die verursacht wird , sizevon Datensätzen # 5 und # 8 , die geteilt in zwei Eimern. Stattdessen besteht die ideale Lösung darin, die Summe jedes Mal zurückzusetzen, wenn sie 1 erreicht. Dadurch wird die bucketSpalte erhöht und eine neue SUMOperation ab dem sizeWert des aktuellen Datensatzes gestartet. Da die Reihenfolge der Datensätze für diesen Vorgang wichtig ist, habe ich die valueSpalte eingefügt, die in absteigender Reihenfolge sortiert werden soll.

Meine ersten Versuche umfassten das Durchführen mehrerer Durchgänge über die Daten, einmal zum Ausführen des SUMVorgangs, noch einmal zum Durchführen CEILINGusw. Hier ist ein Beispiel dafür, was ich zum Erstellen der crude_sumSpalte getan habe :

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

Dies wurde in einer UPDATEOperation verwendet, um den Wert in eine Tabelle einzufügen, mit der später gearbeitet werden soll.

Bearbeiten: Ich würde gerne noch einmal versuchen, dies zu erklären, also geht es weiter. Stellen Sie sich vor, jeder Datensatz ist ein physischer Gegenstand. Diesem Element ist ein Wert zugeordnet und eine physische Größe von weniger als eins. Ich habe eine Reihe von Eimern mit einer Volumenkapazität von genau 1, und ich muss bestimmen, wie viele dieser Eimer ich benötige und in welchen Eimer jeder Artikel gemäß dem Wert des Artikels geht, sortiert vom höchsten zum niedrigsten.

Ein physischer Gegenstand kann nicht an zwei Orten gleichzeitig existieren, daher muss er sich in dem einen oder anderen Eimer befinden. Aus diesem Grund kann ich keine laufende Total + CEILING-Lösung durchführen, da Datensätze dadurch ihre Größe auf zwei Buckets übertragen können.

Zikes
quelle
Sie sollten Ihre SQL hinzufügen, um zu verdeutlichen, was Ihr erster Versuch beinhaltete.
Mdahlman
Werden Sie Daten nach dem Bucket aggregieren, den Sie berechnen, oder ist die Bucket-Nummer die endgültige Antwort, nach der Sie suchen?
Jon Seigel
2
Ack. Ich würde wahrscheinlich eine clientseitige App verwenden, da dies ein besseres Streaming von Datensätzen unterstützt als eine Cursorschleife, die jeweils eine Zeile abruft. Ich denke, solange alle Updates in Stapeln durchgeführt werden, sollte es einigermaßen gut funktionieren.
Jon Seigel
1
Wie die anderen bereits erwähnt haben, distinct_counterschwert das Erfordernis des Aufbockens die Dinge. Aaron Bertrand hat eine großartige Zusammenfassung Ihrer Optionen auf SQL Server für diese Art von Fensterarbeiten. Ich habe die "skurrile Update" -Methode verwendet, um zu berechnen distinct_sum, die Sie hier auf SQL Fiddle sehen können , aber dies ist unzuverlässig.
Nick Chammas
1
@ JonSeigel Wir sollten beachten, dass das Problem des Platzierens von X Elementen in einer minimalen Anzahl von Buckets nicht effizient mit einem zeilenweisen Algorithmus der SQL-Sprache gelöst werden kann. Zum Beispiel benötigen Artikel der Größe 0,7; 0,8; 0,3 2 Eimer, aber wenn sie nach ID sortiert sind, benötigen sie 3 Eimer.
Stoleg

Antworten:

9

Ich bin nicht sicher, welche Art von Leistung Sie suchen, aber wenn CLR oder externe App keine Option ist, bleibt nur ein Cursor übrig. Auf meinem alten Laptop komme ich mit der folgenden Lösung in etwa 100 Sekunden durch 1.000.000 Zeilen. Das Schöne daran ist, dass es linear skaliert, so dass ich mir ungefähr 20 Minuten Zeit nehmen würde, um das Ganze durchzugehen. Mit einem anständigen Server sind Sie schneller, aber nicht um eine Größenordnung. Es würde also noch einige Minuten dauern, bis dies abgeschlossen ist. Wenn dies ein einmaliger Prozess ist, können Sie sich die Langsamkeit wahrscheinlich leisten. Wenn Sie dies regelmäßig als Bericht oder ähnliches ausführen müssen, möchten Sie die Werte möglicherweise in derselben Tabelle speichern und nicht aktualisieren, wenn neue Zeilen hinzugefügt werden, z. B. in einem Trigger.

Wie auch immer, hier ist der Code:

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;

Es löscht und erstellt die Tabelle MyTable neu, füllt sie mit 1000000 Zeilen und macht sich dann an die Arbeit.

Der Cursor kopiert jede Zeile in eine temporäre Tabelle, während die Berechnungen ausgeführt werden. Am Ende gibt die Auswahl die berechneten Ergebnisse zurück. Sie sind möglicherweise etwas schneller, wenn Sie die Daten nicht kopieren, sondern stattdessen ein direktes Update durchführen.

Wenn Sie die Möglichkeit haben, ein Upgrade auf SQL 2012 durchzuführen, können Sie sich die neuen von Window Spool unterstützten Moving Window Aggregate ansehen, die Ihnen eine bessere Leistung bieten sollen.

Nebenbei bemerkt, wenn Sie eine Assembly mit erlaubnis_set = safe installiert haben, können Sie einem Server mit Standard-T-SQL mehr schlechte Dinge antun als mit der Assembly, also würde ich weiter daran arbeiten, diese Barriere zu entfernen - Sie haben eine gute Verwendung Fall hier, wo CLR Ihnen wirklich helfen würde.

Sebastian Meine
quelle
Ich habe dieses akzeptiert, weil es so einfach zu implementieren war und ich es später bei Bedarf leicht ändern und debuggen kann. Die Antwort von @ NickChammas ist ebenfalls richtig und läuft wahrscheinlich effizienter. Ich denke, es ist eine Frage der Präferenz für alle anderen, die auf ein ähnliches Problem stoßen.
Zikes
9

Ohne die neuen Fensterfunktionen in SQL Server 2012 kann eine komplexe Fensterung mithilfe rekursiver CTEs durchgeführt werden. Ich frage mich, wie gut dies gegen Millionen von Zeilen funktioniert.

Die folgende Lösung deckt alle von Ihnen beschriebenen Fälle ab. Sie können es hier auf SQL Fiddle in Aktion sehen .

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

Jetzt atme tief ein. Hier gibt es zwei wichtige CTEs, denen jeweils ein kurzer Kommentar vorangestellt ist. Der Rest sind nur "Bereinigungs" -CTEs, um beispielsweise die richtigen Zeilen zu ziehen, nachdem wir sie eingestuft haben.

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

Diese Lösung geht davon aus, dass ides sich um eine lückenlose Sequenz handelt. Wenn nicht, müssen Sie Ihre eigene lückenlose Sequenz generieren, indem Sie am Anfang einen zusätzlichen CTE hinzufügen, der die Zeilen ROW_NUMBER()in der gewünschten Reihenfolge nummeriert (z ROW_NUMBER() OVER (ORDER BY value DESC). B. ).

Fankly, das ist ziemlich ausführlich.

Nick Chammas
quelle
1
Diese Lösung scheint nicht den Fall zu behandeln, in dem eine Zeile ihre Größe zu mehreren Buckets beitragen könnte. Eine fortlaufende Summe ist einfach genug, aber ich brauche diese Summe, um sie jedes Mal zurückzusetzen, wenn sie 1 erreicht. Sehen Sie sich die letzte Beispieltabelle in meiner Frage an und vergleichen Sie sie crude_summit distinct_sumden zugehörigen bucketSpalten, um zu sehen, was ich meine.
Zikes
2
@Zikes - Ich habe diesen Fall mit meiner aktualisierten Lösung behoben.
Nick Chammas
Das sieht so aus, als ob es jetzt funktionieren sollte. Ich werde daran arbeiten, es in meine Datenbank zu integrieren, um es zu testen.
Zikes
@Zikes - Nur neugierig, wie wirken sich die verschiedenen hier veröffentlichten Lösungen auf Ihren großen Datenbestand aus? Ich vermute, Andriy's ist der schnellste.
Nick Chammas
5

Dies fühlt sich wie eine dumme Lösung an und lässt sich wahrscheinlich nicht gut skalieren. Testen Sie daher sorgfältig, ob Sie sie verwenden. Da das Hauptproblem von dem im Eimer verbleibenden "Leerzeichen" herrührt, musste ich zuerst einen Fülldatensatz erstellen, um ihn mit den Daten zu verbinden.

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
quelle
1
+1 Ich denke, dies hat Potenzial, wenn geeignete Indizes vorhanden sind.
Jon Seigel
3

Das Folgende ist eine weitere rekursive CTE-Lösung, obwohl ich sagen würde, dass sie einfacher ist als der Vorschlag von @ Nick . Es ist tatsächlich näher an @ Sebastians Cursor , nur ich habe Laufdifferenzen anstelle von Laufsummen verwendet. (Zuerst dachte ich sogar, dass @ Nicks Antwort dem entsprechen würde, was ich hier vorschlage, und nachdem ich erfahren hatte, dass es sich tatsächlich um eine ganz andere Frage handelte, entschied ich mich, meine anzubieten.)

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
;

Hinweis: Bei dieser Abfrage wird davon ausgegangen, dass die valueSpalte aus eindeutigen Werten ohne Lücken besteht. Ist dies nicht der Fall, müssen Sie eine berechnete Rangfolge-Spalte basierend auf der absteigenden Reihenfolge von einführen valueund im rekursiven CTE verwenden, anstatt valueden rekursiven Teil mit dem Anker zu verbinden.

Eine SQL Fiddle-Demo für diese Abfrage finden Sie hier .

Andriy M.
quelle
Das ist viel kürzer als das, was ich geschrieben habe. Gute Arbeit. Gibt es einen Grund, warum Sie den im Eimer verbleibenden Raum herunterzählen, anstatt hochzuzählen?
Nick Chammas
Ja, es ist nicht sicher, ob es für die Version, die ich hier gepostet habe, viel Sinn macht. Der Grund war jedenfalls, dass es einfacher / natürlicher schien, einen einzelnen Wert mit einem einzelnen Wert ( sizemit room_left) zu vergleichen, als einen einzelnen Wert mit einem Ausdruck ( 1mit running_size+ size) zu vergleichen. Ich habe zuerst keine is_new_bucketFlagge verwendet, sondern mehrere CASE WHEN t.size > r.room_left ...("mehrere", weil ich auch die Gesamtgröße berechnet (und zurückgegeben) habe, dann aber der Einfachheit halber dagegen gedacht habe), also dachte ich, es wäre eleganter dieser Weg.
Andriy M