Let’s build something Outrageous – Part 12: Finding Things

Let’s build something Outrageous – Part 12: Finding Things

Knowing yourself is the beginning of all wisdom

Aristotle

At some point in your life you will look at the mirror and not recognize the person staring back at you. It’s not only the way you look, but the choices you made and the results of those choices that will seem puzzling. You may decide right then and there to embark in the most important quest of your life. Finding yourself.

Nodes and Relationships don’t get the luxury of having mirrors, but we still need to find them every once in a while. So far all we are able to do is get a node by a label and key or use the id to get a node or relationship. This is great and covers a lot of use cases, but sometimes the primary id is not what we are looking for. We may be looking for all nodes of a type that share a property value equal to something, or greater/less than something else. How can we go about finding the answers to these types of queries in our graph?

Having never done this before, I don’t know. So we’re going to try something here and see what happens. We need to first start with the types of operations we are going to support. For now, this is our list:

We could add case insensitive options to the starts/ends/contains variants, but let’s just keep it simple for now. We’ll figure out how to find Nodes then we can “copy pasta” for the relationships. We’ll create a findNodes method that takes the type of node we are searching for, the name of the property we care about, the operation we are trying to perform, the value we are comparing against and a skip and limit so it can be iterated on. Looks a bit like this:

The easiest things to find are IS_NULL and NOT_IS_NULL since we don’t care what type of property it is, we don’t even have to read the property, we just need to know it exists. If you recall earlier posts we keep track of deleted nodes and deleted properties in Roaring Bitmaps, so we can leverage those to help us answer this operation. For example for IS_NULL, we start with a blank bitmap and we add the deleted properties bitmap to it, then we remove the deleted nodes since those don’t count. Whatever is left are node ids of the properties set to null, so we iterate through them and grab the ones we need. Once we have more than the skip+limit we are done.

Finding properties that are NOT_IS_NULL follows a similar idea. We start with a full bitmap from 0 to max_id, remove the deleted nodes, then remove the deleted properties. Whatever is left has a valid value for that property.

Let’s now move on to the harder ones and try to find a node with a property equal to something. Since we don’t have any indexes we’re going to have to brute force it by looking at every property. We can do so one at a time or in batches. Lets try one at a time first and see where that gets us, we can implement the batching later (or maybe you can, I’d love some help!). We are going to iterate from zero to the max id, return once we get all the nodes we need, skip any deleted nodes and skip any deleted properties.

Before we go much further, we need an Expression class that will evaluate the operation we are trying to perform, the property of the node (a) and the property we are comparing against (b). As much as I love copy and paste, I don’t want to have to do this a billion times, so I’m actually going to use a template for our Evaluate method:

…and more templates for our comparisons:

Look out world, I’m a real C++ programmer now. To use these we need to call them in our loop. For example when looking at an Integer property to compare, we first make sure we are comparing to an integer value, then we pass in “int64_t” for our class to our Evaluate method in Expression and pass in the operation, the property of the node and the value casted from any to int64_t:

If the evaluation of the expression is not true, we ignore it and continue on to the next value. If it does turn out to be true, we break out of the switch statement, add our valid node and increment our current count:

Alright, let’s test this out in our gatling based benchmark by creating one million nodes with a number property between 1 and 10.

Then once that’s done, we’ll go find them. We should have about 10 nodes with each number property, so to make this a hard test, we’re going to return 10 but skip the first 5. That will force the database to go through all 1 million node properties.

We run our test and here are the results:

About 32 requests per second. It takes us about 1 second to get our answer and our max is 3 seconds. That’s not a bad start, but I think we can do better. One of the things we’re doing is calling getIntegerProperty in our loop:

This method is doing a bunch of check work which make sense when being called randomly but not from this internal search method.

I’m going to make “integers” public and trade it for:

Lets recompile, recreate our nodes and try the benchmark again:

Nice. We jumped from 32 to 46 queries per second, dropped our mean to about 2/3 of a second and our max is 2.2 seconds. But something else is bothering me about this query. For every single node I am checking if the value is a of a particular type and I am casting that value to the type we care about. But I should only ever have to do this once per loop, not every single time.

Let’s avoid that extra work. We’ll create a void pointer to hold our value, check and cast into it once and just reinterpret cast in the loop.

We will recompile again and redo our benchmark and what do we get:

Double Nice. We’ve gone from 32 to 57 requests per second, our mean time is down to about half a second and our max… well our max is still hanging out just over 2 seconds but that’s better than the 3 we started with. But there still things I don’t like. For example the way we access the values in the vectors. We have to get the map entry via the property string then fetch the index. Let’s get another point to just the vector and skip finding the property in the map every time:

…and one more time:

Got another 7 requests per second, cut our mean to under half a second and our max is now hovering around 1.7 seconds. But the code looks like a mess. I have two switch statements, pointers, too many ifs. Let’s try again and simplify this by first getting our deleted nodes and properties into a single roaring bitmap. Second by “type” we’ll any_cast the value into the right type. Third, we will get a reference to the vector of values we are going to be checking, and fourth we’ll iterate over this vector. So the code looks like this:

At least it makes more sense. Let’s see what happens when we run our benchmarks:

What? It’s 10 times better. We’re now all the way up to 600 requests per second, our mean is down to 50ms and our max is under 150ms. That is sooooo much better. Ok, so it looks like I have no clue what I’m doing.

UPDATE: I didn’t like having to make the internal pieces of Properties public, so I cleaned it up some by adding reference functions. I was only working on int64_t but I finished the rest and on my latest runs it looks like we got another 20% bump in performance:

If any of you C++ folks like performance puzzles and can help make this faster, I’m all ears. Please join me on Slack.

In the mean time I’m going to investigate a way to vectorize it so we can check multiple node properties in batches instead of doing things one at a time. Until next time!