2011-11-05

Development Setup for Neo4j and PHP: Part 2

Update 2014-02-15: Using Neo4jPHP from a downloaded PHAR file has been deprecated. The preferred and supported way to install the library is via Composer. The examples below have been updated to reflect this. It has also been updated for the 2.0 release of Neo4j.

This is Part 2 of a series on setting up a development environment for building projects using the graph database Neo4j and PHP. In Part 1 of this series, we set up unit test and development databases. In this part, we'll build a skeleton project that includes unit tests, and a minimalistic user interface.

All the files will live under a directory on our web server. In a real project, you'll probably want only the user interface files under the web server directory and your testing and library files somewhere more protected.

Also, I won't be using any specific PHP framework. The principles in the code below should apply equally to any framework you decide to use.

Create the Project and Testing Harness

Create a project in a directory on your web server. For this project, mine is "/var/www/neo4play" on my local host. We'll also need a Neo4j client library. I recommend Neo4jPHP (disclaimer: I'm the author) and all the code samples in Part 2 use it.
> cd /var/www/neo4play
> mkdir -p tests/unit
> mkdir lib
> echo '{"require":{"everyman/neo4jphp":"dev-master"}}' > composer.json
> composer install
> echo "<?php phpinfo(); ?>" > index.php
Test the setup by browsing to http://localhost/neo4play. You should see the output of `phpinfo`.

Now we'll create a bootstrap file that we can include to do project-wide and environment specific setup. Call this file "bootstrap.php" in the root project directory.
<?php
require_once(__DIR__.'/vendor/autoload.php');

error_reporting(-1);
ini_set('display_errors', 1);

if (!defined('APPLICATION_ENV')) {
    define('APPLICATION_ENV', 'development');
}

$host = 'localhost';
$port = (APPLICATION_ENV == 'development') ? 7474 : 7475;
$client = new Everyman\Neo4j\Client($host, $port);
The main point of this file at the moment is to differentiate between our development and testing environments, and set up our connection to the correct database. We do this by attaching the database client to the correct port based on an application constant.

We'll use the bootstrap file to setup a different, unit testing specific bootstrap file. Create the following file as "tests/bootstap-test.php":
<?php
define('APPLICATION_ENV', 'testing');
require_once(__DIR__.'/../bootstrap.php');

// Clean the database
$query = new Everyman\Neo4j\Cypher\Query($client, 'MATCH n-[r]-m DELETE n, r, m');
$query->getResultSet();
The purpose of this file to to tell our application bootstrap that we are in the "testing" environment. Then it cleans out the database so that our tests run from a known state.

Tell PHPUnit to use our test bootstrap with the following config file, called "tests/phpunit.xml":
<phpunit colors="true" bootstrap="./bootstrap-test.php">
    <testsuite name="Neo4j Play Test Results">
        <directory>./unit</directory>
    </testsuite>
</phpunit>
And because we're following TDD, we'll create our first test file, "tests/unit/ActorTest.php":
<?php
class ActorTest extends PHPUnit_Framework_TestCase
{
    public function testCreateActorAndRetrieveByName()
    {
        $actor = new Actor();
        $actor->name = 'Test Guy '.rand();
        Actor::save($actor);

        $actorId = $actor->id;
        self::assertNotNull($actorId);

        $retrievedActor = Actor::getActorByName($actor->name);
        self::assertInstanceOf('Actor', $retrievedActor);
        self::assertEquals($actor->id, $retrievedActor->id);
        self::assertEquals($actor->name, $retrievedActor->name);
    }

