Проблема интервальных графов T-SQL, часть 1

Недавно мой друг Джон Поль Кук, дипломированный медицинский работник и обладатель статуса SQL Server MVP, попросил помочь в решении задачи, связанной с моделированием назначения лекарственных препаратов в виде интервальных графов. Подробное описание задачи дано в статье Сяоцян Вана «Counting Drug Exposure in SAS® with Interval Graph Modeling» (www.nesug.org/Proceedings/nesug10/hl/hl06.pdf). Автор статьи описывает задачу и приводит ее решение с использованием SAS. Джон попросил меня найти оптимальное решение задачи на основе T-SQL.

Я решал множество головоломок T-SQL, мне нравится этот процесс. Часто приходится проводить не один час в поисках рациональных, элегантных решений. А иногда удается найти новые закономерности, пригодные и для решения других задач. Именно так произошло с данной задачей.

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

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

Таблица Prescriptions содержит информацию о назначении лекарственных препаратов для пациентов. Она состоит из следующих столбцов: prescriptionid (суррогатный ключ), patientid, drugid, startdate (начало периода действия рецептуры) и numdays (число дней действия рецепта). В таблице также определен вычисляемый столбец enddate для даты окончания действия рецепта (это день, следующий за последним днем приема лекарства). Например, если трехдневный срок приема лекарства начинается 1 января 2014 года (число дней — 3), то датой окончания будет 4 января 2014 года. Пациент принимает лекарство 1, 2 и 3 января, но не получает дозу 4 января.

Задача, описанная в статье «Counting Drug Exposure in SAS® with Interval Graph Modeling», разделяется на две части:

1. Упаковка пересекающихся периодов назначения лекарственных препаратов.
2. Обнаружение периодов, в течение которых пациент принимает определенное минимальное число лекарств.

Передавая мне задачу, Джон сказал: «Исследователи изучают рецепты в поисках потенциальных побочных эффектов. Если быть откровенным, то задача — не допустить летального исхода».

Трудно придумать более действенный стимул для поиска эффективного решения!

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

Упаковка

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

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

Рисунок 1. Входные и упакованные интервалы

Обратите внимание на три рецептурных периода для Patient 1, Drug 4:

1—startdate: 1/2; numdays: 5
2—startdate: 1/3; numdays: 2
3—startdate: 1/8; numdays: 1

Первый рецепт начинается 2 января и длится 5 дней, поэтому истекает 7 января. Второй рецепт начинается до 7 января, поэтому он переносится на эту дату. Продолжительность второго рецепта — 2 дня, поэтому он завершается 9 января. Третий рецепт начинается до 9 января, поэтому он перенесен на эту дату. Продолжительность третьего рецепта — 1 день, он истекает 10 января. Упакованный рецептурный период представлен стрелкой над отдельными рецептурными периодами; он начинается 2 января и завершается 10 января.

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

Рисунок 2. Упакованные рецепты

Я рассматриваю как решения на основе курсора, так и на основе наборы. Предоставляются метрики производительности, полученные при запуске решений с большим набором тестовых данных. Результаты сбрасываются в среде SQL Server Management Studio (SSMS). Чтобы сбросить результаты после выполнения, щелкните правой кнопкой мыши пустую область на панели запроса, выберите Query Options («Параметры запроса»), затем Discard results after execution («Отбросить результаты после выполнения») и подтвердите режим в разделе Results-Grid. Таким образом запрещается вывод результирующих строк на печать в сетке.

Решение на основе курсора

Решение на основе курсора довольно простое, с обработкой данных за один проход. В листинге 3 показан полный исходный текст решения. Объявляется табличная переменная с именем @Result, в которой хранятся упакованные интервалы.

Строки из таблицы подаются в курсор, сортируются сначала по patientid и drugid (поскольку вычисления производятся отдельно для каждого пациента и лекарственного препарата), затем по startdate и prescriptionid (для разрешения конфликтов). Запрос, который передает данные в курсор, оптимизирован путем упорядоченного сканирования индекса idx_start, поэтому операции сортировки не требуется.

Организуется циклическая обработка записей курсора по одной, с подачей значений текущей записи в локальные переменные. В переменной @firststartdate хранится дата начала недавно упакованного интервала, а в переменной @sumnumdays — число рецептурных дней с нарастающим итогом для недавно упакованного интервала. Для каждой извлеченной записи проверяется следующее условие, чтобы выяснить, нужно ли закрыть текущий упакованный интервал и начать новый:

