Como escrever consultas de janelas que somam uma coluna para criar buckets discretos?

Eu tenho uma tabela que inclui uma coluna de valores decimais, como esta:

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

O que eu preciso realizar é um pouco difícil de descrever, por isso, tenha paciência comigo. O que estou tentando fazer é criar um valor agregado da sizecoluna que incrementa em 1 cada vez que as linhas anteriores somam 1, quando em ordem decrescente de acordo com value. O resultado seria algo parecido com isto:

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

Minha primeira tentativa ingênua foi manter um valor em execução SUMe, em seguida, CEILINGesse valor, no entanto, ele não lida com o caso em que alguns registros sizeacabam contribuindo para o total de dois depósitos separados. O exemplo abaixo pode esclarecer isso:

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

Como você pode ver, se eu fosse usar simplesmente CEILINGno crude_sumregistro # 8 seria atribuído a bucket 2. Isto é causado pelo sizede registros # 5 e # 8 sendo dividido em dois baldes. Em vez disso, a solução ideal é redefinir a soma cada vez que atingir 1, que depois incrementa a bucketcoluna e inicia uma nova SUMoperação começando com o sizevalor do registro atual. Como a ordem dos registros é importante para esta operação, incluí a valuecoluna, que deve ser classificada em ordem decrescente.

Minhas tentativas iniciais envolveram fazer várias passagens sobre os dados, uma vez para executar a SUMoperação, mais uma vez para CEILINGisso, etc. Aqui está um exemplo do que eu fiz para criar a crude_sumcoluna:

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

Que foi usado em um UPDATE operação para inserir o valor em uma tabela para trabalhar posteriormente.

Edit: Eu gostaria de dar uma outra facada em explicar isso, então aqui vai. Imagine que cada registro é um item físico. Esse item tem um valor associado a ele e um tamanho físico menor que um. Eu tenho uma série de buckets com uma capacidade de volume de exatamente 1 e preciso determinar quantos desses buckets serão necessários e qual bucket cada item entra de acordo com o valor do item, classificado do maior para o menor.

Um item físico não pode existir em dois lugares ao mesmo tempo; portanto, ele deve estar em um balde ou no outro. É por isso que não consigo fazer uma CEILINGsolução total + em execução , porque isso permitiria que os registros contribuíssem com seu tamanho para dois buckets.

Não sei ao certo qual tipo de desempenho você está procurando, mas se o CLR ou o aplicativo externo não for uma opção, basta um cursor. No meu laptop antigo, recebo 1.000.000 de linhas em cerca de 100 segundos usando a solução a seguir. O bom disso é que ele é dimensionado linearmente, então eu ficaria olhando cerca de 20 minutos para percorrer a coisa toda. Com um servidor decente, você será mais rápido, mas não uma ordem de grandeza; portanto, ainda levará alguns minutos para concluir isso. Se esse é um processo único, você provavelmente pode pagar pela lentidão. Se você precisar executar isso como um relatório ou semelhante regularmente, convém armazenar os valores na mesma tabela e atualizá-los à medida que novas linhas forem adicionadas, por exemplo, em um gatilho.

Enfim, aqui está o código:

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;

Ele solta e recria a tabela MyTable, preenche-a com 1000000 linhas e depois começa a trabalhar.

O cursor copia cada linha em uma tabela temporária enquanto executa os cálculos. No final, a seleção retorna os resultados calculados. Você pode ser um pouco mais rápido se não copiar os dados, mas fizer uma atualização no local.

Se você tiver a opção de atualizar para o SQL 2012, poderá olhar para os novos agregados de janelas móveis suportados pelo spool de janelas, que deverão oferecer melhor desempenho.

Em uma nota lateral, se você tiver um assembly instalado com permission_set = safe, poderá fazer mais coisas ruins com um servidor com T-SQL padrão do que com o assembly, por isso continuaria trabalhando para remover essa barreira - Você tem um bom uso caso em que o CLR realmente o ajudaria.

Na ausência das novas funções de janelas no SQL Server 2012, a janelas complexas podem ser realizadas com o uso de CTEs recursivas. Eu me pergunto o quão bem isso será executado em milhões de linhas.

A solução a seguir abrange todos os casos que você descreveu. Você pode vê-lo em ação aqui no 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
;

Agora respire fundo. Existem duas CTEs principais aqui, cada uma precedida por um breve comentário. O restante são apenas CTEs de "limpeza", por exemplo, para puxar as linhas corretas depois que as classificamos.

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

Esta solução assume que idé uma sequência contínua. Caso contrário, você precisará gerar sua própria sequência sem intervalos, adicionando uma CTE adicional no início que numerar as linhas de ROW_NUMBER()acordo com a ordem desejada (por exemplo ROW_NUMBER() OVER (ORDER BY value DESC)).

Fankly, isso é bastante detalhado.

Parece uma solução boba, e provavelmente não será bem dimensionada; portanto, teste com cuidado se você a usar. Como o principal problema vem do "espaço" deixado no balde, primeiro tive que criar um registro de preenchimento para união nos dados.

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

A seguir, é outra solução CTE recursiva, embora eu diria que é mais direta do que a sugestão de @ Nick . Na verdade, é mais próximo do cursor de @ Sebastian , apenas eu usei diferenças de execução em vez de totais de execução. (No começo, eu até pensei que a resposta de @ Nick seria na mesma linha do que estou sugerindo aqui, e foi depois de saber que a pergunta dele era de fato muito diferente que eu decidi oferecer a minha.)

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
;

Nota: esta consulta pressupõe que a valuecoluna consiste em valores exclusivos sem intervalos. Se não for esse o caso, você precisará introduzir uma coluna de classificação calculada com base na ordem decrescente de valuee usá-la na CTE recursiva em vez devalue unir a parte recursiva à âncora.

Uma demonstração do SQL Fiddle para esta consulta pode ser encontrada aqui .