GraphQL Optimization: It’s More than N+1
GraphQL was introduced to ease the access to backend data for frontend developers. It gives frontend developers the paradigm they need to simplify the specification of the data for their applications. In GraphQL, the developer declaratively specifies what data they want, not how to get it. As experts in the database field, having arrived on the scene at the rise of relational databases and the emergence of object relational extensions, we at StepZen are maniacally focused on bringing the lessons learned from our heritage to the modern world.
Why Optimize?
Besides optimization of data access being core to our DNA, optimization of GraphQL is important to opening up the aperture for rapid frontend development. The obvious optimization opportunity for a GraphQL operation is to minimize the trips to the backend data sources, whether they are databases, REST APIs or other GraphQL APIs.
While GraphQL makes it easier for developers to specify what data they want and gives them autonomy from the owners of the backends to a degree, these backends are likely under the control of another developer, DBA and/or organization who will care about any extraneous load that will be introduced to their backends.
Reducing traffic to the backends can also:
- Reduce cost by reducing the number of calls to a cost-per-call backend system.
- Avoid rate limits for backends.
- Improve the application performance by reducing the latency of the GraphQL endpoint.
The spamming of backends is often referred to as the N+1 problem, when the application makes N requests instead of 1 to retrieve an object’s details or its child entities.
As we will explain, a GraphQL schema gives a performant GraphQL server the context it needs to avoid such spamming, but it also enables many other opportunities for reducing the number of backend system requests, hence it is more than N+1.
The N+1 Problem
Frontend applications often result in a cascade of independent requests to a single backend that iteratively retrieves the application data. For example, an application may receive a list of authors in a single REST API request but may independently and iteratively make further requests, sometimes to the same endpoint, sometimes to different endpoints, to retrieve the information required to display the author’s name, address and rating.
This is a variant of the well-known N+1 database performance antipattern introduced by object/relational mappers. While simplifying the data access for the developer, O/R mappers also encouraged a pattern of spamming the database with a lot of piecemeal requests. Naive implementations would execute queries against the backends exactly as the programmer invoked, but fortunately, O/R mapping engines came up with several strategies for mitigating this pattern.
In the case of web APIs, this problem becomes a bit more obscure because the original endpoint does not return the information the application needs in one call, and different parts of the application may need different slices of data. As performance problems appear, developers may be able to analyze their data access and consolidate backend calls, but they may also need to request different endpoints to do so and then convince a backend developer to provide it. GraphQL alleviates this tension between frontend and backend developers, allowing the developers to request all and only the data they require from a single endpoint. It is then the job of the GraphQL server to recognize the pattern and avoid backend spamming.
More than N+1
While most N+1 solutions center around reducing multiple requests to filling in detail data for a given entity (author name, rating, etc.), or for retrieving all the child objects for a given entity (such as the book details for all of an author’s books), the general principle of making one request instead of many can be applied much more broadly.
A GraphQL operation (request to a GraphQL endpoint) expresses what the frontend developer needs, not how to get it, and is expressed as a selection set of fields, typically with sub-selections.
The selection set can be arbitrarily deep and arbitrarily wide, which allows the frontend developer to fetch the data type needed in a single request from the GraphQL endpoint.
Depth is how deeply nested a returned object may be. For example, consider the following schema:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
type Author { id: ID! name: String genre: String publisher: String rating: Float books: [Book] } type Book { id:ID! title: String auth_id: ID } type Query { author(id: ID!): Author } |
The following selection set’s depth is three:
|
1 |
{author(id:1) { name books { title}} |
Sometimes the depth is limited by the schema, as is the case with our current schema.
However, a GraphQL schema can still be very deep and often recursive. Consider that data about an author may include a list of similar authors. This can be achieved by extending our above schema as follows:
|
1 2 3 |
extend type Author { similar: [Author] } |
Such a schema leads to selection sets that are arbitrarily deep. The optimization opportunity that can be seen from this schema is to recognize when a similar author has been previously retrieved in the traversal of the data. Optimizing in this fashion can also assist in recognizing cycles in the data and avoiding unnecessary deeply nested traversals.
Width is how many fields are selected at a given depth in the selection tree. Width is not limited by the schema but can occur in selections due to aliases. In this trivial example, the width is three at the name level with the same field being selected three times using aliases:
|
1 |
{ author(id:1) { n1:name n2:name n3:name}} |
Width at the top level is a key feature in fulfilling the goal of the frontend developer issuing a single request to fetch the required data, and it leads to arbitrary wide operations. For example, consider the data to display a page with information about a user’s favorite authors in addition to promotions for the current top-selling books and local book signings:
|
1 2 3 4 5 6 |
{ a1: author(id:1) { name birthplace email} a2: author(id:2) { name birthplace email} topSellingBooks { title } authorsOnTour(zip:”94118”) { name birthplace email} } |
A couple of optimization opportunities can be seen in this selection:
- Will fetching author information be a single request to the backend or multiple?
- If authorsOnTour returns authors one and/or two, can the execution for a1 or a2 reuse the work of authorsOnTour?
With the request typically generated, possibly by independent code modules, an application may issue a request with duplicate, or near-duplicate, items. For example, in an operation that selects 20-plus top-level fields, there could be similar items, such as:
|
1 2 3 4 5 6 7 |
{ < other fields > <strong> author_for_popup: author(id:1) { name genre publisher }</strong> < other fields > <strong> main_author: author(id:1) { name books { title } }</strong> < other fields > } |
Can the GraphQL server discover these so that it effectively executes a single backend request corresponding to:
|
1 |
author(id:1) { name genre publisher books {title }} |
With the selection set being arbitrarily deep and wide, you can see now that GraphQL optimization opportunities can exist across the entire selection tree in the operation, not just filling in an entity’s detail for its next level, including across top-level fields (or indeed fields at any level).
The frontend developer should not care about these optimizations. They request the data they need, in the shape they need, potentially with duplicates and expect the correct results.
The GraphQL server can execute the query any way it wants as long as it produces the right results. Just like the early days of SQL, a declarative query can still perform poorly if the runtime for fulfilling the query does not take advantage of the context it has to run the query efficiently.
StepZen’s declarative approach provides that context, such as the relationship of fields to backends and their types (such as database or GraphQL) and capabilities.
Optimization Techniques
With a declarative approach, a GraphQL server can use its knowledge of an incoming operation, the operation’s variables, the schema and the relationship of fields to backends, to analyze and optimize the request, thereby reducing operation latency for the frontend.
With a full understanding of the request, techniques such as the following can be used to reduce the number of backend requests for an operation. As with relational optimizations, such techniques are used in combination, but each is described individually.
Deduplication
As its name implies, this technique removes duplicate requests to a backend from the GraphQL server layer. In this simple case, consider the following repetitive operation:
|
1 2 3 4 5 |
{ a1: author(id:1) { name } a2: author(id:2) { name } a3: author(id:1) { name } } |
In this case, we can eliminate the request to the backend for a3 as we will already have that data from the request for a1. While this would not normally occur at the topmost selection layer, it occurs frequently when the query is pulling together data from multiple backends. In these cases, a request from one backend often produces the arguments needed to form the request to another backend. The results from the first request can contain duplicates, and we can reduce the calls to the second backend by making one request for each unique value and then distribute the results appropriately in the result.
Consider a GraphQL server that consolidates book information from a Postgres database (the books backend) with author detail information from a REST API (the authors backend) and the following query:
|
1 2 3 |
{ books(topic:"cookbooks") {title author { name }} } |
To resolve the above query, the GraphQL server will first make a request to the books backend to get the title and author auth_id for all cookbooks. Since an author of a cookbook likely writes more than one, their ID will occur multiple times from this first request. The engine must then make subsequent requests to the authors backend to get the author’s name. If there are only 20 authors for 100 cookbooks, a deduplication will make 20 (one per unique author) rather than 100 requests to the authors backend.
Reuse
Reuse avoids backend requests by reusing previous results. In this situation, we do not have the collective set of backend requests known ahead of time, but as we are making requests, we may recognize that we already have the needed data.
Consider the following query:
|
1 2 3 4 5 6 |
{ huxley: authors(name:"Huxley") { books { title } similar {name books { title }} orwell: authors(name:"Orwell") { books { title } similar {name books { title }} } |
It is likely that Huxley and Orwell are in each other’s similar list. If we have already retrieved Huxley’s book information from the books backend, then when we encounter a request to retrieve this again as part of Orwell’s similar list, we can reuse the data we already have.
This technique also helps with very deep queries that could occur due to the recursive schemas as it detects cycles in the data. For example, a query that wanted to get five degrees of similarity would not repeatedly request for the same authors but would reuse that information in filling out the result.
|
1 2 3 4 5 6 7 8 |
{ authors(name: “Huxley”) { similar { name similar { name similar { name similar {name similar {name}}}}}} } |
While reuse and deduplication both avoid multiple requests for the same data, reuse differs from deduplication in that the duplicity occurs at different levels of the tree. Reuse must find the work from previous requests where deduplication knows at the time that it is providing for multiple parts of the result.
So, in our example, deduplication would collapse three requests for id:100 into a single backend request and use it to populate the three instances, but with reuse, a later request for id:100 will find results from a previously executed request and use that to populate its instance.
Deduplication and reuse have the added advantage that they provide a consistent result. Since results for the same identifier are reused throughout the query, there is no opportunity for subsequent execution to return different results. For example, without deduplication and reuse, an author’s rating could appear as 3.4 in one part of the result but 3.7 in another.
Caching
Caching keeps local copies of frequently demanded data to avoid expensive retrievals and recomputation. In a GraphQL server, we can apply caching at many different levels:
- Backend requests: responses to given backend requests, such as HTTP requests and database queries.
- GraphQL field: responses in the context of the schema, such as caching the response of query selection field that could bring together data from multiple backends so it can be used to avoid reconstructing the same selection field in a future request.
- GraphQL operation: response to an entire set of selections, operation text and variables since applications tend to send the same set of operations.
Caching reduces the load on the backend while reducing latency of the frontend. It is like reuse, except the cached data will span requests, and with that comes other scenarios that must be handled, such as the invalidation of cached results when the source data has been modified, and evicting cached items when the local storage is full. Fortunately, caching has been around for a long time, and there are many well-known techniques employed throughout the hardware and software stack that we can leverage.
Prefetching of Fields
Another well-known technique, prefetching, retrieves additional data in anticipation of future needs. In GraphQL, we can add fields to a selection if we recognize a pattern of those fields being subsequently requested.
For example, with a query of {author { name birthplace }} the backend request is augmented to include other fields of the Author type, such as email, birth, death. Then when a future query requests email (or any of the other fields returned), caching can be used rather than requesting from the backend.
For example, in a database, instead of executing minimal
|
1 2 3 |
SELECT name, birthplace FROM authors WHERE name = “Greene” |
the query is instead also returned email, birth and death:
|
1 2 3 |
SELECT id, name, birthplace, email, birth, death FROM authors WHERE name = “Greene” |
Deduplication, reuse, caching and prefetching are techniques that are completely encapsulated by the GraphQL server and can therefore be applied to any backend without any additional support. There are two more optimizations that we consider that, in contrast, require additional access patterns from the backends. Fortunately, these access patterns are very common.
Batching
Batching is the ability to take a number of individual backend requests (typically after deduplication) and send them as a single request to the backend. Consider the following query:
|
1 2 3 4 5 |
{ greene: authors(name:"Greene") { name birthplace email} huxley: authors(name:"Huxley") { name birthplace email} orwell: authors(name:"Orwell") { name birthplace email} } |
A single backend request to return details for all three authors simultaneously would save multiple requests (in this case two) to the same backend. To leverage this optimization the backend must be able to support multivalued parameters. Fortunately, this type of capability is fairly straightforward with SQL queries, REST calls and GraphQL endpoints as the following examples demonstrate.
SQL databases: The SQL used to define the API to return information for a single author can easily be rewritten to use an IN list, a temporary join table, or less elegantly, to submit multiple SQL statements in the same client request.
REST calls: REST APIs can support multivalued parameters by simply repeating the query parameter, such as/authors?name=Greene&name=Huxley&name=Orwell, or by providing a different endpoint that accepts a list of names in a POST body instead of a path element author/<name>.
GraphQL endpoint: For GraphQL, we can simply include multiple top-level field selections in the operation, such as:
|
1 2 3 4 5 |
{ batch001: authors(name:”Greene”) { name birthplace email } batch002: authors(name:”Huxley”) { name birthplace email } batch003: authors(name:”Orwell”) {name birthplace email } } |
A less obvious requirement for the backend is that the response to the widened request must preserve the mapping from the requested objects to their results so the GraphQL server can associate the returned results with the request parameter. In our example, we return name in the result type because the result needs to map the returned book lists to their associated author, and the GraphQL server can then use this mapping to build its result.
In SQL this is easy as the request parameters can be added to the rows returned in the results, but this may not be readily available in other APIs. For example, some weather REST APIs are passed a lat/long but return the lat/long of a weather station or grid point, not the input lat/long. There is precedence to formulate such responses introduced to support aggregation in XML and JSON.
Combining
As its name suggests, combining pulls together requests from different levels into a single request from the backend. This requires that the GraphQL server understands which requests are from the same backend and can be combined into a single request.
Consider, in our running example, how the books field of the Author type might be resolved:
|
1 2 3 4 5 6 7 |
type Author { … books: [Book] @materializer( query: “bookByAuthor” arguments: [{name: auth_id”, field: “id”}] } |
The @materializer directive tells us that the books for a given author are those that satisfy the booksByAuthor query, with the auth_id of the query matching the author’s id.
The GraphQL operation —
|
1 2 3 |
{ author(id: 1) {id name books {title}} } |
— would naively be satisfied by first requesting id and name from the author backend, followed by a request for books with the given auth_id from the books backend. If both backends were databases, this would result in the following sequence of database queries:
|
1 2 |
1. SELECT name, id FROM authors WHERE id=1 2. SELECT title FROM books WHERE auth_id = 1 |
If both of these backends were from the same database, then we could combine these two requests into one:
|
1 2 3 |
SELECT A.name, B.title FROM authors A, books B WHERE A.id = 1 AND B.author_id = A.id |
While this kind of combined request is easily possible with a SQL database and can be supported by some REST APIs, it is not supported by all REST APIs and careful consideration must be given. For example, getting the pinned tweets for a Twitter user along with their details is possible, but other APIs will require additional endpoints.
Similar to batching, when such requests are combined, the GraphQL server needs to be able to unpack the response into the required object field structure.
Conclusion
GraphQL introduces a declarative data layer that promises to speed the development of frontends. Much like the way relational databases separated the logical schema from the physical schema, opening up a new world for data independence and access optimization, GraphQL provides data independence between frontend data consumption from backend data retrieval.
This ability allows the GraphQL engine to have a holistic view of the data needs of the entire application that may be co-developed over time by multiple programmers.
We have identified several opportunities for optimizing GraphQL and have suggested several techniques for minimizing backend requests when an application is using GraphQL. Variations of these techniques have been previously used throughout the hardware and software stack. While a few of the proposed techniques can be effectively implemented by bespoke resolvers, such an approach will be limited to the extent that it can optimize, as it will not have full visibility into the data model.
At StepZen, we are adding a unique, declarative way to build and run GraphQL APIs accessing REST, database and GraphQL backends. This declarative approach to the schema definition language (SDL) gives us more context, such as the relationships of fields to backends, their types and capabilities. This visibility increases the opportunities to optimize. Furthermore, we can implement these optimizations behind the scenes without burdening the schema developer or the backend services. The schema developer simply describes the data and the linkages, and we do the rest.
We are just scratching the surface of the potential optimizations and data independence we can provide with GraphQL. Just like SQL optimization evolved from flexible index definitions, simple predicate pushdown, cost-based join optimizations and query rewrite engine, we believe GraphQL optimization will evolve with the needs and opportunities the data independence layer provides.