Сортировка иерархий в T-SQL

Работа с базами данных в .NET Framework --- Оконные функции T-SQL --- Сортировка иерархий

Представьте, что вам нужно представить информацию определенной иерархии в отсортированном виде. Нужно разместить родительские элементы перед потомками. Также нужен контроль над порядком размещения элементов, находящихся на одном уровне. Для создания тестовых данных воспользуемся следующим кодом, который создает и наполняет данными таблицу по имени dbo.Employees (не нужно ее путать с существующей таблицей HR.Employees, где хранятся другие данные):

USE TSQL2012;

IF OBJECT_ID('dbo.Employees') IS NOT NULL DROP TABLE dbo.Employees;
GO
CREATE TABLE dbo.Employees
(
  empid   INT         NOT NULL PRIMARY KEY,
  mgrid   INT         NULL     REFERENCES dbo.Employees,
  empname VARCHAR(25) NOT NULL,
  salary  MONEY       NOT NULL,
  CHECK (empid <> mgrid)
);

INSERT INTO dbo.Employees(empid, mgrid, empname, salary) VALUES
  (1,  NULL, 'David'  , $10000.00),
  (2,  1,    'Eitan'  ,  $7000.00),
  (3,  1,    'Ina'    ,  $7500.00),
  (4,  2,    'Seraph' ,  $5000.00),
  (5,  2,    'Jiru'   ,  $5500.00),
  (6,  2,    'Steve'  ,  $4500.00),
  (7,  3,    'Aaron'  ,  $5000.00),
  (8,  5,    'Lilach' ,  $3500.00),
  (9,  7,    'Rita'   ,  $3000.00),
  (10, 5,    'Sean'   ,  $3000.00),
  (11, 7,    'Gabriel',  $3000.00),
  (12, 9,    'Emilia' ,  $2000.00),
  (13, 9,    'Michael',  $2000.00),
  (14, 9,    'Didi'   ,  $1500.00);

CREATE UNIQUE INDEX idx_unc_mgrid_empid ON dbo.Employees(mgrid, empid);

Допустим, что сотрудников надо представить в иерархическом порядке — менеджер перед подчиненными, а также расположить сотрудников в порядке empname. Для решения этой задачи можно использовать два инструмента: функцию ROW_NUMBER и рекурсивное CTE-выражение. Сначала определяем обычное CTE по имени EmpsRN, где вычисляется атрибут по имени n, представляющий номер строки с секционированием по mgrid и упорядочением по empname и empid (empid добавляется по необходимости для детерминизма):

WITH EmpsRN AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY mgrid ORDER BY empname, empid) AS n
  FROM dbo.Employees
)
SELECT * FROM EmpsRN;

Затем определяется рекурсивное CTE по имени EmpsPath, которое итеративно перечисляет сотрудников по одному уровню за раз, начиная с корня (исполнительного директора) и далее по иерархической структуре организации. Можно построить бинарный путь для каждого сотрудника, который начинается с пустого пути в корне и на каждом уровне подчинения конкатенируется путь руководителя с бинарной формой n (номером строки). Заметьте, что для минимизации размера пути нужно столько байт, чтобы охватить максимальное число прямых подчиненных, которые есть у одного менеджера. Например, если число прямых подчиненных не превышает 255, достаточно одного байта, два байта поддерживают до 32 767 прямых подчиненных и т.д. Допустим, в нашем случае нужно два байта. Можно также вычислить уровень сотрудника в дереве (расстояние от корня), назначив корню значение 0 и на каждом уровне добавляя 1. Вот код, который вычисляет как путь сортировки, так и уровень:

WITH EmpsRN AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY mgrid ORDER BY empname, empid) AS n
  FROM dbo.Employees
),
EmpsPath
AS
(
  SELECT empid, empname, salary, 0 AS lvl,
    CAST(0x AS VARBINARY(MAX)) AS sortpath
  FROM dbo.Employees
  WHERE mgrid IS NULL

  UNION ALL

  SELECT C.empid, C.empname, C.salary, P.lvl + 1, P.sortpath + CAST(n AS BINARY(2))
  FROM EmpsPath AS P
    JOIN EmpsRN AS C
      ON C.mgrid = P.empid
)
SELECT *
FROM EmpsPath;

Надо еще обеспечить, чтобы сотрудники отображались в правильном порядке, для чего нужно выполнить упорядочение по sortpath. Можно также организовать отступы, отображающие уровень сотрудника в иерархии, реплицируя строку n раз. Вот код законченного решения:

WITH EmpsRN AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY mgrid ORDER BY empname, empid) AS n
  FROM dbo.Employees
),
EmpsPath
AS
(
  SELECT empid, empname, salary, 0 AS lvl,
    CAST(0x AS VARBINARY(MAX)) AS sortpath
  FROM dbo.Employees
  WHERE mgrid IS NULL

  UNION ALL

  SELECT C.empid, C.empname, C.salary, P.lvl + 1, P.sortpath + CAST(n AS BINARY(2))
  FROM EmpsPath AS P
    JOIN EmpsRN AS C
      ON C.mgrid = P.empid
)
SELECT empid, salary, REPLICATE(' | ', lvl) + empname AS empname
FROM EmpsPath
ORDER BY sortpath;

Посмотрите, как в результате менеджер всегда располагается перед подчиненными, а сотрудники на одном уровне упорядочиваются по empname:

Если на одном уровне требуется другой порядок, допустим по зарплате, просто измените соответствующим образом предложение упорядочения окна в функции ROW_NUMBER:

WITH EmpsRN AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY mgrid ORDER BY salary, empid) AS n
  FROM dbo.Employees
),
EmpsPath
AS
(
  SELECT empid, empname, salary, 0 AS lvl,
    CAST(0x AS VARBINARY(MAX)) AS sortpath
  FROM dbo.Employees
  WHERE mgrid IS NULL

  UNION ALL

  SELECT C.empid, C.empname, C.salary, P.lvl + 1, P.sortpath + CAST(n AS BINARY(2))
  FROM EmpsPath AS P
    JOIN EmpsRN AS C
      ON C.mgrid = P.empid
)
SELECT empid, salary, REPLICATE(' | ', lvl) + empname AS empname
FROM EmpsPath
ORDER BY sortpath;

Вот результат выполнения этого запроса:

Итог

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

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