sql - 在 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

But this obviously involves combining result sets from two queries and doesn't seem very efficient - is there a better way to write this in a single query?

这已经足够有效了。

你可以这样做:

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查询实际上更有效一点，因为它使用 Merge Join连接结果，合并连接出来的记录自然有序，所以 Stream Aggregate不需要排序。