Функции обратного распределения и смещения T-SQL

102

Работа с базами данных в .NET Framework --- Оконные функции T-SQL --- Функции обратного распределения и смещения

Функции обратного распределения (inverse distribution functions) производят вычисления, которые можно представить себе как операцию, обратную выполняемой функциям распределения рангов PERCENT_RANK и CUME_DIST. Функции распределения рангов вычисляют ранг значения относительно других значений в секции или группе как число в диапазоне от 0 до 1 (процент). Функции обратного распределения выполняют практически обратное. Получая на вход процент @pct, они возвращают значение из секции или группы, которому этот процент соответствует. Проще говоря, они возвращают значение, по отношению к которому @pct процентов значений являются меньше этого значения. Если вам все еще непонятен смысл этого предложения, все станет яснее на примерах. Функции обратного распределения больше известны как процентили.

В стандарте существует два варианта функций обратного распределения: PERCENTILE_DISC, которая возвращает существующее значение из совокупности, используя модель дискретного распределения, и PERCENTILE_CONT, которая возвращает интерполированное значение с использованием модели непрерывного распределения. Я объяснял особенности этих двух расчетов в статье "Аналитические функции". Напомню вкратце, что PERCENTILE_DISC возвращает первое значение в группе, накопительное распределение которой больше или равно входного значения. Функция PERCENTILE_CONT определяет две строки, между которыми попадает входное значение процента, и вычисляет интерполяцию двух упорядоченных значений с использованием модели непрерывного распределения.

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

Напомню запрос данных из таблицы Scores, которые вычисляет 50-й процентиль (медиану) тестовых значений, используя оба варианта функции, в том числе и оконный:

DECLARE @pct AS FLOAT = 0.5;

SELECT testid, score,
  PERCENTILE_DISC(@pct) WITHIN GROUP(ORDER BY score) 
      OVER(PARTITION BY testid) AS percentiledisc,
  PERCENTILE_CONT(@pct) WITHIN GROUP(ORDER BY score) 
      OVER(PARTITION BY testid) AS percentilecont
FROM Stats.Scores;

Результат запроса с вычислением процентелей

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

-- Не работает в T-SQL
DECLARE @pct AS FLOAT = 0.5;

SELECT testid, 
  PERCENTILE_DISC(@pct) WITHIN GROUP(ORDER BY score) AS percentiledisc,
  PERCENTILE_CONT(@pct) WITHIN GROUP(ORDER BY score) AS percentilecont
FROM Stats.Scores
GROUP BY testid;

Но эти версии не реализованы в SQL Server 2012, так что для получения такого же результата нам понадобятся альтернативные методы.

Так как существует реализация оконных версий этих функций, одним из простых методов достижения результата является использование параметра DISTINCT, примерно так:

DECLARE @pct AS FLOAT = 0.5;

SELECT DISTINCT testid,
  PERCENTILE_DISC(@pct) WITHIN GROUP(ORDER BY score)
    OVER(PARTITION BY testid) AS percentiledisc,
  PERCENTILE_CONT(@pct) WITHIN GROUP(ORDER BY score)
    OVER(PARTITION BY testid) AS percentilecont
FROM Stats.Scores;

Другой способ — присвоить уникальные номера строкам в каждой секции, а затем отфильтровать лишь строки с номером 1, вот так:

DECLARE @pct AS FLOAT = 0.5;

WITH C AS
(
  SELECT testid,
    PERCENTILE_DISC(@pct) WITHIN GROUP(ORDER BY score) OVER(PARTITION BY testid) AS percentiledisc,
    PERCENTILE_CONT(@pct) WITHIN GROUP(ORDER BY score) OVER(PARTITION BY testid) AS percentilecont,
    ROW_NUMBER() OVER(PARTITION BY testid ORDER BY (SELECT NULL)) AS rownum
  FROM Stats.Scores
)
SELECT testid, percentiledisc, percentilecont
FROM C
WHERE rownum = 1;

