Jak napisać zapytanie podsumowujące, które sumuje kolumnę w celu utworzenia dyskretnych segmentów?

11

Mam tabelę, która zawiera kolumnę wartości dziesiętnych, takich jak ta:

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

To, co muszę osiągnąć, jest trochę trudne do opisania, więc proszę o wyrozumiałość. To, co próbuję zrobić, to utworzyć zagregowaną wartość sizekolumny, która zwiększa się o 1 za każdym razem, gdy poprzednie wiersze sumują się do 1, gdy w porządku malejącym zgodnie z value. Wynik wyglądałby mniej więcej tak:

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

Moja naiwna pierwsza próba polegała na utrzymywaniu działania, SUMa następnie na CEILINGtej wartości, jednak nie dotyczy to przypadku, w którym niektóre rekordy sizeprzyczyniają się w sumie do dwóch oddzielnych segmentów. Poniższy przykład może to wyjaśnić:

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

Jak widać, gdybym po prostu używać CEILINGna crude_sumpłycie # 8 będzie przypisany do wiadra 2. Jest to spowodowane przez sizezapisów # 5 i # 8 rozdzielona na dwa wiadra. Zamiast tego idealnym rozwiązaniem jest resetowanie sumy za każdym razem, gdy osiągnie 1, co następnie zwiększa bucketkolumnę i rozpoczyna nową SUMoperację, rozpoczynając od sizewartości bieżącego rekordu. Ponieważ kolejność rekordów jest ważna dla tej operacji, dołączyłem valuekolumnę, która ma być sortowana w kolejności malejącej.

Moje pierwsze próby obejmowały wielokrotne przekazywanie danych, raz, aby wykonać SUMoperację, raz jeszcze CEILING, itd. Oto przykład tego, co zrobiłem, aby utworzyć crude_sumkolumnę:

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

Który został użyty w UPDATEoperacji, aby wstawić wartość do tabeli do późniejszej pracy.

Edycja: Chciałbym wziąć kolejny kłopot z wyjaśnieniem tego, więc proszę bardzo. Wyobraź sobie, że każdy rekord jest przedmiotem fizycznym. Ten przedmiot ma powiązaną z nim wartość i rozmiar fizyczny mniejszy niż jeden. Mam serię wiader o pojemności dokładnie 1 i muszę określić, ile z tych wiader potrzebuję i które wiadro zawiera każdy element zgodnie z wartością przedmiotu, posortowane od najwyższej do najniższej.

Przedmiot fizyczny nie może istnieć w dwóch miejscach jednocześnie, więc musi znajdować się w jednym lub drugim wiadrze. Dlatego nie mogę wykonać działającego CEILINGrozwiązania total + , ponieważ pozwoliłoby to rekordom na zwiększenie ich rozmiaru do dwóch segmentów.

Zikes
źródło
Powinieneś dodać swój SQL, aby wyjaśnić, co zawierała Twoja początkowa próba.
mdahlman
Czy zamierzasz agregować dane według obliczanego segmentu, czy też numer segmentu to ostateczna odpowiedź, której szukasz?
Jon Seigel
2
Ack. Prawdopodobnie wybrałbym aplikację po stronie klienta, ponieważ będzie ona obsługiwać lepsze przesyłanie rekordów w przeciwieństwie do pętli kursora, która pobiera jeden wiersz na raz. Myślę, że tak długo, jak wszystkie aktualizacje są wykonywane partiami, powinno działać całkiem dobrze.
Jon Seigel
1
Jak już wspomnieli inni, wymóg kubełkowania na distinct_countkomplikuje rzeczy. Aaron Bertrand ma świetne podsumowanie twoich opcji na SQL Server dla tego rodzaju okienkowania. Użyłem metody „dziwacznej aktualizacji” do obliczenia distinct_sum, którą można zobaczyć tutaj na SQL Fiddle , ale jest to niewiarygodne.
Nick Chammas,
1
@JonSeigel Należy zauważyć, że problemu umieszczenia elementów X w minimalnej liczbie segmentów nie można skutecznie rozwiązać za pomocą algorytmu wiersz po języku języka SQL. Np. Przedmioty o rozmiarze 0,7; 0,8; 0,3 będą potrzebowały 2 wiader, ale jeśli posortowane według id, będą potrzebowały 3 wiader.
Stoleg

Odpowiedzi:

9

Nie jestem pewien, jakiego rodzaju wydajności szukasz, ale jeśli CLR lub aplikacja zewnętrzna nie jest opcją, kursor pozostaje. Na moim starym laptopie przechodzę przez 1 000 000 wierszy w około 100 sekund przy użyciu następującego rozwiązania. Zaletą jest to, że skaluje się liniowo, więc spędziłbym około 20 minut, aby przejść przez całą rzecz. Przy przyzwoitym serwerze będziesz szybszy, ale nie o rząd wielkości, więc ukończenie go zajmie jeszcze kilka minut. Jeśli jest to jednorazowy proces, prawdopodobnie możesz sobie pozwolić na powolność. Jeśli musisz regularnie uruchamiać to jako raport lub podobny, możesz przechowywać wartości w tej samej tabeli i aktualizować je wraz z dodawaniem nowych wierszy, np. W wyzwalaczu.

W każdym razie oto kod:

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;

Porzuca i odtwarza tabelę MyTable, wypełnia ją 1000000 wierszami, a następnie przystępuje do pracy.

Kursor kopiuje każdy wiersz do tabeli tymczasowej podczas wykonywania obliczeń. Na koniec select zwraca obliczone wyniki. Możesz być trochę szybszy, jeśli nie kopiujesz danych, ale zamiast tego dokonujesz aktualizacji w miejscu.

