Пробелы и диапазоны в T-SQL

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

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

SET NOCOUNT ON;
USE TSQL2012;

-- dbo.T1 (numeric sequence with unique values, interval: 1)
IF OBJECT_ID('dbo.T1', 'U') IS NOT NULL DROP TABLE dbo.T1;

CREATE TABLE dbo.T1
(
  col1 INT NOT NULL
    CONSTRAINT PK_T1 PRIMARY KEY
);
GO

INSERT INTO dbo.T1(col1)
  VALUES(2),(3),(7),(8),(9),(11),(15),(16),(17),(28);

-- dbo.T2 (temporal sequence with unique values, interval: 1 day)
IF OBJECT_ID('dbo.T2', 'U') IS NOT NULL DROP TABLE dbo.T2;

CREATE TABLE dbo.T2
(
  col1 DATE NOT NULL
    CONSTRAINT PK_T2 PRIMARY KEY
);
GO

INSERT INTO dbo.T2(col1) VALUES
  ('20120202'),
  ('20120203'),
  ('20120207'),
  ('20120208'),
  ('20120209'),
  ('20120211'),
  ('20120215'),
  ('20120216'),
  ('20120217'),
  ('20120228');

Пробелы

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

Требуемый результат нахождения пробелов в диапазоне чисел

А вот нужный результат для последовательности меток дат и времени в T2:

Требуемый результат нахождения пробелов в диапазоне дат

В версиях SQL Server предшествующих SQL Server 2012 методики работы с пробелами были довольно дорогими и подчас сложными. Но с появлением функций LAG и LEAD эту задачу стало возможным решать просто и эффективно. Давайте текущее значение в последовательности col1 назовем cur, следующее значение в последовательности назовем nxt. Затем можно фильтром отобрать только пары, разница между которыми больше интервала. Затем надо добавить один интервал к cur и отнять интервал от nxt, чтобы получить сведения о пробеле. Вот полное решение для числовой последовательности и план его выполнения:

WITH C AS
(
  SELECT col1 AS cur, LEAD(col1) OVER(ORDER BY col1) AS nxt
  FROM dbo.T1
)
SELECT cur + 1 AS rangestart, nxt - 1 AS rangeend
FROM C
WHERE nxt - cur > 1;
План решения задачи нахождения пробелов

Полюбуйтесь, насколько эффективен этот план: в нем выполняется только один упорядоченный просмотр индекса на основе столбца col1. Для применения этой же методики к временной последовательности надо просто задействовать функцию DATEDIFF для вычислении разницы между cur и nxt, а затем функцию DATEADD для добавления или вычитания интервала:

WITH C AS
(
  SELECT col1 AS cur, LEAD(col1) OVER(ORDER BY col1) AS nxt
  FROM dbo.T2
)
SELECT DATEADD(day, 1, cur) AS rangestart, DATEADD(day, -1, nxt) rangeend
FROM C
WHERE DATEDIFF(day, cur, nxt) > 1;

Диапазоны

Задача нахождения диапазонов подразумевает выявление диапазонов существующих значений. Вот ожидаемый результат для числовой последовательности:

Требуемый результат нахождения диапазонов чисел

А вот требуемый результат для временной последовательности дат:

Требуемый результат нахождения диапазонов дат

Одно из самых эффективных решений задачи поиска диапазонов предусматривает использование ранжирования. Используется функция DENSE_RANK для создания последовательности целых чисел в упорядочении по col1 и вычисляется разница между col1 и «плотным рангом» (drnk), примерно так;

SELECT col1,
  DENSE_RANK() OVER(ORDER BY col1) AS drnk,
  col1 - DENSE_RANK() OVER(ORDER BY col1) AS diff
FROM dbo.T1;
Результат запроса с поиском диапазонов

Заметьте, что в пределах диапазона разница одинакова, причем она уникальна для каждого диапазона. Это происходит потому, что col1 и drnk увеличиваются с одним интервалом. При переходе на следующий диапазон col1 увеличивается более, чем на один интервал, a drnk всегда увеличивается на один интервал. Поэтому разница в каждом последующем интервале больше, чем в предыдущем. Благодаря тому, что эта разница одинакова и уникальна в пределах каждого диапазона, можно использовать ее в качестве идентификатора группы. Так что остается только сгруппировать строки по этой разнице и вернуть максимальное и минимальное значение col1 в каждой группе:

