Проблемы с графиком: подключиться с помощью NOCYCLE до замены в SQL-сервере?

Question

вопрос:

У меня есть следующий (направленный) график:

И эта таблица:

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

GO

И это содержание:

      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              );   

Теперь я могу запросить лучшее соединение из точки x в точку y следующим образом:

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

Теперь я хочу создать неориентированный граф, для которого я могу, например, также получитьпуть от D до A

Я начну с самого простого изменения и просто объявлю обратное направление для 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

Теперь, как и ожидалось, мой запрос выдает исключение:

Превышен бесконечный уровень рекурсии / макс. Уровень рекурсии (100)

Поскольку число возможных соединений теперь бесконечно.

Теперь в Oracle вы делаете то же самое с помощью "connect by before"вместо дерева.И если проблема цикла (бесконечная рекурсия) возможна, вы просто добавляете NOCYCLE к CONNECT BY PRIOR, делая его «CONNECT BY NOCYCLE PRIOR»

Теперь в MS-SQL я исправил это поведение, добавив:

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

к предложению внутреннего соединения, по сути эмулирующему NOCYCLE.

Однако, поскольку LIKE в основном strstr (или хуже strcasestr) и, следовательно, максимально медленнее, чем проверка массива родительских элементов, яочень беспокоюсь о производительности.

В конце концов, это всего лишь пример, и я намерен добавить данные по всей стране.Таким образом, конечный результат потенциально может быть очень медленным.

У кого-нибудь еще есть лучший (= более быстрый) метод замены NOCYCLE в MS SQL?

Или это тот момент, когда я просто имеюнет другого выбора, кроме как перейти на Oracle (для этого с приемлемой скоростью)?

Примечание. Решение для любых временных таблиц (большого объема данных) будет работать медленнее, поскольку временные таблицы будут перенесены на жесткий диск при недостатке ОЗУ (абсолютная уверенность).

То жеподходит для любого решения с использованием функций и табличных функций.

Answer 1

Для повышения производительности выберите сохранение возможных путей между узлами в постоянной таблице

TABLE T_Hops_Path
(
  FromNode,
  ToNode,
  HopCount,
  TotalDistance
)

Если ваша древовидная структура не меняется часто, вы можете написать хранимую процедуру, которая генерирует эту таблицу каждые N часов.