    public function testActorDoesNotExist()
    {
        $retrievedActor = Actor::getActorByName('Test Guy '.rand());
        self::assertNull($retrievedActor);
    }
}
So we know we want a domain object called "Actor" (apparently we're building some sort of movie application) and that Actors have names and ids. We also know we want to be able to look up an Actor by their name. If we can't find the Actor by name, we should get a `null` value back.

Run the tests:
> cd tests
> phpunit
Excellent, our tests failed! If you've been playing along, they probably failed because the "Actor" class isn't defined. Our next step is to start creating our domain objects.

Defining the Application Domain

So far, we only have one domain object, and a test that asserts its behavior. In order to make the test pass, we'll need to connect to the database, persist entities to it, and then query it for those entities.

For persisting our entities, we'll need a way to get the client connection in our "Actor" class and any other domain object classes we define. To do this, we'll create an application registry/dependency-injection container/pattern-buzzword-of-the-month class. Put the following in the file "lib/Neo4Play.php":
<?php
class Neo4Play
{
    protected static $client = null;

    public static function client()
    {
        return self::$client;
    }

    public static function setClient(Everyman\Neo4j\Client $client)
    {
        self::$client = $client;
    }
}
Now our domain objects will have access to the client connection through `Neo4Play::client()` when we persist them to the database. It's time to define our actor class, in the file "lib/Actor.php":
<?php
use Everyman\Neo4j\Node,
    Everyman\Neo4j\Index;

class Actor
{
    public $id = null;
    public $name = '';

    public static function save(Actor $actor)
    {
    }

    public static function getActorByName($name)
    {
    }
}
Requiring our classes and setting up the client connection is part of the bootstrapping process of the application, so we'll need to add some thing to "bootstrap.php":
<?php
require_once(__DIR__.'/vendor/autoload.php');
require_once(__DIR__.'/lib/Neo4Play.php');
require_once(__DIR__.'/lib/Actor.php');

// ** set up error reporting, environment and connection... **//

Neo4Play::setClient($client);
We have a stub class for the domain object. The tests will still fail when we run them again, but at least all the classes should be found correctly.

Let's start with finding an Actor by name. With our knowledge of graph databases, we know this will involve an index lookup, and that we will get a Node object in return. If the lookup returns no result, we'll get a `null`. If we do get a Node back, we'll want to hold on to it, for updating the Actor later.

Modify the Actor class with the following contents:
class Actor
{
    //

    protected $node = null;

    //

    public static function getActorByName($name)
    {
        $actorIndex = new Index(Neo4Play::client(), Index::TypeNode, 'actors');
        $node = $actorIndex->findOne('name', $name);
        if (!$node) {
            return null;
        }

        $actor = new Actor();
        $actor->id = $node->getId();
        $actor->name = $node->getProperty('name');
        $actor->node = $node;
        return $actor;
    }
}
The main thing we're trying to accomplish here is keeping our domain classes as Plain-Old PHP Objects, that don't require any special class inheritance or interface, and that hide the underlying persistence layer from the outside world.

The tests still fail. We'll finish up our Actor class by saving the Actor to the database.
class Actor
{
    //

    public static function save(Actor $actor)
    {
        if (!$actor->node) {
            $actor->node = new Node(Neo4Play::client());
        }

        $actor->node->setProperty('name', $actor->name);
        $actor->node->save();
        $actor->id = $actor->node->getId();

        $actorIndex = new Index(Neo4Play::client(), Index::TypeNode, 'actors');
        $actorIndex->add($actor->node, 'name', $actor->name);
    }

    //
}
Run the tests again. If you see all green, then everything is working properly. To double check, browse to the testing instance webadmin panel http://localhost:7475/webadmin/#. You should see 2 nodes and 1 property (Why 2 nodes? Because there is a node 0 -- the reference node -- that is not deleted when the database is cleaned out.)

Build Something Useful

It's time to start tacking on some user functionality to our application. Thanks to our work on the unit tests, we can create actors in the database and find them again via an exact name match. Let's expose that functionality.

Change the contents of "index.php" to the following:
<?php
require_once('bootstrap.php');

if (!empty($_POST['actorName'])) {
    $actor = new Actor();
    $actor->name = $_POST['actorName'];
    Actor::save($actor);
} else if (!empty($_GET['actorName'])) {
    $actor = Actor::getActorByName($_GET['actorName']);
}

?>
<form action="" method="POST">
Add Actor Name: <input type="text" name="actorName" />
<input type="submit" value="Add" />
</form>

<form action="" method="GET">
Find Actor Name: <input type="text" name="actorName" />
<input type="submit" value="Search" />
</form>

<?php if (!empty($actor)) : ?>
    Name: <?php echo $actor->name; ?><br />
    Id: <?php echo $actor->id; ?><br />
<?php elseif (!empty($_GET['actorName'])) : ?>
    No actor found by the name of "<?php echo $_GET['actorName']; ?>"<br />
<?php endif; ?>
Browse to your index file. Mine is at http://localhost/neo4play/index.php.

You should see the page you just created. Enter a name in the "Add Actor Name" box and click the "Add" button. If everything went according to plan, you should see the actor name and the id assigned to the actor by the database.

Try finding that actor using the search box. Note the actor's id.

Browse to http://localhost:7474/webadmin/# and click the "Data browser" tab. Enter the actor id in the text box at the top. The node you created when you added the actor should show up.

The interesting thing is that our actual application doesn't know anything about how the Actors are stored. Nothing in "index.php" references graphs or nodes or indexes. This means that, in theory, we could swap out the persistence layer for a SQL databases later, or MongoDB, or anything else, and nothing in our application would have to change. If we started with a SQL database, we could easily transition to a graph database.

Explore the Wonderful World of Graphs

Your development environment is now set up, and your application is bootstrapped. There's a lot more to add to this application, including creating movies, and linking actors and movies together. Maybe you'll want to add a social aspect, with movie recommendations. Graph databases are powerful tools that enable such functionality to be added easily.

Go ahead and explore the rest of the Neo4jPHP library (wiki and API). Also, be sure to checkout the Neo4j documentation, especially the sections about the REST API, Cypher and Gremlin (two powerful graph querying and processing languages.)

All the code for this sample application is available as a gist: http://gist.github.com/1341833.

Happy graphing!

Development Setup for Neo4j and PHP: Part 1

Update 2014-02-15: Using Neo4jPHP from a downloaded PHAR file has been deprecated. The preferred and supported way to install the library is via Composer. The examples below have been updated to reflect this. It has also been updated for the 2.0 release of Neo4j.

I would really love to see more of my fellow PHP developers talking about, playing with, and building awesome applications on top of graph databases. They really are a powerful storage solution that fits well into a wide variety of domains.

In this two part series, I'll detail how to set up a development environment for building a project with a graph database (specifically Neo4j). Part 1 will show how to set up the development and unit testing databases. In Part 2, we'll create a basic application that talks to the database, including unit tests.

All the steps below were performed on Ubuntu 10.10 Maverick, but should be easy to translate to any other OS.

Grab the Components

There are a few libraries and software tools needed for the project. First off, we'll need to install our programming environment, specifically PHP, PHPUnit and Java. How to do this is dependent on your operating system. My setup is PHP 5.3, PHPUnit 3.6 and Sun Java 6.

Next, we need to get Neo4j. Download the latest tarball from http://neo4j.org/download. I usually go with the latest milestone release (2.0 at this time.)
> cd ~/Downloads
> wget http://dist.neo4j.org/neo4j-community-2.0.1-unix.tar.gz

Set Up the Development Instance

It is possible to put test and development data in the same database instance, but I prefer a two database solution, even when using a SQL database. I do this because 1) I don't have to worry about accidentally blowing away any development data I care about, and 2) I don't have to worry about queries and traversals in my unit tests accidentally pulling in development data, and vice versa.

