Нашли ошибку или опечатку? Выделите текст и нажмите

Поменять цветовую

гамму сайта?

Поменять
Обновления сайта
и новые разделы

Рекомендовать в Google +1

Вычисление нарастающих итогов в T-SQL

191
Исходник базы данных

Это еще одна часто встречающаяся задача. Основной принцип заключается в накоплении значений одного атрибута (агрегируемого элемента) на основе упорядочения по другому атрибуту или атрибутам (элемент упорядочения), возможно при наличии секций строк, определенных на основе еще одного атрибута или атрибутов (элемент секционирования). В жизни существует много примеров вычисления нарастающих итогов, например вычисление остатков на банковских счетах, отслеживание наличия товаров на складе или текущих цифр продаж и т.п.

До SQL Server 2012 решения, основанные на наборах и используемые для вычисления нарастающих итогов, были исключительно ресурсоемкими. Поэтому люди обычно обращались к итеративным решениями, которые работали небыстро, но в некоторых ситуациях все-таки быстрее, чем решения на основе наборов. Благодаря расширению поддержки оконных функций в SQL Server 2012, нарастающие итоги можно вычислять, используя простой основанный на наборах код, производительность которого намного выше, чем в старых решениях на основе T-SQL - как основанных на наборах, так и итеративных. Я мог бы показать новое решение и перейти к следующему разделу; но чтобы вы по-настоящему поняли масштаб изменений, я опишу старые способы и сравню их производительность с новым подходом. Естественно, вы вправе прочитать только первую часть, описывающую новый подход, и пропустить остальную часть статьи.

Для демонстрации разных решений я воспользуюсь остатками на счетах. Вот код, который создает и наполняет таблицу Transactions небольшим объемом тестовых данных:

SET NOCOUNT ON;
USE TSQL2012;

IF OBJECT_ID('dbo.Transactions', 'U') IS NOT NULL DROP TABLE dbo.Transactions;

CREATE TABLE dbo.Transactions
(
  actid  INT   NOT NULL,                -- столбец секционирования
  tranid INT   NOT NULL,                -- столбец упорядочения
  val    MONEY NOT NULL,                -- мера
  CONSTRAINT PK_Transactions PRIMARY KEY(actid, tranid)
);
GO

-- небольшой набор тестовых данных
INSERT INTO dbo.Transactions(actid, tranid, val) VALUES
  (1,  1,  4.00),
  (1,  2, -2.00),
  (1,  3,  5.00),
  (1,  4,  2.00),
  (1,  5,  1.00),
  (1,  6,  3.00),
  (1,  7, -4.00),
  (1,  8, -1.00),
  (1,  9, -2.00),
  (1, 10, -3.00),
  (2,  1,  2.00),
  (2,  2,  1.00),
  (2,  3,  5.00),
  (2,  4,  1.00),
  (2,  5, -5.00),
  (2,  6,  4.00),
  (2,  7,  2.00),
  (2,  8, -4.00),
  (2,  9, -5.00),
  (2, 10,  4.00),
  (3,  1, -3.00),
  (3,  2,  3.00),
  (3,  3, -2.00),
  (3,  4,  1.00),
  (3,  5,  4.00),
  (3,  6, -1.00),
  (3,  7,  5.00),
  (3,  8,  3.00),
  (3,  9,  5.00),
  (3, 10, -3.00);

Каждая строка таблицы представляет банковскую операцию на счете. Депозиты отмечаются как транзакции с положительным значением в столбце val, а снятие средств — как отрицательное значение транзакции. Наша задача — вычислить остаток на счете в каждый момент времени путем аккумулирования сумм операций в строке val при упорядочении по столбцу tranid, причем это нужно сделать для каждого счета отдельно. Желаемый результат должен выглядеть так:

Пример вычисления нарастающих итогов

Для тестирования обоих решений нужен больший объем данных. Это можно сделать с помощью такого запроса:

DECLARE
  @num_partitions     AS INT = 10,
  @rows_per_partition AS INT = 10000;

TRUNCATE TABLE dbo.Transactions;

