Problemas de gráficos: ¿se conecta por NOCYCLE antes de la sustitución en el servidor SQL?

Question

pregunta:

tengo el siguiente gráfico (dirigida):

Y esta tabla:

CREATE TABLE [dbo].[T_Hops](
    [UID] [uniqueidentifier] NULL, 
    [From] [nvarchar](1000) NULL, 
    [To] [nvarchar](1000) NULL, 
    [Distance] [decimal](18, 5) NULL 
) ON [PRIMARY] 

GO 

Y este contenido:

 INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'E'    ,10.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'E'    ,'D'    ,20.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'B'    ,5.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'B'    ,'C'    ,10.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'C'    ,'D'    ,5.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'F'    ,2.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'F'    ,'G'    ,6.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'G'    ,'H'    ,3.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'H'    ,'D'    ,1.00000    ); 

Ahora puede consultar el mejor conexión del punto x al punto y así:

WITH AllRoutes 
(
    [UID] 
    ,[FROM] 
    ,[To] 
    ,[Distance] 
    ,[Path] 
    ,[Hops] 
) 
AS 
(
    SELECT 
     [UID] 
     ,[FROM] 
     ,[To] 
     ,[Distance] 
     ,CAST(([dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path] 
     ,1 AS [Hops] 
     FROM [dbo].[T_Hops] 
     WHERE [FROM] = 'A' 

    UNION ALL 


    SELECT 
     [dbo].[T_Hops].[UID] 
     --,[dbo].[T_Hops].[FROM] 
     ,Parent.[FROM] 
     ,[dbo].[T_Hops].[To] 
     ,CAST((Parent.[Distance] + [dbo].[T_Hops].[Distance]) AS [decimal](18, 5)) AS distance 
     ,CAST((Parent.[Path] + '/' + [dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path] 
     ,(Parent.[Hops] + 1) AS [Hops] 
    FROM [dbo].[T_Hops] 

    INNER JOIN AllRoutes AS Parent 
      ON Parent.[To] = [dbo].[T_Hops].[FROM] 

) 

SELECT TOP 100 PERCENT * FROM AllRoutes 


/* 
WHERE [FROM] = 'A' 
AND [To] = 'D' 
AND CHARINDEX('F', [Path]) != 0 -- via F 
ORDER BY Hops, Distance ASC 
*/ 

GO 

Ahora quiero crear un grafo no dirigido, para que pueda, por ejemplo, también obtener el camino de D a A

comienzo con un cambio más simple, y solo anuncio la dirección inversa para HD.

INSERT INTO [dbo].[T_Hops] 
      ([UID] 
      ,[From] 
      ,[To] 
      ,[Distance]) 
    VALUES 
      (newid() --<UID, uniqueidentifier,> 
      ,'D' --<From, nvarchar(1000),> 
      ,'H' --<To, nvarchar(1000),> 
      ,1 --<Distance, decimal(18,5),> 
      ) 
GO 

Ahora, como se esperaba, mi consulta se produce una excepción:

nivel de recursividad/máx recursividad infinita (100) superó

Debido a que el número de conexiones posibles es infinita ahora.

Ahora en Oracle usted hace lo mismo con "connect by prior" en lugar de un árbol. Y si un problema ciclo (bucle) es posible, que acaba de añadir NOCYCLE a CONECTAR POR PREVIO, por lo que es "CONNECT BY NOCYCLE previa"

Ahora en MS-SQL, que fija que el comportamiento añadiendo:

AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%' 

a la cláusula de unión interna, esencialmente emulando NOCYCLE.

Sin embargo, como LIKE es básicamente strstr (o peor strcasestr), y por lo tanto máximo más lento que el control de un conjunto de elementos primarios, Estoy muy preocupado por el rendimiento.

Después de todo, esto es solo un ejemplo, y tengo la intención de agregar básicamente los datos para todo un país. Por lo tanto, el resultado final podría ser extremadamente lento.

¿Alguien más tiene un método mejor (= más rápido) de cómo reemplazar NOCYCLE en MS SQL?

¿O es este el punto en el que simplemente no tengo otra opción que cambiar a Oracle (para hacer esto a una velocidad aceptable)?

Nota: Cualquier tablas temporales (gran cantidad de datos) solución será más lenta, porque las tablas temporales se pueden intercambiar en el disco duro cuando no hay suficiente memoria RAM (certeza absoluta).

Igual va para cualquier solución que use funciones y funciones con valores de tabla.

Answer 1

Para mejorar selectos posibles caminos almacenar el rendimiento entre nodos en una tabla permanente

TABLE T_Hops_Path 
(
    FromNode, 
    ToNode, 
    HopCount, 
    TotalDistance 
) 

Si su estructura de árbol no cambia la frecuencia con que se puede escribir un procedimiento almacenado que genera esta tabla cada N horas.