logo标签列表

SQL Server 2008 CTE 计算两点之间的所有路径

sqlsql-server-2008common-table-expressionrecursive-query
3
我尝试了很多使用CTE的方法，但仍然存在问题。 例如，我有一个表格，像这样：（在我的表格中，有6,873,368行）
+--------+----------+---------+
| SOURCE | DEST     | DISTANCE| 
+--------+----------+---------+
|  1     | 1        |  125    | 
|  1     | 2        |  100    | 
|  1     | 3        |  002    | 
|  1     | 4        |  058    | 
|  2     | 1        |  000    | 
|  2     | 2        |  050    | 
|  2     | 3        |  125    | 
|  2     | 4        |  785    | 
|  3     | 1        |  000    | 
|  3     | 2        |  050    | 
|  3     | 3        |  125    | 
|  3     | 4        |  785    | 
+--------+----------+---------+

我想从源1一直走到目的地4，例如对于某些路线，使用CTE可以完美解决问题，但对于我有的行数太多时，时间会非常长（某些解决方案需要超过29分钟）。
我尝试了这个：
;WITH T_Route (CONNECTION_DEST, STEPS, WEIGTH, WAY, RESSOURCE_SRC,RESSOURCE_DEST,RESSOURCE_TYPE) 
AS
   (SELECT DISTINCT C.CONNECTION_SRC 
                   , 0
                   , 0
                   , @SRC
                   , @SRC
                   , @SRC
                   , 1
    FROM #CheminCircuit AS C
    WHERE C.RESSOURCE_SRC = @SRC

    UNION  ALL

    SELECT arrival.CONNECTION_DEST
            , departure.STEPS + 1
            , departure.WEIGTH + arrival.VOL
            , departure.WAY + ',' + arrival.RESSOURCE_DEST 
            , departure.RESSOURCE_DEST
            , arrival.RESSOURCE_DEST
            , arrival.RESSOURCE_TYPE
    FROM #CheminCircuit AS arrival
    INNER JOIN T_Route AS departure ON departure.CONNECTION_DEST = case when departure.STEPS < @STEPS then arrival.CONNECTION_SRC else 0 end -- AND arrival.RESSOURCE_SRC not like '%' + @DEST + '%' AND departure.STEPS < @STEPS
    WHERE departure.WAY NOT LIKE '%,' + arrival.RESSOURCE_DEST + '%' 
    AND (arrival.RESSOURCE_TYPE NOT IN (SELECT T.[Index] FROM Type_Ressource T WHERE T.[Index] IN (1)) OR arrival.RESSOURCE_DEST IN (@SRC,@DEST))
    )
,SHORT (WEIGTH)
AS
    (SELECT WEIGTH
     FROM T_Route
     WHERE  RESSOURCE_DEST  = @DEST)

SELECT *
FROM  T_Route AS T

我期望的输出应该像这样：
+--------+----------+----------------+--------+--------+
| SOURCE | DEST     | DISTANCE       | TIME   |STEPS   |
+--------+----------+----------------+--------+--------+
|  1     | 4        |  1->2->3->4    |  285   | 2      |
|  1     | 4        |  1->4          |  183   | 0      |
|  1     | 4        |  1->3->4       |  185   | 1      |
|  1     | 4        |  1->2->4       |  283   | 1      |
+--------+----------+---------+------+--------+--------+

我只想计算我需要的路线，而不是从所有点到所有点的路线，比如从A到B的路线 :) 如果可能的话，你有什么快速的方法可以建议吗？
我尝试了很多方法，但我不知道如何在达到所需值时停止CTE？
在执行“select * from CTE”语句之前，我已经得到了这个结果：
    +--------+----------+----------------+--------+--------+
    | SOURCE | DEST     | DISTANCE       | TIME   |STEPS   |
    +--------+----------+----------------+--------+--------+
    |  1     | 4        |  1->2->4->3    |  285   | 2      |
    |  1     | 4        |  1->4->1       |  183   | 0      |
    |  1     | 4        |  1->3->4->2->1 |  185   | 1      |
    |  1     | 4        |  1->2->4       |  283   | 1      |
    +--------+----------+---------+------+--------+--------+

