Cache complexity analyzer in-memory/redis

[sobrinho]

Is your feature request related to a problem? Please describe.

After the optimization in #5631,
our GraphQL/analyze dropped from ~806ms to ~176ms. However, 176ms is still
significant for a hot path since the complexity analyzer runs on every request,
even when the same query has been analyzed before.

Describe the solution you'd like

I would like a way to cache the complexity analysis result across requests —
either in-process (Ruby Hash/LRU, sub-microsecond) or in a shared store like
Redis (~1ms). The gem itself does not need to know how to cache; that
responsibility can stay with the application. What the gem needs to provide is
a stable fingerprint for the incoming query so the application can use it
as a cache key.

The challenge is determining what the fingerprint should cover. The complexity
of a query depends on its structure and on certain variables — most notably
pagination arguments (e.g. first, last) — so those must be included in the
fingerprint.

Describe alternatives you've considered

Keying the cache on the full query string + all variables is too conservative:
two calls with the same query structure but different id arguments would
always miss the cache even though their complexity is identical.

Keying on the query string alone (ignoring all variables) is too aggressive:
it would treat first: 10 and first: 1000 as the same, producing incorrect
complexity results.

The right fingerprint is the query structure (document or normalized AST)
combined with only the variables that influence complexity, such as pagination
arguments.

Additional context

#5631

[sobrinho]

Naive in-memory example:

class CachedQueryComplexityAnalyzer < GraphQL::Analysis::QueryComplexity
  COMPLEXITY_CACHE = {}

  def initialize(...)
    super
    @cache_key = Digest::SHA256.hexdigest(@query.query_string)
  end

  def visit?
    !COMPLEXITY_CACHE.key?(@cache_key)
  end

  def result
    COMPLEXITY_CACHE[@cache_key] ||= super
  end
end

The problem, as mentioned, is that a variable like first: 10 vs first: 100 directly impacts complexity, so keying on the query string alone produces incorrect results. The natural fix is to include the variables in the key — but then two calls with the same query structure but different id arguments never share a cache entry, making the cache too coarse to be useful:

class CachedQueryComplexityAnalyzer < GraphQL::Analysis::QueryComplexity
  COMPLEXITY_CACHE = {}

  def initialize(...)
    super
    @cache_key = Digest::SHA256.hexdigest(@query.query_string + @query.variables.inspect)
  end

  def visit?
    !COMPLEXITY_CACHE.key?(@cache_key)
  end

  def result
    COMPLEXITY_CACHE[@cache_key] ||= super
  end
end

What I have in mind is that the gem could traverse the AST or Document to extract only the variables that actually influence complexity — pagination arguments and the like — and expose them as a stable fingerprint. The application would then decide how to use it (in-memory, Redis, etc.), keeping the gem itself lean:

class CachedQueryComplexityAnalyzer < GraphQL::Analysis::QueryComplexity
  COMPLEXITY_CACHE = {}

  def initialize(...)
    super
    @cache_key = Digest::SHA256.hexdigest(@query.query_string + @query.variables_important_for_complexity.inspect)
  end

  def visit?
    !COMPLEXITY_CACHE.key?(@cache_key)
  end

  def result
    COMPLEXITY_CACHE[@cache_key] ||= super
  end
end

Eventually this could fall back to Redis, Rails.cache, or any other store — and the in-process layer could use an LRU or any eviction strategy. It's up to the app to decide:

class CachedQueryComplexityAnalyzer < GraphQL::Analysis::QueryComplexity
  COMPLEXITY_CACHE = {}

  def initialize(...)
    super
    @cache_key = Digest::SHA256.hexdigest(@query.query_string + @query.variables_important_for_complexity.inspect)
  end

  def visit?
    !(COMPLEXITY_CACHE[@cache_key] ||= Rails.cache.read(@cache_key))
  end

  def result
    COMPLEXITY_CACHE[@cache_key] ||= Rails.cache.fetch(@cache_key) { super }
  end
end

[sobrinho]

Here's my PoC:

