Commit History - all paths

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


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?