Unlike SQL or many NOSQL database servers, Neo4j cannot have more than one database in a single instance. The only way to get two databases is to run two separate instances on two separate ports or hosts. The instructions below describe how to set up our development and unit testing databases on the same host but listening on different ports.

First, create a point to hold both neo4j instances, and unpack the development instance:
> mkdir -p ~/neo4j
> cd ~/neo4j
> tar -xvzf ~/Downloads/neo4j-community-2.0.1-unix.tar.gz
> mv neo4j-community-2.0.1 dev
Next, configure the server by editing the file "~/neo4j/dev/conf/neo4j-server.properties". Make sure that the server is on port 7474
org.neo4j.server.webserver.port=7474
If you will be accessing the database instance from a host other than localhost, uncomment the following line:
org.neo4j.server.webserver.address=0.0.0.0
Save the config and exit. Now it's time to start the instance.
> ~/neo4j/dev/bin/neo4j start
You should be able to browse to the Neo4j Browser panel: http://localhost:7474

Set Up the Testing Instance

Unpack the test instance:
> cd ~/neo4j
> tar -xvzf ~/Downloads/neo4j-community-2.0.1-unix.tar.gz
> mv neo4j-community-2.0.1 test
Next, configure the server by editing the file "~/neo4j/test/conf/neo4j-server.properties". Make sure that the server is on port 7475 (note that this is a different port from the development instance!)
org.neo4j.server.webserver.port=7475
If you will be accessing the database instance from a host other than localhost, uncomment the following line:
org.neo4j.server.webserver.address=0.0.0.0
We need one more change to differentiate the testing from the development instance. Edit the file "~/neo4j/test/conf/neo4j-wrapper.properties" and change the instance name line:
wrapper.name=neo4j-test
Save and exit, then start the instance.
> ~/neo4j/test/bin/neo4j start
You should be able to browse to the Neo4j Browser panel: http://localhost:7475

Congratulations! Everything is set up and ready for us to build our application. In Part 2 of this series, I'll talk about setting up unit tests and building a basic application using a graph database as a backend.