IF @prevpatientid <> @patientid
OR @prevdrugid <> @drugid
OR DATEADD(day, @sumnumdays, @firststartdate) < @startdate

Текущий упакованный интервал закрывается, если выполнено любое из следующих условий:

• любой из элементов группы (patientid или drugid) изменяется;
• начальная дата текущего упакованного интервала (@firststartdate) плюс число рецептурных дней с нарастающим итогом с момента его начала (@sumnumdays) меньше начальной даты нового рецептурного интервала.

В случае совпадения новый упакованный интервал закрывается, его информация записывается в табличную переменную, затем открывается новый упакованный интервал путем инициализации @firststartdate значением @startdate и @sumnumdays значением 0. Если текущий упакованный интервал не закрыт (то есть новый интервал должен продлить его), значение @sumnumdays увеличивается на @numdays.

После завершения цикла информация о последнем упакованном интервале вставляется в табличную переменную (если применимо), затем курсор закрывается и переназначается. На моем компьютере решение на основе курсора было выполнено за 31 секунду.

Решение на основе наборов

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

Рисунок 3. Вычисление grphelper и grp

На первом шаге вычисляется значение, именуемое grphelper. Это значение вычисляется как текущее значение startdate минус сумма с нарастающим итогом всех значений numdays интервалов на данный момент, кроме текущего интервала. Эти вычисления реализованы в следующем запросе:

SELECT prescriptionid, patientid, drugid, startdate, numdays,
DATEADD(day,
— SUM(numdays) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) + numdays,
startdate) AS grphelper
FROM dbo.Prescriptions;

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

Рисунок 4. Вычисление grphelper

Второй шаг заключается в вычислении grp как максимального на данный момент значения grphelper. В следующем запросе это вычисление добавляется сверх предшествующего запроса, представленного CTE C1:

WITH C1 AS
(
SELECT prescriptionid, patientid, drugid, startdate, numdays,
DATEADD(day,
— SUM(numdays) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) + numdays,
startdate) AS grphelper
FROM dbo.Prescriptions
)
SELECT *,
MAX(grphelper) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) AS grp
FROM C1;

На рисунке 5 показан вывод этого запроса. Он содержит как значения grphelper, так и grp.

Рисунок 5. Вычисление grp

На рисунке 3 представлены четыре примера с сопутствующими объяснениями, из которых можно сделать вывод, что значение grp уникально для каждого упакованного интервала. Обратите внимание, что RT представляет сумму с нарастающим итогом для количества дней numdays, исключая текущий интервал.

Первые два примера относятся к двум первым интервалам для данного пациента и лекарства; интервал I1 представляет самый первый интервал, а I2 представляет второй интервал (начавшийся одновременно или после начала I1). Последние два пример похожи, единственное различие — в существовании рецептов перед I1 и I2.

В первом примере предполагается, что I2 перекрывается с I1. В данном случае grphelper1 = s1 — RT1 = s1 — 0 = s1.

Поскольку в этом примере I2 пересекается с I1, grphelper2 (s2 — d1) <= s1. Таким образом, grphelper2 <= grphelper1, и в результате grp2 = grp1. Другими словами, если два интервала перекрываются, оба получают одинаковое значение grp и потому принадлежат к одному упакованному интервалу.

Во втором примере предполагается, что I2 начинается после завершения I1. В данном случае grphelper2 (s2 — d1) > grphelper1 (s1). Поэтому grp2 > grp1. Другими словами, два интервала получают различные значения grp и принадлежат к разным упакованным интервалам.

Третий и четвертый примеры похожи на первый и второй, соответственно; однако I1 и I2 не являются первыми рецептурными интервалами. Различие в этих примерах в том, что значения RT для I1 и I2 содержат дополнительную величину delta, равную нарастающему итогу значений numdays для интервалов, начавшихся прежде интервалов I1 и I2.

