在SQL Server中有效查询有向/无向图边的表

Question

我有一个SQL服务器表,其中每一行代表图形网络中的一个边.FromNodeID和ToNodeID是节点表的外键,架构如下所示:

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;

但这显然涉及组合来自两个查询的结果集,并且看起来效率不高 - 是否有更好的方法在单个查询中编写它？(注意,我不想再将反转的边插入表中 - 我需要能够在运行时将边处理为有向或无向).

谢谢你的建议!

Answer 1

但这显然涉及组合两个查询的结果集，并且似乎不是很有效 - 有没有更好的方法在单个查询中编写它？

这已经足够高效了。

你可以这样做：

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)

正如您所看到的，这些计划本质上是相同的：它们都从相应的索引中获取值并连接结果。

该UNION查询实际上更高效一些，因为它使用 aMerge Join来连接结果，并且合并连接出来的记录自然有序，因此Stream Aggregate不需要排序。