Этот запрос transitive_closure занимает 20 секунд!Зачем?

Question

Этот запрос работал отлично и быстро, когда у меня почти 500 строк в таблице Member_Contact_Edges. Но теперь у меня есть около 1000 строк в этой таблице, и этот запрос занимает 20-30 секунд. Я не мог понять, где проблема. Я попробовал Кластерный и Некластерный индекс. Я перепробовал все комбинации индексов, но безуспешно.

 ;WITH transitive_closure(member_a, member_b, distance, path_string) AS

  (SELECT member_a, member_b, 1 AS distance, CAST(member_a as varchar(MAX)) + '.' + CAST(member_b as varchar(MAX)) + '.' AS path_string
          FROM Member_Contact_Edges
          WHERE member_a = @source AND contact_durum=1 -- source

   UNION ALL

   SELECT tc.member_a, e.member_b, tc.distance + 1, CAST(tc.path_string as varchar(MAX)) + CAST(e.member_b as varchar(MAX)) + '.' AS path_string
          FROM Member_Contact_Edges AS e
          JOIN transitive_closure AS tc ON e.member_a = tc.member_b
          WHERE tc.path_string NOT LIKE '%' + CAST(e.member_b as varchar(MAX)) + '.%' AND e.contact_durum=1
   )

   SELECT distance, path_string FROM transitive_closure
          WHERE member_b=@target AND distance <= 3 -- destination
          ORDER BY member_a, member_b, distance;

Вот как я называю хранимую процедуру:

   Exec Contacts_KacinciDerece @source = 30284, @target=24688

Вывод: (Это то, что я ожидал, и этот запрос создает это)

Спасибо.

Answer 1

У вас есть path_string NOT LIKE '%' + CAST(e.member_b as varchar(MAX)) + '.%'

• Невозможно оптимизировать ни LIKE, ни ведущий символ LIKE, не говоря уже о
• В любом случае поле path_string вычисляется

Каждая дополнительная строка в Member_Contact_Edges умножает количество строк, которые необходимо отсканировать (квадрат) без каких-либо преимуществ индексов.

Это O(n^2) как минимум : подозреваю, выше ...

Answer 2

Похоже, оператор NOT LIKE - это ключ к производительности. Мне удалось выполнить запрос за 160 мс, ограничив расстояние.

Но здесь возникает проблема:

Если я не использую оператор NOT LIKE, он выбирает одного и того же человека дважды или более из-за рекурсивного выбора.

Например;

;WITH transitive_closure(member_a, member_b, distance, path_string) AS

(SELECT member_a, member_b, 1 AS distance, CAST(member_a as varchar(MAX)) + '.' + CAST(member_b as varchar(MAX)) + '.' AS path_string
      FROM Member_Contact_Edges
      WHERE member_a = @source AND contact_durum=1 -- source

UNION ALL

SELECT tc.member_a, e.member_b, tc.distance + 1, CAST(tc.path_string as varchar(MAX)) + CAST(e.member_b as varchar(MAX)) + '.' AS path_string
      FROM Member_Contact_Edges AS e
      JOIN transitive_closure AS tc ON e.member_a = tc.member_b
      WHERE tc.member_b <> e.member_b AND tc.distance<4 AND e.contact_durum=1
)

SELECT distance, path_string FROM transitive_closure
      WHERE member_b=@target AND distance < 4 -- destination
      ORDER BY member_a, member_b, distance;