Как я могу написать оконный запрос, который суммирует столбец для создания отдельных сегментов?

У меня есть таблица, которая включает в себя столбец десятичных значений, таких как это:

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столбца, который увеличивается на 1 каждый раз, когда предыдущие строки суммируют до 1, когда в порядке убывания в соответствии с 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, и мне нужно определить, сколько из этих сегментов мне понадобится и в какой блок входит каждый элемент, в соответствии со стоимостью элемента, отсортированного от наивысшего к наименьшему.

Физический предмет не может существовать в двух местах одновременно, поэтому он должен находиться в одном ведре или другом. Вот почему я не могу выполнить CEILINGрешение по промежуточному итогу + , потому что это позволило бы записям вносить свой размер в два сегмента.

Я не уверен, какой тип производительности вы ищете, но если CLR или внешнее приложение не вариант, курсор это все, что осталось. На моем старом ноутбуке я прохожу 1000000 строк примерно за 100 секунд, используя следующее решение. Приятно то, что он линейно масштабируется, так что я бы посмотрел примерно на 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, вы можете взглянуть на новые движущиеся агрегаты окон, поддерживаемые с помощью спулинга окон, которые должны повысить производительность.

Кстати, если у вас есть сборка, установленная с параметром allow_set = safe, вы можете сделать больше вредных вещей для сервера со стандартным T-SQL, чем со сборкой, так что я бы продолжал работать над устранением этого барьера. случай, когда CLR действительно поможет вам.

В отсутствие новых оконных функций в 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, который нумерует строки в ROW_NUMBER()соответствии с желаемым порядком (например, ROW_NUMBER() OVER (ORDER BY value DESC)).

На самом деле, это довольно многословно.

Это похоже на глупое решение, и оно, вероятно, не будет хорошо масштабироваться, поэтому проверяйте внимательно, если вы его используете. Поскольку основная проблема связана с «пробелом», оставленным в корзине, мне сначала нужно было создать запись-заполнитель для объединения в данные.

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

Ниже приведено еще одно рекурсивное решение CTE, хотя я бы сказал, что оно более простое, чем предложение @ Nick . Это на самом деле ближе к курсору @ Себастьяна , только я использовал текущие различия вместо промежуточных итогов. (Сначала я даже подумал, что ответ @ Ника будет соответствовать тому, что я предлагаю здесь, и именно после того, как я узнал, что это на самом деле совершенно другой запрос, я решил предложить мой.)

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
;

Примечание: этот запрос предполагает, что valueстолбец состоит из уникальных значений без пробелов. Если это не так, вам нужно будет ввести вычисляемый столбец ранжирования, основанный на нисходящем порядке, valueи использовать его в рекурсивном CTE, а не valueсоединять рекурсивную часть с якорем.

Демоверсию SQL Fiddle для этого запроса можно найти здесь .