The N + 1 Problem
It’s Math… And It’s Not
What is N + 1? And why is it a problem? I found this question required a bit of a geeky dive. First I felt I needed to understand a little bit more about relational databases and SQL queries. In addition, I needed a basic refresher of ORMs (Object Relational Mapping). So let’s rewind just a little bit:
According to Manu Ajith, “an ORM framework is written in an object oriented language (like Ruby, Python, PHP etc.) and wrapped around a relational database. The object classes are mapped to the data tables in the database and the object instances are mapped to rows in those tables”.
A relational database is exactly what it sounds like: “A relational database is a collection of data items with pre-defined relationships between them… Each column in a table holds a certain kind of data and a field stores the actual value of an attribute. The rows in the table represent a collection of related values of one object or entity. Each row in a table could be marked with a unique identifier called a primary key, and rows among multiple tables can be made related using foreign keys…”
An ORM framework allows us to more easily interact with the data in our (relational) database, reflective of the way we’ve instantiated our class instances with their various attributes. Active Record is one such ORM framework. It comes “out of the box” with Ruby on Rails. One great perk of Active Record is that it is compatible with many different relational databases. Here are a few others, again as per Manu Ajith:
- Data is represented as models.
- Associations can be implemented using these models.
- Inheritance can be achieved through related models.
- Validation of data before being saved into the database.
- Object oriented way of dealing with database operations.
One other big advantage is that Active Record takes over the job of performing SQL queries, the more complex of which can be somewhat intimidating (INNER JOIN… or LEFT OUTER JOIN?? um, no thanks). For anyone who doesn’t “know” SQL, here is a description via our friends at W3 Schools:
- SQL stands for Structured Query Language
- SQL lets you access and manipulate databases
- SQL became a standard of the American National Standards Institute (ANSI) in 1986, and of the International Organization for Standardization (ISO) in 1987
✴️ Note: The most basic SQL commands are actually pretty easy and interesting to explore, W3Schools has a cool interactive tutorial for anyone who wants to get their feet a little bit wet.
So. Back to that dastardly N + 1 and it’s inherent… problem. If we have a database of students and we want to query their report card history, we would have N number of queries (one for each student => their report cards), plus 1 query for Student.all. If the school was a small one (Marlboro College in VT has 192 students enrolled*), this is what the Ruby code and corresponding SQL queries might look like:
Student.all.map { |student| student.report_card }.flatten
In this case, N = 192. Which isn’t great but isn’t terrible. But the University of Central FL boasts 59,483 students.* When N = 59,483… that is a lot of queries! We always want to minimize the number of database queries for optimal performance and page loading.
Happily, Active Record provides us with an easy solution to the too-many-queries problem: “Active Record lets you specify in advance all the associations that are going to be loaded. This is possible by specifying the includes method of the Model.find call. With includes, Active Record ensures that all of the specified associations are loaded using the minimum possible number of queries.”
Using .includes, the Ruby code would look like this: Student.includes(:report_cards).map { |student| student.report_card }.flatten
And there would only be 2 SQL queries associated. DB optimized! ✅
Under the hood, Active Record is employing a technique called eager loading. As per the Ruby on Rails Guide: “Eager loading is the mechanism for loading the associated records of the objects returned by Model.find using as few queries as possible.” If you’re interested to learn more of what happens behind the scenes, here is a really terrific article that takes a deeper dive into both the problem and the solution, including what looks to me like the equivalent of time complexity (linear time!) for N + 1 SQL queries, and how Active Record uses eager loading by caching data.
For my purposes, I’m just happy to know why we use .includes in our Rails controllers for the Classes that “have many things”. Using .includes would produce 2 SQL queries, one for Activity.all, and one for all user_activities. No N + 1 Problem here!!
*Student data from US News & World Report
