Refactoring and Evolving a Model

This model answers the first question just fine. But suppose we had to answer a new question?

What must Neo4j traverse to find this answer?

This is a painful one. To find flight AY189, we need to traverse every relationship in the graph, because it is impossible to anchor on relationships. What can we do to make flight data available as an anchor?

This is a perfect use case for adding intermediate nodes. Adding Flight nodes allows us to anchor on flight data, dramatically reducing traversal.

But we are still not satisfied with the way we are handling Q1. Airlines are required to publish flight plans 12 months or more in advance. How much work must Neo4j do to answer Q1?

Again, the answer is painful. Neo4j must check every flight leaving Malmo, then consult the flight data to see which ones leave on the appropriate day. That’s even before we check to see which of those flights land in the desired place! How can we elevate the flight date in order to reduce the amount of wasted hops?

Again, intermediate nodes come to the rescue. AirportDay nodes reduce the density of Airport nodes, as there are many fewer days in the graph than there are flights. We still need to check every AirportDay to find the right date, but the scope of wasted traversal is lessened.

Whenever we execute a model change, we also need to check that our older queries are not disrupted. What about Q2?

As long as we continue to be able to anchor on Flight, Q2 is unaffected. This refactor causes no problems.

But thinking more on Q1. How might we arrange things to reduce wasted traversal even further? In other words, how might we elevate flight date even higher on the hierarchy of accessibility?

There are only two ways to do this:

We will refactor to make date a relationship type.

Date as the relationship type hardly changes the model at all, with drastic performance improvements. Now, we can traverse only to the relevant AirportDay. Again, Q2 is unaffected.

This is one of the two solutions we had. The other was to anchor on AirportDay. How would the model need to change to make that possible?

We could eliminate the Airport nodes entirely, and store airport data on the AirportDay nodes. This shrinks the graph by removing a modest number of Airport nodes, and a large number of Date-typed HAS_DAY relationships. This also performs 2 fewer hops per traversal—​a tiny improvement, but one that could add up at scale. We would need to test this benefit more rigorously in production.

The downside to this model is that it is far less intuitive to a human looking at it. As mentioned earlier, refactoring is rarely pure positive; the gains you make in one area often involve sacrifices in others.

So we have a model that seems to work well for Q1. But we have been making one dangerous assumption: that there is a direct flight available. What will Neo4j need to do in order to find an itinerary with 2, 3, 4, or more legs?

This is an expensive problem for this model. Neo4j will traverse every flight leaving that day, and look at destinations. But in the non-direct case, none of the destinations is the correct one. So Neo4j will need to check all the HAS_FLIGHT relationships on those destinations, and see if the second-order destinations include the desired one. If that is not the case, repeat until you find the desired destination. The size of the traversed graph increases exponentially as more and more layovers are added. What can we do to reduce this?

Once again, intermediate nodes come to the rescue! In this case, we are doing two things, further subdividing flights based on destination, but more importantly, we are elevating flight destinations from a 3-hop downstream object to a 1-hop downstream object.

How does the non-direct traversal work in this case?

First, Neo4j will check every Destination served by that AirportDay. If the target destination is not there, follow ONE Flight chain to the Airport Day of the destination, then check the served Destinations of that AirportDay. The scope of the graph still grows, but it grows at a rate proportional to the number of Destinations served by an airport, not the number of Flights. And airports tend to have multiple flights per destination, leaving at different times of day.

Once an itinerary leading to the target destination is found, Neo4j can branch out and traverse all the flights connecting those AirportDays.

As always, we must consider: how does this refactor affect Q2?

Once again, the answer is that it does not—​we can still anchor on Flight, so Q2 is not disrupted.

Note that this model could never have been produced by simply following our “build initial model” paradigm. AirportDay and Destination nodes are completely opaque relative to the questions we asked. We are OK with that, because, as you will learn that when you implement the model in Cypher, refactoring a graph is relatively inexpensive. Moreover, getting a rough first model quickly reduces the total time we would need to reach this more refined version.