Задачи T-SQL

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

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

Задача возобновления количества

Задача возобновления количества связана с упорядоченной последовательностью транзакций, которые добавляют и удаляют объекты из текущего запаса. Например, объект может быть товаром на складе. Положительное количество представляет добавление количества на склад; отрицательное количество представляет удаление количества со склада — например, при обслуживании заказа. Исходный текст в листинге 1 формирует таблицу Transactions и заполняет ее малым набором тестовых данных.

Классический расчет с применением таких транзакций — вычисление предположительного количества складских запасов после каждой транзакции. Это делается с помощью простого подсчета с нарастающим итогом (столбец qty) на основе порядка транзакций (столбец txid). Однако у нашей задачи есть особенность, усложняющая ее решение. Если уровень запасов падает ниже нуля, то недостающее количество добавляется из другого источника. Поэтому в таком случае нужно вернуть нулевое, а не отрицательное значение уровня запасов, и вернуть количество replenish (возобновление) в отдельном столбце. На рисунке 1 показан предположительный результат для малого набора тестовых данных.

Рисунок 1. Предположительный результат для задачи возобновления количества

Для оценки производительности решения требуется более крупный набор тестовых данных. Запустите программный код из листинга 2, чтобы создать вспомогательную функцию GetNums. Эта функция возвращает последовательность целых чисел между параметрами @low и @high, которые используются в качестве входных данных.

Затем выполните программный код листинга 3, чтобы записать в таблицу Transactions 1 000 000 строк с использованием вспомогательной функции. Изменяя числовые величины, вы можете испытать свое решение с таблицами различных размеров.

Решение задачи возобновления количества

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

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

Второе вычисление — текущее минимальное значение rt (обозначено mn) на основе порядка транзакций. Значение mn вычисляется с помощью оконной функции, которая агрегирует результат другой оконной функции, поэтому вы определяете обобщенное табличное выражение (CTE) с именем C1 на основе запроса, вычисляющего rt; затем можно вычислить mn во внешнем запросе для C1.

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

WITH C1 AS
(
SELECT *,
SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt
FROM dbo.Transactions
)
SELECT *,
MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mn
FROM C1;

На рисунке 2 показан вывод этого программного кода.

Рисунок 2. Текущий минимум нарастающего итога

Суть решения в осознании, что после каждой транзакции, когда значение mn отрицательно, -mn (минус mn) — общее количество, возобновленное до сих пор (обозначено replenish_rt). Когда значение rt впервые падает ниже нуля, -mn очевидно представляет собой возобновление количества после этой транзакции. Следующее снижение rt ниже предшествующего низшего значения rt будет следующей точкой возобновления, и возобновление количества в этой точке есть разница между абсолютными значениями текущего rt и предшествующего низшего значения rt. На втором шаге вычисляется возобновление количества с нарастающим итогом (replenish_rt) как –mn, когда mn — отрицательная величина, и как 0 в ином случае. В следующем программном коде реализован второй шаг решения:

WITH C1 AS
(
SELECT *,
SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt
FROM dbo.Transactions
),
C2 AS
(
SELECT *,
MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mn
FROM C1
)
SELECT txid, val, rt, replenish_rt
FROM C2
CROSS APPLY (VALUES(CASE WHEN mn < 0 THEN -mn ELSE 0 END)) AS A(replenish_rt);

Вычисление столбца replenish_rt выполняется с использованием оператора CROSS APPLY в предложении FROM, чтобы сделать столбец доступным в запросе (FROM — первое логически оцениваемое предложение). На рисунке 3 показан вывод второго шага решения.

Рисунок 3. Возобновление с нарастающим итогом

Последний шаг в решении определяет CTE с именем C2 на основе последнего запроса. Затем внешний запрос выполняет два вычисления: правильного уровня запасов после учета возобновления из внешнего источника и собственно возобновления количества. Правильный уровень запасов есть текущее значение rt плюс текущее значение replenish_rt. Текущее возобновление количества есть текущее значение replenish_rt за вычетом предыдущего значения (или минус нуль для первой транзакции). Можно использовать оконную функцию LAG, чтобы получить предшествующее значение replenish_rt. Следующий программный код содержит полное решение для задачи:

