N+1 Queries

N+1 queries are a pervasive category of performance pitfall or “antipattern”. N+1 queries are an efficiency problem that can occur when a program tries to load the children of a parent-child relationship. It is most commonly discussed in connection with relational databases and is typically seen in code that makes use of an ORM or Object-relational mapping. An ORM maps the objects of an object-oriented application to tables in a relational database management system. Using an ORM, the relationships and data properties of the objects in an application can be easily stored and retrieved from a database without the need to write SQL.

While using an ORM can offer developers a huge boost in productivity they also come at a cost. ORMs such as Ruby’s popular ActiveRecord, obscure complexity and make assumptions to aid developers in quickly writing functional code. Unfortunately however, all of the assumptions and simplifications of an ORM can also result in suboptimal program behavior such as N+1 queries.

Let’s take a look at a quick example of such an inefficiency using the sample chinook SQLite database. The tables and relationships of this database look like this:

Let’s say we have an Ruby application configured to access this database through ActiveRecord and we want to write some code to print the title of each album released by the first four artists on the artists table. Our code might look something like this:

def first_four_artists_album_titles
  artists = Artist.limit(4)

  artists.each do |art|
    art.albums.each do |alb|
      puts alb.title
    end
  end
end

Executing the #first_four_artists_album_titles method should give us the desired outcome:

=> 'For Those About To Rock We Salute You'
=> 'Let There Be Rock'
=> 'Balls to the Wall'
=> 'Restless and Wild'
=> 'Big Ones'
=> 'Jagged Little Pill'

Great! Now, let’s take a look at what the SQL for that command probably looked like:

-- obtains the data for artists 1-4
SELECT * FROM artists LIMIT 4
-- obtains the data for each set of albums
-- corresponding to each artist. 
SELECT * FROM albums WHERE albums.artistid = 1
SELECT * FROM albums WHERE albums.artistid = 2
SELECT * FROM albums WHERE albums.artistid = 3
SELECT * FROM albums WHERE albums.artistid = 4

This approach is in-line with what is known as lazy-loading: each album is queried as we need it. Therefore, each time the inner loop of our method runs it queries the database for the data for the current artist’s albums. I’m not an expert in database optimization, but it isn’t too hard to imagine how slow querying like this could at scale due to database and potentially network latencies. It seems to be a general rule that it is most efficient for an application to obtain data through the fewest possible number of queries. In this instance, the number of queries is equal to N (the number parent artist objects) + 1 (the initial query to obtain the ids of the relevant artists). This represents linear query growth; if we were to ask the program to instead obtain the albums of the first 1,000 artists our program would need to make 1001 queries of the database! This is not a good diagnosis for the performance of our application.

What can we do to optimize the number of queries? In raw SQL, this query can easily be taken care of in two queries with the following code:

-- obtains the data for artists 1-4
SELECT * FROM artists LIMIT 4
SELECT * FROM albums WHERE albums.artistid IN (1, 2, 3, 4)

This code, which adopts the eager-loading paradigm, selects the data for the albums that match any of the first four artist’s ids in one fell swoop. This approach has the benefit of maintaining a constant number of queries as the number of parent artist objects grows. So how can we get ActiveRecord to query our database like this and more importantly how cumbersome will it be?

Thankfully implementing this kind of eager-loading approach in active record is refreshingly when utilizing ActiveRecord’s #includes method. To adapt our earlier code we simply need to make a small addition to the first line of the method’s definition so that our code now looks like this:

def first_four_artists_album_titles
  artists = Artist.includes(:albums).limit(4)

  artists.each do |art|
    art.albums.each do |alb|
      puts alb.title
    end
  end
end

The #includes(:album) invocation in this modified version of the code is all it takes to eliminate the N+1 query problem in our code. It is deceptively simple. In addition to making the query to the database significantly more efficient, this method populates the @association_cache instance variable of each of the four instances of Artist. The @association_cache of these objects is by default an empty hash but when the #includes method is invoked the artist’s albums are added to the cache. Later in our code, when art.albums.each is invoked, the album data is found in the cache and no additional queries to the database need to be made.

I don’t think that #includes will always be a suitable option in my code but I’m extremely glad that I’ve gotten a chance to understand N+1 queries and am now prepared to be vigilant about avoiding them wherever possible.