INSERT INTO dbo.Transactions WITH (TABLOCK) (actid, tranid, val)
  SELECT NP.n, RPP.n,
    (ABS(CHECKSUM(NEWID())%2)*2-1) * (1 + ABS(CHECKSUM(NEWID())%5))
  FROM dbo.GetNums(1, @num_partitions) AS NP
    CROSS JOIN dbo.GetNums(1, @rows_per_partition) AS RPP;

Можете задать свои входные данные, чтобы изменить число секций (счетов) и строк (транзакций) в секции.

Основанное на наборах решение с использованием оконных функций

Я начну рассказ с решения на основе наборов, в котором используется оконная функция агрегирования SUM. Определение окна здесь довольно наглядно: нужно секционировать окно по actid, упорядочить по tranid и фильтром отобрать строки в кадре с крайней нижней (UNBOUNDED PRECEDING) до текущей. Вот соответствующий запрос:

SELECT actid, tranid, val,
  SUM(val) OVER(PARTITION BY actid
                ORDER BY tranid
                ROWS BETWEEN UNBOUNDED PRECEDING
                         AND CURRENT ROW) AS balance
FROM dbo.Transactions;

Этот код не только простой и прямолинейный — он и выполняется быстро. План этого запроса показан на рисунке:

План выполнения запроса с оконными функциями

В таблице есть кластеризованный индекс, который отвечает требованиям POC и пригоден для использования оконными функциями. В частности, список ключей индекса основан на элементе секционирования (actid), за которым следует элемент упорядочения (tranid), также для обеспечения покрытия индекс включает все остальные столбцы в запросе (val). План содержит упорядоченный просмотр, за которым следует вычисление номера строки для внутренних нужд, а затем - оконного агрегата. Так как есть POC-индекс, оптимизатору не нужно добавлять в план оператор сортировки. Это очень эффективный план. К тому же он линейно масштабируется. Позже, когда я покажу результаты сравнения производительности, вы увидите, насколько эффективнее этот способ по сравнению со старыми решениями.

До SQL Server 2012 использовались либо вложенные запросы, либо соединения. При использовании вложенного запроса нарастающие итоги вычисляются путем фильтрации всех строк с тем же значением actid, что и во внешней строке, и значением tranid, которое меньше или равно значения во внешней строке. Затем к отфильтрованным строкам применяется агрегирование. Вот соответствующий запрос:

SELECT actid, tranid, val,
  (SELECT SUM(T2.val)
   FROM dbo.Transactions AS T2
   WHERE T2.actid = T1.actid
     AND T2.tranid <= T1.tranid) AS balance
FROM dbo.Transactions AS T1;

Аналогичный подход можно реализовать с применением соединений. Используется тот же предикат, что и в предложении WHERE вложенного запроса в предложении ON соединения. В этом случае для N-ой транзакции одного и того же счета A в экземпляре, обозначенном как T1, вы будете находить N соответствий в экземпляре T2, при этом номера транзакций пробегают от 1 до N. В результате сопоставления строки в T1 повторяются, поэтому нужно сгруппировать строки по всем элементам с T1, чтобы получить информацию о текущей транзакции и применить агрегирование к атрибуту val из T2 для вычисления нарастающего итога. Готовый запрос выглядит примерно так:

SELECT T1.actid, T1.tranid, T1.val,
  SUM(T2.val) AS balance
FROM dbo.Transactions AS T1
  JOIN dbo.Transactions AS T2
    ON T2.actid = T1.actid
   AND T2.tranid <= T1.tranid
GROUP BY T1.actid, T1.tranid, T1.val;

На рисунке ниже приведены планы обоих решений:

Планы выполнения запросов с использованием вложенных запросов и соединений

Заметьте, что в обоих случаях в экземпляре T1 выполняется полный просмотр кластеризованного индекса. Затем для каждой строки в плане предусмотрена операция поиска в индексе начала раздела текущего счета на конечной странице индекса, при этом считываются все транзакции, в которых T2.tranid меньше или равно T1.tranid. Точка, где происходит агрегирование строк, немного отличается в планах, но число считанных строк одинаково.

