What is the "N+1 selects problem" in ORM (Object-Relational Mapping)?

Asked 2023-09-20 20:54:28 View 59,678

The "N+1 selects problem" is generally stated as a problem in Object-Relational mapping (ORM) discussions, and I understand that it has something to do with having to make a lot of database queries for something that seems simple in the object world.

Does anybody have a more detailed explanation of the problem?

Answers

Let's say you have a collection of Car objects (database rows), and each Car has a collection of Wheel objects (also rows). In other words, CarWheel is a 1-to-many relationship.

Now, let's say you need to iterate through all the cars, and for each one, print out a list of the wheels. The naive O/R implementation would do the following:

SELECT * FROM Cars;

And then for each Car:

SELECT * FROM Wheel WHERE CarId = ?

In other words, you have one select for the Cars, and then N additional selects, where N is the total number of cars.

Alternatively, one could get all wheels and perform the lookups in memory:

SELECT * FROM Wheel;

This reduces the number of round-trips to the database from N+1 to 2. Most ORM tools give you several ways to prevent N+1 selects.

Reference: Java Persistence with Hibernate, chapter 13.

Answered   2023-09-20 20:54:28

  • To clarify on the "This is bad" - you could get all the wheels with 1 select (SELECT * from Wheel;), instead of N+1. With a large N, the performance hit can be very significant. - anyone
  • @tucuxi I'm surprised you got so many upvotes for being wrong. A database is very good about indexes, doing the query for a specific CarID would return very fast. But if you got all the Wheels are once, you would have to search for CarID in your application, which is not indexed, this is slower. Unless you have major latency issues reaching your database going n + 1 is actually faster - and yes, I benchmarked it with a large variety of real world code. - anyone
  • @ariel The 'correct' way is to get all the wheels, ordered by CarId (1 select), and if more details than the CarId are required, make a second query for all cars (2 queries total). Printing things out is now optimal, and no indexes or secondary storage were required (you can iterate over results, no need to download them all). You benchmarked the wrong thing. If you are still confident of your benchmarks, would you mind posting a longer comment (or a full answer) explaining your experiment and results? - anyone
  • "Hibernate (I'm not familiar with the other ORM frameworks) gives you several ways to handle it." and these way are? - anyone
  • @Ariel Try running your benchmarks with database and application servers on separate machines. In my experience, round trips to the database cost more in overhead than the query itself. So yes, the queries are really fast, but it's the round trips that wreak havok. I've converted "WHERE Id = const" to "WHERE Id IN (const, const, ...)" and gotten orders of magnitude increases out of it. - anyone

What is the N+1 query problem

The N+1 query problem happens when the data access framework executed N additional SQL statements to fetch the same data that could have been retrieved when executing the primary SQL query.

The larger the value of N, the more queries will be executed, the larger the performance impact. And, unlike the slow query log that can help you find slow running queries, the N+1 issue won’t be spotted because each individual additional query runs sufficiently fast to not trigger the slow query log.

The problem is executing a large number of additional queries that, overall, take sufficient time to slow down response time.

Let’s consider we have the following post and post_comments database tables which form a one-to-many table relationship:

The post and post_comments tables

We are going to create the following 4 post rows:

INSERT INTO post (title, id)
VALUES ('High-Performance Java Persistence - Part 1', 1)
 
INSERT INTO post (title, id)
VALUES ('High-Performance Java Persistence - Part 2', 2)
 
INSERT INTO post (title, id)
VALUES ('High-Performance Java Persistence - Part 3', 3)
 
INSERT INTO post (title, id)
VALUES ('High-Performance Java Persistence - Part 4', 4)

And, we will also create 4 post_comment child records:

INSERT INTO post_comment (post_id, review, id)
VALUES (1, 'Excellent book to understand Java Persistence', 1)
 
INSERT INTO post_comment (post_id, review, id)
VALUES (2, 'Must-read for Java developers', 2)
 
INSERT INTO post_comment (post_id, review, id)
VALUES (3, 'Five Stars', 3)
 
INSERT INTO post_comment (post_id, review, id)
VALUES (4, 'A great reference book', 4)

N+1 query problem with plain SQL

If you select the post_comments using this SQL query:

List<Tuple> comments = entityManager.createNativeQuery("""
    SELECT
        pc.id AS id,
        pc.review AS review,
        pc.post_id AS postId
    FROM post_comment pc
    """, Tuple.class)
.getResultList();

And, later, you decide to fetch the associated post title for each post_comment:

for (Tuple comment : comments) {
    String review = (String) comment.get("review");
    Long postId = ((Number) comment.get("postId")).longValue();
 
    String postTitle = (String) entityManager.createNativeQuery("""
        SELECT
            p.title
        FROM post p
        WHERE p.id = :postId
        """)
    .setParameter("postId", postId)
    .getSingleResult();
 
    LOGGER.info(
        "The Post '{}' got this review '{}'",
        postTitle,
        review
    );
}

You are going to trigger the N+1 query issue because, instead of one SQL query, you executed 5 (1 + 4):

SELECT
    pc.id AS id,
    pc.review AS review,
    pc.post_id AS postId
FROM post_comment pc
 
SELECT p.title FROM post p WHERE p.id = 1
-- The Post 'High-Performance Java Persistence - Part 1' got this review
-- 'Excellent book to understand Java Persistence'
    