WITH C AS
(
  SELECT col1, col1 - DENSE_RANK() OVER(ORDER BY col1) AS grp
  FROM dbo.T1
)
SELECT MIN(col1) AS start_range, MAX(col1) AS end_range
FROM C
GROUP BY grp;

План этого решения показан на рисунке:

План решения задачи нахождения диапазонов

План очень эффективен, потому что при вычислении плотного ранга используется упорядочение индекса на основе col1.<,/

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

Эта же методика применима к временным интервалам, но решение не так очевидно. Вспомните, что в описанном решении создается идентификатор групп, а именно значение, одинаковое для всех членов одного диапазона и отличающееся от значений для членов в других диапазонах. Во временных последовательностях интервалы между значениями col1 и плотного ранга разные - у первого интервал день, а у второго единица. Чтобы этот способ работал, просто вычтите из значения col1 количество временных интервалов, равное плотному рангу. Для этого надо воспользоваться функцией DATEADD. Тогда вы получите метку даты и времени, которая одинакова для всех членов одного диапазона и отличается от значений в других диапазонах.

Вот код законченного решения:

WITH C AS
(
  SELECT col1, DATEADD(day, -1 * DENSE_RANK() OVER(ORDER BY col1), col1) AS grp
  FROM dbo.T2
)
SELECT MIN(col1) AS start_range, MAX(col1) AS end_range
FROM C
GROUP BY grp;

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

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

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

CREATE TABLE dbo.Intervals
(
  id        INT  NOT NULL,
  startdate DATE NOT NULL,
  enddate   DATE NOT NULL
);

INSERT INTO dbo.Intervals(id, startdate, enddate) VALUES
  (1, '20120212', '20120220'),
  (2, '20120214', '20120312'),
  (3, '20120124', '20120201');

Эти интервалы могут представлять периоды активности, действительности или любые другие типы периодов. Задача заключается в том, чтобы при заданном периоде (с началом @from и @to конца), упаковать интервалы в нем. Иначе говоря, вам надо объединить перекрывающиеся и непосредственно прилегающие интервалы. Вот ожидаемый результат для приведенных тестовых данных при периоде с 1 января 2012 года до 31 декабря 2012 года:

Результат запроса для выбора диапазона дат

В решении ниже, описанная в статье "Вспомогательные виртуальные таблицы чисел" функция GetNums, используется для генерации последовательности дат, которые укладываются в данный период. В коде определяется CTE по имени Dates, представляющее этот набор дат. Далее код соединяет CTE-выражение Dates (псевдоним D) в таблице Intervals (псевдоним I), сопоставляя каждой дате интервалы, которые ее содержат, используя такой предикат соединения: D.dt BETWEEN I.startdate AND I.enddate. Далее в коде используется описанная выше методика вычисления идентификатора групп (назовем его grp), который определяет диапазоны. На базе этого запроса в коде определяется CTE-выражение по имени Groups. Наконец внешний запрос группирует строки по grp и возвращает минимальную и максимальную дату каждого диапазона, которые и представляют собой границы упакованных интервалов. Вот код законченного решения:

DECLARE
  @from AS DATE = '20120101',
  @to   AS DATE = '20121231';

WITH Dates AS
(
  SELECT DATEADD(day, n-1, @from) AS dt
  FROM dbo.GetNums(1, DATEDIFF(day, @from, @to) + 1) AS Nums
),
Groups AS
(
  SELECT D.dt, 
    DATEADD(day, -1 * DENSE_RANK() OVER(ORDER BY D.dt), D.dt) AS grp
  FROM dbo.Intervals AS I
    JOIN Dates AS D
      ON D.dt BETWEEN I.startdate AND I.enddate
)
SELECT MIN(dt) AS rangestart, MAX(dt) AS rangeend
FROM Groups
GROUP BY grp;

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

Есть версии задачи нахождения диапазонов, которые намного сложнее базовой версии. Допустим, к примеру, что нужно игнорировать пробелы меньшие или равные определенному размеру, например в числовой последовательности нас не интересуют пробелы 2 и меньше. Тогда ожидаемый результат будет таким:

Ожидаемый результат запроса с игнорированием пробелов

Заметьте, что значения 7, 8, 9 и 11 все являются частью одного диапазона с началом в 7 и концом в 11. Пробел между 9 и 11 игнорируется, потому что он меньше 2.

