Commit History - all paths

I have created a graph based on commit history of a source code control tool. The basic graph is

(c:Commit)-[:PARENT]->(p:Commit)

in which every commit except the first references one or more parent commits. The commit is indexed on its URI.
I'm looking to find all nodes between 2 given commits (answering the question: what commits have been added since some starting commit, excluding commits that aren't part of the path).

I have a query that works:

MATCH p = (c:Commit {uri:"latest_commit_uri"})-[:PARENT*0..10]->(o:Commit {uri:"starting_commit_uri"})
return p;

This gives me what I need, but doesn't perform very well if it remove the 0..10. I have tried with 2 commits that are fairly close to one another in the graph and it performs well, but the further apart the nodes get, the worse it gets. I would have expected the performance to be roughly linear since both nodes are indexed and can be found quickly.
For example, the shortest path between one node I have been working with and another node is 33 commits, and there are probably 200-300 nodes in all of the paths put together. But this query never returns.

My question is: is there a better way to do this? It seems to me this would be exactly the kind of query neo4j should excel at. What am I missing?

This is looking for all possible paths that meet the pattern, so it won't stop looking even if it finds a path, it will exhaustively keep searching. If there is only one such possible path, then there are some optimizations we can make.

You could add a LIMIT 1 to the end.

Or you can use a shortestPath() function on the pattern:

MATCH p = shortestPath((c:Commit {uri:"latest_commit_uri"})-[:PARENT*0..10]->(o:Commit {uri:"starting_commit_uri"}))
return p;

This will do a bidirectional bfs expansion until such a path is found.

Also make sure to EXPLAIN the query to make sure index lookups are being used for both nodes.

Andrew -
Thanks for the reply.
What I am really looking for is the subgraph of nodes between 2 nodes. My strategy was to traverse all possible paths between 2 nodes, then gather and dedupe the nodes (hence the question). But I can understand why this might be challenging on a huge graph (I didn't expect the perform to get so bad so quickly for the database in question, though - the paths are relatively simple and limited).
After a bit more research, I've decided to try apoc.path.subgraphAll, which appear to provide what I need. It's going to take me a bit to get it apoc installed to try it out. Do you think this will be an efficient approach?