SELECT p.title FROM post p WHERE p.id = 2
-- The Post 'High-Performance Java Persistence - Part 2' got this review
-- 'Must-read for Java developers'
     
SELECT p.title FROM post p WHERE p.id = 3
-- The Post 'High-Performance Java Persistence - Part 3' got this review
-- 'Five Stars'
     
SELECT p.title FROM post p WHERE p.id = 4
-- The Post 'High-Performance Java Persistence - Part 4' got this review
-- 'A great reference book'

Fixing the N+1 query issue is very easy. All you need to do is extract all the data you need in the original SQL query, like this:

List<Tuple> comments = entityManager.createNativeQuery("""
    SELECT
        pc.id AS id,
        pc.review AS review,
        p.title AS postTitle
    FROM post_comment pc
    JOIN post p ON pc.post_id = p.id
    """, Tuple.class)
.getResultList();
 
for (Tuple comment : comments) {
    String review = (String) comment.get("review");
    String postTitle = (String) comment.get("postTitle");
 
    LOGGER.info(
        "The Post '{}' got this review '{}'",
        postTitle,
        review
    );
}

This time, only one SQL query is executed to fetch all the data we are further interested in using.

N+1 query problem with JPA and Hibernate

When using JPA and Hibernate, there are several ways you can trigger the N+1 query issue, so it’s very important to know how you can avoid these situations.

For the next examples, consider we are mapping the post and post_comments tables to the following entities:

Post and PostComment entities

The JPA mappings look like this:

@Entity(name = "Post")
@Table(name = "post")
public class Post {
 
    @Id
    private Long id;
 
    private String title;
 
    //Getters and setters omitted for brevity
}
 
@Entity(name = "PostComment")
@Table(name = "post_comment")
public class PostComment {
 
    @Id
    private Long id;
 
    @ManyToOne
    private Post post;
 
    private String review;
 
    //Getters and setters omitted for brevity
}

FetchType.EAGER

Using FetchType.EAGER either implicitly or explicitly for your JPA associations is a bad idea because you are going to fetch way more data that you need. More, the FetchType.EAGER strategy is also prone to N+1 query issues.

Unfortunately, the @ManyToOne and @OneToOne associations use FetchType.EAGER by default, so if your mappings look like this:

@ManyToOne
private Post post;

You are using the FetchType.EAGER strategy, and, every time you forget to use JOIN FETCH when loading some PostComment entities with a JPQL or Criteria API query:

List<PostComment> comments = entityManager
.createQuery("""
    select pc
    from PostComment pc
    """, PostComment.class)
.getResultList();

You are going to trigger the N+1 query issue:

SELECT 
    pc.id AS id1_1_, 
    pc.post_id AS post_id3_1_, 
    pc.review AS review2_1_ 
FROM 
    post_comment pc

SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 1
SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 2
SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 3
SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 4

Notice the additional SELECT statements that are executed because the post association has to be fetched prior to returning the List of PostComment entities.

Unlike the default fetch plan, which you are using when calling the find method of the EntityManager, a JPQL or Criteria API query defines an explicit plan that Hibernate cannot change by injecting a JOIN FETCH automatically. So, you need to do it manually.

If you didn't need the post association at all, you are out of luck when using FetchType.EAGER because there is no way to avoid fetching it. That's why it's better to use FetchType.LAZY by default.

But, if you wanted to use post association, then you can use JOIN FETCH to avoid the N+1 query problem:

List<PostComment> comments = entityManager.createQuery("""
    select pc
    from PostComment pc
    join fetch pc.post p
    """, PostComment.class)
.getResultList();

for(PostComment comment : comments) {
    LOGGER.info(
        "The Post '{}' got this review '{}'", 
        comment.getPost().getTitle(), 
        comment.getReview()
    );
}

This time, Hibernate will execute a single SQL statement:

SELECT 
    pc.id as id1_1_0_, 
    pc.post_id as post_id3_1_0_, 
    pc.review as review2_1_0_, 
    p.id as id1_0_1_, 
    p.title as title2_0_1_ 
FROM 
    post_comment pc 
INNER JOIN 
    post p ON pc.post_id = p.id
    
-- The Post 'High-Performance Java Persistence - Part 1' got this review 
-- 'Excellent book to understand Java Persistence'

-- The Post 'High-Performance Java Persistence - Part 2' got this review 
-- 'Must-read for Java developers'

-- The Post 'High-Performance Java Persistence - Part 3' got this review 
-- 'Five Stars'

-- The Post 'High-Performance Java Persistence - Part 4' got this review 
-- 'A great reference book'

FetchType.LAZY

Even if you switch to using FetchType.LAZY explicitly for all associations, you can still bump into the N+1 issue.

This time, the post association is mapped like this:

@ManyToOne(fetch = FetchType.LAZY)
private Post post;

Now, when you fetch the PostComment entities:

List<PostComment> comments = entityManager
.createQuery("""
    select pc
    from PostComment pc
    """, PostComment.class)
.getResultList();

Hibernate will execute a single SQL statement:

SELECT 
    pc.id AS id1_1_, 
    pc.post_id AS post_id3_1_, 
    pc.review AS review2_1_ 
FROM 
    post_comment pc

But, if afterward, you are going to reference the lazy-loaded post association:

for(PostComment comment : comments) {
    LOGGER.info(
        "The Post '{}' got this review '{}'", 
        comment.getPost().getTitle(), 
        comment.getReview()
    );
}