WITH C1 AS
(
SELECT *,
SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt
FROM dbo.Transactions
),
C2 AS
(
SELECT *,
MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mn
FROM C1
)
SELECT txid, val,
rt + replenish_rt AS stocklevel,
replenish_rt — LAG(replenish_rt, 1, 0) OVER(ORDER BY txid) AS replenish
FROM C2
CROSS APPLY (VALUES(CASE WHEN mn < 0 THEN -mn ELSE 0 END)) AS A(replenish_rt);

На рисунке 4 показан план для этого решения. Удивительно, что вычисления всех трех оконных функций в плане выполняются на основе упорядоченного сканирования кластеризованного индекса (определенного для txid в качестве ключа). Не понадобилось ни одного явного оператора сортировки. Для выполнения этого запроса с большим набором тестовых данных на моем компьютере потребовалось 8 секунд.

Рисунок 4. План запроса для решения первой задачи

Задача расхода количества

Вторая задача предложена мне обладателем сертификата MVP SQL Server Гэри Решефом. Я пока не нашел для нее хорошего реляционного решения, поэтому предлагаю подумать над этой задачей читателям (и продолжу работать над ней сам).

Как и предыдущая, эта задача связана с последовательностью транзакций с соответствующими количествами. На сей раз количества всегда неотрицательны. Примером может служить добавление количества какого-либо объекта в контейнер. Требуется показать общее количество в контейнере после каждой транзакции, но надо сбрасывать его в 0 всегда, когда значение превышает 5. Наглядная иллюстрация — контейнер с ограниченной вместимостью, который нужно выгрузить, когда количество превышает вместимость. Используйте программный код в листинге 4, чтобы заполнить таблицу Transactions малым набором тестовых данных для проверки правильности решения.

На рисунке 5 показан желательный результат для малого набора тестовых данных. Используйте программный код в листинге 5 для заполнения таблицы Transactions с большим набором тестовых данных.

Рисунок 5. Желательный результат для задачи расхода количества

Существуют простые решения для задачи с использованием курсора T-SQL, рекурсивного запроса и CLR. Однако, как уже отмечалось выше, я пока не нашел производительного реляционного решения.

В этой статье описаны две задачи T-SQL, связанные с последовательностью транзакций с соответствующими количествами, в ходе которых необходимо вычислить уровень запаса после каждой транзакции. Сложность задач по сравнению с обычными задачами определения уровня запасов заключается в наличии особых требований. В задаче возобновления количества уровню запасов присваивается значение 0 всегда, когда количество падает ниже 0; в задаче расхода количества уровню запасов присваивается значение 0 всегда, когда количество превышает 5.

Я показал реляционное решение для первой задачи, но все еще ищу эффективное решение для второй.

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.Transactions', N'U') IS NOT NULL DROP TABLE dbo.Transactions;
CREATE TABLE dbo.Transactions
(
txid INT NOT NULL PRIMARY KEY,
val INT NOT NULL
);
— Малый набор тестовых данных для проверки правильности
INSERT INTO dbo.Transactions(txid, val)
VALUES(1,2),(2,-5),(3,4),(4,1),(5,-10),(6,3),(7,1),(8,-2),(9,1),(10,-2),(11,1),(12,-9);
GO

IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;
GO
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high — @low + 1) @low + rownum — 1 AS n
FROM Nums
ORDER BY rownum;
GO

TRUNCATE TABLE dbo.Transactions;
INSERT INTO dbo.Transactions(txid, val)
SELECT n, SIGN(1+2*SIGN(CHECKSUM(NEWID())))*(ABS(CHECKSUM(NEWID()))%10+1) AS val
FROM dbo.GetNums(1, 1000000) AS Nums;
GO

TRUNCATE TABLE dbo.Transactions;
INSERT INTO dbo.Transactions(txid, val)
VALUES(1,2),(2,500),(3,4),(4,1),(5,10),(6,3),(7,1),(8,2),(9,1),(10,2),(11,1),(12,9);

TRUNCATE TABLE dbo.Transactions;
INSERT INTO dbo.Transactions(txid, val)
SELECT n, ABS(CHECKSUM(NEWID()))%11 AS val
FROM dbo.GetNums(1, 1000000) AS Nums;