2011-10-04

A Humbling Reference

Sometimes I have an experience that reminds me of how near-sighted I can get when I'm head-down in a problem.

What do you think the output of the following code will be (no cheating by running it first!):
<?php
$a = array(array("result" => "a"));
for ($i=0; $i < 2; $i++) {
    foreach ($a as $j => $v) {
        $v["result"] .= "a";
        echo $v["result"] ."\n";
    }
}
foreach ($a as $k => $v) echo $v["result"] ."\n";
If the goal is to add the character "a" twice onto each result element of each sub-array, at first glance this seems like a perfectly reasonable way to go about it.

But hold up! Each time through, we seem to have only added one "a" onto the result. And in the second foreach loop, it seems like we didn't modify the value at all! What gives?

Well, it might be obvious to most of you, but when it was costing me an hour and a half of my work day it was buried in a nest of process forking and stream handling, part of which looked something like this:
while ($currentExecution) {
    foreach ($currentExecution as $i => $handle) {
        $handle['output'] .= stream_get_contents($handle['outstream']);
        $status = proc_get_status($handle['process']);
        if (!$status['running']) {
            fclose($handle['outstream']);
            proc_terminate($handle['process']);
            echo $handle['output']."\n";
            unset($currentExecution[$i]);
        }
    }
}
Same concept as before: I have an array of process handles (opened with proc_open) and I'm looping through, gathering the output of each process as it is generated, until the process is finished running, at which point I close the process and display the output. The symptom was that, sometimes, I would only see the end of the output and not the beginning.

The times when this happened were the times where a process handle went through the outer while loop more than once, the same as in the contrived example above. The reason for this is because when you are working with a value inside a foreach loop, you are actually working with a copy of that value (technically a copy-on-write). So modifications made to the value do not persist through multiple passes through the while loop.

As it turns out, the solution here is quite simple. Actually, there are several solutions. Here's the easiest one, applied to the original example:
<?php
$a = array(array("result" => "a"));
for ($i=0; $i < 2; $i++) {
    foreach ($a as $j => &$v) {
        $v["result"] .= "a";
        echo $v["result"] ."\n";
    }
}
foreach ($a as $k => $v) echo $v["result"] ."\n";
The difference is subtle: it's the "&" prepended to the $v in the foreach loop. This tells the loop to use a reference to the value instead of a copy. Here's another possible solution:
<?php
$a = array(array("result" => "a"));
for ($i=0; $i < 2; $i++) {
    foreach ($a as $j => $v) {
        $a[$j]["result"] .= "a";
        echo $a[$j]["result"] ."\n";
    }
}
foreach ($a as $k => $v) echo $v["result"] ."\n";
In this case, we're not even using the variable $v. We're using the array index to refer to the value inside of the array directly. Because we're modifying the actual array value and not the copy, the changes persist through the loop.

The final solution (and the one I ended up going with) is to make the value an object instead of an array:
<?php
$obj->result = "a";
$a = array($obj);
for ($i=0; $i < 2; $i++) {
        foreach ($a as $j => $v) {
                $v->result .= "a";
                echo $v->result ."\n";
        }
}
foreach ($a as $k => $v) echo $v->result ."\n";
Objects in PHP are always passed around by reference, including in foreach loops. So modifying the object's property inside the loop modifies the actual object, not a copy.

The most annoying thing about this whole experience? I had solved this problem for someone else a few weeks ago, telling them what the issue was just from hearing them describe the situation and without even seeing their code run. So the deeper lesson here is this: when you've been staring at code for so long that it's making you cross-eyed and frustrated, walk away. And most importantly, get someone else who hasn't been working on it to look it over.

...something something forest...something something trees...

Sample code available at http://gist.github.com/1263522

2011-09-23

Phar Flung Phing

One of the cooler features of PHP 5.3 is the ability to package up a set of PHP class files and scripts into a single archive, known as a PHAR ("PHp ARchive"). PHAR files are pretty much equivalent to Java's JAR files: they allow you to distribute an entire library or application as a single file. I decided to see how easy it would be to wrap up Neo4jPHP in a PHAR for distribution.

Surprisingly, there isn't much information out there on creating PHAR files outside of the PHP manual and a few older posts. They deal mainly with creating a PHAR with a hand-written script specific to the project being packaged, using PHP's PHAR classes and methods.

Since I also started playing with Phing recently, I decided to see if I could incorporate packaging a project as a PHAR into my build system. It turns out, it's pretty easy, given that Phing has a built-in PharPackage task.

