高效查詢SQL Server中有向/無向圖表邊緣表

我有一個SQL服務器表，其中每一行代表圖形網絡中的一條邊。該FromNodeID和ToNodeID外鍵的一個節點表，並且架構是這樣的：高效查詢SQL Server中有向/無向圖表邊緣表

CREATE TABLE #Edges (
    EdgeID int identity (1,1), 
    FromNodeID int, 
    ToNodeID int 
); 

INSERT INTO #Edges (FromNodeID, ToNodeID) VALUES 
    (1,2), 
    (1,3), 
    (1,4), 
    (2,3), 
    (3,5), 
    (4,5), 
    (5,6);

現在，如果我認爲每一個邊緣被引導（即單程），則可以很容易地制定出所有那些我可以直接從任何節點獲得的節點。我的索引添加到FromNodeID列，然後運行這樣的查詢：

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3

結果：5

但是這將是構建我的表/查詢，如果我想最好的辦法將每個邊緣視爲單向。即從節點3開始，我希望得到的結果：

結果：1，2，5

我能想到的最簡單的方法是將一個額外的索引添加到ToNodeID列，然後運行這樣的查詢：

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 
UNION SELECT FromNodeID FROM #Edges WHERE ToNodeID = 3;

但是這顯然涉及到合併的結果集兩個查詢似乎並沒有非常有效的 - 有沒有更好的方式在單個查詢寫？（請注意，我不想再將反轉的邊緣插入表格中 - 我需要能夠在運行時將邊緣視爲定向或無定向）。

感謝您的任何建議！

來源

2011-01-26 Clare Nia

如果`＃邊緣`從FromNodeID = ToNodeID的情況下得到保護，則您的UNION版本將使用`UNION ALL`而不是`UNION`獲勝。即使允許使用自引用節點，您最好使用`SELECT ... WHERE FromNodeID = 3 AND ToNodeID <> 3 UNION ALL SELECT ... WHERE FromNodeID <> 3 AND ToNodeID = 3 UNION ALL SELECT 3 FROM #Edges WHERE FromNodeID = 3 AND ToNodeID = 3`，但前提是您不需要對節點進行排序（否則它的性能會比您的版本差）。 – 2011-01-27 09:27:53

但是這顯然涉及到從兩個查詢相結合的結果集，而且似乎不是很有效 - 有沒有更好的方式在單個查詢寫？

這很有效。

你可以這樣做：

SELECT CASE 3 WHEN FromNodeId THEN ToNodeId ELSE FromNodeId END 
FROM Edges 
WHERE 3 IN (FromNodeId, ToNodeId)

但這將是基本相同（將UNION這些引擎蓋下索引）。

這裏有一個腳本來測試：

CREATE TABLE #Edges 
     (
     EdgeID INT IDENTITY (1,1) PRIMARY KEY, 
     FromNodeID int NOT NULL, 
     ToNodeID int NOT NULL 
     ) 
CREATE INDEX ix_edges_from ON #Edges (FromNodeID, ToNodeId) 
CREATE INDEX ix_edges_to ON #Edges (ToNodeID, FromNodeId) 
; 
WITH q (rn) AS 
     (
     SELECT 1 
     UNION ALL 
     SELECT rn + 1 
     FROM q 
     WHERE rn < 1000 
     ) 
INSERT 
INTO #Edges (FromNodeId, ToNodeId) 
SELECT q1.rn, q2.rn 
FROM q q1 
CROSS JOIN 
     q q2 
WHERE (q1.rn + q2.rn) % 37 = 0 
OPTION (MAXRECURSION 0)

對於UNION：

SELECT ToNodeId 
FROM #Edges 
WHERE FromNodeId = 3 
UNION 
SELECT FromNodeId 
FROM #Edges 
WHERE ToNodeId = 3 


    |--Stream Aggregate(GROUP BY:([Union1006])) 
     |--Merge Join(Concatenation) 
      |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD) 
      |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

對於IN：

|--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN (3)=[tempdb].[dbo].[#Edges].[FromNodeID] THEN [tempdb].[dbo].[#Edges].[ToNodeID] ELSE [tempdb].[dbo].[#Edges].[FromNodeID] END)) 
     |--Sort(DISTINCT ORDER BY:([tempdb].[dbo].[#Edges].[EdgeID] ASC)) 
      |--Concatenation 
       |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD) 
       |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

正如你所看到的，計劃在本質上是相同的：它們都從相應的索引中取值並連接重新sults。

的UNION查詢其實一點更有效，因爲它使用一個Merge Join來連接的結果，並記錄出來的合併連接天然有序的，所以Stream Aggregate不需要排序。

來源

2011-01-26 21:08:35 Quassnoi

謝謝你的明確答案和支持信息！ – 2011-01-26 22:21:07

我能想到的有三個選項：只在表格中執行，只在查詢中執行，或者創建一個view。對於表，創建強制對稱閉包的triggers（例如，當插入（a，b）時，也插入（b，a）;將（a，b）更新爲（c，d）時，刪除舊的對稱保留b，a）對，然後插入（d，c））。請注意，這可能無法正常工作，因爲某些RDBMS（我不確定SQL Server是否是一個）不允許插入/更新觸發器觸發的表。

在查詢，

SELECT CASE FromNodeID WHEN 3 THEN ToNodeId ELSE FromNodeId END 
    FROM #Edges 
    WHERE FromNodeID=3 OR ToNodeID=3

對於視圖中創建一個是原始表的對稱閉。我認爲你仍然需要使用UNION，但它可以簡化查詢編寫。

CREATE VIEW undirected_edges (FirstEdgeID,SecondEdgeId) 
    AS (SELECT FromNodeID, ToNodeID FROM #Edges) 
    UNION DISTINCT 
    (SELECT ToNodeID, FromNodeID FROM #Edges)

來源

2011-01-26 21:11:04 outis

你一定要處理直接從SQL Server的圖形？如果您真的關心性能，則應該使用專門用於表示和處理圖形的數據結構之一。如果我使用通用數據庫後端來查看圖表，我對圖表所做的大部分工作（以及我已經完成的工作）都是不可行的。

我使用過的最有效的表示法之一是我編寫的一本編譯器書籍的附錄中描述的：Keith Cooper和Linda Torczon撰寫的編譯器。

來源

2011-01-26 21:18:40

高效查詢SQL Server中有向/無向圖表邊緣表

回答

相關問題