WEB Advent 2011 / A Stitch in Time Saves Nine

The N+1 Problem

It is easiest to describe the N+1 problem by example. Take a look at the following bit of PHP in a hypothetical blog app:

<?php
/**
* @var Solar_Sql_Adapter|Zend_Db_Adapter
* $sql An SQL database connection object.
*/

// 1 query to get 10 blog posts.
$stmt = 'SELECT * FROM posts LIMIT 10';
$posts = $sql->fetchAll($stmt);

// 10 queries (1 per blog post) to get
// the comments for each post
foreach ($posts as &$post) {

   $stmt = 'SELECT *
            FROM comments
            WHERE post_id = :post_id';

   $bind = array(
       'post_id' => $post['id'],
   );

   $post['comments'] = $sql->fetchAll(
       $stmt,
       $bind
   );
}

We have a master set of rows (the blog posts), but we need to additionally fetch many rows of comments for each blog post. To do that, we loop through the master set of rows and issue one query for each. This gets us the many rows of comments for that blog post.

This is the N+1 problem. In order to build up a list of 10 records, we issued 11 queries: 1 for the master set of 10 records, and then 10 more (N) queries to fetch the comments. If we also needed to get multiple tags for each post, it would be 20 more, 10 queries for the comments, and an additional 10 queries for the tags, for a total of 21 queries to build 10 records.

This can quickly become a performance problem even for small sets of data with many relationships. It is especially bad when you need to fetch, for example, 5 additional sets of related data for a master set of 40,000 rows. There will 1 query to get the master set of 40,000 rows, plus 5 queries per row for the related data, for 200,001 queries in total.

The Solution

There are at least two ways to solve the N+1 problem and reduce the number of queries dramatically.

One way is to write a query that joins the comments to the posts in a single massive result set. We will see repetition of the same blog posts over and over, so we would need to loop through the result set and pick out the distinct posts and retain the multiple comments for each one. There are several drawbacks:

  1. It’s hard to do LIMIT/OFFSET on the master set of rows that we want to retrieve.

  2. We get back an oversized result from the database with lots of repeated information. To extract the related data, we need to loop through the result set in PHP and discard the repeated parts of rows, keeping track of which ones were repeated and which ones are new.

  3. If we have two or more “to-many” relationships, it becomes difficult to construct the query and then pick apart the result set into your domain objects. The repetition problem from point 2 becomes exponentially more troublesome.

Instead, I suggest a way to solve the N+1 problem that is easier to implement and more scalable across several to-many relationships. After we query for the master set of rows, we issue a single additional query to get all of the related rows in one shot, and then stitch them into the master set in a PHP loop. The following is a rewritten version of the earlier example using the query-and-stitch technique:

<?php
/**
* @var Solar_Sql_Adapter|Zend_Db_Adapter
* $sql An SQL database connection object.
*/

// 1 query to get 10 blog posts.
$stmt = 'SELECT * FROM posts LIMIT 10';
$rows = $sql->fetchAll($stmt);

// Find the ID of each post and key a 
// $posts array on them.
$posts = array();
foreach ($rows as $post) {
   $id = $post['id'];
   $posts[$id] = $post;
}

// 1 additional query to get all
// comments for all the posts.
$stmt = 'SELECT *
        FROM comments
        WHERE post_id IN (:post_ids)';

$bind = array(
   'post_ids' => array_keys($posts),
);

$rows = $sql->fetchAll($stmt, $bind);

// Stitch the comment rows into the posts.
// It is easy to find the right post for
// the comment, because we have keyed the
// posts on their ID.
foreach ($rows as $comment) {
   $id = $comment['post_id'];
   $posts[$id]['comments'][] = $comment;
}

We now have one additional loop in the PHP code compared to the original solution. The tradeoff is that we have saved ourselves 9 additional queries overall; we have gone from 11 (1 for the posts and 10 for the comments) to 2 (1 for the posts and 1 for the comments).

Extending The Solution

We can add rows from as many relationships as we like using the same technique. For example, if we also needed to fetch multiple tags in a many-to-many relationship for each post, we would do something like this:

<?php
/**
* @var Solar_Sql_Adapter|Zend_Db_Adapter
* $sql An SQL database connection object.
* 
* @var array $posts The master array of
* posts, keyed on their IDs.
*/

// 1 query to get all tags through the
// association mapping table.
$stmt = 'SELECT
           posts_tags.post_id AS post_id,
           tags.*
       FROM tags
       JOIN posts_tags
           ON posts_tags.tag_id = tags.id
           AND posts_tags.post_id IN (:post_ids)';

$bind = array(
   'post_ids' => array_keys($posts),
);

$rows = $sql->fetchAll($stmt, $bind);

// Stitch the tags into the posts.
foreach ($rows as $tag) {
   $id = $tag['post_id'];
   $posts[$id]['tags'][] = $tag;
}

In the original solution, we would have had a single loop in the PHP code, but a total of 21 queries. With query-and-stitch, we have 3 loops, but only 3 queries. The performance of the multiple PHP loops is practically guaranteed to be better than the performance of 21 queries.

Automating the Solution

The query-and-stitch technique is applicable in any context, whether a new codebase or a legacy one, using a framework or not. However, at some point we are going to want to generalize the technique so we can wrap it in a class for reuse.

In fact, query-and-stitch is what many ORMs do under the hood when you ask to include a relation in an eager-fetch against the master set of rows. Using an ORM is one way to automate away the N+1 problem.

Lots of PHP developers don’t like ORMs, though. After having developed a robust ORM system with Jeff Moore, I am fully acquainted with the tradeoffs involved in using ORMs. They can be opaque, ineffective, or unpredictable in edge cases, and almost always require you to learn a special way of constructing your retrieval requests. (That way can be either through a SQL-lookalike language or through a particular set of methods and informational properties.) Even then, you may not be fully insulated from the N+1 problem, especially if the ORM lazy-loads records in a loop where you did not eager-fetch the necessary data.

In contemplating the N+1 problem combined with the tradeoffs of using ORMs, it occurred to me that the core of the N+1 problem is not the SQL being used. The problem is the marshaling of the results into your domain model objects. With that in mind, I have put together an initial version of a data-marshaling package called Aura.Marshal that uses the stitching technique above.

The package is very limited in its scope. All it does it take result sets and marshal them into domain model objects. It is completely database access layer agnostic; you can use the PHP MySQL functions, PDO, Solar SQL, Zend DB, or anything else. When you define your domain relationships in a type manager and then feed the types with your own query results, Aura.Marshal will link up the objects for you using the stitching described above. This helps to provide an automated way of avoiding N+1 while giving us complete control over the queries being used to retrieve the data we need.

Conclusion

I hope the query-and-stitch technique helps you to solve your own N+1 problems. If you have comments, questions, or criticism, please feel free to leave a comment on my companion blog post.

Developer Gift

I have one gift idea, in three parts. Make it an ATF Christmas! If the nerd in your life likes alcohol, tobacco, and firearms, he or she is sure to appreciate a pack of good cigars, a bottle of fine scotch, or perhaps some appropriately-sized ammunition. The prices on these things are only going up, so get them now while you can still afford them.

Other posts