O problema N+1

É mais fácil descrever o problema N+1 através de exemplo. Dê uma olhada no seguinte trecho de PHP em app hipotético de blog:

<?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
);
}

Temos um conjunto mestre de linhas (as postagens do blog), mas precisamos ainda buscar muitas linhas de comentários para cada artigo do blog. Para fazer isso, nós fizemos um loop pelo conjunto mestre de linhas e lançamos uma query para cada um. Isso leva a várias linhas de comentários para esse artigo do blog.

Esse é o problema N+1. Para construir uma lista de 10 registros, emitimos 11 queries : uma para o conjunto mestre de 10 registros, em seguida, mais 10 (N) queries para buscar os comentários. Se também precisássemos obter várias tags para cada postagem, seriam mais 20, 10 queries para os comentários, e um adicional de 10 queries para as tags, num total de 21 queries para a construção de 10 registros.

Isso pode rapidamente se tornar um problema de desempenho, mesmo para pequenos conjuntos de dados com muitos relacionamentos. É especialmente ruim quando você precisa buscar,  por exemplo, cinco conjuntos adicionais de dados relacionados para um conjunto mestre de 40 mil linhas. Haverá uma query para obter o conjunto mestre de 40 mil linhas, mais 5 queries por linha para os dados relacionados, para 200.001 queries no total.

A solução

Existem pelo menos duas maneiras de resolver o problema N+1 e reduzir o número de queries de forma dramática.

Uma maneira é escrever uma query que une os comentários para os posts em um único conjunto de resultados maciços. Vamos ver uma ou outra repetição dos posts do blog, de modo que seria necessário percorrer o conjunto de resultados, escolher as mensagens distintas e reter os vários comentários para cada um. Existem vários inconvenientes:

1. É difícil fazer LIMIT/OFFSET no conjunto mestre de linhas que desejamos recuperar.
2. Recebemos de volta um resultado de grandes dimensões a partir do banco de dados com muita informação repetida. Para extrair os dados relacionados, precisamos percorrer o conjunto de resultados no PHP e descartar as partes repetidas das linhas, mantendo o controle de quais foram repetidas e os que são novas.
3. Se tivermos dois ou mais relacionamentos um-para-muitos, torna-se difícil construir a query e, em seguida, escolher independentemente do conjunto de resultados nos objetos de seu domínio. O problema de repetição a partir do ponto 2 torna-se exponencialmente mais problemático.

Em vez disso, sugiro uma maneira de resolver o problema N +1 que é mais fácil de implementar e mais escalonável em vários relacionamentos um-para-muitos. Após termos query para o mestre conjunto de linhas, nós emitimos uma única query adicional para obter todas as linhas relacionadas em uma tentativa, e depois uni-las para o conjunto mestre em um loop PHP. O que segue abaixo é uma versão reescrita do exemplo anterior, utilizando a técnica de query-and-stitch:

<?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;
}

Temos agora um loop adicional no código PHP em comparação com a solução original. Em compensação, nós salvamos nove queries adicionais; passamos de 11 (1 para as postagens e 10 para os comentários) para 2 (1 para os posts e 1 para os comentários).

Estendendo a solução

Nós podemos adicionar quantas linhas de muitos relacionamentos quisermos usando a mesma técnica. Por exemplo, se nós também precisássemos buscar várias tags em um relacionamento muitos-para-muitos para cada post, desejaríamos fazer algo mais ou menos assim:

<?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;
}

Na solução original, teríamos tido um único loop no código PHP, mas um total de 21 queries. Com query-and-stitch, temos 3 loops, mas apenas 3 queries. O desempenho dos múltiplos loops de PHP é praticamente garantido para ser melhor do que o desempenho de 21 queries.

Automatizando a solução

A técnica query-and-stitch é aplicável em qualquer contexto, seja uma base de código nova ou uma herança, usando um framework ou não. No entanto, em algum momento, vamos querer generalizar a técnica para que possamos envolvê-la  em uma classe para reutilização.

Na verdade, muitos ORMs fazem query-and-stitch nos bastidores quando você pede para incluir uma relação em um eager-fetch no conjunto mestre de linhas. Utilizar um ORM é uma forma de automatizar o problema N+1.

Apesar disso, muitos desenvolvedores de PHP não gostam de ORMs. Depois de ter desenvolvido um sistema ORM robusto com Jeff Moore, estou totalmente familiarizado com as vantagens e desvantagens envolvidas na utilização desse método. Eles podem ser opacos, ineficazes ou imprevisíveis em casos extremos, e quase sempre exigem que você aprenda uma maneira especial de construir suas solicitações de recuperação. (Isso pode ser tanto por uma linguagem do tipo SQL ou por um determinado conjunto de métodos e propriedades informacionais.) Mesmo assim, você pode não estar totalmente isolado do problema N+1, especialmente se os registros lazy-loads do  ORM em um loop onde você não tenha feito um eager-fetch nos dados necessários.

Ao analizar o problema N+1 combinado com as vantagens e desvantagens do uso de ORMs, ocorreu-me que o centro do problema N+1 não é o uso do SQL. O problema é o empacotamento dos resultados em seus objetos de modelo de domínio. Com isso em mente, eu reuni uma versão inicial de um pacote data-marshaling chamado Aura.Marshal que utiliza a técnica stitch acima.

O pacote é muito limitado em seu escopo. Tudo o que ele faz é pegar conjuntos de resultados e reuni-los em objetos de modelo de domínio. É completamente independente de camada de acesso a banco de dados; você pode usar as funções PHP MySQL, PDO, Solar SQL, Zend DB, ou qualquer outra coisa. Quando você define as relações de domínio em um tipo de gerenciador e, em seguida, alimenta os tipos com os resultados de queries próprias, Aura.Marshal vai ligar os objetos para você, utilizando a técnica stitch descrito acima. Isso ajuda a fornecer uma forma automatizada de evitar N+1, enquanto nos dá total controle sobre as queries sendo usados para recuperar os dados que precisamos.

Conclusão

Espero que a técnica de query-and-stitch e ajude-o a resolver seus próprios problemas N+1.

***

Texto original disponível em http://phpadvent.org/2011/a-stitch-in-time-saves-nine-by-paul-jones