Jeśli masz opcję uaktualnienia do SQL 2012, możesz spojrzeć na nowe obsługiwane przez bufor okna ruchome agregaty okien, które powinny zapewnić lepszą wydajność.

Na marginesie, jeśli masz zainstalowany zestaw z uprawnieniem zestaw_zestawu = bezpieczny, możesz zrobić więcej złych rzeczy na serwerze ze standardowym T-SQLem niż z zestawem, więc kontynuowałbym pracę nad usunięciem tej bariery - masz dobry użytek sprawa tutaj, gdzie CLR naprawdę by ci pomógł.

Sebastian Meine
źródło
Zaakceptowałem ten ze względu na to, jak łatwo było go wdrożyć i jak łatwo mogę go zmienić i debugować później, gdy zajdzie taka potrzeba. @ Odpowiedź NickChammas jest również poprawna i prawdopodobnie działa wydajniej, więc myślę, że jest to kwestia preferencji dla każdego, kto podejdzie do podobnego problemu.
Zikes,
9

W przypadku braku nowych funkcji okienkowania w programie SQL Server 2012 skomplikowane okienkowanie można wykonać za pomocą rekurencyjnych CTE. Zastanawiam się, jak dobrze poradzi sobie z milionami wierszy.

Poniższe rozwiązanie obejmuje wszystkie opisane przypadki. Możesz zobaczyć to w akcji tutaj na 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
;

Teraz weź głęboki oddech. Istnieją tutaj dwa kluczowe CTE, każde poprzedzone krótkim komentarzem. Reszta to po prostu „czyszczenie” CTE, na przykład, aby wyciągnąć odpowiednie rzędy po ich uszeregowaniu.

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

To rozwiązanie zakłada, że idjest to sekwencja bez przerw. Jeśli nie, musisz wygenerować własną sekwencję bez przerw, dodając na początku dodatkowy CTE, który numeruje wiersze ROW_NUMBER()zgodnie z pożądaną kolejnością (np ROW_NUMBER() OVER (ORDER BY value DESC).).

Fankly, to jest dość gadatliwe.

Nick Chammas
źródło
1
Wydaje się, że to rozwiązanie nie dotyczy przypadku, w którym rząd może przyczynić się do zwiększenia swojego rozmiaru do wielu segmentów. Krocząca suma jest dość łatwa, ale potrzebuję tej sumy do resetowania za każdym razem, gdy osiągnie 1. Zobacz ostatnią przykładową tabelę w moim pytaniu i porównaj crude_sumz distinct_sumpowiązanymi bucketkolumnami, aby zobaczyć, co mam na myśli.
Zikes
2
@Zikes - rozwiązałem tę sprawę moim zaktualizowanym rozwiązaniem.
Nick Chammas,
Wygląda na to, że teraz powinno działać. Będę pracować nad integracją go z moją bazą danych, aby go przetestować.
Zikes,
@Zikes - Ciekawe, jak działają różne zamieszczone tutaj rozwiązania w stosunku do dużego zbioru danych? Domyślam się, że Andriy's jest najszybszy.
Nick Chammas
5

To wydaje się głupie rozwiązanie i prawdopodobnie nie będzie dobrze skalować, więc przetestuj dokładnie, jeśli go używasz. Ponieważ główny problem wynika z „przestrzeni” pozostawionej w segmencie, najpierw musiałem utworzyć rekord wypełniający, aby połączyć dane z danymi.

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
źródło
1
+1 Myślę, że ma to potencjał, jeśli istnieją odpowiednie indeksy.
Jon Seigel
3

Oto kolejne rekurencyjne rozwiązanie CTE, chociaż powiedziałbym, że jest prostsze niż sugestia @ Nicka . W rzeczywistości jest bliżej kursora @ Sebastiana , tylko ja użyłem różnic biegowych zamiast sum całkowitych. (Na początku nawet myślałem, że odpowiedź @ Nicka będzie zgodna z tym, co tutaj sugeruję, i dopiero po dowiedzeniu się, że jego pytanie było w rzeczywistości zupełnie innym pytaniem, które postanowiłem zaoferować).

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
;

Uwaga: to zapytanie zakłada, że valuekolumna składa się z unikalnych wartości bez przerw. Jeśli tak nie jest, musisz wprowadzić obliczoną kolumnę rankingu na podstawie malejącej kolejności valuei użyć jej w rekurencyjnym CTE zamiast valuełączyć część rekurencyjną z kotwicą.

Demo SQL Fiddle dla tego zapytania można znaleźć tutaj .

Andriy M.
źródło
To jest znacznie krótsze niż to, co napisałem. Dobra robota. Czy jest jakiś powód, dla którego odliczasz miejsce pozostawione w wiadrze zamiast liczyć?
Nick Chammas
Tak, nie jestem pewien, czy ma to sens w przypadku wersji, którą tutaj opublikowałem. W każdym razie powodem było to, że porównanie pojedynczej wartości z pojedynczą wartością ( sizez room_left) wydawało się łatwiejsze / bardziej naturalne, niż porównywanie pojedynczej wartości z wyrażeniem ( 1z running_size+ size). Na początku nie użyłem is_new_bucketflagi, ale kilka CASE WHEN t.size > r.room_left ...(„kilka”, ponieważ również obliczałem (i zwracałem) całkowity rozmiar, ale potem pomyślałem przeciwko temu ze względu na prostotę), więc pomyślałem, że będzie bardziej elegancki w ten sposób.
Andriy M,