Чтобы понять, сколько строк просматривается, надо учесть число элементов данных. Пусть p — число секций (счетов), а r — число строк в секции (транзакции). Тогда число строк в таблице примерно равно p*r, если считать, что транзакции распределены по счетам равномерно. Таким образом, приведенный в верхней части просмотр охватывает p*r строк. Но больше всего нас интересует происходящее в итераторе Nested Loops.

В каждой секции план предусматривает чтение 1 + 2 + ... + r строк, что в сумме составляет (r + r*2) / 2. Общее количество обрабатываемых в планах строк составляет p*r + p*(r + r2) / 2. Это означает, что число операций в плане растет в квадрате с увеличением размера секции, то есть если увеличить размер секции в f раз, объем работы увеличится примерно в f2 раз. Это плохо. Для примера 100 строкам соответствует 10 тыс. строк, а тысяче строк соответствует миллион и т.д. Проще говоря это приводит к сильному замедлению выполнения запросов при немаленьком размере секции, потому что квадратичная функция растет очень быстро. Подобные решения работают удовлетворительно при нескольких десятках строк на секцию, но не больше.

Решения с использованием курсора

Решения на основе курсора реализуются «в лоб». Объявляется курсор на основе запроса, упорядочивающего данные по actid и tranid. После этого выполняется итеративный проход записей курсора. При обнаружении нового счета сбрасывается переменная, содержащая агрегат. В каждой итерации в переменную добавляется сумма новой транзакции, после этого строка сохраняется в табличной переменной с информацией о текущей транзакции плюс текущее значение нарастающего итога. После итеративного прохода возвращается результат из табличной переменной. Вот код законченного решения:

DECLARE @Result AS TABLE
(
  actid   INT,
  tranid  INT,
  val     MONEY,
  balance MONEY
);

DECLARE
  @actid    AS INT,
  @prvactid AS INT,
  @tranid   AS INT,
  @val      AS MONEY,
  @balance  AS MONEY;

DECLARE C CURSOR FAST_FORWARD FOR
  SELECT actid, tranid, val
  FROM dbo.Transactions
  ORDER BY actid, tranid;

OPEN C

FETCH NEXT FROM C INTO @actid, @tranid, @val;

SELECT @prvactid = @actid, @balance = 0;

WHILE @@fetch_status = 0
BEGIN
  IF @actid <> @prvactid
    SELECT @prvactid = @actid, @balance = 0;

  SET @balance = @balance + @val;

  INSERT INTO @Result VALUES(@actid, @tranid, @val, @balance);
  
  FETCH NEXT FROM C INTO @actid, @tranid, @val;
END

CLOSE C;

DEALLOCATE C;

SELECT * FROM @Result;

План запроса с использованием курсора показан на рисунке:

План запроса с использованием курсора

Этот план масштабируется линейно, потому что данные из индекса просматриваются только раз в определенном порядке. Также у каждой операции получения строки из курсора примерно одинаковая стоимость в расчете на каждую строку. Если принять нагрузку, создаваемую при обработке одной строки курсора, равной g, стоимость этого решения можно оценить как p*r + p*r*g (как вы помните, p — это число секций, а r — число строк в секции). Так что, если увеличить число строк на секцию в f раз, нагрузка на систему составит p*r*f + p*r*f*g, то есть будет расти линейно. Стоимость обработки в расчете на строку высока, но из-за линейного характера масштабирования, с определенного размера секции это решение будет демонстрировать лучшую масштабируемость, чем решения на основе вложенных запросов и соединений из-за квадратичного масштабирования этих решений. Проведенное мной измерение производительности показало, что число, когда решение с курсором работает быстрее, равно нескольким сотням строк на секцию.

Несмотря на выигрыш в производительности, обеспечиваемый решениями на основе курсора, в общем случае их надо избегать, потому что они не являются реляционными.

Решения на основе CLR