Еще вариант — использовать TOP (1) WITH TIES, с упорядочением по одинаковым номерам строк, в результате также получим только строки с номером строки 1:

DECLARE @pct AS FLOAT = 0.5;

SELECT TOP (1) WITH TIES testid,
  PERCENTILE_DISC(@pct) WITHIN GROUP(ORDER BY score) OVER(PARTITION BY testid) AS percentiledisc,
  PERCENTILE_CONT(@pct) WITHIN GROUP(ORDER BY score) OVER(PARTITION BY testid) AS percentilecont
FROM Stats.Scores
ORDER BY ROW_NUMBER() OVER(PARTITION BY testid ORDER BY (SELECT NULL));

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

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

Если вам необходимо посчитать процентили в версиях, предшествующих SQL Server 2012, потребуется самостоятельно реализовать логику вычислений. В PERCENTILE_DISC нужно вернуть первое значение в группе, накопительное распределение которой больше или равно значению входного процента. Для вычисления накопительного распределения каждого значения необходимо знать, сколько строк предшествовало или равно этому значению (np) и сколько строк содержится в каждой группе (nr). Тогда накопительное распределение будет равно np*nr.

Обычно при вычислении np нужно вернуть значение на единицу меньшее минимального ранга, превышающего текущее значение. Для этого могут понадобиться ресурсоемкие вложенные запросы и функция RANK. Благодаря Адаму Маканику (Adam Machanic), получить тот же результат можно меньшими усилиями. Когда существование одинаковых строк исключается (то есть упорядочение уникально), для всех строк функция ROW_NUMBER возвращает число равное np. Когда одинаковые строки возможны (упорядочение неуникально) функция возвращает число равное np для одной из строк, а для всех остальных строк — значение, меньшее np. Так как мы с вами говорим о равных строках, по определению в случаях, когда номер строки меньше чем np, значение сортировки такое же, как и в случае, когда номер строки равен np. Благодаря этому факту, функция ROW_NUMBER подходит для наших нужд очень специфического представления np. Что до вычисления nr, то можно использовать простую оконную функцию COUNT. Вот код, который реализует данную логику:

DECLARE @pct AS FLOAT = 0.5;

WITH C AS
(
  SELECT testid, score,
    ROW_NUMBER() OVER(PARTITION BY testid ORDER BY score) AS np,
    COUNT(*) OVER(PARTITION BY testid) AS nr
  FROM Stats.Scores
)
SELECT testid, MIN(score) AS percentiledisc
FROM C
WHERE    1.0 * np / nr >= @pct
GROUP BY testid;

Результат запроса расчета процентилей для старых версий SQL Server

Что касается альтернативы для функции PERCENTILE_CONT в версиях, предшествующих SQL Server 2012, кратко напомню описание логики вычислений:

Используем функцию PERCENTILE_CONT(@pct) WITHIN GROUP (ORDER BY score).
Пусть n — количество строк в группе.
Пусть g равно @pct * (n - 1) и пусть i — целая, а f — дробная часть g.
Пусть row0 и row1 это строки, чьи номера при нумерации, начиная с нуля, попадают в диапазон от FLOOR(g) до CEILING(g). Здесь предполагается, что номера строк определяются с такого же окна секционирования и упорядочения, чтоб и группировка и упорядочение в функции PERCENTILE_CONT.

Функция PERCENTILE_CONT вычисляется как row0.score + f * (row1.score - row0.score). Это интерполяция значений в двух строках в предположении непрерывного распределения (на основании дробной части g). Следующий код реализует эту логику:

DECLARE @pct AS FLOAT = 0.5;

WITH C1 AS
(
  SELECT testid, score,
    ROW_NUMBER() OVER(PARTITION BY testid ORDER BY score) - 1 AS rownum,
    @pct * (COUNT(*) OVER(PARTITION BY testid) - 1) AS a
  FROM Stats.Scores
),
C2 AS
(
  SELECT testid, score, a-FLOOR(a) AS factor
  FROM C1
  WHERE rownum IN (FLOOR(a), CEILING(a))
)
SELECT testid, MIN(score) + factor * (MAX(score) - MIN(score)) AS percentilecont
FROM C2
GROUP BY testid, factor;