All steps below were performed on Ubuntu 10.10 Maverick

Step 1 - Get Phing

The Phing docs are pretty explicit and easy to follow. If you have PEAR installed, simply do:
> sudo pear channel-discover pear.phing.info
> sudo pear install phing/phing
If all goes well, you should the location of the phing command line utility when you run
> which phing

Step 2 - Allow PHP to create PHARs

This is one that most of the posts I found on creating PHARs fail to mention. In the default installation of PHP, PHARs are read-only (this prevents a nasty security hole, whereby any PHP script on your machine has the ability to modify other PHARs.) In order to prevent this, the php.ini setting "phar.readonly" must be turned off. I did this by creating a new file in my PHP conf.d directory:
> sudo sh -c "echo 'phar.readonly=0' > /etc/php5/conf.d/phar.ini"

Step 3 - Create a stub

In a PHAR, the stub file is run when the PHAR is `include`d or `require`d in a script (or when the PHAR is invoked from the command line.) The purpose of the stub is to do any setup necessary for the library contained in the PHAR. Since I'm packaging a library, the stub I created doesn't do anything more than set up autoloading of my library's classes.

Save the following file as "stub.php" in the root of your project:
<?php
Phar::mapPhar('myproject.phar');
spl_autoload_register(function ($className) {
	$libPath = 'phar://myproject.phar/lib/';
	$classFile = str_replace('\\',DIRECTORY_SEPARATOR,$className).'.php';
	$classPath = $libPath.$classFile;
	if (file_exists($classPath)) {
		require($classPath);
	}
});
__HALT_COMPILER();
The "__HALT_COMPILER();" line must be the last thing in the file. The call to `Phar::mapPhar()` registers the PHAR with PHP and allows any of the files inside to be found via the "phar://" stream wrapper. Any files or directories contained in the PHAR can be referenced as "phar://myproject.phar/path/inside/phar/MyClass.php". Since all my project files are namespaced, autoloading is a matter of translating the class name into a path inside the PHAR.

Step 4 - Create a build file

Phing's documentation is pretty extensive, so I won't go into to much detail about what each piece of the build file means. The important part is the PharPackage task in the "package" target.

Save the following file as "build.xml" in the root of your project:
<?xml version="1.0" encoding="UTF-8"?>
<project name="MyProject" default="package">

  <!-- Target: build -->
  <target name="build">
    <delete dir="./build" />
    <mkdir dir="./build" />
    <copy todir="./build">
      <fileset dir=".">
        <include name="lib/" />
      </fileset>
    </copy>
  </target>

  <!-- Target: package -->
  <target name="package" depends="build">
    <delete file="./myproject.phar" />
    <pharpackage
      destfile="./myproject.phar"
      basedir="./build"
      compression="gzip"
      stub="./stub.php"
      signature="sha1">
      <fileset dir="./build">
        <include name="**/**" />
      </fileset>
      <metadata>
        <element name="version" value="1.2.3" />
        <element name="authors">
          <element name="Joe Developer">
            <element name="email" value="joe.developer@example.com" />
          </element>
        </element>
      </metadata>
    </pharpackage>
  </target>
</project>
The important part is the "package" target, the default target of this build file. It depends on the "build" target, whose only purpose is to copy out all the files that will be packaged in the PHAR into a separate "build" directory. This strips out any testing, example or other non-library files. Any previously created package is deleted.

The main work of packaging is done via the "pharpackage" task. In this case, I'm specifying that the output package should be called "myproject.phar" and be put in the same directory as the build file, the PHAR should be compressed with "gzip", the stub to load when requiring the file is at "./stub.php" and the PHAR should be signed with a SHA1 hash.

Metadata appears to be optional, but Phing throws up a nasty looking warning if it's not there (it tries to convert an empty value to an array.) Nested metadata is turned into a PHP array and serialized.

Step 5 - Phling your PHAR

Run the following command in the directory with your build file:
> phing
# or, if the "package" task is not the default
> phing package
If all went well, there should be a file called "myproject.phar" in the root of your project. You can test it out by running this test script:
<?php
require("myproject.phar");

$thing = new Class\In\My\Project();
If PHP doesn't complain about a missing class, the PHAR set up correctly and autoloading is working.

The Neo4jPHP PHAR is available at http://github.com/downloads/jadell/Neo4jPHP/neo4jphp.phar.

2011-08-25

Getting Neo4jPHP working with CodeIgniter 2

