The GraphQL N+1 Problem and SQL Window Functions
Tags: graphql, ruby, rails, webdev
Published: 2022-10-07 19:40:36

A post by Clinton Pahl and Nick Boers, PhD

## Table Of Contents

* [Introduction](#section-1)
* [AssociationLoader and its Drawbacks](#section-2)
* [Background for the SQL Window Loader](#section-3)
* [Aggregate Functions](#section-4)
* [Window Functions](#section-5)
* [Memory-Efficient N+1 Resolution](#section-5)
* [Introducing the WindowLoader](#section-6)
* [Conclusion](#section-7)

## Introduction <a name="section-1"></a>

At Jobber, we're constantly evolving a modern [GraphQL](https://graphql.org/) API to support our Web-based interface, mobile app interfaces, and third-party integrations. GraphQL allows these clients to specify the field structure and data they need in response to API queries. For example, consider the following GraphQL query:

```graphql
query JobVisits {
  jobs {
    nodes {
      visits {
        nodes {
          title
        }
      }
    }
  }
}
```

In this GraphQL query, the client has requested the title for each job visit. The response will contain an array of jobs, and for each job, an array of visits with titles. The structure of the JSON response is similar to the query:

```json
{
  "data": {
    "jobs": {
      "nodes": [
        {
          "visits": {
            "nodes": [
              {
                "title": "Initial Assessment of Property"
              },
              ...
            ]
          }
        },
        ...
      ]
    }
  }
}
```

In our Rails application, we use the popular [graphql](https://graphql-ruby.org/) Ruby gem to resolve GraphQL queries. When used naively, it essentially resolves queries as a depth-first tree traversal, which leads to the N+1 problem in GraphQL.

GraphQL’s N+1 problem, which might be better thought of as the 1+N problem, refers to the number of fetches from a backend data store necessary to resolve a relationship. In the previous example, a single fetch can obtain all of the jobs for an account. After obtaining all of the jobs, a naive resolver fetches the visits for the first job, the visits for the second job, and so on. After one fetch to get all the jobs, N additional fetches get the visits. Given the depth of relationships possible in a GraphQL query, these fetches from the backend data store can quickly balloon and lead to poor performance.

The poor performance will specifically be seen in API response times. Let’s assume the above query returned 100 jobs and that fetching the visits for each job from the database takes 2 ms. In this example, the additional 100 fetches will add 200 ms to the response time for just **one** field.

## `AssociationLoader` and its Drawbacks <a name="section-2"></a>

For the relationships subject to the N+1 problem, the [graphql-batch](https://github.com/Shopify/graphql-batch) Ruby gem and its `AssociationLoader` provide some relief. This gem was developed by Shopify. Using Ruby promises (provided by the [promise.rb](https://rubygems.org/gems/promise.rb) Ruby gem), it fundamentally alters the order of field resolution for GraphQL queries, and in a sense, converts the query from a depth-first traversal to a breadth-first traversal.

As a breadth-first traversal, a call to resolve `visits` for a single job doesn’t actually fetch data for the job’s visits. Instead, it returns a promise. The resolver returns a promise for each call to resolve visits. Once they're all batched, the data can be fetched from the backend in a single operation.

Under the hood, the `AssociationLoader` leverages `::ActiveRecord::Associations::Preloader`. Resolving a field with promises involves collecting all of the records (e.g., jobs) where an association (e.g., visits) needs to be resolved. The Active Record `Preloader` then goes ahead and fetches all of the data in a single data fetch operation. After loading the data, the individual promises are fulfilled using the Active Record data loaded into memory.

Using the `AssociationLoader` and GraphQL Ruby [field extensions](https://graphql-ruby.org/type_definitions/field_extensions.html), developers can easily configure a field to preload the required associations when it's resolved:

```ruby
field :visits, Types::VisitType.connection_type, null: false, preload: :visits
```

Unfortunately, this approach has a weakness as soon as a GraphQL query includes pagination arguments. Consider the following slightly more complicated GraphQL query, which obtains the first three visits for each job.

```graphql
query FirstThreeJobVisits {
  jobs {
    nodes {
      visits(first: 3) {
        nodes {
          title
        }
      }
    }
  }
}
```

In this example, the Active Record `Preloader` can still be used to satisfy the `visits` association for each job. Suppose `jobs` contains all of the jobs, resolving `visits` in a single fetch might involve a call like

```ruby
::ActiveRecord::Associations::Preloader.new.preload(jobs, :visits)
```

Unfortunately, this code will fetch all of the visits for each job, even though the GraphQL response will only include the first three visits for each job. In this approach, the Rails application will need to perform the pagination, and in the process, it fetches unnecessary data from the database, which consume unnecessary memory in the Rails application.

## Background for the SQL Window Loader <a name="section-3"></a>

Our initial solution to preloading was based on the `AssociationLoader`, and it served us well to a point.  It addressed the GraphQL N+1 problem, and it significantly reduced our API response times when compared to not addressing the N+1 problem. Unfortunately, as we increased the use of connection types (with their `first`, `last`, `before`, and `after` arguments), retrieving all associated records from the database only to paginate them in the Rails application was inefficient. For objects with many associated records, it consumes more memory than necessary.

After recognizing the problem, we brainstormed options to offload some of the work onto the database server to ultimately reduce the Rails application’s memory consumption. One particularly promising avenue involved SQL window functions. After deciding to pursue SQL window functions, we started our work by considering the `WindowKeyLoader` [example](https://github.com/Shopify/graphql-batch/blob/master/examples/window_key_loader.rb) described in the [graphql-batch](https://github.com/Shopify/graphql-batch) repository.

Given that many readers may be unfamiliar with SQL window functions, the following subsections provide some background.

### Aggregate Functions <a name="section-4"></a>

An understanding of SQL aggregate functions will help in understanding SQL window functions. Consider  a traditional SQL aggregate function such as `count()`. In a statement involving such an aggregate function, the `GROUP BY` clause groups records, each distinct group becomes a row in the result. The database management system (DBMS) applies the aggregate function to each group’s records to produce the function’s output.

For example, consider the following query:

```sql
SELECT
  account_id,
  count(user_id) AS user_count
FROM
  users
GROUP BY
  account_id
```

This query

1. selects records from the `users` table,
2. groups those records by `account_id` and essentially flattens them so each row in the result has a distinct `account_id`, and
3. computes the field `user_count` for each row in the result by applying the function `count()` to the records in each group.

That (simplified) explanation of the `GROUP BY` clause provides some background for understanding <u>window</u> functions.

### Window Functions <a name="section-5"></a>

When using a window function, records are conceptually grouped only for the context of the function. Those groups are <u>not</u> flattened in the result. The `OVER` clause immediately following the function name will apply the function to a window, and the `OVER` clause itself defines the groups of that window.

For example, consider the following query:

```sql
SELECT
  account_id,
  user_id,
  login_count,
  rank() OVER partition_by_account_id AS user_rank
FROM
  users 
WINDOW partition_by_account_id AS (
  PARTITION BY account_id
  ORDER BY
    login_count DESC
)
```

In this example, the DBMS applies `rank()` to subsets of the records, where `PARTITION BY account_id` defines the subsets. For each unique account ID, the result includes a field `user_rank` with values from 1 to _n_ where _n_ is the number of users for the unique account ID. The users are ranked by the number of times they have logged into the system.

### Memory-Efficient N+1 Resolution <a name="section-6"></a>

Recall the following GraphQL query from earlier, which obtains the first three visits for each job.

```graphql
query FirstThreeJobVisits {
  jobs {
    nodes {
      visits(first: 3) {
        nodes {
          title
        }
      }
    }
  }
}
```

If jobs typically have very few visits, the `AssociationLoader` might be a reasonable solution. If jobs have many visits, it would load many visits from the database that would ultimately be discarded because of the `first: 3` filter.

Using SQL window functions, it’s possible to apply the `first: 3` filter at the query level and load only the necessary records into the Rails application. For example, the following query would only load the first 3 visits for each job.

```sql
SELECT
  numbered_visits.*
FROM (
  SELECT
    *,
    row_number() OVER partition_by_job_id AS row_number
  FROM
    visits
  WHERE
    job_id IN (...)
  WINDOW partition_by_job_id AS (
    PARTITION BY job_id
    ORDER BY id ASC
  )
) AS numbered_visits
WHERE
  row_number <= 3
```

For direct associations (i.e., those where a foreign key links two tables), deriving this SQL is a rather mechanical process. It’s mechanical enough that we created a new `WindowLoader` to make use of SQL window functions for resolving these associations.

## Introducing the `WindowLoader` <a name="section-7"></a>

When data access patterns suggest an SQL window function will improve the performance resolving a field, simply adding our new `window_load` argument to the GraphQL `field` [method](https://graphql-ruby.org/fields/introduction.html) will cause the resolver to use SQL window functions when resolving the field. The new `window_load` argument provides the name of the association, e.g.,

```ruby
module GraphqlSchema
  module Main
    module Types
      class JobType < GraphqlSchema::Common::Types::BaseObject
        ...   
        field :visits, Types::VisitType.connection_type, window_load: :visits
        ...
      end
    end
  end
end
```

In our `BaseField`, derived from the graphql Ruby gem’s `Schema::Field`, the initializer accepts this `window_load` argument. When the argument specifies an association, the `BaseField` constructor adds a custom connection extension to the field (`WindowConnectionExtension`).

Our `WindowConnectionExtension` class inherits from the gem’s `Schema::Field::ConnectionExtension` and `Schema::FieldExtension` classes. This connection extension has two hooks that wrap field resolution: `resolve` and `after_resolve`. The former hook is called to resolve the field, and in this instance, it uses our `WindowLoader` class to obtain a Ruby promise for the resolution of the field. The latter hook is called after field resolution and after the resolution of promises, and in this instance, it uses our `WindowConnection` class.

The former class, `GraphqlSchema::Common::Loaders::WindowLoader`, which inherits from `GraphQL::Batch::Loader`, first records the foreign keys that will need to be used in the SQL query. In response to `.load` calls, it returns promises. To finally resolve the promises, it generates and runs a single SQL query that uses the previously-described window functions. Most developers using this window loader are totally unaware these steps occur behind the scenes.

The latter class, `GraphqlSchema::Common::Pagination::WindowConnection`, which inherits from `GraphQL::Pagination::ArrayConnection`, produces a result with the expected fields for pagination, e.g., cursors and total counts.

## Conclusion <a name="section-8"></a>

Naively using the graphql Ruby gem to resolve GraphQL queries for a Ruby on Rails API leads to an implementation that suffers from GraphQL’s N+1 problem. Iterating on that solution with a gem such as graphql-batch with its `AssociationLoader` can dramatically improve the situation by solving the N+1 problem and significantly reducing API response times. When a GraphQL query accepts arguments for pagination, a solution like the `AssociationLoader` can lead to loading more data than necessary from the database, and as a result, higher than necessary memory consumption in the Rails server. With SQL window functions, it’s possible to offload the pagination onto the database server so that the Rails application does not receive more records than necessary. Given the flexibility of the graphql and graphql-batch gems, it’s possible to create an easy to use interface for loading data using SQL window functions.

## About Jobber 

Our awesome Jobber technology teams span across Payments, Infrastructure, AI/ML, Business Workflows & Communications. We work on cutting edge & modern tech stacks using React, React Native, Ruby on Rails, & GraphQL. 

If you want to be a part of a collaborative work culture, help small home service businesses scale and create a positive impact on our communities, then visit our [careers](https://getjobber.com/about/careers?utm_source=devto&utm_medium=social&utm_campaign=eng_blog) site to learn more!