You will get the N+1 query issue:

SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 1
-- The Post 'High-Performance Java Persistence - Part 1' got this review 
-- 'Excellent book to understand Java Persistence'

SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 2
-- The Post 'High-Performance Java Persistence - Part 2' got this review 
-- 'Must-read for Java developers'

SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 3
-- The Post 'High-Performance Java Persistence - Part 3' got this review 
-- 'Five Stars'

SELECT p.id AS id1_0_0_, p.title AS title2_0_0_ FROM post p WHERE p.id = 4
-- The Post 'High-Performance Java Persistence - Part 4' got this review 
-- 'A great reference book'

Because the post association is fetched lazily, a secondary SQL statement will be executed when accessing the lazy association in order to build the log message.

Again, the fix consists in adding a JOIN FETCH clause to the JPQL query:

List<PostComment> comments = entityManager.createQuery("""
    select pc
    from PostComment pc
    join fetch pc.post p
    """, PostComment.class)
.getResultList();

for(PostComment comment : comments) {
    LOGGER.info(
        "The Post '{}' got this review '{}'", 
        comment.getPost().getTitle(), 
        comment.getReview()
    );
}

And, just like in the FetchType.EAGER example, this JPQL query will generate a single SQL statement.

Even if you are using FetchType.LAZY and don't reference the child association of a bidirectional @OneToOne JPA relationship, you can still trigger the N+1 query issue.

How to automatically detect the N+1 query issue

If you want to automatically detect N+1 query issue in your data access layer, you can use the db-util open-source project.

First, you need to add the following Maven dependency:

<dependency>
    <groupId>com.vladmihalcea</groupId>
    <artifactId>db-util</artifactId>
    <version>${db-util.version}</version>
</dependency>

Afterward, you just have to use SQLStatementCountValidator utility to assert the underlying SQL statements that get generated:

SQLStatementCountValidator.reset();

List<PostComment> comments = entityManager.createQuery("""
    select pc
    from PostComment pc
    """, PostComment.class)
.getResultList();

SQLStatementCountValidator.assertSelectCount(1);

In case you are using FetchType.EAGER and run the above test case, you will get the following test case failure:

SELECT 
    pc.id as id1_1_, 
    pc.post_id as post_id3_1_, 
    pc.review as review2_1_ 
FROM 
    post_comment pc

SELECT p.id as id1_0_0_, p.title as title2_0_0_ FROM post p WHERE p.id = 1

SELECT p.id as id1_0_0_, p.title as title2_0_0_ FROM post p WHERE p.id = 2


-- SQLStatementCountMismatchException: Expected 1 statement(s) but recorded 3 instead!

Answered   2023-09-20 20:54:28

  • But now you have a problem with pagination. If you have 10 cars, each car with 4 wheels and you want to paginate cars with 5 cars per page. So you basically you have SELECT cars, wheels FROM cars JOIN wheels LIMIT 0, 5. But what you get is 2 cars with 5 wheels (first car with all 4 wheels and second car with only 1 wheel), because LIMIT will limit the entire resultset, not only root clause. - anyone
  • Thank you for article. I will read it. By fast scroll - I saw that solution is Window Function, but they are fairly new in MariaDB - so the problem persist in older versions. :) - anyone
  • @VladMicalcea could Entity Graph be used instead of join fetch? - anyone
  • Thanks for the answer, it cleared things. This could have been accepted answer :) - anyone
  • @catch23, I think this can be helpful. - anyone
SELECT 
table1.*
, table2.*
INNER JOIN table2 ON table2.SomeFkId = table1.SomeId

That gets you a result set where child rows in table2 cause duplication by returning the table1 results for each child row in table2. O/R mappers should differentiate table1 instances based on a unique key field, then use all the table2 columns to populate child instances.

SELECT table1.*

SELECT table2.* WHERE SomeFkId = #

The N+1 is where the first query populates the primary object and the second query populates all the child objects for each of the unique primary objects returned.

Consider:

class House
{
    int Id { get; set; }
    string Address { get; set; }
    Person[] Inhabitants { get; set; }
}

class Person
{
    string Name { get; set; }
    int HouseId { get; set; }
}

and tables with a similar structure. A single query for the address "22 Valley St" may return:

Id Address      Name HouseId
1  22 Valley St Dave 1
1  22 Valley St John 1
1  22 Valley St Mike 1

The O/RM should fill an instance of Home with ID=1, Address="22 Valley St" and then populate the Inhabitants array with People instances for Dave, John, and Mike with just one query.

A N+1 query for the same address used above would result in:

Id Address
1  22 Valley St

with a separate query like

SELECT * FROM Person WHERE HouseId = 1

and resulting in a separate data set like

Name    HouseId
Dave    1
John    1
Mike    1

and the final result being the same as above with the single query.

The advantages to single select is that you get all the data up front which may be what you ultimately desire. The advantages to N+1 is query complexity is reduced and you can use lazy loading where the child result sets are only loaded upon first request.

