Feature request: Exponential complexity calculation

[MerzDaniel]

There should be a possibility for an exponential complexity calculation. Our graphql data models have a lot of relations and most of these can return multiple entities. Therefore the depth of the query can exponentially increase the returned data size. This should be possible to be taken into account in the complexity calculation.

The complexity of a type which is fetched as part of a set should exponentially increase the complexity. This could be extended for the DirectiveEstimator:

type board {
posts: [Post] @Complexity(childMultiplier: 3) #complexity.value should be optional
}

This also could be extended on the options for the directive estimator:

directiveEstimator({ childComplexity: 1, childListMultiplier: 3 })

The childListMultiplier calculates the complexity of the child sub query and multiplies it with the defined value

Example

The following example shows the issue without exponential complexity calculation:

type Board { name: String
posts: [Post] @Complexity(value: 5)
}
type User { name: String
boards: [Board] @Complexity(value: 5)
}
type Post { text: String
viewers: [User] @Complexity(value: 5)
}
type Query {
boards(ids: [ID]): [Board] @Complexity(value: 5)
}

With the queries

query {
q1: boards(ids:["1"]) { n1: name n2: name n3: name n4: name }
q2: boards(ids:["1"] { posts { text } posts2: posts { viewers { name } } }
q3: boards(ids:["1"] { posts { viewers { boards { name } } } }
}

All queries have a simple complexity of around 5. Using the directive Estimator q2 has a complexity of 22 and q3 21, although the amount of returned entities is exponentially bigger in q3.

[ivome]

This sounds like a good thing to add to the directive estimator. With the fieldExtensionEstimator this is already possible by customizing the estimator function.

We would just have to decide how this behaves with the multipliers (that are meant for this exact feature). Maybe we call this defaultMultiplier which can then be overridden if a multiplier is explicitly set?

Something like this:

type Query {
  posts(limit: Int): [Post] @complexity(multipliers: ["limit"], defaultMultiplier: 50)
}

If no limit is provided, the default multiplier of 50 is used, otherwise, the limit is used as the multiplier. Would that work for your use-case?

[MerzDaniel]

Yes this would be a possibility. But it is quite verbose when typing

The field level multipliers mostly have effect on the root level query (e.g. query($ids: [ID]){ posts(ids:$ids) { text } }). In the second level of a query, the data rarely is queried using ids. So defaultMultiplier would be the most used prop.

How about alternatively passing an int to the multipliers prop?

type Post { text: String
viewers: [User] @Complexity(multipliers: 5)
}

[ivome]

How about alternatively passing an int to the multipliers prop?

How do you want to define the input types for that argument? This needs to be strictly typed in GraphQL.
I think the verbosity is worth the clarity it provides IMHO, but happy to discuss alternatives. I think we should not break backward compatibility and we should have a fallback mechanism that allows us to use dynamic multipliers together with the static values as fallback.

[MerzDaniel]

Right, this is not possible. I was just in the typescript thinking

How about a specific complexity multiplier directive that can be configured centrally? Then the original concept of the simple directive estimator is unchanged. The new directive would solely focus on the exponential complexity. Both directives could be used for estimating complexity if needed

The idea of the existing Directive estimator is more focused on linear growth of the fetched data in my opinion

How about this:

directive @ExponentialComplexity( factor: Int )

... estimators: [ exponentialDirectiveEstimator( { defaultFactor: 5 }) , simpleEstimator() ]

type Post {
viewers: @ExponentialComplexity()
editors: @ExponentialComplexity(factor: 3)
}

[ivome]

This would definitely work and could be implemented with a custom estimator. Only issue with that would be if you have input values that need to change the factor:

{
  posts(limit: 1000000) {
    title
  }
}

Then you probably end up with a solution like I suggested above. But you could certainly configure two estimators with different directives that have different behaviors.

[MerzDaniel]

This should be possible by combining the annotations and using both estimators:

Viewer { posts(limit: Int): [Post] @Complexity(multipliers: ["limit"]) @ExponentialComplexity }

... estimators: [ directiveEstimator(), exponentialDirectiveEstimator( { defaultFactor: 5 }) , simpleEstimator() ]

We on our side would solely rely on the exponential estimator with small multipliers (e.g. 3), but the combination of both estimators should still be possible.

[MerzDaniel]

So I think we have these options discussed:

1. Extend the Complexity annotation with a childListMultiplier and make the complexity value optional. This multiplies the complexity of list fields with a static value. This should be configurable in the options with a default value. Alternative name: defaultMultiplier
2. Introduce a ExponentialDirectiveComplexity estimator that solely cares about the the static complexity multiplier

Both are fine I think. Which would you prefer?

[ivome]

I think the defaultMultiplier as outlined in my initial comment makes the most sense. That way we add functionality to handle fallback values for multiplier arguments if an argument is not provided, you can implement the complexity calculation as required by your usecase and we don't have to add another complexity calculator (but a user could still implement that on their end if needed).

[y4nnick]

Is there any update on this feature? Would be super nice!

[ivome]

I haven't found the time to look into that. Happy to review and merge a PR if anyone wants to add this.

[simplenotezy]

Curious about this too. I am interested in ensuring certain fields are only selectable in top level, i.e. controlling the depth.

For example:

query UserWithFriends {
	id
	name
	username
	friends { # this should be allowed
		id
		name
		username
		friends { # this should not be allowed
			id
			name
			username
			friends {
				# matrix...
			}
		}
	}
}