Zakładając, że wszystkie pary istnieją również w swojej lustrzanej kombinacji (4,5) i (5,4) . Ale poniższe rozwiązania działają równie dobrze bez duplikatów.
Prosty przypadek
Wszystkie połączenia można ustawić w jednej kolejności rosnącej i komplikacje, które dodałem w skrzypce nie są możliwe, możemy zastosować to rozwiązanie bez duplikatów w rCTE:
Zaczynam od uzyskania minimalnego a_sno na grupę, z minimalnym powiązanym b_sno :
SELECT row_number() OVER (ORDER BY a_sno) AS grp
, a_sno, min(b_sno) AS b_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno;
Wymaga to tylko jednego poziomu zapytania, ponieważ funkcję okna można zbudować na agregacie:
Wynik:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Unikam rozgałęzień i zduplikowanych (zwielokrotnionych) wierszy – potencjalnie dużo droższe z długimi łańcuchami. Używam ORDER BY b_sno LIMIT 1 w skorelowanym podzapytaniu, aby to poleciało w rekurencyjnym CTE.
Kluczem do wydajności jest dopasowany indeks, który jest już obecny dostarczony przez ograniczenie PK PRIMARY KEY (a_sno,b_sno) :nie odwrotnie (b_sno, a_sno)
WITH RECURSIVE t AS (
SELECT row_number() OVER (ORDER BY d.a_sno) AS grp
, a_sno, min(b_sno) AS b_sno -- the smallest one
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp
, (SELECT b_sno -- correlated subquery
FROM data
WHERE a_sno = c.sno
AND a_sno < b_sno
ORDER BY b_sno
LIMIT 1)
FROM cte c
WHERE c.sno IS NOT NULL
)
SELECT * FROM cte
WHERE sno IS NOT NULL -- eliminate row with NULL
UNION ALL -- no duplicates
SELECT grp, a_sno FROM t
ORDER BY grp, sno;
Mniej prosty przypadek
Wszystkie węzły można osiągnąć w kolejności rosnącej z jedną lub kilkoma gałęziami od korzenia (najmniejsze sno ).
Tym razem zdobądź wszystkie większe sno i deduplikuj węzły, które mogą być odwiedzane wielokrotnie za pomocą UNION na końcu:
WITH RECURSIVE t AS (
SELECT rank() OVER (ORDER BY d.a_sno) AS grp
, a_sno, b_sno -- get all rows for smallest a_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp, d.b_sno
FROM cte c
JOIN data d ON d.a_sno = c.sno
AND d.a_sno < d.b_sno -- join to all connected rows
)
SELECT grp, sno FROM cte
UNION -- eliminate duplicates
SELECT grp, a_sno FROM t -- add first rows
ORDER BY grp, sno;
W przeciwieństwie do pierwszego rozwiązania, nie otrzymujemy tutaj ostatniego wiersza z wartością NULL (spowodowane przez skorelowane podzapytanie).
Obydwa powinny działać bardzo dobrze - zwłaszcza przy długich łańcuchach / wielu gałęziach. Wynik zgodny z oczekiwaniami:
Skrzypce SQL (z dodanymi wierszami w celu wykazania trudności).
Wykres nieskierowany
Jeśli istnieją lokalne minima, których nie można osiągnąć od korzenia z przechodzeniem w górę, powyższe rozwiązania nie będą działać. Rozważ rozwiązanie Farhęga w tym przypadku.
