Как отсортировать связанный список в sql?

Я применил связанный список как таблицу базы данных самореференций:

CREATE TABLE LinkedList(
    Id bigint NOT NULL,
    ParentId bigint NULL,
    SomeData nvarchar(50) NOT NULL)

где Id - первичный ключ, а ParentId - это идентификатор предыдущего node в списке. Первый node имеет ParentId = NULL.

Теперь я хочу SELECT из таблицы, сортируя строки в том же порядке, в каком они должны появляться, в качестве узлов в списке.

Например: если таблица содержит строки

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60088   60089     3
60089   38324     2
61039   61497     5
61497   60088     4
109397  109831    7
109831  61039     6

Затем сортировка, используя критерии, должна привести к:

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60089   38324     2
60088   60089     3
61497   60088     4
61039   61497     5
109831  61039     6
109397  109831    7

Вы должны использовать Colour SomeData в качестве элемента управления, поэтому, пожалуйста, не обманывайте команду ORDER с помощью SomeData: -)

Ответ 1

В Oracle:

SELECT Id, ParentId, SomeData
FROM (
  SELECT ll.*, level AS lvl
  FROM LinkedList ll
  START WITH
    ParentID IS NULL
  CONNECT BY
    ParentId = PRIOR Id
)
ORDER BY
  lvl

Р. S. Плохая практика использовать NULL как ParentID, поскольку она не может быть указана индексами. Вместо этого вставьте суррогатный корень с идентификатором 0 или -1 и используйте START WITH ParentID = 0.

Ответ 2

Я нашел решение для SQLServer, но выглядит большим и гораздо менее элегантным, чем

Quassnoi.

WITH SortedList (Id, ParentId, SomeData, Level)
AS
(
  SELECT Id, ParentId, SomeData, 0 as Level
    FROM LinkedList
   WHERE ParentId IS NULL
  UNION ALL
  SELECT ll.Id, ll.ParentId, ll.SomeData, Level+1 as Level
    FROM LinkedList ll
   INNER JOIN SortedList as s
      ON ll.ParentId = s.Id
)

SELECT Id, ParentId, SomeData
  FROM SortedList
 ORDER BY Level

Ответ 3

(edit: d'oh! Пока я отлаживал, вы тоже его нашли!)

В SQL Server:

;WITH cte (Id, ParentId, SomeData, [Level]) AS (
    SELECT Id, ParentId, SomeData, 0
    FROM LinkedList
    WHERE ParentId IS NULL
    UNION ALL
    SELECT ll.Id, ll.ParentId, ll.SomeData, cte.[Level] + 1
    FROM LinkedList ll
    INNER JOIN cte ON ll.ParentID = cte.ID
)
SELECT * FROM cte
ORDER BY [Level]

Ответ 4

Версия PostgreSQL.

Создать таблицу, индексы и данные:

DROP TABLE IF EXISTS LinkedList;

CREATE TABLE LinkedList (
    Id BIGINT NOT NULL,
    ParentId BIGINT NULL,
    SomeData VARCHAR(50)
);

CREATE INDEX LinkedList_Id_idx on LinkedList (Id);
CREATE index LinkedList_ParentId_idx on LinkedList (ParentId);

INSERT INTO LinkedList
    (Id, ParentId, SomeData)
VALUES 
    (24971,   NULL,      0),
    (38324,   24971,     1),
    (60088,   60089,     3),
    (60089,   38324,     2),
    (61039,   61497,     5),
    (61497,   60088,     4),
    (109397,  109831,    7),
    (109831,  61039,     6);

Фактический запрос:

WITH RECURSIVE SortedList AS (
    SELECT
        *,
        0 AS SortKey
    FROM LinkedList
    WHERE ParentId IS NULL
    UNION ALL (
        SELECT
            LinkedList.*,
            SortedList.SortKey + 1 AS SortKey
        FROM LinkedList
        INNER JOIN SortedList
            ON (LinkedList.ParentId = SortedList.Id)
    )
)
SELECT
    *
FROM SortedList
ORDER BY SortKey;

Результаты:

   id   | parentid | somedata | sortkey
--------+----------+----------+---------
  24971 |          | 0        |       0
  38324 |    24971 | 1        |       1
  60089 |    38324 | 2        |       2
  60088 |    60089 | 3        |       3
  61497 |    60088 | 4        |       4
  61039 |    61497 | 5        |       5
 109831 |    61039 | 6        |       6
 109397 |   109831 | 7        |       7

Также были сделаны некоторые тесты:

\set N 10000

DELETE FROM LinkedList;
INSERT INTO LinkedList VALUES (1, NULL, 1);
INSERT INTO LinkedList (
    SELECT
        generate_series AS Id,
        (generate_series - 1) AS ParentId,
        generate_series AS SomeData
    FROM GENERATE_SERIES(2, :N)
);

EXPLAIN ANALYZE
WITH RECURSIVE SortedList AS (
    SELECT
        *,
        0 AS SortKey
    FROM LinkedList
    WHERE ParentId IS NULL
    UNION ALL (
        SELECT
            LinkedList.*,
            SortedList.SortKey + 1 AS SortKey
        FROM LinkedList
        INNER JOIN SortedList
            ON (LinkedList.ParentId = SortedList.Id)
    )
)
SELECT
    *
FROM SortedList
ORDER BY SortKey;

Результаты:

Sort  (cost=6236.12..6300.16 rows=25616 width=138) (actual time=17857.640..17858.207 rows=10000 loops=1)
  Sort Key: sortedlist.sortkey
  Sort Method: quicksort  Memory: 1166kB
  CTE sortedlist
    ->  Recursive Union  (cost=4.40..2007.10 rows=25616 width=138) (actual time=0.032..17844.139 rows=10000 loops=1)
          ->  Bitmap Heap Scan on linkedlist  (cost=4.40..42.78 rows=16 width=138) (actual time=0.031..0.032 rows=1 loops=1)
                Recheck Cond: (parentid IS NULL)
                Heap Blocks: exact=1
                ->  Bitmap Index Scan on linkedlist_parentid_idx  (cost=0.00..4.40 rows=16 width=0) (actual time=0.006..0.006 rows=2 loops=1)
                      Index Cond: (parentid IS NULL)
          ->  Hash Join  (cost=5.20..145.20 rows=2560 width=138) (actual time=0.896..1.780 rows=1 loops=10000)
                Hash Cond: (linkedlist_1.parentid = sortedlist_1.id)
                ->  Seq Scan on linkedlist linkedlist_1  (cost=0.00..96.00 rows=3200 width=134) (actual time=0.002..0.784 rows=10000 loops=10000)
                ->  Hash  (cost=3.20..3.20 rows=160 width=12) (actual time=0.001..0.001 rows=1 loops=10000)
                      Buckets: 1024  Batches: 1  Memory Usage: 9kB
                      ->  WorkTable Scan on sortedlist sortedlist_1  (cost=0.00..3.20 rows=160 width=12) (actual time=0.000..0.001 rows=1 loops=10000)
  ->  CTE Scan on sortedlist  (cost=0.00..512.32 rows=25616 width=138) (actual time=0.034..17851.344 rows=10000 loops=1)
Planning Time: 0.163 ms
Execution Time: 17858.957 ms

Так что этот запрос довольно медленный.