Одно возможное решение на основе CLR (Common Language Runtime) по сути является одной из форм решения с использованием курсора. Разница в том, что вместо использования курсора T-SQL, который тратит много ресурсов на получение очередной строки и выполнение итерации, применяются итерации .NET SQLDataReader и .NET, которые работают намного быстрее. Одна из особенностей CLR которая делает этот вариант быстрее, заключается в том, что результирующая строка во временной таблице не нужна — результаты пересылаются напрямую вызывающему процессу. Логика решения на основе CLR похожа на логику решения с использованием курсора и T-SQL. Вот код C#, определяющий хранимую процедуру решения:

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;

public partial class StoredProcedures
{
    [Microsoft.SqlServer.Server.SqlProcedure]
    public static void AccountBalances()
    {
        using (SqlConnection conn = new SqlConnection("context connection=true;"))
        {
            SqlCommand comm = new SqlCommand();
            comm.Connection = conn;
            comm.CommandText = @"" +
                "SELECT actid, tranid, val " +
                "FROM dbo.Transactions " +
                "ORDER BY actid, tranid;";

            SqlMetaData[] columns = new SqlMetaData[4];
            columns[0] = new SqlMetaData("actid"  , SqlDbType.Int);
            columns[1] = new SqlMetaData("tranid" , SqlDbType.Int);
            columns[2] = new SqlMetaData("val"    , SqlDbType.Money);
            columns[3] = new SqlMetaData("balance", SqlDbType.Money);

            SqlDataRecord record = new SqlDataRecord(columns);

            SqlContext.Pipe.SendResultsStart(record);

            conn.Open();

            SqlDataReader reader = comm.ExecuteReader();

            SqlInt32 prvactid = 0;
            SqlMoney balance = 0;

            while (reader.Read())
            {
                SqlInt32 actid = reader.GetSqlInt32(0);
                SqlMoney val = reader.GetSqlMoney(2);

                if (actid == prvactid)
                {
                    balance += val;
                }
                else
                {
                    balance = val;
                }

                prvactid = actid;

                record.SetSqlInt32(0, reader.GetSqlInt32(0));
                record.SetSqlInt32(1, reader.GetSqlInt32(1));
                record.SetSqlMoney(2, val);
                record.SetSqlMoney(3, balance);

                SqlContext.Pipe.SendResultsRow(record);
            }

            SqlContext.Pipe.SendResultsEnd();
        }
    }
}

Чтобы иметь возможность выполнить эту хранимую процедуру в SQL Server, сначала надо на основе этого кода построить сборку по имени AccountBalances и развернуть в базе данных TSQL2012. Если вы не знакомы с развертыванием сборок в SQL Server, можете почитать раздел «Хранимые процедуры и среда CLR» в статье «Хранимые процедуры».

Если вы назвали сборку AccountBalances, а путь к файлу сборки — "C:\Projects\AccountBalances\bin\Debug\AccountBalances.dll", загрузить сборку в базу данных и зарегистрировать хранимую процедуру можно следующим кодом:

CREATE ASSEMBLY AccountBalances 
  FROM 'C:\Projects\AccountBalances\bin\Debug\AccountBalances.dll';
GO

CREATE PROCEDURE dbo.AccountBalances
AS EXTERNAL NAME AccountBalances.StoredProcedures.AccountBalances;

После развертывания сборки и регистрации процедуры можно ее выполнить следующим кодом:

EXEC dbo.AccountBalances;

Как я уже говорил, SQLDataReader является всего лишь еще одной формой курсора, но в этой версии затраты на чтение строк значительно меньше, чем при использовании традиционного курсора в T-SQL. Также в .NET итерации выполняются намного быстрее, чем в T-SQL. Таким образом, решения на основе CLR тоже масштабируются линейно. Тестирование показало, что производительность этого решения становится выше производительности решений с использованием подзапросов и соединений, когда число строк в секции переваливает через 15.

По завершении надо выполнить следующий код очистки:

DROP PROCEDURE dbo.AccountBalances;
DROP ASSEMBLY AccountBalances;

Вложенные итерации