Для решения этой задачи можно использовать функции LAG и LEAD. Сначала определяем CTE но имени C1, в котором запрос таблицы T1 вычисляет следующие два атрибута: isstart и isend. Атрибут isstart является флагом, который равен единице, когда значение последовательности является первым в диапазоне, и нулю в противном случае. Значение не является первым значением в диапазоне, если разница между col1 и предыдущим значением (полученным с применением функции LAG) меньше или равна 2, в противном случае это первое значение диапазона. Аналогично, значение не является последним значением в диапазоне, если разница следующим значением (полученным с применением функции LEAD) и col1 меньше или равна 2, в противном случае это последнее значение диапазона.

Затем в коде определяется CTE по имени C2, которое отбирает только строки, в которых значения последовательности являются началом или концом диапазона. С помощью функции LEAD выделяются пары начала и конца каждого диапазона. Это достигается за счет использования выражения 1 - isend в качестве смещения функции LEAD. Это означает, что если текущая строка, представляющая начало диапазона, одновременно представляет ею конец, то смещение равно нулю, иначе оно равно единице. Наконец внешний запрос просто отбирает из результатов C2 только те строки, в которых isstart равно единице 1. Вот код законченною решения:

WITH C1 AS
(
  SELECT col1,
    CASE WHEN col1 - LAG(col1) OVER(ORDER BY col1)  <= 2 THEN 0 ELSE 1 END AS isstart, 
    CASE WHEN LEAD(col1) OVER(ORDER BY col1) - col1 <= 2 THEN 0 ELSE 1 END AS isend
  FROM dbo.T1
),
C2 AS
(
  SELECT col1 AS rangestart, LEAD(col1, 1-isend) OVER(ORDER BY col1) AS rangeend, isstart
  FROM C1
  WHERE isstart = 1 OR isend = 1
)
SELECT rangestart, rangeend
FROM C2
WHERE isstart = 1;

План этого запроса показан на рисунке:

План решения задачи нахождения диапазонов при игнорировании пробелов равных и меньших 2

В следующем примере задачи нахождения диапазонов потребуются тестовые данные, сгенерированные следующим кодом:

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

CREATE TABLE dbo.T1
(
  id  INT         NOT NULL PRIMARY KEY,
  val VARCHAR(10) NOT NULL
);
GO

INSERT INTO dbo.T1(id, val) VALUES
  (2, 'a'),
  (3, 'a'),
  (5, 'a'),
  (7, 'b'),
  (11, 'b'),
  (13, 'a'),
  (17, 'a'),
  (19, 'a'),
  (23, 'c'),
  (29, 'c'),
  (31, 'a'),
  (37, 'a'),
  (41, 'a'),
  (43, 'a'),
  (47, 'c'),
  (53, 'c'),
  (59, 'c');

В этой версии задачи нужно определить диапазоны идентификаторов, в которых значение атрибута val одинаково. Надо иметь в виду, что одному значению val могут соответствовать несколько диапазонов. Вот ожидаемый результат:

Ожидаемый результат запроса с вычислением диапазонов идентификаторов

Первый шаг этого решения - вычислить разницу между номерами строк с использованием упорядочения по id и номером строк (назовем его grp) на основе упорядочения по vol и id:

SELECT id, val,
  ROW_NUMBER() OVER(ORDER BY id)
    - ROW_NUMBER() OVER(ORDER BY val, id) AS grp
FROM dbo.T1;
Результат запроса поиска диапазонов с упорядочиванием

Заметьте, что для каждого уникального значения в атрибуте val, значение grp является уникальным в каждом диапазоне. Это происходит потому, что при упорядочении по id у номеров строк есть пробелы между разными диапазонами, а в номерах строк при упорядочении по val и id их нет. Поэтому для одного значения val при переходе от одного диапазона к следующему разница увеличивается, а в рамках диапазона она остается неизменной. Чтобы завершить решение, определим CTE на основе предыдущего запроса, после чего во внешнем запросе сгруппируем строки по val и grp и вернем минимальный и максимальный идентификаторы для каждого значения val:

WITH C AS
(
  SELECT id, val,
    ROW_NUMBER() OVER(ORDER BY id)
      - ROW_NUMBER() OVER(ORDER BY val, id) AS grp
  FROM dbo.T1
)
SELECT MIN(id) AS mn, MAX(id) AS mx, val
FROM C
GROUP BY val, grp
ORDER BY mn;
Пройди тесты
Лучший чат для C# программистов