但我想在CTE期间停止结果传输到dest：4 谢谢 :)
什么数据库系统，以及哪个版本？SQL只是结构化查询语言 - 许多数据库系统使用的语言 - SQL不是数据库产品...这样的东西通常是供应商特定的 - 所以我们真的需要知道您正在使用什么数据库系统....（请相应更新标签） - marc_s
抱歉我没有说清楚，我正在使用SQL Server 2008。 - Clément Fayard
CTE 计算了整个过程，这种方式花费的时间太长了。我尝试修改 CTE 中的内连接，但没有任何结果。 - Clément Fayard
1
仅浏览查询，最大的性能杀手很可能是您的连接和where子句，特别是“NOT LIKE”不可搜索（以“％”开头），但您可能无法摆脱它。CTE在大型数据集中会受到影响，因此将查询更改为使用带有“while”循环的索引临时表进行递归可能不太美观，但可以加快速度。 - Rhumborl
但我不确定我的内连接语句是否正确或者我的where子句是否正确。 - Clément Fayard
如果我给temps表添加索引，这个公用表表达式（CTE）会更快吗？或者我可以使用while循环来实现这个？ - Clément Fayard
1个回答
1
我喜欢你使用CTE的想法，但是使用NOT LIKE '% + ..非常低效。
我尝试使用二进制数学而不是字符串比较来进行此比较的另一种方法！
基本上，我们将“路径”存储为2^(目的地)之和。
因此，经过目的地ID 1和3的路线将是2^1 + 2^3 = 2 + 8 = 10。
希望您能看出这是一种有效的存储所有已访问目的地（但不按顺序）的方法。
然后，要查看过去是否已经访问了步骤，我们仅比较相关位。
您可以通过2 MOD (2^(当前destinationID + 1))来执行此操作（基本上从存储的路径二进制中删除所有更高的destination，只留下其中ID小于或等于当前destination的destination），并检查此数字是否小于2 ^ (当前destination ID)。 < p > < em > 注意 - 使用单个字段存储二进制方式字段将允许使用整数作为数据类型的ID从0到30（< code > 2 ^ 31-1 是可以存储的最大数字）
因此，使用INT时最大ID为30
如果我们使用BIGINT，则最大ID为62
如果我们使用DECIMAL（38,0），则最大ID为125（尽管它是一个17字节/ 136位字段，但最大ID为10 ^ 38-1）

不确定我是否解释得很好，所以这就是实践...

DECLARE @CheminCircuit TABLE([Source] INT, Dest INT, DISTANCE INT)
INSERT @CheminCircuit
        ( Source, Dest, DISTANCE )
VALUES  ( 1,1,125), (1,2,100),(1,3,2),(1,4,58),(2,1,0),
        (2,2,50),(2,3,125),(2,4,785),(3,1,0),(3,2,50),(3,3,125),(3,4,785)

DECLARE @maxSteps INT
SELECT @maxSteps = COUNT(DISTINCT Dest) 
       FROM @CheminCircuit AS cc WHERE Dest <> @src

; WITH T_Route ([Source], [Dest], Distance, Way, WayBin, STEPS)
AS(
    SELECT Source, 
       Dest, 
       DISTANCE, 
       CAST(CAST(@src AS NVARCHAR(255)) + '->' + CAST(Dest AS NVARCHAR(255)) AS NVARCHAR(255)), 
       POWER(2,Source) + POWER(2,Dest), 
       1
    FROM @CheminCircuit AS cc WHERE Source = @src AND cc.Dest <> cc.Source

    UNION ALL

    SELECT T_Route.Source, cc.Dest, 
           T_Route.Distance + cc.DISTANCE, 
           CAST( T_Route.Way + '->' + CAST(cc.Dest AS NVARCHAR(255)) AS NVARCHAR(255)), 
           T_Route.WayBin + POWER(2,cc.Dest), 
           T_Route.STEPS + 1
    FROM @CheminCircuit AS cc
        JOIN T_Route ON T_Route.Dest = cc.Source
    WHERE T_Route.STEPS < @maxSteps 
        AND T_Route.Dest <> @dst AND cc.Dest <> cc.Source 
        AND (T_Route.WayBin % POWER(2, cc.Dest+1) ) < POWER(2,cc.Dest)
)
SELECT * FROM T_Route WHERE Dest = @dst

这将得到所需的结果（或多或少），保留HTML。
Source  Dest    Distance    Way         WayBin  STEPS
------  ----    --------    --          ------  -----
1       4       58          1->4        18      1
1       4       787         1->3->4     26      2
1       4       837         1->3->2->4  30      3
1       4       885         1->2->4     22      2
1       4       1010        1->2->3->4  30      3

你也会注意到，我正在检查CTE自连接中是否超过了最大步骤数。
嗨 :) 谢谢你的回答，我尝试将它应用到我的表格上，但是出现了错误，可能是由于目标方面的能力问题，我得到了这个错误信息：Erreur de dépassement arithmétique pour le type int, valeur = 281474976710656.000000。在我的表格中，我有6034个源和目标，也许这就是问题所在？ - Clément Fayard
是的，这种方法只适用于源和目标较小的ID值 - 如上所述编辑 - 对于INT，最多为30，对于DECIMAL（38,0），最多为125。您可以通过拥有多个字段并将值分配到它们之间来技术性地覆盖更多的ID - 但这意味着您需要49个字段来存储数据！我怀疑在那些更高的ID上它是否能正常工作，因为精度会丢失。因此，我认为也许应该放弃CTE的想法，转而考虑使用while循环，在其中构建两个表（route和routeItem）-每次迭代从一个表复制到另一个表。 - James S
注意：如果您只想在到达目的地时停止CTE，则可以在CTE的递归部分的WHERE子句中添加“AND departure.RESSOURCE_DEST <> @DEST”。 - James S
不过，仍然有可能使用 VARBINARY（8000）作为存储列使该方法起作用，但需要再多考虑一下。如果我能想出来，就会更新答案！ - James S
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接