Max De Marzi

Valentine’s Day was earlier this week, maybe you took your significant other to dinner, sent flowers or candy to your crush, even bought a card for that special someone. I bet however you didn’t profess your love to your favorite software library. I did. I love Roaring Bitmaps. Like Mariah Carey, I can’t live without it, so I won’t. I added Roaring Bitmaps to RageDB.

Of course we’re already using Roaring Bitmaps to keep track of deleted nodes, deleted relationships and null properties for both. What I mean is that I made it so we can use it from our Lua “query” language. Let me show you. I wrapped it in a class called Roar so I could tweak it a bit:

 class Roar {

  protected:
    Roaring64Map map;

  public:
    Roar();
    void addIds(std::vector<uint64_t> ids);
    void addNodeIds(std::vector<Link> links);
    void addRelationshipIds(std::vector<Link> links);
    std::vector<uint64_t> getIds();
    sol::as_table_t<std::vector<uint64_t>> getIdsLua();

I have a few extra methods that return Lua tables which will hook into a new Sol3 usertype. For example I added getNodeHalfLinks and getRelationshipHalfLinks which will both return a vector of Links with either the node ids or relationship ids filled out and zeros for the other side. Why is this useful? Well I don’t know yet, but I gotta feeling.

        lua.new_usertype<Roar>("Roar", sol::constructors<Roar()>(),
          "addIds", &Roar::addIds,
          "addNodeIds", &Roar::addNodeIds,
          "addRelationshipIds", &Roar::addRelationshipIds,
          "getIds", &Roar::getIds,
          "getNodeHalfLinks", &Roar::getNodeHalfLinksLua,
          "getRelationshipHalfLinks", &Roar::getRelationshipHalfLinksLua,

Regardless, Roaring Bitmaps are amazing for graph traversals because they can help you keep track of unique node or relationship ids. They can help you build temporary bitmap indexes, they can do all sorts of fun optimization tricks when you take two or more of them and calculate their union, difference or intersection.

We’re going to go back to the LDBC Social Network Benchmarks and going to try a harder challenge. We’re going to write the first complex query. Take a look at the description below:

The relevance section of the image above is referring to how smart the query optimizer should be in order to execute this query fast. Look at me, I am the query optimizer now. There are a bunch of ways to write this query, let’s try a few. We can start off by getting the node ids of every single Person in our graph with a certain name and adding these ids to a Roaring Bitmap. Then we get the starting person and the people they know one hop away. We need to look for people with know with the certain name up to 3 levels away so we’ll create 3 more bitmaps to hold these node ids as we find them. Let’s go ahead and add the people we found at the first hop to “seen1”:

local node_ids = Roar.new()
local targets = FindNodeIds("Person", "firstName", Operation.EQ, "Chen", 0, 999999)
node_ids:addIds(targets)

local node_id = NodeGetId("Person", "1129")
local people = NodeGetLinksByIdForType(node_id, "KNOWS")
local seen1 = Roar.new()
local seen2 = Roar.new()
local seen3 = Roar.new()
seen1:addNodeIds(people)

Now we’ll do one of those fancy Bulk Traversals we added last time and take all the people we know at level one and get their KNOWS relationship Links. For each of these people we’ll add just the Node Ids of the links to a second roaring bitmap “seen2”, get rid of any we have already seen in “seen1” and of course get rid of our starting person node id.

local people2 = LinksGetLinksForType(people, "KNOWS")
for i,links in pairs(people2) do 
  seen2:addNodeIds(links)
end  
seen2:inplace_difference(seen1)
seen2:remove(node_id)

Now we can be smart and take an optimization. If we take the intersection of “seen2” and our target “node_ids” and there are 20 or more left, then we’re done so don’t even bother expanding out to the 3rd KNOWS relationship. If we didn’t find the 20 friends with the name, then we have to go one more time. I haven’t gotten around to coding NodesGetNeighborsIdsForType yet, so we’ll grab the half links with the nodes ids filled out from the seen bitmap and traverse that way. We then remove anyone we saw already in seen2 and seen1, as well as our starting node.

if(seen2:intersection(node_ids):cardinality() < 20) then
    local people3 = LinksGetLinksForType(seen2:getNodeHalfLinks(), "KNOWS") 
    for i,links2 in pairs(people3) do 
        seen3:addNodeIds(links2) 
    end
    seen3:inplace_difference(seen2)
    seen3:inplace_difference(seen1)
    seen3:remove(node_id)
end

At this point we have all our 3 levels traversed out, now we need to just intersect them with the people who have the name we are looking for and sort them.

seen1:inplace_intersection(node_ids)
seen2:inplace_intersection(node_ids)
seen3:inplace_intersection(node_ids)

We have 3 things to sort on according to the spec. The distance to our starting node, the last name of the person we found and their id if the distance and last names are the same. We’ll grab the 3 bitmaps in an array and process each one. We don’t need to grab the full blown Node objects, so instead we’ll bulk grab the “lastName” and “id” properties and fill in the distance from person value as we go along.

local known = {}
local found = {seen1, seen2, seen3}

for i = 1, #found do
  if (found[i]:cardinality() > 0) then
    local lastNames = NodesGetProperty(found[i]:getIds(), "lastName")
    local ids = NodesGetProperty(found[i]:getIds(), "id")

    for j = 1, found[i]:cardinality() do
      otherPerson = {
        ["otherPerson.id"] = ids[j],
        ["otherPerson.lastName"] = lastNames[j],
        ["distanceFromPerson"] = i
      }
      table.insert(known, otherPerson)
    end
  end
end

We gathered the values for the sort, but haven’t sorted yet. So let’s make a generic function to handle this and we’ll also grab the top 20 at the end.

function sort_on_values(t,...)
  local a = {...}
  table.sort(t, function (u,v)
    for i = 1, #a do
      if u[a[i]] > v[a[i]] then return false end
      if u[a[i]] < v[a[i]] then return true end
    end
  end)
end

sort_on_values(known,"distanceFromPerson","otherPerson.lastName", "otherPerson.id")
local smaller = table.move(known, 1, 20, 1, {})

Getting close to the end here. For these people we need to get where they studied and where they worked :

local results = {}
for j, person in pairs(smaller) do
    local studied_list = {}
    local worked_list = {} 
    local studied = NodeGetRelationshipsForDirectionForType("Person", person["otherPerson.id"], Direction.OUT, "STUDY_AT" )
    local worked = NodeGetRelationshipsForDirectionForType("Person", person["otherPerson.id"], Direction.OUT, "WORK_AT" )
 
    for s = 1, #studied do
        table.insert(studied_list, NodeGetPropertyById(studied[s]:getEndingNodeId(), "name"))
        table.insert(studied_list, RelationshipGetProperty(studied[s]:getId(), "classYear"))
    end
    
   for s = 1, #worked do
          table.insert(worked_list, NodeGetPropertyById(worked[s]:getEndingNodeId(), "name"))
          table.insert(worked_list, RelationshipGetProperty(worked[s]:getId(), "workFrom"))
    end

Finally we need to fill out the rest of the node properties and format the date to the LDBC spec:

    local properties = NodeGetProperties("Person", person["otherPerson.id"] )
      otherPerson = {
        ["otherPerson.id"] = person["otherPerson.id"],
        ["otherPerson.lastName"] = properties["lastName"],
        ["distanceFromPerson"] = person["distanceFromPerson"],
        ["otherPerson.birthday"] = properties["birthday"],
        ["otherPerson.creationDate"] = date(properties["creationDate"]):fmt("${iso}Z"),
        ["otherPerson.gender"] = properties["gender"],
        ["otherPerson.browserUsed"] = properties["browserUsed"],
        ["otherPerson.locationIP"] = properties["locationIP"],
        ["otherPerson.email"] = properties["email"],
        ["otherPerson.speaks"] = properties["speaks"],
        ["universities"] = table.concat(studied_list, ", "),
        ["companies"] = table.concat(worked_list, ", ")
      }
      table.insert(results, otherPerson)
  end

results

Ok, so that’s a bit of a monster coming in at about 100 lines. Half of it is formatting, sorting and random nonsense so it wasn’t really that bad. So what do we get for our efforts on the LDBC Social Network Size 10 dataset for parameters 1129 and “Chen” for the name?

9ms. Yup. Nine. That’s pretty nice. The trick here is there are so many people named “Chen” we didn’t have to traverse 3 hops out, we found enough after 2, so we had a pretty fast query. Alright what about doing it a different way? What if instead of finding everyone with the name first, we just started traversing and checked as we went along?

We will start with the node we want to traverse from and get everyone they know.

local node_id = NodeGetId("Person", "1129")
local people = NodeGetLinksByIdForType(node_id, "KNOWS")
local seen1 = Roar.new()

Then we will check to see which of those people are named “Chen”. If get 20 or more we are done, if not we keep going.

seen1:addNodeIds(people)
local named1 = FilterNodes(seen1:getIds(), "Person", "firstName", Operation.EQ, "Chen")
local named2 = {}
local named3 = {}

if(#named1 < 20) then 

We’re basically going to do the same thing, but instead of staring from one person we’ll use our Bulk methods and traverse from all the people we know and then check to see if we have more than 20 folks named “Chen”. If not, well you get the picture. The full query is here for the curious. It also comes in at about 100 lines of code

  local seen2 = Roar.new()

  local people2 = LinksGetLinksForType(people, "KNOWS")
  for i,links in pairs(people2) do 
    seen2:addNodeIds(links)
  end  
  seen2:inplace_difference(seen1)
  seen2:remove(node_id)

  named2 = FilterNodes(seen2:getIds(), "Person", "firstName", Operation.EQ, "Chen")

  if((#named1 + #named2) < 20) then

So is this query any better, or faster?

Of course not. 9ms is already pretty hard to beat. But what happens if we aren’t so lucky and we have to deal with a name that either doesn’t exist or appears less than 20 times in the 3 hop neighborhood and we have to do the full traversal? Our query time jumps. If we try “Carmen” instead of “Chen” we get about 80ms for both of these ways of writing this query. What else can we try?

Well what about bi-directionality? There is absolutely nothing wrong with going both ways, sometimes it’s a huge advantage. Let’s give it a try.

We’ll start with Carmen and get everyone she knows. This is the walking backward step of our traversal.

local target_ids = Roar.new()
local targets = FindNodeIds("Person", "firstName", Operation.EQ, "Carmen", 0, 999999)
target_ids:addIds(targets)
table.sort(targets)
local target_knows = LinksGetLinksForType(target_ids:getNodeHalfLinks(), "KNOWS") 
local target_knows_ids = Roar.new()

Unfortunately we can’t assume we just dancing with Carmen, we have to consider there may be more than one node here, so we’ll need to build a structure to be able to get back to to them through the people that know them. This is screaming at us you need a Path construct and yes I really should go ahead and build one, but we’re going to do it the hard way first. We’ll create a backwards list of the people that known to each of our starting named targets.

local backwards = {}

for i,links in pairs(target_knows) do 
  target_knows_ids:addNodeIds(links)
  local neighbors = {}
  for j, neighbor in pairs(links) do
      table.insert(neighbors, neighbor:getNodeId())
  end
  table.insert(backwards, neighbors)
end 

Then we will flip it around so it becomes a map and each “friend” points to one or more named targets. I’ll convert the id of the node to a string because Lua seems to freak out when you create a map with very high integer keys.

local forwards = {}
for i, id in pairs(target_knows_ids:getIds()) do
  forwards[tostring(id)] = {}
end

for i, ids in pairs(backwards) do
    for j, neigh in pairs(ids) do
    table.insert(forwards[tostring(neigh)], targets[i])
    end
end

Now we go to the other side of our traversal. Let’s get our starting node and the people they know. We’ll setup the levels like we have in the past, but we’ll add a “near2” where the magic will happen and we will converge the two directions.

local node_id = NodeGetId("Person", "30786325583618")
local people = NodeGetLinksByIdForType(node_id, "KNOWS")
local seen1 = Roar.new()
local seen2 = Roar.new()
local near2 = Roar.new()
local seen3 = Roar.new()

seen1:addNodeIds(people)

local people2 = LinksGetLinksForType(people, "KNOWS")
for i,links in pairs(people2) do 
  seen2:addNodeIds(links)
end  

Ok, here comes the magic so pay attention. We’ll start off by making “near2” a copy of “seen2” using inplace_union and then instead of intersecting the target_ids, we will intersect the nodes known by the target ids!

seen2:inplace_difference(seen1)
seen2:remove(node_id)
near2:inplace_union(seen2)

seen1:inplace_intersection(target_ids)
seen2:inplace_intersection(target_ids)
near2:inplace_intersection(target_knows_ids)

That will allow us to create our “seen3” by joining the traversals from the forwards map we created earlier. The rest of the query is just like the first one. Here is the full thing.

for i, id in pairs(near2:getIds()) do
   seen3:addIds(forwards[tostring(id)])
end  

What did our hard work do for us? Check it out:

7. Seven milliseconds using this bidirectional strategy. It works great when there are a few unique people with the given name, not so great when it is a popular name. If we try the parameters for the other two options we bump back up to about 56ms for both. Still we’re crying about 7ms here, 9ms there, 56ms, 80ms… it’s still super fast and guess what. No indexes. That’s right we haven’t added any indexing what so ever to RageDB yet. We’re able to find People with a firstName equal to something fast because we have Schema! Both scanning the entire Person firstName “column” or filtering only on a few node properties along the way are both pretty fast when they are all together.

Still loads to add, but you know what surprised me the most? That I can send in any 100 lines of code and get an answer back in 7ms. Many other databases are still parsing the query or trying to come back with a query plan while LuaJIT is already done executing and serializing the results back to JSON.

I N S A N E