Третий пример — I2 пересекается с I1, но существуют интервалы, предшествующие I1. Теперь нужно учесть delta, но поскольку delta вычитается из обеих сторон уравнения, то результат не изменяется. В этом примере I2 пересекает I1, поэтому grphelper2 (s2 — d1 — delta) <= s1 — delta. Таким образом, grphelper2 <= grphelper1. Следовательно, grp2 = grp1. Другими словами, когда I2 пересекает I1, даже если существуют предшествующие рецепты, значения grp обоих по-прежнему одинаковы, и они принадлежат к одному упакованному интервалу.

Четвертый пример — I2 следует за I1, но с существующими предыдущими рецептами. В данном случае grphelper2 (s2 — d1 — delta) > grphelper1 (s1 — delta). Поэтому grp2 > grp1. Двум интервалам назначаются различные значения grp; следовательно, они принадлежат различным упакованным интервалам.

Полученное значение grp уникально идентифицирует упакованные интервалы для одного пациента и группы препаратов. Остается сгруппировать строки по значениям patientid, drugid и grp и вычислить начало и конец каждого упакованного интервала. В листинге 4 приведен полный исходный текст запроса.

На рисунке 6 показан план запроса.

Рисунок 6. План для запроса в листинге 4

Интересная особенность плана запроса — индекс idx_start сканируется только один раз в ORDER, и вычисления оконной функции основываются на этом ORDER. Ни одно из них не требует явной операции сортировки. Поэтому данному решению свойственно эффективное линейное масштабирование. На моем компьютере для его выполнения потребовалось 4 секунды.

Тем не менее, существует потенциал для улучшения методов обработки оконных агрегатных функций оптимизатором. В настоящее время оконные агрегатные функции с фреймом оптимизированы с использованием двух операторов, именуемых Window Spool и Stream Aggregate. Оператор Window Spool представляет список строк, а оператор Stream Aggregate вычисляет эти строки. Если фрейм начинается с UNBOUNDED PRECEDING, оптимизатор идентифицирует случай как fast track и вместо того, чтобы записать все применимые строки во фрейм, а затем обработать их, получает предыдущее накопление строки и добавляет значение текущей строки, вычисляя новый нарастающий итог.

Проблема в том, что SQL Server записывает одну строку в очередь с агрегатом, а другую с подробностями (помните, что в отличие от групповых, оконные функции не скрывают подробности). Имеется огромный потенциал для оптимизации особого (и очень распространенного) случая с фреймом ROWS UNBOUNDED PRECEDING. Теоретически данный вариант может быть оптимизирован, как и функция ROW_NUMBER: с помощью оператора Sequence Project, который вычисляет значения результата на ходу, при этом не требуется дополнительная работа по записи строк в Window Spool (рабочую таблицу) и их агрегирования. Такая оптимизация должна обеспечить гораздо более быстрое выполнение запросов: вероятно, примерно за 1 секунду вместо 4 секунд. Надеюсь, что компания Microsoft углубит оптимизацию оконных функций, чтобы повысить производительность решений на основе наборов.