До этого момента я показывал итеративные решения и решения на основе наборов. Следующее решение основано на вложенных итерациях, которые являются гибридом итеративного и основанного на наборах подходов. Идея заключается в том, чтобы предварительно скопировать строки из таблицы-источника (в нашем случае это банковские счета) во временную таблицу вместе с новым атрибутом по имени rownum, который вычисляется с использованием функции ROW_NUMBER. Номера строк секционируются по actid и упорядочиваются по tranid, поэтому первой транзакции в каждом банковском счете назначается номер 1, второй транзакции — 2 и т.д. Затем во временной таблице создается кластеризованный индекс со списком ключей (rownum, actid). Затем используется рекурсивное выражение CTE или специально созданный цикл для обработки по одной строке за итерацию во всех счетах. Затем нарастающий итог вычисляется путем суммирования значения, соответствующего текущей строке, со значением, связанным с предыдущей строкой. Вот реализация этой логики с использованием рекурсивного CTE:

SELECT actid, tranid, val,
  ROW_NUMBER() OVER(PARTITION BY actid ORDER BY tranid) AS rownum
INTO #Transactions
FROM dbo.Transactions;

CREATE UNIQUE CLUSTERED INDEX idx_rownum_actid ON #Transactions(rownum, actid);

WITH C AS
(
  SELECT 1 AS rownum, actid, tranid, val, val AS sumqty
  FROM #Transactions
  WHERE rownum = 1
  
  UNION ALL
  
  SELECT PRV.rownum + 1, PRV.actid, CUR.tranid, CUR.val, PRV.sumqty + CUR.val
  FROM C AS PRV
    JOIN #Transactions AS CUR
      ON CUR.rownum = PRV.rownum + 1
      AND CUR.actid = PRV.actid
)
SELECT actid, tranid, val, sumqty
FROM C
OPTION (MAXRECURSION 0);

DROP TABLE #Transactions;

А это реализация с использованием явного цикла:

SELECT ROW_NUMBER() OVER(PARTITION BY actid ORDER BY tranid) AS rownum,
  actid, tranid, val, CAST(val AS BIGINT) AS sumqty
INTO #Transactions
FROM dbo.Transactions;

CREATE UNIQUE CLUSTERED INDEX idx_rownum_actid ON #Transactions(rownum, actid);

DECLARE @rownum AS INT;
SET @rownum = 1;

WHILE 1 = 1
BEGIN
  SET @rownum = @rownum + 1;
  
  UPDATE CUR
    SET sumqty = PRV.sumqty + CUR.val
  FROM #Transactions AS CUR
    JOIN #Transactions AS PRV
      ON CUR.rownum = @rownum
     AND PRV.rownum = @rownum - 1
     AND CUR.actid = PRV.actid;

  IF @@rowcount = 0 BREAK;
END

SELECT actid, tranid, val, sumqty
FROM #Transactions;

DROP TABLE #Transactions;

Это решение обеспечивает хорошую производительность, когда есть большое число секций с небольшим числом строк в секциях. Тогда число итераций небольшое, а основная работа выполняется основанной на наборах частью решения, которая соединяет строки, связанные с одним номером строки, со строками, связанными с предыдущим номером строки.

Многострочное обновление с переменными

Показанные до этого момента приемы вычисления нарастающих итогов гарантированно дают правильный результат. Описываемая в этом разделе методика неоднозначна, потому что основана на наблюдаемом, а не задокументированном поведении системы, кроме того она противоречит принципам релятивности. Высокая ее привлекательность обусловлена большой скоростью работы.

В этом способе используется инструкция UPDATE с переменными. Инструкция UPDATE может присваивать переменным выражения на основе значения столбца, а также присваивать значениям в столбцах выражение с переменной. Решение начинается с создания временной таблицы по имени Transactions с атрибутами actid, tranid, val и balance и кластеризованного индекса со списком ключей (actid, tranid). Затем временная таблица наполняется всеми строками из исходной БД Transactions, причем в столбец balance всех строк вводится значение 0,00. Затем вызывается инструкция UPDATE с переменными, связанными с временной таблицей, для вычисления нарастающих итогов и вставки вычисленного значения в столбец balance.

