N+1 Problem

While developing complex architecture in your applications, you often have to handle one-to-many relationships. One of the pitfalls you may face is N+1 problem. Simply, this problem means that for every relationship you will need to execute separate query.

Let's see how we can approach this problem using Laravel Query Builder with MySQL database. For those who are using Eloquent, Jeffrey Way covered it in his Laracasts lessons. However, there are situations when you want to use Query Builder to process this relations.

Let's say we have online store application that handles users orders. We gonna have two tables in our relational schema: Users and Orders.

Table Users will consist of two fields user_id and user_name.

Table Posts will have three fields: order_id, user_id, order_price.

So, for single user we will have multiple orders, which represents one-to-many relationship. In my daily report, I want to see list of all users with all orders they made. In my User model I will have this function:

function getUsersWithOrders()
{
    $users = DB::table('users')->get();

    foreach( $users as $id => $user ) 
    {
        $users[$id]['orders'] = DB::table('orders')->where('user_id',$user['user_id'])->get();
    }

    return $users;
}

Calling this function will produce following output:

{
    "0": {
        "user_id": "1",
        "user_name": "John Doe",
        "orders": [
            {
                "order_id": "1",
                "user_id": "1",
                "order_price": "35.44",
            },
            {
                "order_id": "2",
                "user_id": "1",
                "order_price": "672.26",
            }
        ]
    },
    "1": {
        "user_id": "2",
        "user_name": "Sergey Tsibel",
        "orders": [
            {
                "order_id": "3",
                "user_id": "2",
                "order_price": "430.12",
            },
            {
                "order_id": "4",
                "user_id": "2",
                "order_price": "23.11",
            }
        ]
    }
}

Eventhough, result of this function is correct, we've just created N+1 problem. In our case, for every user, we are making separate request to our database to get list of orders associated with this user. How is this bad? Well, if we will have 5 users, it means we will produce 5 extra queries to our orders table. Doesn't sounds too scary. However, if we will have list of 40,000 users we will produce 200,000 added queries which will drastically decrease performance of our application. Remember this rule: we want to avoid executing queries in a loop. Keeping that in mind, how can we improve our function? By reducing complexity from O(n) to O(2). In other words, we can rewrite our function so that it will execute only 2 queries in any scenario and here is how we do it:

function getUsersWithOrders()
{
    $users = DB::table('users')->lists('user_name','user_id');
    
    $user_ids = array_keys($users);
    //find all orders related to list of our users
    $orders = DB::table('orders')->whereIn('user_id',$user_ids)->get();
    
    foreach( $orders as $order ) 
    {
        $user_id = $order['user_id'];
        //initialize array of orders for each user
        if(!isset($users[$user_id]['orders'])) $users[$user_id]['orders'] = [];
        //push order to that array
        $users[$user_id]['orders'][]= $order;
    }
    return $users;
}

This function will produce exact same output as our older version of it. N+1 problem solved, world saved.

comments powered by Disqus