Чрезвычайно медленный запрос с использованием CONNECT BY Oracle 10

Question

У меня есть таблица challenge, содержащая около 12000 строк. Каждая точка соединяется с четырьмя точками вокруг него, например 100 подключается к 99 101 11 и 189. Я пробовал это с помощью таблицы с небольшим масштабом, и он работал нормально, но по мере увеличения размера таблицы запрос стал экспоненциально медленнее и теперь он даже не закончит. Вот мой запрос

SELECT level, origin, destination 
FROM challenge 
WHERE destination = 2500 
START WITH origin = 1 
CONNECT BY NOCYCLE PRIOR destination = origin; 

Любые советы по оптимизации этого запроса будут очень признательны.

Answer 1

Итак, вы находите каждый путь от узла 1 до узла 2500 в графе степени 4 (прямоугольная решетка?) Тысяч узлов. Я ожидаю, что их будет довольно много. Задача просто попросила вас посчитать их? Потому что я думаю, что дело в том, что вам нужно выяснить, сколько есть, делая математику, а не вычисление грубой силы.

Например, если это прямоугольная сетка 50x50 с узлом 1 и узлом 2500 в противоположных углах, то минимальная длина пути составляет 100 шагов. Путь из 100 шагов будет иметь 50 из них по горизонтали и 50 из них по вертикали, и они могут быть в любом порядке. Объясните, сколько способов вы можете упорядочить строку из 50 H и 50 V, и вы можете обнаружить, что это число, с которым даже могучий Oracle будет иметь проблемы. (Генерация строк, то есть. Выполнение вычисления просто требует большой целочисленной арифметики, которую Oracle, возможно, сделает довольно быстро, как только вы сообщите ей формулу.)

И ваш запрос на самом деле хуже этого. Он не запрашивает только пути минимальной длины. Таким образом, он также вернет все пути длины 102, которые удалятся от места назначения где-то на этом пути. И пути длиной 104, которые занимают 2 обратных шага. И пути длиной 2498, которые посещают почти все узлы! Подсчет этих путей сложнее, чем подсчет коротких путей, потому что вы должны исключать те, которые пересекают себя.