Используются переменные @prevaccount и @prevbalance, а значение в столбце balance вычисляется с применением следующего выражения:

SET @prevbalance = balance = CASE
                                 WHEN actid = @prevaccount
                                   THEN @prevbalance + val
                                 ELSE val
                               END

Выражение CASE проверяет, не совпадают ли идентификаторы текущего и предыдущего счетов, и, если они равны, возвращает сумму предыдущего и текущего значений в столбце balance. Если идентификаторы счетов разные, возвращается сумма текущей транзакции. Далее результат выражения CASE вставляется в столбец balance и присваивается переменной @prevbalance. В отдельном выражении переменной ©prevaccount присваивается идентификатор текущего счета.

После выражения UPDATE решение представляет строки из временной таблицы и удаляет последнюю. Вот код законченного решения:

CREATE TABLE #Transactions
(
  actid          INT,
  tranid         INT,
  val            MONEY,
  balance        MONEY
);

CREATE CLUSTERED INDEX idx_actid_tranid ON #Transactions(actid, tranid);

INSERT INTO #Transactions WITH (TABLOCK) (actid, tranid, val, balance)
  SELECT actid, tranid, val, 0.00
  FROM dbo.Transactions
  ORDER BY actid, tranid;

DECLARE @prevaccount AS INT, @prevbalance AS MONEY;

UPDATE #Transactions
  SET @prevbalance = balance = CASE
                                 WHEN actid = @prevaccount
                                   THEN @prevbalance + val
                                 ELSE val
                               END,
      @prevaccount = actid
FROM #Transactions WITH(INDEX(1), TABLOCKX)
OPTION (MAXDOP 1);

SELECT * FROM #Transactions;

DROP TABLE #Transactions;

План этого решения показан на следующем рисунке. Первая часть представлена инструкцией INSERT, вторая - UPDATE, а третья - SELECT:

План выполнения решения с использование инструкции UPDATE с переменными

В этом решении предполагается, что при оптимизации выполнения UPDATE всегда будет выполняться упорядоченный просмотр кластеризованного индекса, и в решении предусмотрен ряд подсказок, чтобы предотвратить обстоятельства, которые могут помешать этому, например параллелизм. Проблема в том, что нет никакой официальной гарантии, что оптимизатор всегда будет посматривать в порядке кластеризованного индекса. Нельзя полагаться на особенности физических вычислений, когда нужно обеспечить логическую корректность кода, если только в коде нет логических элементов, которые по определению могут гарантировать такое поведение. В данном коде нет никаких логических особенностей, которые могли бы гарантировать именно такое поведение. Естественно выбор, использовать или нет этот способ, лежит целиком на вашей совести. Я считаю, что безответственно использовать его, даже если вы тысячи раз проверяли и «вроде бы все работает, как надо».

К счастью, в SQL Server 2012 этот выбор становится практически ненужным. При наличии исключительно эффективного решения с использованием оконных функций агрегирования не приходится задумываться о других решениях.

Измерение производительности

Я провел измерение и сравнение производительности различных методик. Результаты приведены на рисунках ниже:

Измерение производительности вычисления нарастающих итогов, часть 1
Измерение производительности вычисления нарастающих итогов, часть 2

Я разбил результаты на два графика из-за того, что способ с использованием вложенного запроса или соединения настолько медленнее остальных, что мне пришлось использовать для него другой масштаб. В любом случае, обратите внимание, что большинство решений демонстрируют линейную зависимость объема работы от размера секции, и только решение на основе вложенного запроса или соединения показывают квадратичную зависимость. Также ясно видно, насколько эффективнее новое решение на основе оконной функции агрегирования. Решение на основе UPDATE с переменными тоже очень быстрое, но по описанным уже причинам я не рекомендую его использовать. Решение с использованием CLR также вполне быстрое, но в нем нужно писать весь этот код .NET и разворачивать сборку в базе данных. Как ни посмотри, а основанное на наборах решение с использованием оконных агрегатов остается самым предпочтительным.

Пройди тесты