Результат запроса с использованием PERCENTILE_CONT

Функции смещения

В стандарте SQL не определены версии для упорядоченного набора для функций FIRST_VALUE, LAST_VALUE и NTH_VALUE, вернее в нем определены только оконные версии, которые и реализованы в SQL Server 2012. В качестве примера, следующий запрос возвращает с каждым заказом текущий размер заказа, а также значения первого и последнего заказов клиента:

SELECT custid, orderdate, orderid, val,
  FIRST_VALUE(val) OVER(PARTITION BY custid
                        ORDER BY orderdate, orderid) AS val_firstorder,
  LAST_VALUE(val)  OVER(PARTITION BY custid
                        ORDER BY orderdate, orderid
                        ROWS BETWEEN CURRENT ROW
                                 AND UNBOUNDED FOLLOWING) AS val_lastorder
FROM Sales.OrderValues;

Результат запроса с использованием функций смещения FIRST_VALUE и LAST_VALUE

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

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

Вам может прийти в голову использовать функции упорядоченного набора FIRST_VALUE и LAST_VALUE в качестве более гибких версий функций MIN и МАХ соответственно. Они более гибкие в том смысле, что функции MIN и МАХ используют входное значение как упорядочивающий элемент, так и как выражение, которое необходимо возвратить, кроме того они не поддерживают множественные упорядочивающие элементы. Функции FIRST_VALUE и LAST_VALUE позволяют вам вернуть один элемент как выражение значения на основе элемента упорядочения или других элементах. Так почему бы не реализовать поддержку этих функций с групповым агрегированием и упорядочением набора?

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

WITH C AS
(
  SELECT custid, 
    FIRST_VALUE(val) OVER(PARTITION BY custid
                          ORDER BY orderdate, orderid) AS val_firstorder,
    LAST_VALUE(val)  OVER(PARTITION BY custid
                          ORDER BY orderdate, orderid
                          ROWS BETWEEN CURRENT ROW
                                   AND UNBOUNDED FOLLOWING) AS val_lastorder,
    ROW_NUMBER() OVER(PARTITION BY custid ORDER BY (SELECT NULL)) AS rownum
  FROM Sales.OrderValues
)
SELECT custid, val_firstorder, val_lastorder
FROM C
WHERE rownum = 1;

Результат запроса с групповым агрегированием FIRST_VALUE и LAST_VALUE

Но функции FIRST_VALUE и LAST VALUE (оконные версии) доступны только в SQL Server 2012. Вдобавок, функции NTH_VALUE нет ни в одной версии SQL Server, включая SQL Server 2012. Есть несколько способов реализовать эту функциональность в предыдущих версиях SQL Server, используя только функции ROW_NUMBER. Вычисляя номер строки по возрастанию и отфильтровывая только строки с номером 1, получим эквивалент FIRST_YALUE, а фильтруя строки по номеру n — эквивалент NTH_VALUE FROM FIRST. Схожим образом, используя номера строк в убывающем порядке, получим эквивалент LAST_VALUE и NTH_VALUE FROM LAST. Вот пример реализации такой логики, возвращающий первое, последнее и третье значение заказов для каждого клиента с упорядочением по orderdate и orderid:

WITH OrdersRN AS
(
  SELECT custid, val,
    ROW_NUMBER() OVER(PARTITION BY custid
                      ORDER BY orderdate, orderid) AS rna,
    ROW_NUMBER() OVER(PARTITION BY custid
                      ORDER BY orderdate DESC, orderid DESC) AS rnd
  FROM Sales.OrderValues
)
SELECT custid,
  MAX(CASE WHEN rna = 1 THEN val END) AS firstorderval,
  MAX(CASE WHEN rnd = 1 THEN val END) AS lastorderval,
  MAX(CASE WHEN rna = 3 THEN val END) AS thirdorderval