Answered   2023-09-20 20:54:28

  • The other advantage of n + 1 is that it's faster because the database can return the results directly from an index. Doing the join and then sorting requires a temp table, which is slower. The only reason to avoid n + 1 is if you have a lot of latency talking to your database. - anyone
  • Joining and sorting can be quite fast (because you will be joining on indexed-and-possibly-sorted fields). How big is your 'n+1'? Do you seriously believe that the n+1 problem only applies to high-latency database connections? - anyone
  • @ariel - Your advice that N+1 is the "fastest" is wrong, even though your benchmarks may be correct. How is that possible? See en.wikipedia.org/wiki/Anecdotal_evidence, and also my comment in the other answer to this question. - anyone
  • @Ariel - I think I understood it fine :). I'm just trying to point out that your result only applies to one set of conditions. I could easily construct a counter example that showed the opposite. Does that make sense? - anyone
  • To reiterate, the SELECT N + 1 problem is, at its core: I have 600 records to retrieve. Is it faster to get all 600 of them in one query, or 1 at a time in 600 queries. Unless you're on MyISAM and/or you have a poorly normalized/poorly indexed schema (in which case the ORM isn't the problem), a properly tuned db will return the 600 rows in 2 ms, while returning the individual rows in about 1 ms each. So we often see N + 1 taking hundreds of milliseconds where a join takes only a couple - anyone

Supplier with a one-to-many relationship with Product. One Supplier has (supplies) many Products.

***** Table: Supplier *****
+-----+-------------------+
| ID  |       NAME        |
+-----+-------------------+
|  1  |  Supplier Name 1  |
|  2  |  Supplier Name 2  |
|  3  |  Supplier Name 3  |
|  4  |  Supplier Name 4  |
+-----+-------------------+

***** Table: Product *****
+-----+-----------+--------------------+-------+------------+
| ID  |   NAME    |     DESCRIPTION    | PRICE | SUPPLIERID |
+-----+-----------+--------------------+-------+------------+
|1    | Product 1 | Name for Product 1 |  2.0  |     1      |
|2    | Product 2 | Name for Product 2 | 22.0  |     1      |
|3    | Product 3 | Name for Product 3 | 30.0  |     2      |
|4    | Product 4 | Name for Product 4 |  7.0  |     3      |
+-----+-----------+--------------------+-------+------------+

Factors:

  • Lazy mode for Supplier set to “true” (default)

  • Fetch mode used for querying on Product is Select

  • Fetch mode (default): Supplier information is accessed

  • Caching does not play a role for the first time the

  • Supplier is accessed

Fetch mode is Select Fetch (default)

// It takes Select fetch mode as a default
Query query = session.createQuery( "from Product p");
List list = query.list();
// Supplier is being accessed
displayProductsListWithSupplierName(results);

select ... various field names ... from PRODUCT
select ... various field names ... from SUPPLIER where SUPPLIER.id=?
select ... various field names ... from SUPPLIER where SUPPLIER.id=?
select ... various field names ... from SUPPLIER where SUPPLIER.id=?

Result:

  • 1 select statement for Product
  • N select statements for Supplier

This is N+1 select problem!

Answered   2023-09-20 20:54:28

  • Is it supposed to be 1 select for the Supplier then N selects for the Product? - anyone
  • @bencampbell_ Yeah, initially I felt the same. But then with his example, it is One product to many suppliers. - anyone
  • So basically, it's 1 query for the child and N query for the parent. Please correct me if I am wrong! - anyone

I can't comment directly on other answers, because I don't have enough reputation. But it's worth noting that the problem essentially only arises because, historically, a lot of dbms have been quite poor when it comes to handling joins (MySQL being a particularly noteworthy example). So n+1 has, often, been notably faster than a join. And then there are ways to improve on n+1 but still without needing a join, which is what the original problem relates to.

However, MySQL is now a lot better than it used to be when it comes to joins. When I first learned MySQL, I used joins a lot. Then I discovered how slow they are, and switched to n+1 in the code instead. But, recently, I've been moving back to joins, because MySQL is now a heck of a lot better at handling them than it was when I first started using it.

These days, a simple join on a properly indexed set of tables is rarely a problem, in performance terms. And if it does give a performance hit, then the use of index hints often solves them.

This is discussed here by one of the MySQL development team:

http://jorgenloland.blogspot.co.uk/2013/02/dbt-3-q3-6-x-performance-in-mysql-5610.html

So the summary is: If you've been avoiding joins in the past because of MySQL's abysmal performance with them, then try again on the latest versions. You'll probably be pleasantly surprised.

Answered   2023-09-20 20:54:28

  • Calling early versions of MySQL a relational DBMS is quite a stretch... If people encountering those problems had been using a real database, they would not have encountered those kinds of problems. ;-) - anyone
  • Interestingly, many of these types of problems were solved in MySQL with the introduction and subsequent optimization of the INNODB engine, but you'll still run into people trying to promote MYISAM because they think it's faster. - anyone
  • FYI, one of the 3 common JOIN algorithms used in RDBMS' is called nested loops. It fundamentally is an N+1 select under the hood. The only difference is the DB made an intelligent choice to use it based off statistics and indexes, rather than client code forcing it down that path categorically. - anyone
  • @Brandon Yes! Much like JOIN hints and INDEX hints, forcing a certain execution path in all cases will rarely beat the database. The database is almost always very, very good at choosing the optimal approach to get the data. Maybe in the early days of dbs you needed to 'phrase' your question in a peculiar way to coax the db along, but after decades of world class engineering, you can now get the best performance by asking your database a relational question and letting it sort out how to fetch and assemble that data for you. - anyone
  • Not only is the database utilizing indexes and statistics, all of the operations are also local I/O, much of which is often operating against highly efficient cache rather than disk. The database programmers devote an awful lot of attention to optimizing these sorts of things. - anyone

