Loopy Lattices and Recursion
Previously, we looked at graphs of grids called “lattices”. If you’ve ever driven in Manhattan, Chicago or downtown Austin you’ve experienced these graphs first hand. You were at a Node when you were stopped at a light, and the streets you drove on were the relationships. Our goal then was to get to our destination as quickly as possible given the possible routes, our goal today is to find the number of possible shortest paths between the top-left node and the bottom-right node of these graphs. For example, in a 2x2 lattice, we calculate that there are six paths from Node 1 to Node 9.
As the lattice grows a tiny bit, the number of paths increases significantly. Between the first and last node, a 3x3 lattice has 20 paths, a 6x6 lattice has 924 paths… and the 20x20 lattice has 137,846,528,820 shortest paths! Yet we are able to calculate this number in under a second. This is all thanks to our semantic optimizer, which is a query optimizer that uses the knowledge of user constraints, the knowledge of the data at hand, and the knowledge of mathematics to find an algorithm to answer a query in the fastest way it can. Today we will touch upon just one feature: recursion.
The semantic optimizer understands this concept and our language "Rel" makes it really easy to express. These two combine to make recursion not only possible but an actual joy to use. In many other systems it is hard, painful, or sometimes not even possible without stored procedures.
Before we jump in to the details, lets make sure we all understand something. How do you make sourdough bread? Well, you need some ingredients: flour, water, salt and you have to use a “starter”, or you can use an old piece of sourdough bread. But how do you get an old piece of sourdough bread? Well, you need flour, water, salt and you can use a starter, or you can use an old piece of sourdough bread. Oh! This is recursion. The ingredients for recursion are: a “base case”, which is the starting point, a “recursive rule”, which is self referencing, and a “termination condition”, which tells us when we can stop.
If you want to learn more about recursion in RAI, please take a look at this guide. If you want to learn how we computed over 137 billion paths in 0.41 seconds, keep reading as we dive into the code below.
In the first 10 lines, we create our graph. The size of the lattice is 20, and the total number of nodes is 441. Every node has a relationship to the node to its right except for the ones on the right side. Every node has a relationship to the one below it except for the ones on the bottom side. The “range” function here creates a list of node ids from 1 to the number of nodes one at a time.
def lattice_size = 20
def number_of_nodes = (lattice_size + 1) * (lattice_size + 1)
def node = range[1, number_of_nodes, 1]
def edge(node_number, right_node) = node(node_number) and right_node =
node_number + 1 and modulo[node_number, lattice_size + 1] > 0
def edge(node_number, down_node) = node(node_number) and down_node =
node_number + lattice_size + 1 and down_node <= number_of_nodes
def number_of_paths_of_length(node_number, path_length, path_count) =
node_number=1, path_length=0, path_count=1
def number_of_paths_of_length[node_number, path_length] =
sum[other_node, paths_of_length : paths_of_length =
number_of_paths_of_length[other_node, path_length - 1] and edge(other_node, node_number)]
def output = number_of_paths_of_length[number_of_nodes, 2 * lattice_size]In lines 11 and 12 we define a single “base case”, which just states that Node 1 has a single path of length 0.
In lines 14-16 we express the “recursive case” by stating that the "number of paths of a certain length a node has" is equal to the sum of the number of paths of a certain length minus one of all of that node's neighbors. That’s a mouthful — an example will help here.
Let’s imagine that we are Node 9 in the image below. We can see that our neighbors are Node 6 and Node 8. We can count the lines and see that Node 1 has three shortest paths to Node 6 and three shortest paths to Node 8. Therefore it makes sense that the sum of those two counts (3 + 3 = 6) is the number of shortest paths from Node 1 to Node 9.
Our semantic optimizer can’t stare at a picture to find the answer; instead it will take account of what it knows and find a set of steps to execute until it cannot find any more new information.
We will now dive into the generated query plan and execution. Let’s take a look at how it analyses the number_of_paths_of_length definition. It starts off with:
def :number_of_paths_of_length(node_number#0, path_length#0, path_count#0) =
:_base_case#0(node_number#0, path_length#0, path_count#0) or
reduce[(x#0, y#0, z#0) : :rel_primitive_add(x#0, y#0, z#0),
(other_node#1, x#8, paths_of_length#1) :
:number_of_paths_of_length(other_node#1, x#8, paths_of_length#1) and
:rel_primitive_subtract(path_length#0, 1, x#8) and
:edge(other_node#1, node_number#0),
(noinit#0) : false](path_count#0)The first part up to the “or” is just our base case:
def number_of_paths_of_length(node_number, path_length, path_count) =
node_number=1, path_length=0, path_count=1Don’t try to read anything into the #0 or #1, #8 at the end of variable names. They do not mean anything; they are just there to make the variable names unique in our query plan.
The second part after the “or” is our recursive case:
def number_of_paths_of_length[node_number, path_length] =
sum[other_node, paths_of_length : paths_of_length =
number_of_paths_of_length[other_node, path_length - 1]
and edge(other_node, node_number)]The optimizer will convert that into a slightly different logical query plan. The base case stays the same, but the recursive definition gets a few small modifications:
reduce[(_x#1, _y#1, _z#1) : :rel_primitive_add(_x#1, _y#1, _z#1),
(other_node#1, _t#0) :
:edge(other_node#1, node_number#0) and
reduce[(_x#0, _y#0, _z#0) : :rel_primitive_add(_x#0, _y#0, _z#0),
(x#8, paths_of_length#1) :
:number_of_paths_of_length(other_node#1, x#8, paths_of_length#1)
and :rel_primitive_subtract(path_length#0, 1, x#8),
(_no_init#0) : false](_t#0),
(_no_init#1) : false](path_count#0)The “edge” is moved up and instead of one “reduce”, we now have two. But the second “reduce” comes after the “edge”, so we do not have to traverse the same relationships multiple times per iteration.
From this logical plan, we generate a physical plan which has the actual steps we are going to take to figure out the answer. The optimizer generates three steps. The first two are transient and not part of our output, and the third holds our results.
The first step is going to compute the number of paths to add to any node connected to this one at a specific path length. The inputs are the combination of other_node and path_length, and the answer is _t#0, which is the sum of the number of paths before this path length. This is the part where Node 9 asks Node 3 and Node 8 how many paths they each have from Node 1.
@function @transient
def :_intermediate#0(other_node#1, path_length#0, _t#0) =
reduce[(_x#0, _y#0, _z#0) : :rel_primitive_add(_x#0, _y#0, _z#0),
(x#8, paths_of_length#1) :
:number_of_paths_of_length(other_node#1, x#8, paths_of_length#1) and
:rel_primitive_add(1, x#8, path_length#0),
(_no_init#0) : false](_t#0)The second step says for the combination of node number and path length, the answer is the sum of the previous step “intermediate 0” for any nodes that are connected to us via an edge relation up to this path length. This is the part where Node 9 sums the answers from its neighbors, which gave their answers in the previous step.
@function @transient
def :_intermediate#1(node_number#0, path_length#0, path_count#0) =
reduce[(_x#1, _y#1, _z#1) : :rel_primitive_add(_x#1, _y#1, _z#1),
(other_node#1, _t#0) :
:edge(other_node#1, node_number#0) and
:_intermediate#0(other_node#1, path_length#0, _t#0),
(_no_init#1) : false](path_count#0)The third step says for the combination of node number and path length, the answer is the base case or the previous step “intermediate 1”. At the end here will be Node 9 reporting the answer.
def :number_of_paths_of_length(node_number#0, path_length#0, path_count#0) =
:_base_case#0(node_number#0, path_length#0, path_count#0) or
:_intermediate#1(node_number#0, path_length#0, path_count#0)This will become clearer when we see it in action. We will run the query in a lattice of only nine nodes, but the idea is the same regardless of the lattice size; the larger graph just takes more iterations to finish. Here are the results after the first iteration:
// Naive recursion, iteration 1
// Evaluating `_intermediate#0` resulted in the following:
(1, 1) => (1,)
// Evaluating `_intermediate#1` resulted in the following:
(2, 1) => (1,)
(4, 1) => (1,)
// Evaluating `number_of_paths_of_length` resulted in the following:
(1, 0, 1)
(2, 1, 1)
(4, 1, 1)Intermediate step 0 evaluates nodes 2 and 4, both of which result in 1, which is the number of paths they will pass along to any node connected to them at path length 2.
Intermediate step 1 finds the nodes connected to 2 and 4 at path length 2, which are nodes 3, 5, and 7 and adds the answer from step 0 to them. Since Node 5 is connected by both Node 2 and Node 4, it gets an answer of 2. The third step keeps track of our answers so far.
Let’s keep going:
// Naive recursion, iteration 3
// Evaluating `_intermediate#0` resulted in the following:
(1, 1) => (1,)
(2, 2) => (1,)
(3, 3) => (1,)
(4, 2) => (1,)
(5, 3) => (2,)
(7, 3) => (1,)
// Evaluating `_intermediate#1` resulted in the following:
(2, 1) => (1,)
(3, 2) => (1,)
(4, 1) => (1,)
(5, 2) => (2,)
(6, 3) => (3,)
(7, 2) => (1,)
(8, 3) => (3,)
// Evaluating `number_of_paths_of_length` resulted in the following:
(1, 0, 1)
(2, 1, 1)
(3, 2, 1)
(4, 1, 1)
(5, 2, 2)
(6, 3, 3)
(7, 2, 1)
(8, 3, 3)We continue as before with intermediate step 0 starting with the answers from step 2 in the previous iteration and increasing the path length. Intermediate step 1 finds that nodes 6 and 8 have edges to existing nodes and sums their answers. Node 6 gets 2 from Node 5, and 1 from Node 3. Node 8 gets 2 from Node 5, and 1 from Node 7.
We are almost there:
// Naive recursion, iteration 4
// Evaluating `_intermediate#0` resulted in the following:
(1, 1) => (1,)
(2, 2) => (1,)
(3, 3) => (1,)
(4, 2) => (1,)
(5, 3) => (2,)
(6, 4) => (3,)
(7, 3) => (1,)
(8, 4) => (3,)
// Evaluating `_intermediate#1` resulted in the following:
(2, 1) => (1,)
(3, 2) => (1,)
(4, 1) => (1,)
(5, 2) => (2,)
(6, 3) => (3,)
(7, 2) => (1,)
(8, 3) => (3,)
(9, 4) => (6,)
// Evaluating `number_of_paths_of_length` resulted in the following:
(1, 0, 1)
(2, 1, 1)
(3, 2, 1)
(4, 1, 1)
(5, 2, 2)
(6, 3, 3)
(7, 2, 1)
(8, 3, 3)
(9, 4, 6)In the fourth iteration we finally reach the last node in this lattice: Node 9. It gets a sum of 6 because it gets a count of 3 from Node 6 and a count of 3 from Node 8, which is the correct and final answer. The recursion function runs a few more times, until it finds nothing has changed and therefore it stops. It has reached the fixpoint. Here the computation stops and our query returns the final answer.
You may be wondering, are we recalculating all the answers for all the entries every time for every step or are we only calculating the answers to new entries?
If you take a peek back up you will notice it is called “naive recursion”. In this style of recursion every entry is recalculated. But fear not, we have also implemented “semi-naive recursion”, which understands it won’t find new information from pre-calculated answers and focuses on just the new entries. We’ll save that for another time.
If you would like to dive really deep into the “secret sauce” of the semantic optimizer, please refer to the following papers: Convergence of Datalog over (Pre-) Semirings and Optimizing Recursive Queries with Program Synthesis.
Do you want to learn more about RelationalAI? Watch this video from Martin Bravenboer. He focuses on the semantic optimizer starting at 45:30.