Что дальше?

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

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.Prescriptions', N'U') IS NOT NULL
DROP TABLE dbo.Prescriptions;
IF OBJECT_ID(N'dbo.Patients', N'U') IS NOT NULL
DROP TABLE dbo.Patients;
CREATE TABLE dbo.Patients
(
patientid INT NOT NULL,
CONSTRAINT PK_Patients PRIMARY KEY(patientid)
);
CREATE TABLE dbo.Prescriptions
(
prescriptionid INT NOT NULL IDENTITY,
patientid INT NOT NULL,
drugid INT NOT NULL,
startdate DATE NOT NULL,
numdays INT NOT NULL,
enddate AS DATEADD(day, numdays, startdate),
CONSTRAINT CHK_Prescriptions_ed_sd CHECK(numdays > 0)
);
CREATE UNIQUE CLUSTERED INDEX idx_start
ON dbo.Prescriptions
(patientid, drugid, startdate, prescriptionid);
ALTER TABLE dbo.Prescriptions
ADD CONSTRAINT PK_Prescriptions PRIMARY KEY
NONCLUSTERED(prescriptionid);
— код для заполнения таблиц с малым набором тестовых данных
TRUNCATE TABLE dbo.Prescriptions;
TRUNCATE TABLE dbo.Patients;
INSERT INTO dbo.Patients(patientid) VALUES(1);
INSERT INTO dbo.Prescriptions
(patientid, drugid, startdate, numdays) VALUES
(1, 1, '20140101', 3),
(1, 2, '20140101', 5),
(1, 3, '20140102', 4),
(1, 4, '20140102', 5),
(1, 4, '20140103', 2),
(1, 2, '20140105', 5),
(1, 3, '20140106', 4),
(1, 1, '20140107', 3),
(1, 4, '20140108', 1),
(1, 4, '20140120', 4),
(1, 4, '20140122', 1),
(1, 5, '20140212', 3),
(1, 5, '20140215', 3),
(1, 5, '20140220', 1),
(1, 5, '20140223', 1),
(1, 5, '20140226', 1);

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
DECLARE
@numpatients AS INT = 10000,
@numdrugs AS INT = 10,
@numprescriptions AS INT = 10,
@firststartdate AS DATE = '20140101',
@laststartdate AS DATE = '20141231',
@maxnumdays AS INT = 30;
TRUNCATE TABLE dbo.Prescriptions;
TRUNCATE TABLE dbo.Patients;
INSERT INTO dbo.Patients(patientid)
SELECT PT.n AS patientid
FROM dbo.GetNums(1, @numpatients) AS PT;
INSERT INTO dbo.Prescriptions
(patientid, drugid, startdate, numdays)
SELECT
PT.n AS patientid,
D.n AS drugid,
DATEADD(day,
ABS(CHECKSUM(NEWID()))
% DATEDIFF(day, @firststartdate, @laststartdate),
@firststartdate ) AS startdate,
ABS(CHECKSUM(NEWID())) % @maxnumdays + 1 AS numdays
FROM dbo.GetNums(1, @numpatients) AS PT
CROSS JOIN dbo.GetNums(1, @numdrugs) AS D
CROSS JOIN dbo.GetNums(1, @numprescriptions) AS PR;

SET NOCOUNT ON;
DECLARE @Result AS TABLE
(
patientid INT NOT NULL,
drugid INT NOT NULL,
startdate DATE NOT NULL,
enddate DATE NOT NULL
);
DECLARE
@patientid AS INT,
@drugid AS INT,
@startdate AS DATE,
@numdays AS INT,
@sumnumdays AS INT,
@prevpatientid AS INT,
@prevdrugid AS INT,
@firststartdate AS DATE;
DECLARE C FAST_FORWARD FOR
SELECT patientid, drugid, startdate, numdays
FROM dbo.Prescriptions
ORDER BY patientid, drugid, startdate, prescriptionid;
OPEN C;
FETCH NEXT FROM C INTO
@patientid, @drugid, @startdate, @numdays;
SELECT
@prevpatientid = @patientid,
@prevdrugid = @drugid,
@firststartdate = @startdate,
@sumnumdays = 0;
WHILE @@fetch_status = 0
BEGIN
IF @prevpatientid <> @patientid
OR @prevdrugid <> @drugid
OR DATEADD(day, @sumnumdays, @firststartdate)
< @startdate
BEGIN
INSERT INTO @Result(patientid, drugid, startdate, enddate)
VALUES(@prevpatientid, @prevdrugid, @firststartdate,
DATEADD(day, @sumnumdays, @firststartdate));
SELECT
@firststartdate = @startdate,
@sumnumdays = 0;
END
SELECT
@sumnumdays += @numdays,
@prevpatientid = @patientid,
@prevdrugid = @drugid;
FETCH NEXT FROM C INTO
@patientid, @drugid, @startdate, @numdays;
END
IF @sumnumdays > 0
INSERT INTO @Result(patientid, drugid, startdate, enddate)
VALUES(@prevpatientid, @prevdrugid, @firststartdate,
DATEADD(day, @sumnumdays, @firststartdate));
CLOSE C;
DEALLOCATE C;
SELECT * FROM @Result;

WITH C1 AS
(
SELECT prescriptionid, patientid, drugid, startdate, numdays,
DATEADD(day,
— SUM(numdays) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING)
+ numdays,
startdate) AS grphelper
FROM dbo.Prescriptions
),
C2 AS
(
SELECT *,
MAX(grphelper) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) AS grp
FROM C1
)
SELECT
patientid, drugid,
MIN(startdate) AS startdate,
DATEADD(day, SUM(numdays), MIN(startdate)) AS enddate
FROM C2
GROUP BY patientid, drugid, grp;