如何编写对一列求和以创建离散存储桶的窗口查询？

Question

我有一个表格，其中包含一列十进制值，例如：

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

我需要完成的事情有点难以描述，所以请耐心等待。我想要做的是创建size列的聚合值，当根据value. 结果看起来像这样：

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

我天真的第一次尝试是保持运行SUM，然后CEILING是该值，但是它无法处理某些记录size最终对两个单独存储桶做出贡献的情况。下面的例子可能会澄清这一点：

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

如您所见，如果我只是CEILING在crude_sum记录 #8 上使用将被分配到存储桶 2。这是由于size记录 #5 和 #8 被分成两个存储桶造成的。相反，理想的解决方案是在每次达到 1 时重置总和，然后增加bucket列并从当前记录SUM的size值开始新的操作。因为记录的顺序对这个操作很重要，所以我包含了value旨在按降序排序的列。

我最初的尝试涉及对数据进行多次传递，一次执行SUM操作，一次执行操作CEILING，等等。这是我创建crude_sum列的示例：

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

它用于UPDATE将值插入到表中以供稍后使用的操作中。

编辑：我想再解释一下，所以在这里。想象每个记录都是一个物理项目。该项目具有与其关联的值，并且物理尺寸小于 1。我有一系列容量正好为 1 的桶，我需要根据项目的值确定我需要多少个这些桶以及每个项目放入哪个桶，从高到低排序。

一个物理项目不能同时存在于两个地方，因此它必须在一个桶或另一个桶中。这就是为什么我不能执行运行总计 +CEILING解决方案的原因，因为这将允许记录将它们的大小贡献给两个存储桶。

Answer 1

我不确定您正在寻找什么类型的性能，但是如果 CLR 或外部应用程序不是一个选项，那么只剩下一个光标了。在我的旧笔记本电脑上，我使用以下解决方案在大约 100 秒内完成了 1,000,000 行。它的好处是它可以线性扩展，所以我会花 20 分钟左右的时间来完成整个过程。使用像样的服务器，您会更快，但不是一个数量级，因此完成此操作仍需要几分钟。如果这是一个一次性的过程，您可能可以承受缓慢。如果您需要定期将其作为报告或类似方式运行，您可能希望将这些值存储在同一个表中，并在添加新行时更新它们，例如在触发器中。

无论如何，这是代码：

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;

它删除并重新创建表 MyTable，用 1000000 行填充它，然后开始工作。

游标在运行计算时将每一行复制到临时表中。最后，选择返回计算结果。如果您不复制数据而是进行就地更新，您可能会快一点。

如果您可以选择升级到 SQL 2012，您可以查看新的支持窗口假脱机的移动窗口聚合，这将为您提供更好的性能。

附带说明一下，如果您安装了一个使用 permission_set=safe 的程序集，那么您可以使用标准 T-SQL 对服务器做更多的坏事，而不是使用该程序集，所以我将继续努力消除该障碍 - 您有一个很好的用途在这里，CLR 真的会帮助你。

Answer 2

如果没有 SQL Server 2012 中的新窗口函数，复杂的窗口可以通过使用递归 CTE 来完成。我想知道这对数百万行的表现如何。

以下解决方案涵盖了您描述的所有情况。你可以在 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
;

现在深呼吸。这里有两个关键的 CTE，每个前面都有一个简短的评论。其余的只是“清理”CTE，例如，在我们对它们进行排名后提取正确的行。

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

此解决方案假定这id是一个无间隙序列。如果没有，您将需要通过在开头添加一个额外的 CTE 来生成您自己的无间隙序列，该 CTEROW_NUMBER()根据所需的顺序（例如ROW_NUMBER() OVER (ORDER BY value DESC)）对行进行编号。

说实话，这很冗长。

Answer 3

这感觉像是一个愚蠢的解决方案，它可能无法很好地扩展，因此如果您使用它，请仔细测试。由于主要问题来自存储桶中剩余的“空间”，我首先必须创建一个填充记录以合并到数据中。

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