Query Complexity

Overview

To a protect a typical REST API, what you will often see is a rate limit for how many times the user can request a given resource/set of resources within a given interval. For GraphQL requests, this type of paradigm does not make as much sense, since each request can vary greatly in compute cost. For example, a user requesting their own username value is way less expensive than a user requesting the latest 5000 audit log entries. To solve this problem, we can apply a cost value to each individual field and resolver within the GraphQL schema. When the user sends a request, we add up the cost of all the fields they've requested, and only allow the request if the total cost is below a predetermined limit. This concept is called "query complexity". You can read more about it and how it is implemented within a NestJS application here.

Dynamic complexity

Query complexity can be statically defined as a number within your code, or you can provide a function which calculates a query's complexity based on the provided query arguments. For example, when a user calls the resolver findManyUser, they can pass a pagination argument. If the user requests only 5 documents, this will likely be significantly less expensive than if they request 5,000 documents. You can account for this by checking exactly how many documents the user requested within their pagination argument.

A perfect complexity function will scale 1:1 with the compute time and response bandwidth needed for the given resolver. However, this is not a trivial problem, and many (or most) query complexity functions will simply be an estimate. Some of the things that should be taken into account when calculating complexity include:

• Pagination take value
• Number of permission checks necessary
• Sorting (indexed vs. non-indexed columns)
• Filter complexity
• Any other high-value task

Sometimes, fields take no or extremely little compute power to resolve, so it may be tempting to set complexity to 0 for those fields. While the complexity of fields can be 0 (or negative, for that matter), this isn't recommended most of the time with our current estimators. Compute time is only one resource which is expended when responding to a query; the query response also takes up bandwidth to send back to the user.

A basic findMany complexity estimator may look something like this:

function estimateFindManyQueryComplexity(options: ComplexityEstimatorArgs): number {
  // Default page size of 20 elements
  return (options.args.pagination?.take ?? 20) * options.childComplexity;
}

In this situation, if all of the child fields which the user requested have a complexity of 0, the user's Pagination take argument value can be as high as they'd like, and the estimated complexity will always be 0, despite ever-increasing size in the response payload. For this reason, we currently have all basic, pre-fetched fields have a default complexity of 1.

Maximum complexity

As of writing this, default maximum complexity is currently defined at 500, however this value can (and should) be adjusted as needed. This is a living application early in its life, and our needs will adapt over time. To account for those needs, adjusting maximum complexity may be something that has to happen more than once. You should be sure of the implications of your new complexity value before increasing or decreasing it. If you're decreasing it, will there be any extremely expensive queries which simply cannot be completed anymore, or not in an efficient manner? If you're increasing the maximum complexity, are there any cheap operations which perhaps need their cost increased as well?

There is no reason why maximum complexity has to be an application-wide static value. Here are two considerations to take for future iterations of the project:

• User-based complexity - You may decide that different users should have different complexity maximums based on their requirements for the API. An Administrator doing lots of sorting and filtering may need a higher complexity than a user simply listing the most recent productions. Maximum complexities could be user-controlled, group-controlled, or both.
• Time-based complexity - Per-request (stateless) complexity will prevent any one query from being overly complex, however it does not prevent a user from submitting large amounts of requests within a short time span, effectively accomplishing the same as if they had included all of the requested values within the same query in the first place. This should be fixed by applying a similar rate limiting to REST APIs that is weighted to each individual request (i.e., make it stateful). For example, a user may have a 5,000 complexity limit per 10 seconds. That user can spend their 5,000 complexity however they want, but once they use it up, they have to wait until the end of the current 10-second interval to get another 5,000 complexity.