Join in OrientDB

I started working on OrientDB which is a NoSQL dbms which brings in the goodness of both Graph and Document DBs.

We (me and my team) were heavy on relational databases until we started working on OrientDB, it was a bit hard for us to get away from the Relational thinking where you try to do everything with SQL and think "Inner Joins" :)

However, what we realized was simply coz you are working on a NoSQL DB, the inner join like scenarios could not be avoided. A very good example is integrating with other systems in the organizations that have a relational DB as the back end.

Inner join like scenarios could be created using sub queries in OrientDB where we used the LET block to access the parent query context. However, we realized this is not the way to go forward in the hard way.

Here's a typical example.

My Schema:

Department {

 deptId : INTEGER

 deptName : STRING

} 

Employee {

 empId : INTEGER

 empName : STRING

 deptId : INTEGER

}

Query to get departments linked to employees;

SELECT empName, $dept[0].deptName

FROM Employee

LET $dept = (SELECT FROM Department WHERE deptId = $parent.current.deptId)

For development we usually use a simple data set for easy debugging. There this worked wonderfully well and we were happy. However, when we started testing with larger sets of test data, the time taken for the query horribly increased. 

But we had a hidden weapon - Indexes!! We created indexes for Department.deptId and we were certain that the inner query would pick up the index. But to our utter horror, it didn't! The time taken was unchanged. We did a query profiling using the EXPLAIN feature and it did not indicate any index usage.

With out the index, the time complexity of the query was O(n²) since for each of the Employees (parent query) all the departments are searched. The expectation with the index was to bring the time complexity to O(n).

Therefore, we moved from pure SQL to OrientDB back-end functions. These are more like stored procedures in a Relational context and could be written in JavaScript, SQL and Groovy (for the time being). We liked JavaScript. Here's how the function body looked like;

var employeeList = db.query("SELECT FROM Employee");

for (var i = 0; i < employeeList.length; i++) {

  var deptId = employeeList[i].field("empId");

  

  var departmentList = db.query("SELECT FROM Department WHERE deptId = ? ", deptId);

  

  print(departmentList[0].field("name"));

}

The function first queries the list of Employees, then execute a direct SELECT query for the Department that should be liked. This query actually uses the index, and makes the execution time almost a constant. Selecting all the employees would be an additional cost. However, since OrientDB does a lazy load, this is not bad as it seems.

The above strategy actually helped us reduce certain queries that took around 10 minutes to 30 seconds.

IllumiRoom : Peripheral Projected Illusions for Interactive Experience

Video gaming is a popular past time and a multi-billion dollar industry spread worldwide. The numbers playing video games is on the increase all the time, and the game developers are spending millions of dollars in R&D to find ways to make the gaming experience as realistic as possible.

The latest trend in video gaming is to make the player her or himself to become the controller tracking the gesture of the player. Nintendo Wii with the Wii Remote, Sony PlayStation with Move and Eye and Microsoft Xbox with Kinect are three main gaming consoles that supported gesture tracking. Out of the three, Microsoft Kinect stands out tall since unlike its two competitors Kinect does not require the game player to hold any controller for gesture tracking. With the huge success received by Kinect where more than 24 million units were sold worldwide, Microsoft is motivated to take the gaming experience to a whole different level.

Imaging you sitting down in your living room to play a video game on your television. When the game starts, the room mysteriously transforms to look like an environment, matching the shading in the video game. The colors of the room become supersaturated and carton edges appear on your furniture. You come across an enemy in the game and suddenly a streaking bullet flies towards your character and then out of the television. The enemy throws a grenade towards you. The grenade rolls out of the television, bouncing off the coffee table and explodes in your living room, throwing shrapnel across the furniture. The entire living room appears to shake as you take damage from the explosion. Although this sounds like science fiction, Microsoft’s “Project IllumiRoom” which is still in R&D has completed a proof-of-concept which proves that the date this becomes a reality is not far from now!

IllumiRoom ??

“IllumiRoom” augments the area surrounding the television with peripheral projected visualizations. Well, what does that actually mean? Have a look at figure 1 below;

Figure 1 : Extending filed of view

The image on the left showcases the actual living room with the TV in the middle and some furniture surrounding the TV. The image on the right shows how IllumiRoom can extend the field of view so that the area surrounding the TV augmented with similar shadings of the game.

IllumiRoom focuses on three types of special enhancements;

1. Extend the field of view – The example explained above (Figure 1)

2. Change the appearance of the room – For example, if it’s snowing in the game, a snow visualization can be projected which corresponds to the motion of the game (Figure 2)

Figure 2 : Changing appearance

3. Induce apparent motion – For example, visually make the edges of the furniture in the room wobble when you get hit by enemy bullets (Figure 3)

Figure 3 : Induce apparent motion

How does IllumiRoom work?

As explained earlier, IllumiRoom “projects” visualizations. But the interesting question is how do the projections get adjusted to the room geometry?

The current prototype uses a Kinect sensor to capture the color of the objects in the room and the 3 dimensional geometry of the room, which becomes the key input when rendering the visualizations to be projected. The projection is done via a commonly used wide filed-of-view projector as show in in figure 4. Since Kinect is used to analyze the room geometry, the system can self-calibrate and project illusions in any type of room.

Figure 4 : To key hardware elements used

Once this goes in to production, this will be via a single device that combines both the features of the Kinect sensor and the projector, ideally sitting on top of the living room coffee table as shown in figure 5.

Figure 5 : Projection

IllumiRoom supports different types of extending the field of view. As explained earlier, it can entirely extend the gaming environment to your living room or it can selectively extend the field of view to either extend the weapon fire, other players in the game, important objects etc. However, this requires hard integrations with the games source code.

IllumiRoom has also invented algorithms to detect the camera motion of any given video filed. It can even intercept the gaming controller input. Therefore, even without integrating with a games source code, there can be illuminations projected to induce the corresponding motion of the game.

Limitations

Since the IllumiRoom is not designed to project visualizations on a white flat surface, it should compensate for colors and geometry in the room. Therefore, the perceived projected visualization quality is always lower.

Since it’s projecting, it’s also subjected to limitations on any projection system, mainly neutralizing bright ambient illumination. Therefore, the best effects can be perceived if IllumiRoom is setup in a dark environment.

Conclusion

Still in its earlier stages, we can expect a lot of improvements over the coming years before this hit the markets. The usages may not limit to gaming, it can also extend to other forms of entertainment, education etc. If Microsoft could integrate IllumiRoom with Kinect, the possibilities can be enormous. One challenge is to bring down the cost of the system as it involves a projector which is not a common house-hold item right now.

The capabilities of IllumiRoom are much greater than what’s explained in this short article. More information with a set of videos which really speaks out of what IllumiRoom is capable of can be found at http://research.microsoft.com/en-us/projects/Illumiroom

References

1. http://en.wikipedia.org/wiki/Kinect
2. http://research.microsoft.com/en-us/projects/Illumiroom

Images:

1. http://www.brettrjones.com/illumiroom/#more-464