A good explanation of the problem can be found in the Phabricator documentation

TL;DR

It is much faster to issue 1 query which returns 100 results than to issue 100 queries which each return 1 result.

Load all your data before iterating through it.

More in-detail

The N+1 query problem is a common performance antipattern. It looks like this:

$cats = load_cats();
foreach ($cats as $cat) {
   $cats_hats => load_hats_for_cat($cat);
   // ...
}

Assuming load_cats() has an implementation that boils down to:

SELECT * FROM cat WHERE ...

..and load_hats_for_cat($cat) has an implementation something like this:

SELECT * FROM hat WHERE catID = ...

..you will issue "N+1" queries when the code executes, where N is the number of cats:

SELECT * FROM cat WHERE ...
SELECT * FROM hat WHERE catID = 1
SELECT * FROM hat WHERE catID = 2
SELECT * FROM hat WHERE catID = 3
SELECT * FROM hat WHERE catID = 4
...

Answered   2023-09-20 20:54:28

  • Best explaining answer in short. - anyone

We moved away from the ORM in Django because of this problem. Basically, if you try and do

for p in person:
    print p.car.colour

The ORM will happily return all people (typically as instances of a Person object), but then it will need to query the car table for each Person.

A simple and very effective approach to this is something I call "fanfolding", which avoids the nonsensical idea that query results from a relational database should map back to the original tables from which the query is composed.

Step 1: Wide select

  select * from people_car_colour; # this is a view or sql function

This will return something like

  p.id | p.name | p.telno | car.id | car.type | car.colour
  -----+--------+---------+--------+----------+-----------
  2    | jones  | 2145    | 77     | ford     | red
  2    | jones  | 2145    | 1012   | toyota   | blue
  16   | ashby  | 124     | 99     | bmw      | yellow

Step 2: Objectify

Suck the results into a generic object creator with an argument to split after the third item. This means that "jones" object won't be made more than once.

Step 3: Render

for p in people:
    print p.car.colour # no more car queries

See this web page for an implementation of fanfolding for python.

Answered   2023-09-20 20:54:28

  • i'm so glad i stumbled on your post, because i thought i was going crazy. when i found out about the N+1 problem, my immediate thought was- well, why don't you just create a view that contains all the information you need, and pull from that view? you have validated my position. thank you sir. - anyone
  • We moved away from the ORM in Django because of this problem. Huh? Django has select_related, which is meant to solve this - in fact, its docs start with an example similar to your p.car.colour example. - anyone
  • This is an old anwswer, we have select_related() and prefetch_related() in Django now. - anyone
  • Cool. But select_related() and friend don't seem to do any of the obviously useful extrapolations of a join such as LEFT OUTER JOIN. The problem isn't an interface problem, but an issue to do with the strange idea that objects and relational data are mappable....in my view. - anyone

Suppose you have COMPANY and EMPLOYEE. COMPANY has many EMPLOYEES (i.e. EMPLOYEE has a field COMPANY_ID).