FROM OrdersRN
GROUP BY custid;

Результат запроса с реализацией NTH_VALUE

Есть еще один прием для вычислений первого и последнего значений, основанный на принципе параллельной сортировки. Идея состоит в том, чтобы сгенерировать одну строку, конкатенирующую сначала упорядочивающие элементы (в нашем случае orderdate и orderid), а затем все элементы, которые необходимо возвратить. Затем с помощью агрегирования MIN или МАХ получают строку, содержащую первое или последнее значение. Уловка состоит в том, чтобы при преобразовании исходных значений в строки, отформатировать их таким образом, чтобы сохранить исходный порядок. В нашем случае, это означает преобразование значений orderdate в строку CHAR(8) с использованием стиля 112, который генерирует дату в формате YYYYMMDD (здесь YYYY — год, MM — месяц, a DD — день). Что до значений orderid, которые являются положительными целыми, их нужно преобразовать в формат фиксированного размера с ведущими пробелами или нулями.

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

SELECT custid,
  CONVERT(CHAR(8), orderdate, 112)
    + STR(orderid, 10)
    + STR(val, 14, 2)
    COLLATE Latin1_General_BIN2 AS s
FROM Sales.OrderValues;

Обратите внимание на использование бинарной сортировки, которая помогает немного повысить скорость сравнения. На втором шаге, определяется обобщенное табличное выражение (CTE), основанное на предыдущем запросе. Затем, во внешнем запросе, к строке применяется агрегирование MIN и МАХ, из результата выделяется часть, представляющая значение, и приводится обратно к исходному типу. Вот полное решение и сокращенный результат его работы:

WITH C AS
(
  SELECT custid,
    CONVERT(CHAR(8), orderdate, 112)
      + STR(orderid, 10)
      + STR(val, 14, 2)
      COLLATE Latin1_General_BIN2 AS s
  FROM Sales.OrderValues
)
SELECT custid,
  CAST(SUBSTRING(MIN(s), 19, 14) AS NUMERIC(12, 2)) AS firstorderval,
  CAST(SUBSTRING(MAX(s), 19, 14) AS NUMERIC(12, 2)) AS lastorderval
FROM C
GROUP BY custid;

Заметьте, я использовал тот факт, что целые значения orderid являются неотрицательными. Если вы работаете с числовым упорядочивающим элементом, который поддерживает отрицательные значения, придется добавить логику, которая обеспечит корректную сортировку. Это сложно, но не невозможно. Например, предположим, что значения orderid могут быть отрицательными. Чтобы при сортировке отрицательные числа следовали перед положительными, можно добавить ноль в строке перед отрицательным числом и единицу перед неотрицательным. Далее, чтобы обеспечить, чтобы отрицательные значения сортировались верно (например, чтобы -2 следовало перед -1), можно добавить к значению 2147483648 (модуль минимально возможного отрицательного целого -2147483648) перед его преобразованием в строку символов. Вот как будет выглядеть пример полностью:

WITH C AS
(
  SELECT custid,
    CONVERT(CHAR(8), orderdate, 112)
      + CASE SIGN(orderid) WHEN -1 THEN '0' ELSE '1' END -- отрицательные величины сортируются до неотрицательных
      + STR(CASE SIGN(orderid) 
              WHEN -1 THEN 2147483648 -- к отрицательным величинам добавляется abs(minnegative)
              ELSE 0 
            END + orderid, 10)
      + STR(val, 14, 2)
      COLLATE Latin1_General_BIN2 AS s
  FROM Sales.OrderValues
)
SELECT custid,
  CAST(SUBSTRING(MIN(s), 20, 14) AS NUMERIC(12, 2)) AS firstorderval,
  CAST(SUBSTRING(MAX(s), 20, 14) AS NUMERIC(12, 2)) AS lastorderval
FROM C
GROUP BY custid;

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