class MaxQueryComplexityAnalyzer < GraphQL::Analysis::QueryComplexity
  MAX_COMPLEXITY = ENV["GRAPHQL_MAX_COMPLEXITY"]&.to_i
  PAGINATION_ARGS = %w[first last].freeze
  EMPTY_ARRAY = [].freeze

  def analyze?
    !!MAX_COMPLEXITY
  end

  def on_enter_field(node, _parent, visitor)
    # TODO: This is not a public API but super returns void when the field is skipped or something if otherwise (brittle)
    return unless super

    field_defn = visitor.field_definition
    return unless field_defn

    relevant = relevant_arg_names(field_defn)
    return if relevant.empty?

    node.arguments.each do |arg_node|
      next unless relevant.include?(arg_node.name)

      value = resolve_value(arg_node.value)

      fingerprint << arg_node.name
      fingerprint << value.to_s
    end
  end

  def result
    query_complexity = cached_query_complexity

    if query_complexity > MAX_COMPLEXITY
      GraphQL::AnalysisError.new("Query has complexity of #{query_complexity}, which exceeds max complexity of #{MAX_COMPLEXITY}")
    end
  end

  protected

  def relevant_arg_names(field_defn)
    if field_defn.connection?
      # Connections have pagination args that are relevant to complexity
      PAGINATION_ARGS
    elsif field_defn.complexity.is_a?(Proc)
      # Complexity proc is a black-box and might depend on any args
      field_defn.arguments.keys
    else
      # Otherwise, the complexity is static
      EMPTY_ARRAY
    end
  end

  def resolve_value(value_node)
    case value_node
    when GraphQL::Language::Nodes::NullValue
      nil
    when GraphQL::Language::Nodes::VariableIdentifier
      query.variables[value_node.name]
    else
      value_node.value
    end
  end

  def fingerprint
    # TODO: How to work with multiplex queries here?
    @fingerprint = Digest::SHA256.new << subject.query_string
  end

  def cached_query_complexity
    # Use your storage of choice here, Rails.cache is an example
    Rails.cache.fetch("graphql:query_complexity:#{fingerprint}", ttl: 24.hours) { max_possible_complexity }
  end
end

I tried a separate analyzer only for the fingerprint but since visitor visits each analyzer in order, the fingerprint wasn't ready in appropriate time to skip the AST on this one:

# Does not work, visit? is called before the visitor visits all fields on the fingerprint analyzer
def visit?
  query.context[:complexity_fingerprint]
end

#5631 reduced from 806ms to 176ms. Using this analyzer in cold call reduces from 806ms to 176ms on cache miss and from 806ms to 1ms on cache hit (Redis behind Rails.cache). Cold as low as 1µs using in-memory cache in front of Redis back-end.

@rmosolgo how do you feel about this? Does it worthy to have a fingerprint natively?

[rmosolgo]

Hey, I think this is a really cool idea. There is currently a built-in fingerprint implementation, Query#fingerprint:

graphql-ruby/lib/graphql/query.rb

Lines 338 to 362 in a6ddab8

	# This contains a few components:
	#
	# - The selected operation name (or `anonymous`)
	# - The fingerprint of the query string
	# - The number of given variables (for readability)
	# - The fingerprint of the given variables
	#
	# This fingerprint can be used to track runs of the same operation-variables combination over time.
	#
	# @see operation_fingerprint
	# @see variables_fingerprint
	# @return [String] An opaque hash identifying this operation-variables combination
	def fingerprint
	@fingerprint ||= "#{operation_fingerprint}/#{variables_fingerprint}"
	end
	# @return [String] An opaque hash for identifying this query's given query string and selected operation
	def operation_fingerprint
	@operation_fingerprint ||= "#{selected_operation_name || "anonymous"}/#{Fingerprint.generate(query_string || "")}"
	end
	# @return [String] An opaque hash for identifying this query's given a variable values (not including defaults)
	def variables_fingerprint
	@variables_fingerprint ||= "#{provided_variables.size}/#{Fingerprint.generate(provided_variables.to_json)}"
	end

Would that implementation work here?

Another possible issue context: custom complexity hooks take context as an argument and could produce different values depending on what's in context. ObjectCache has a concept of context_fingerprint (https://graphql-ruby.org/object_cache/schema_setup.html#context-fingerprint)`, maybe that could be used here too if it's an issue.

[sobrinho]

What do you think about a Query#complexity_fingerprint?

The idea would be the same: track the query + pagination variables + static complexity, with a fallback for cases where complexity is calculated via a block.

I personally only use static values for complexity (not blocks), so we could either document blocks as unsupported or return nil when a complexity block is used. If it's not a block, it's a static value and can be safely cached.

We don't use Pro/Enterprise, so it might be tricky to tie this into context_fingerprint, but you could potentially expose it there as well.