We have a Neo4J database representing an evolutionary process with about 100K nodes and 200K relations. Nodes are individuals in generations, and edges represent parent-child relationships. The primary goal is to be able to take one or nodes of interest in the final generation, and explore their evolutionary history (roughly, "how did we get here?").

The "obvious" first query to find all their ancestors doesn't work because there are just too many possible ancestors and paths through that space:

```
match (a)-[:PARENT_OF*]->(c {is_interesting: true}) 
return distinct a;

```

So we've pre-processed the data so that some edges are marked as "special" such that *almost* every node has at most one "special" parent edge, although occasionally both parent edges are marked as "special". My hope, then, was that this query would (efficiently) generate the (nearly) unique path along "special" edges:

```
match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

```

This, however, is still unworkably slow. 

This is frustrating because "as a human", the logic is simple: Start from the small number of "interesting" nodes (often 1, never more than a few dozen), and chase back along the almost always unique "special" edges. Assuming a very low number of nodes with two "special" parents, this should be something like O(N) where N is the number of generations back in time. 

In Neo4J, however, going back 25 steps from a unique "interesting" node where *every* step is unique, however, takes 30 seconds, and once there's a *single* bifurcation (where both parents are "special") it gets worse much faster as a function of steps. 28 steps (which gets us to the first bifurcation) takes 2 minutes, 30 (where there's still only the one bifurcation) takes 6 minutes, and I haven't even thought to try the full 100 steps to the beginning of the simulation.

Some similar work last year seemed to perform better, but we used a variety of edge labels (e.g., `(a)-[:SPECIAL_PARENT_OF*]->(c)` as well as `(a)-[:PARENT_OF*]->(c)`) instead of using data fields on the edges. Is querying on relationship field values just not a good idea? We have quite a few different values attached to a relationship in this model (some boolean, some numeric) and we were hoping/assuming we could use those to efficiently limit searches, but maybe that wasn't really the case.

Suggestions for how to tune our model or queries would be greatly appreciated.

**Update** I should have mentioned, this is all with Neo4J 2.1.7. I'm going to give 2.2 a try as per Brian Underwood's suggestion and will report back.