In some O/R configurations, when you have a mapped Company object and go to access its Employee objects, the O/R tool will do one select for every employee, wheras if you were just doing things in straight SQL, you could select * from employees where company_id = XX. Thus N (# of employees) plus 1 (company)

This is how the initial versions of EJB Entity Beans worked. I believe things like Hibernate have done away with this, but I'm not too sure. Most tools usually include info as to their strategy for mapping.

Answered   2023-09-20 20:54:28

Here's a good description of the problem

Now that you understand the problem it can typically be avoided by doing a join fetch in your query. This basically forces the fetch of the lazy loaded object so the data is retrieved in one query instead of n+1 queries. Hope this helps.

Answered   2023-09-20 20:54:28

Check Ayende post on the topic: Combating the Select N + 1 Problem In NHibernate.

Basically, when using an ORM like NHibernate or EntityFramework, if you have a one-to-many (master-detail) relationship, and want to list all the details per each master record, you have to make N + 1 query calls to the database, "N" being the number of master records: 1 query to get all the master records, and N queries, one per master record, to get all the details per master record.

More database query calls → more latency time → decreased application/database performance.

However, ORMs have options to avoid this problem, mainly using JOINs.

Answered   2023-09-20 20:54:28

  • joins are not a good solution (often), because they may result in a cartesian product, meaning the number of result rows is the number of root table results multiplied with the number of results in each child table. particularly bad over multiple herarchy levels. Selecting 20 "blogs" with 100 "posts" on each and 10 "comments" on each post will result in 20000 result rows. NHibernate has workarounds, like the "batch-size" (select children with in clause on parent ids) or "subselect". - anyone

In my opinion the article written in Hibernate Pitfall: Why Relationships Should Be Lazy is exactly opposite of real N+1 issue is.

If you need correct explanation please refer Hibernate - Chapter 19: Improving Performance - Fetching Strategies

Select fetching (the default) is extremely vulnerable to N+1 selects problems, so we might want to enable join fetching

Answered   2023-09-20 20:54:28

  • i read the hibernate page. It doesn't say what the N+1 selects problem actually is. But it says you can use joins to fix it. - anyone
  • batch-size is required for select fetching, to select child objects for multiple parents in one select statement. Subselect could be another alternative. Joins can get really bad if you have multiple hierarchy levels and a cartesian product is created. - anyone

The supplied link has a very simply example of the n + 1 problem. If you apply it to Hibernate it's basically talking about the same thing. When you query for an object, the entity is loaded but any associations (unless configured otherwise) will be lazy loaded. Hence one query for the root objects and another query to load the associations for each of these. 100 objects returned means one initial query and then 100 additional queries to get the association for each, n + 1.

http://pramatr.com/2009/02/05/sql-n-1-selects-explained/

Answered   2023-09-20 20:54:28

N+1 select issue is a pain, and it makes sense to detect such cases in unit tests. I have developed a small library for verifying the number of queries executed by a given test method or just an arbitrary block of code - JDBC Sniffer

Just add a special JUnit rule to your test class and place annotation with expected number of queries on your test methods:

@Rule
public final QueryCounter queryCounter = new QueryCounter();

@Expectation(atMost = 3)
@Test
public void testInvokingDatabase() {
    // your JDBC or JPA code
}

Answered   2023-09-20 20:54:28

N+1 problem in Hibernate & Spring Data JPA

N+1 problem is a performance issue in Object Relational Mapping that fires multiple select queries (N+1 to be exact, where N = number of records in table) in database for a single select query at application layer. Hibernate & Spring Data JPA provides multiple ways to catch and address this performance problem.

What is N+1 Problem?

To understand N+1 problem, lets consider with a scenario. Let’s say we have a collection of User objects mapped to DB_USER table in database, and each user has collection or Role mapped to DB_ROLE table using a joining table DB_USER_ROLE. At the ORM level a User has many to many relationship with Role.

Entity Model
@Entity
@Table(name = "DB_USER")
public class User {

    @Id
    @GeneratedValue(strategy=GenerationType.AUTO)
    private Long id;
    private String name;

    @ManyToMany(fetch = FetchType.LAZY)                   
    private Set<Role> roles;
    //Getter and Setters 
 }

@Entity
@Table(name = "DB_ROLE")
public class Role {

    @Id
    @GeneratedValue(strategy= GenerationType.AUTO)
    private Long id;

    private String name;
    //Getter and Setters
 }

A user can have many roles. Roles are loaded Lazily. Now lets say we want to fetch all users from this table and print roles for each one. Very naive Object Relational implementation could be - UserRepository with findAllBy method

public interface UserRepository extends CrudRepository<User, Long> {

    List<User> findAllBy();
}

The equivalent SQL queries executed by ORM will be:

First Get All User (1)

Select * from DB_USER;

Then get roles for each user executed N times (where N is number of users)

Select * from DB_USER_ROLE where userid = <userid>;

So we need one select for User and N additional selects for fetching roles for each user, where N is total number of users. This is a classic N+1 problem in ORM.

How to identify it?

Hibernate provide tracing option that enables SQL logging in the console/logs. using logs you can easily see if hibernate is issuing N+1 queries for a given call.

If you see multiple entries for SQL for a given select query, then there are high chances that its due to N+1 problem.

N+1 Resolution

At SQL level, what ORM needs to achieve to avoid N+1 is to fire a query that joins the two tables and get the combined results in single query.

Fetch Join SQL that retrieves everything (user and roles) in Single Query

OR Plain SQL

select user0_.id, role2_.id, user0_.name, role2_.name, roles1_.user_id, roles1_.roles_id from db_user user0_ left outer join db_user_roles roles1_ on user0_.id=roles1_.user_id left outer join db_role role2_ on roles1_.roles_id=role2_.id

Hibernate & Spring Data JPA provide mechanism to solve the N+1 ORM issue.

1. Spring Data JPA Approach:

If we are using Spring Data JPA, then we have two options to achieve this - using EntityGraph or using select query with fetch join.

public interface UserRepository extends CrudRepository<User, Long> {

    List<User> findAllBy();             

    @Query("SELECT p FROM User p LEFT JOIN FETCH p.roles")  
    List<User> findWithoutNPlusOne();

    @EntityGraph(attributePaths = {"roles"})                
    List<User> findAll();
}

N+1 queries are issued at database level using left join fetch, we resolve the N+1 problem using attributePaths, Spring Data JPA avoids N+1 problem

2. Hibernate Approach:

If its pure Hibernate, then the following solutions will work.

Using HQL :

from User u *join fetch* u.roles roles roles

Using Criteria API:

Criteria criteria = session.createCriteria(User.class);
criteria.setFetchMode("roles", FetchMode.EAGER);

All these approaches work similar and they issue a similar database query with left join fetch

Answered   2023-09-20 20:54:28

The issue as others have stated more elegantly is that you either have a Cartesian product of the OneToMany columns or you're doing N+1 Selects. Either possible gigantic resultset or chatty with the database, respectively.

I'm surprised this isn't mentioned but this how I have gotten around this issue... I make a semi-temporary ids table. I also do this when you have the IN () clause limitation.

This doesn't work for all cases (probably not even a majority) but it works particularly well if you have a lot of child objects such that the Cartesian product will get out of hand (ie lots of OneToMany columns the number of results will be a multiplication of the columns) and its more of a batch like job.

First you insert your parent object ids as batch into an ids table. This batch_id is something we generate in our app and hold onto.

INSERT INTO temp_ids 
    (product_id, batch_id)
    (SELECT p.product_id, ? 
    FROM product p ORDER BY p.product_id
    LIMIT ? OFFSET ?);

Now for each OneToMany column you just do a SELECT on the ids table INNER JOINing the child table with a WHERE batch_id= (or vice versa). You just want to make sure you order by the id column as it will make merging result columns easier (otherwise you will need a HashMap/Table for the entire result set which may not be that bad).

Then you just periodically clean the ids table.

This also works particularly well if the user selects say 100 or so distinct items for some sort of bulk processing. Put the 100 distinct ids in the temporary table.

Now the number of queries you are doing is by the number of OneToMany columns.

Answered   2023-09-20 20:54:28

Without going into tech stack implementation details, architecturally speaking there are at least two solutions to N + 1 Problem:

  • Have Only 1 - big query - with Joins. This makes a lot of information be transported from the database to the application layer, especially if there are multiple child records. The typical result of a database is a set of rows, not graph of objects (there are solutions to that with different DB systems)
  • Have Two(or more for more children needed to be joined) Queries - 1 for the parent and after you have them - query by IDs the children and map them. This will minimize data transfer between the DB and APP layers.

Answered   2023-09-20 20:54:28

  • A brief and clear answer at last. - anyone

A generalisation of N+1

The N+1 problem is an ORM specific name of a problem where you move loops that could be reasonably executed on a server to the client. The generic problem isn't specific to ORMs, you can have it with any remote API. In this article, I've shown how JDBC roundtrips are very costly, if you're calling an API N times instead of only 1 time. The difference in the example is whether you're calling the Oracle PL/SQL procedure:

  • dbms_output.get_lines (call it once, receive N items)
  • dbms_output.get_line (call it N times, receive 1 item each time)

They're logically equivalent, but due to the latency between server and client, you're adding N latency waits to your loop, instead of waiting only once.

The ORM case

In fact, the ORM-y N+1 problem isn't even ORM specific either, you can achieve it by running your own queries manually as well, e.g. when you do something like this in PL/SQL:

-- This loop is executed once
for parent in (select * from parent) loop

  -- This loop is executed N times
  for child in (select * from child where parent_id = parent.id) loop
    ...
  end loop;
end loop;

It would be much better to implement this using a join (in this case):

for rec in (
  select *
  from parent p
  join child c on c.parent_id = p.id
)
loop
  ...
end loop;

Now, the loop is executed only once, and the logic of the loop has been moved from the client (PL/SQL) to the server (SQL), which can even optimise it differently, e.g. by running a hash join (O(N)) rather than a nested loop join (O(N log N) with index)

Auto-detecting N+1 problems

If you're using JDBC, you could use jOOQ as a JDBC proxy behind the scenes to auto-detect your N+1 problems. jOOQ's parser normalises your SQL queries and caches data about consecutive executions of parent and child queries. This even works if your queries aren't exactly the same, but semantically equivalent.

Answered   2023-09-20 20:54:28

Take Matt Solnit example, imagine that you define an association between Car and Wheels as LAZY and you need some Wheels fields. This means that after the first select, hibernate is going to do "Select * from Wheels where car_id = :id" FOR EACH Car.

This makes the first select and more 1 select by each N car, that's why it's called n+1 problem.

To avoid this, make the association fetch as eager, so that hibernate loads data with a join.

But attention, if many times you don't access associated Wheels, it's better to keep it LAZY or change fetch type with Criteria.

Answered   2023-09-20 20:54:28

  • Again, joins are not a good solution, especially when more than 2 hierarchy levels may be loaded. Check "subselect" or "batch-size" instead; the last will load children by parent IDs in "in" clause, such as "select ... from wheels where car_id in (1,3,4,6,7,8,11,13)". - anyone

N+1 SELECT problem is really hard to spot, especially in projects with large domain, to the moment when it starts degrading the performance. Even if the problem is fixed i.e. by adding eager loading, a further development may break the solution and/or introduce N+1 SELECT problem again in other places.

I've created open source library jplusone to address those problems in JPA based Spring Boot Java applications. The library provides two major features:

  1. Generates reports correlating SQL statements with executions of JPA operations which triggered them and places in source code of your application which were involved in it
2020-10-22 18:41:43.236 DEBUG 14913 --- [           main] c.a.j.core.report.ReportGenerator        :
    ROOT
        com.adgadev.jplusone.test.domain.bookshop.BookshopControllerTest.shouldGetBookDetailsLazily(BookshopControllerTest.java:65)
        com.adgadev.jplusone.test.domain.bookshop.BookshopController.getSampleBookUsingLazyLoading(BookshopController.java:31)
        com.adgadev.jplusone.test.domain.bookshop.BookshopService.getSampleBookDetailsUsingLazyLoading [PROXY]
            SESSION BOUNDARY
                OPERATION [IMPLICIT]
                    com.adgadev.jplusone.test.domain.bookshop.BookshopService.getSampleBookDetailsUsingLazyLoading(BookshopService.java:35)
                    com.adgadev.jplusone.test.domain.bookshop.Author.getName [PROXY]
                    com.adgadev.jplusone.test.domain.bookshop.Author [FETCHING ENTITY]
                        STATEMENT [READ]
                            select [...] from
                                author author0_
                                left outer join genre genre1_ on author0_.genre_id=genre1_.id
                            where
                                author0_.id=1
                OPERATION [IMPLICIT]
                    com.adgadev.jplusone.test.domain.bookshop.BookshopService.getSampleBookDetailsUsingLazyLoading(BookshopService.java:36)
                    com.adgadev.jplusone.test.domain.bookshop.Author.countWrittenBooks(Author.java:53)
                    com.adgadev.jplusone.test.domain.bookshop.Author.books [FETCHING COLLECTION]
                        STATEMENT [READ]
                            select [...] from
                                book books0_
                            where
                                books0_.author_id=1
  1. Provides API which allows to write tests checking how effectively your application is using JPA (i.e. assert amount of lazy loading operations )
@SpringBootTest
class LazyLoadingTest {

    @Autowired
    private JPlusOneAssertionContext assertionContext;

    @Autowired
    private SampleService sampleService;

    @Test
    public void shouldBusinessCheckOperationAgainstJPlusOneAssertionRule() {
        JPlusOneAssertionRule rule = JPlusOneAssertionRule
                .within().lastSession()
                .shouldBe().noImplicitOperations().exceptAnyOf(exclusions -> exclusions
                        .loadingEntity(Author.class).times(atMost(2))
                        .loadingCollection(Author.class, "books")
                );

        // trigger business operation which you wish to be asserted against the rule,
        // i.e. calling a service or sending request to your API controller
        sampleService.executeBusinessOperation();

        rule.check(assertionContext);
    }
}

Answered   2023-09-20 20:54:28

ORM "N plus one" Problem

The "N plus one" problem is a common performance issue that can occur when using Object-Relational Mapping (ORM) frameworks. ORM frameworks are tools used to map database tables to objects in object-oriented programming languages. This problem arises when retrieving data from a relational database using ORM in a specific way.

To understand the "N plus one" problem, let's consider an example scenario where you have two tables: Customer and Order. Each customer can have multiple orders, and there is a one-to-many relationship between the Customer and Order tables. In ORM, you define these relationships using object-oriented concepts such as classes and references.

Now, let's say you want to retrieve all the customers along with their orders. In ORM, you might use a query like this:

customers = Customer.objects.all()

for customer in customers:
    orders = customer.orders.all()
    # Do something with the orders

In this code, you first retrieve all the customers using Customer.objects.all(). Then, for each customer, you retrieve their orders using customer.orders.all().

The issue with this approach is that it results in multiple queries being executed to the database. For example, if you have 100 customers, this code will execute 101 queries: one to retrieve all the customers and 100 more to retrieve the orders for each customer (hence the name "N plus one" problem). This can significantly impact performance, especially when dealing with large datasets.

The "N plus one" problem arises because the ORM framework performs a separate query for each customer's orders instead of fetching all the necessary data in a single query. This behavior is often the default in ORM frameworks to avoid unnecessarily loading all the associated data, which can be a performance concern in other scenarios.

To mitigate the "N plus one" problem, ORM frameworks usually provide ways to optimize data retrieval, such as eager loading or explicit joins. Eager loading allows you to fetch the required data in a single query, reducing the number of database round-trips. By specifying the relationships you want to include, the ORM framework can generate a more efficient query that retrieves all the necessary data at once.

As a demonstration of the "N plus one" problem and its solution, the following shows the actual SQL emitted from an ORM using SQLAlchemy.

Original ORM query with the N plus one problem (1 query for customers and N for each customer's order):

with Session(engine) as session:
    customers = session.scalars(select(Customer))
    for customer in customers:
        print(f"> Customer: #{customer.customer_id}")
        for order in customer.orders:
            print(f">   order #{order.order_id} at {order.order_datetime}")
-- This query gets all customers:
SELECT customer.customer_id, ...
FROM customer

-- The following SQL is executed once for each customer:
SELECT "order".order_id AS order_order_id, ...
FROM "order"
WHERE "order".customer_id = %(param_1)s

After specifying eager loading (with selectinload()), only 2 queries are required:

with Session(engine) as session:
    customers = session.scalars(
        select(Customer).options(selectinload(Customer.orders)))
    for customer in customers:
        print(f"> Customer: #{customer.customer_id}")
        for order in customer.orders:
            print(f">   order #{order.order_id} at {order.order_datetime}")
SELECT customer.customer_id, ...
FROM customer

-- This loads all the orders you need in one query:
SELECT "order".order_id AS order_order_id, ...
FROM "order"
WHERE "order".customer_id IN (%(primary_keys_1)s, %(primary_keys_2)s, ...)

Or, explicitly join and query the required fields (only 1 query is required):

with Session(engine) as session:
    stmt = (
        select(
            Customer.customer_id,
            Order.order_id,
            Order.order_datetime,
        )
        .select_from(Customer)
        .join(Customer.orders)
        .order_by(Customer.customer_id)
    )
    results = session.execute(stmt)

    current_customer_id = None
    for row in results:
        customer_id = row.customer_id
        if current_customer_id != customer_id:
            current_customer_id = customer_id
            print(f"> Customer: #{current_customer_id}")
        print(f">   order #{row.order_id} at {row.order_datetime}")
SELECT customer.customer_id, "order".order_id, ...
FROM customer
JOIN "order" ON customer.customer_id = "order".customer_id
ORDER BY customer.customer_id

In summary, the "N plus one" problem in ORM occurs when the framework executes multiple queries to retrieve associated data for each item in a collection, resulting in a significant performance overhead. Understanding and addressing this problem by optimizing data retrieval strategies can help improve the efficiency of ORM-based applications.

Answered   2023-09-20 20:54:28