Pytanie Jak sortować połączoną listę w sql?


Mam zaimplementowaną listę połączoną jako tabelę bazy danych samoreferencyjnych:

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

gdzie Id jest kluczem podstawowym, a ParentId jest identyfikatorem poprzedniego węzła na liście. Pierwszy węzeł ma ParentId = NULL.

Teraz chcę WYBRAĆ z tabeli, sortując wiersze w takiej kolejności, w jakiej powinny się pojawić, jako węzły na liście.

Np .: jeśli tabela zawiera wiersze

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

Następnie posortowanie go za pomocą kryteriów powinno spowodować:

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

Powinieneś użyć SomeData colum jako kontrola, więc proszę, nie oszukiwajcie tego ZAMÓW według SomeData :-)


14
2018-02-05 12:40


pochodzenie


Twój nie oszukuje komentarza: byłby lepszy, gdybyś wybrał przykładowe dane, które nie uzyskałyby poprawnego wyniku, gdy sam sortowałeś. W ten sposób "oszustwo" nie byłoby możliwe. - AnthonyWJones
Hmm ... Nie sądzę, że zrozumiałeś moją intencję podczas dodawania tej kolumny. Po prostu chciałem ułatwić życie ludziom, którzy mogą znaleźć odpowiedź. Nazwij to "narzędziem do testowania". - Nuno G


Odpowiedzi:


W 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

P. S. Jest to zła praktyka NULL tak jak ParentID, ponieważ nie można go przeszukiwać według indeksów. Wstaw zastępczy root o identyfikatorze 0 lub -1 zamiast tego i użyj START WITH ParentID = 0.


9
2018-02-05 12:43



To bardzo dobra odpowiedź. Jak zrobić to samo w SQLServer 2005? - Nuno G
+1, ale nie dla komentarza anti-NULL: użycie 0 lub -1 wyklucza posiadanie obcego klucza w celu wymuszenia integralności. - Tony Andrews
Zawsze możesz zachować zastępczy root i przechowywać go w bazie danych. Pełne skanowanie pierwszego wpisu będzie zbyt wolne, jeśli tabela zawiera wiele rekordów. - Quassnoi
@Quassnoi: Nie trzeba tworzyć procedury składowanej dla wersji SQL Server 2005 i wyższej. Obsługują wspólne wyrażenia tabelowe (CTE), które umożliwiają wykonanie tego samego, co CONNECT BY. - Tomalak
Tak, CTE są sposobem na to zrobić w SQL Server. Zobacz moje rozwiązanie poniżej. - Nuno G


Znalazłem rozwiązanie dla SQLServer, ale wygląda na duże i znacznie mniej eleganckie niż 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

10
2018-02-05 13:05



Właściwie nazwa SortedList jest nieco myląca - to nie jest właściwie posortowane - po prostu rekursywna ... musisz ORDER BY the final SELECT (zobacz moją odpowiedź) - Marc Gravell♦
W porządku, dodałem kolumnę Level i ORDER BY w ostatnim SELECT. - Nuno G
Czy podobne podejście można zastosować w przypadku SQLite? - Michael
Jest jeden problem z używaniem CTE, który jest limitem rekursji. Domyślnie limit ten wynosi 100, ale można go zwiększyć do 32767, dodając "opcję (maxrecursion 32767)" na końcu zapytania - Boyd


(edytuj: d'oh! Podczas debugowania też to znalazłeś!)

W 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]

5
2018-02-05 13:10



ah - błędne odczytanie pytania; Myślałem, że chcesz zamówić go przez SomeData; jeśli chcesz, aby była połączona z kolejnością, to [Poziom] jest drogą do zrobienia - Marc Gravell♦
Dlaczego półkolonia na starcie? - Greg
@Greg, ponieważ CTE są wybredne; prawie zawsze kończy się to wymaganiem prowadzenia; więc równie dobrze mogę to dodać. Dodaj byle co powyżej przykładu i zaczyna bić - Marc Gravell♦