Задача о последнем значении, отличном от NULL

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

Я попросил у Саймона разрешения поделиться задачей с читателями.

Постановка задачи

Задача довольно проста. Но разве простые задачи одновременно не самые лучшие? Для данной таблицы T1 с ключевым столбцом с именем id и столбцом значений типа, допускающего значение NULL, с именем col1 возвратите отличное от NULL значение col1 в соответствии с порядком id.

Выполните программный код листинга 1, чтобы создать таблицу T1 и заполнить ее малым набором тестовых данных.

На рисунке 1 показан желаемый результат с малым набором тестовых данных.

Рисунок 1. Желаемый результат

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

В таблице T1 хранится последовательность событий, а столбец id представляет их порядок. У события есть несколько атрибутов, один из которых представлен col1. Когда значение атрибута меняется, в строке события отображается новое значение col1; для атрибутов, значения которых неизменны, в строке события показаны значения NULL.

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

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

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

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

Представленные величины производительности были измерены с использованием большого набора тестовых данных; результаты удалены.

Решение 1. Использование только оконной функции

В первом решении мы используем два уровня оконной агрегатной функции MAX. Решение состоит из двух шагов. Первый из них реализован в следующем программном коде:

SELECT id, col1, relevantid,
MAX(relevantid) OVER( ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS grp
FROM dbo.T1
CROSS APPLY ( VALUES( CASE WHEN col1 IS NOT NULL THEN id END ) )
AS A(relevantid);

Чтобы было проще понять, что здесь происходит, познакомьтесь с моими объяснениями относительно выходных данных этого шага (см. рисунок 2).

Рисунок 2. Выходные данные решения 1, шаг 1

В программном коде используется выражение CASE для вычисления столбца результатов с именем relevantid. В этом столбце выводится значение id, если значение col1 изменяется, и значение NULL — если не изменяется. Важная особенность id состоит в том, что по определению его значения увеличиваются; но это обязательно справедливо в отношении значений в столбце col1. Оконная агрегатная функция MAX возвращает максимальное значение relevantid (назовем столбец результатов grp).

Обратите внимание, что на рисунке 2 значение группы (grp) изменяется на текущее id каждый раз, когда изменяется значение col1, и остается неизменным, пока значение col1 не меняется. Таким образом максимальное значение col1 в каждой группе событий — применимое значение col1 для этих событий. На втором шаге в решении выполняется последнее вычисление:

WITH C AS
(
SELECT id, col1, relevantid,
MAX(relevantid) OVER( ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS grp
FROM dbo.T1
CROSS APPLY ( VALUES( CASE WHEN col1 IS NOT NULL THEN id END ) )
AS A(relevantid)
)
SELECT *,
MAX(col1) OVER( PARTITION BY grp
ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS maxcol1ingrp
FROM C;

На рисунке 3 показаны выходные данные этого шага.

Рисунок 3. Выходные данные решения 1, шаг 2

Столбец результатов maxcol1ingrp — последнее значение, отличное от NULL, которое мы ищем. Ниже приводится полное решение после встраивания вычисления relevantid:

WITH C AS
(
SELECT id, col1,
MAX( CASE WHEN col1 IS NOT NULL THEN id END )
OVER( ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS grp
FROM dbo.T1
)
SELECT id, col1,
MAX(col1) OVER( PARTITION BY grp
ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS lastval
FROM C;

На рисунке 4 показан план для этого решения при использовании большого набора тестовых данных.

Рисунок 4. План решения 1

Первая оконная агрегатная функция полагается на порядок индекса. Но вторая оконная агрегатная функция использует другую спецификацию окна, поэтому требуется явная сортировка. Это наиболее затратная часть плана. Для выполнения данного решения на моем компьютере потребовалось 66 секунд.

Во втором решении необходимость в явной сортировке исключена.

Решение 2. Использование объединения и оконной функции

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

SELECT id, col1, binstr,
MAX( binstr ) OVER( ORDER BY id
ROWS UNBOUNDED PRECEDING ) AS mx
FROM dbo.T1
CROSS APPLY ( VALUES( CAST(id AS BINARY(4)) + CAST(col1 AS BINARY(4)) ) )
AS A(binstr);

Разберемся в программном коде и выходных данных, показанных на рисунке 5. На этом шаге значение id и значение col1 преобразуются в двоичную строку и объединяются. Результирующему столбцу присваивается имя binstr. Обратите внимание, что на рисунке 5, когда меняется значение col1, binstr показывает объединенные строки; если значение col1 не меняется, то binstr получает значение NULL. Оконная агрегатная функция MAX вычисляет максимальное значение binstr. В программном коде результирующий столбец именуется mx.

Рисунок 5. Выходные данные решения 2, шаг 1

Правые четыре байта в mx представляют двоичную форму последнего отличного от NULL значения col1. Второй шаг решения извлекает эти четыре байта и преобразует их в формат INT, возвращая желаемый результат соответствующего типа. Ниже приведен программный код, в котором реализован шаг 2:

SELECT id, col1,
CAST(
SUBSTRING(
MAX( CAST(id AS BINARY(4)) + CAST(col1 AS BINARY(4)) )
OVER( ORDER BY id
ROWS UNBOUNDED PRECEDING ),
5, 4)
AS INT) AS lastval
FROM dbo.T1;

На рисунке 6 показан план этого решения.

Рисунок 6. План решения 2

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

Итак, задача о последнем значении, отличном от NULL, заслуживает внимания по нескольким причинам. Она простая и распространенная, но, похоже, не имеет элементарного решения. Для поиска эффективного решения необходимо знание оконных функций и способов их оптимизации, а также творческий подход.

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

— DDL для T1
SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.T1', N'U') IS NOT NULL DROP TABLE dbo.T1;
GO
CREATE TABLE dbo.T1
(
id INT NOT NULL CONSTRAINT PK_T1 PRIMARY KEY,
col1 INT NULL
);
— Малый набор тестовых данных
TRUNCATE TABLE dbo.T1;
INSERT INTO dbo.T1(id, col1) VALUES
( 2, NULL),
( 3, 10),
( 5, -1),
( 7, NULL),
(11, NULL),
(13, -12),
(17, NULL),
(19, NULL),
(23, 1759);

— Определение GetNums: tsql.solidq.com/GetNums.txt
TRUNCATE TABLE dbo.T1;
INSERT INTO dbo.T1 WITH(TABLOCK)
SELECT n AS id, CHECKSUM(NEWID()) AS col1
FROM TSQLV3.dbo.GetNums(1, 10000000) AS Nums
OPTION(MAXDOP 1);