This post is based heavily off of Integrating Doctrine 2 with CodeIgniter 2. I haven't tested it myself, so please use it as a starting point and let me know if I should update anything.

Here are the steps to get Neo4jPHP set up as a CodeIgniter 2 library:
  1. Copy the 'Everyman' folder to application/libraries
  2. Create a file called Everyman.php in application/libraries
  3. Copy the following code into Everyman.php:
    <?php
    class Everyman
    {
        public function __construct()
        {
            spl_autoload_register(array($this,'autoload'));
        }
    
        public function autoload($sClass)
        {
            $sLibPath = __DIR__.DIRECTORY_SEPARATOR;
            $sClassFile = str_replace('\\',DIRECTORY_SEPARATOR,$sClass).'.php';
            $sClassPath = $sLibPath.$sClassFile;
            if (file_exists($sClassPath)) {
                require($sClassPath);
            }
        }
    }
    
  4. Add the following line to application/config/autoload.php:
    $autoload['libraries'] = array('everyman');
    

This is actually a generic autoloader that will attempt to autoload any namespaced class under application/library where the class name matches the file path.

2011-07-23

Performance of Graph vs. Relational Databases

A few weeks ago, Emil Eifrem, CEO of Neo Technology gave a webinar introduction to graph databases. I watched it as a lead up to my own presentation on graph databases and Neo4j.

Right around the 54 minute mark, Emil talks about a very interesting experiment showing the performance difference between a relational database and a graph database for a certain type of problem called "arbitrary path query", specifically, given 1,000 users with an average of 50 "friend" relationships each, determine if one person is connected to another in 4 or fewer hops.

Against a popular open-source relational database, the query took around 2,000 ms. For a graph database, the same determination took 2 ms. So the graph database was 1,000 times faster for this particular use case.

Not satisfied with that, they then decided to run the same experiment with 1,000,000 users. The graph database took 2 ms. They stopped the relational database after several days of waiting for results.

I showed this clip at my presentation to a few people who stuck around afterwards, and we tried to figure out why the graph database had the same performance with 1,000 times the data, while the relational database became unusably slow. The answer has to do with the way in which each type of database searches information.

Relational databases search all of the data looking for anything that meets the search criteria. The larger the set of data, the longer it takes to find matches, because the database has to examine everything in the collection.

Here's an example: let's assume there is a table with "friend" relationships:
> SELECT * FROM friends;
+-------------+--------------+
| user_id     | friend_id    |
+-------------+--------------+
| 1           | 2            |
| 1           | 3            |
| 1           | 4            |
| 2           | 5            |
| 2           | 6            |
| 2           | 7            |
| 3           | 8            |
| 3           | 9            |
| 3           | 10           |
+-------------+--------------+
In order to see if user "9" is connected to user "2", the database has to find all the friends of user "9", and see if user "2" is in that list. If not, find all of their friends, and then see if user "2" is in that list. The database has to scan the entire table each time. This means that if you double the number of rows in the table, you've doubled the amount of data to search, and thus doubled the amount of time it takes to find what you are looking for. (Even with indexing, it still has to find the values in the index tree, which involves traversing that tree. The index tree grows larger with each new record, meaning the time it takes to traverse grows larger as well. And for each search, you always start at the root of the tree.)

Each new batch of friends to look at requires an entirely new scan of the table/index. So more records leads to more search time.

Conversely, a graph database looks only at records that are directly connected to other records. If it is given a limit on how many "hops" it is allowed to make, it can ignore everything more than that number of hops away.
Only the blue records are ever seen during the search. And since a graph traversal "remembers" where it is at any time, it never has to start from the beginning, only from its last known position.

You could add another ring of records around the outside, or add a thousand more rings of records outside, but the search would never need to look at them because they are more steps away than the limit. The only way to increase the number of records searched (and thereby decrease performance) is to add more records within the 2-step limit, or add more relationships between the existing records.

So the reason why having 1,000 vs. 1,000,000 records causes such a stark difference between a relational and a graph database is that relational database performance decreases in relation to the number of records in the table, while graph database performance decreases in relation to the number of connections between the records.

2011-07-19

TriPUG Meetup slides

Here are the slides for my presentation on graph databases at the TriPUG meetup tonight: http://www.slideshare.net/JoshAdell/graphing-databases

Overall, I think it was pretty well received. I didn't mean for it to last an hour and a half, but there it is. There were a lot of new folks there; I'm encouraged at the enthusiasm of the developer community in the Triangle region. Thanks for having me!