Extremely slow query using CONNECT BY Oracle 10

Question

I have a table challenge containing about 12000 rows. Every point connects to the four points around it, for example 100 connects to 99 101 11 and 189. I tried this with a small scale table and it worked just fine but as I increased the size of the table the query became exponentially slower and now it won't even finish. Here's my query

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

Any advice on how to optimize this query would be greatly appreciated.

Answer 1

So you're finding every path from node 1 to node 2500 in a degree-4 graph (rectangular lattice?) of thousands of nodes. I expect there'll be quite a lot of them. Did the challenge just ask you to count them? Because I think the point was that you have to figure out how many there are by doing math, not brute force computation.

For example, if it's a 50x50 rectangular grid with node 1 and node 2500 in opposite corners, then the minimum path length is 100 steps. A path of 100 steps will have 50 of them horizontal and 50 of them vertical, and they can come in any order. Figure out how many ways you can arrange a string of 50 H's and 50 V's and you might find it's a number that even the mighty Oracle will have a bit of a problem with. (Generating the rows, that is. Doing the calculation just requires large integer arithmetic, which Oracle can probably do quite quickly once you tell it the formula.)

And your query is actually worse than that. It doesn't ask only for minimum-length paths. So it will also return all the paths of length 102 that take a step away from the destination somewhere along the way. And paths of length 104 that take 2 backward steps. And paths of length 2498 that visit almost all of the nodes! Counting those paths is more complicated than counting the short paths because you have to exclude the ones that cross themselves.