Improving the GraphQL.NET Data Loader Execution Strategy
Tags: dotnet, graphql, performance
Published: 2021-05-28 13:04:30

**UPDATE 29/05/2021:** Added supporting code on [GitHub](https://github.com/mattjhosking/graphql-dotnet-execution-strategy).
**UPDATE 30/05/2021:** Added support for interface types.

# Improving GraphQL Performance
When using any GraphQL implementation, a key issue that crops up rather quickly is poor performance due to inefficient execution of the back end implementation. For simple CRUD queries, resolvers generally don't have many issues. Once we start retrieving lists of data and/or complex hierarchies, it's critical that the [data loader](https://graphql-dotnet.github.io/docs/guides/dataloader/) 
is used effectively. This will ensure that all resolvers queue their requests to whatever back-end implementation they use (typically database or APIs) so that they can efficiently retrieve the data.

# How the Data Loader Operates
The data loader is used to queue execution nodes to be resolved, which are then executed using the defined execution strategy, unblocking further data loaders, then repeating the process. The problem with the default execution strategy (parallel), is that the order the pending nodes are executed in is not optimal for unblocking other nodes that could become part of an existing batch.

## Example
* You are retrieving all customers, including their addresses, which in turn includes their suburbs
* As part of this query you also want to include "suburb of work" (hypothetical to suit this scenario, but think of it as a limited data collection).
* You execute the query and the following happens:
  1. The customer retrieval is queued.
  2. Since there is no data to act on until this is retrieved, this node is executed before continuing.
  3. The address retrieval is batched for all customers (presumably using a batch address retrieval REST API or SQL query) and the suburb retrieval is batched for all customers. The address suburbs are blocked by address retrieval so they are not batched.
  4. Address retrieval and suburb retrieval is executed.
  5. Now that addresses are available, suburbs can be batched for them.
  6. Suburb retrieval is again executed.

The problem here is that were we to retrieve all addresses, then check again, we could execute one suburb retrieval. The problem expands in more complex scenarios and in one query I had, this meant 45 queries instead of 23.

# Changing the Default Strategy
The execution strategy selection is performed by the registered instance for `IDocumentExecuter`. The easiest way to customise this is to create a class derived from `DocumentExecuter` and override the `SelectExecutionStrategy` method:
```csharp
public class OptimisedDocumentExecutor : DocumentExecuter
{
  protected override IExecutionStrategy SelectExecutionStrategy(ExecutionContext context)
  {
    return context.Operation.OperationType == OperationType.Query
      ? new PrioritisedParallelExecutionStrategy()
      : base.SelectExecutionStrategy(context);
  }
}
```

# Modifying the Parallel Execution Strategy
## Extract the Data Loader Execution
Customising the default `ParallelExecutionStrategy` is harder though. The best way to achieve this is to take the [existing source code](https://github.com/graphql-dotnet/graphql-dotnet/blob/master/src/GraphQL/Execution/ParallelExecutionStrategy.cs) and modify it. The key section we need to modify is the last part of the try/catch in `ExecuteNodeTreeAsync`:
```csharp
//run pending data loaders
while (pendingDataLoaders.Count > 0)
{
  var dataLoaderNode = pendingDataLoaders.Dequeue();
  currentTasks.Add(CompleteDataLoaderNodeAsync(context, dataLoaderNode));
  currentNodes.Add(dataLoaderNode);
}
```

First we move this to its own method that takes all required context, with an additional `pendingDataLoaders` list of execution nodes:
```csharp
private void ProcessDataLoaders(Queue<ExecutionNode> dataLoaderQueue, ExecutionContext context, List<Task> currentTasks, List<ExecutionNode> currentNodes, List<ExecutionNode> pendingDataLoaders)
{
  while (dataLoaderQueue.Count > 0)
  {
    var dataLoaderNode = dataLoaderQueue.Dequeue();
    pendingDataLoaders.Remove(dataLoaderNode);
    currentTasks.Add(CompleteDataLoaderNodeAsync(context, dataLoaderNode));
    currentNodes.Add(dataLoaderNode);
  }
}
```

## Prioritise Blocking Data Loaders
Next we need to change the logic to ensure data loaders that are blocking other data loaders are always processed first. First, change the type of the `pendingDataLoaders` class to `List<ExecutionNode>`, which will also require you to change the following (occurs twice) from `Enqueue` to `Add`:
```csharp
if (pendingNode.Result is IDataLoaderResult)
{
  pendingDataLoaders.Enqueue(pendingNode);
}
```
Then replace the original "run pending data loaders" while loop from above (now that it is moved out to a method) with the following:
```csharp
var pendingLoaderGraphTypes = pendingDataLoaders
    .Select(x => GetGraphTypes(x)?.Name)
    .Where(x => x != null)
    .ToHashSet();

// always process priority data loaders first as they potentially block others that can be batched in
var priorityDataLoaders = new Queue<ExecutionNode>(pendingDataLoaders
    .Where(x => HasChildOfGraphType(x, context, pendingLoaderGraphTypes))
);

var remainingDataLoaders = new Queue<ExecutionNode>(pendingDataLoaders
    .Except(priorityDataLoaders)
);

if (priorityDataLoaders.Count > 0)
{
    ProcessDataLoaders(priorityDataLoaders, context, currentTasks, currentNodes, pendingDataLoaders);
    continue;
}

//run pending data loaders
ProcessDataLoaders(remainingDataLoaders, context, currentTasks, currentNodes, pendingDataLoaders);
```

This has the following flow:
* Get the graph type related to all pending data loaders.
* Get all the pending data loaders that have a child in the query of a pending loader graph type. These become the "priority" data loaders.
* If there are any priority loaders identified, process them first using the extracted method, then restart the flow.
* If there were no priority loaders, process any remaining data loaders.
This ensures that any priority loaders continue to be processed until none can be identified, then resolve the rest.

## Resolving Graph Types for Execution Nodes
I derived the following from GraphQL.NET source:
```csharp
private static IObjectGraphType[] GetGraphTypes(ExecutionNode executionNode)
{
  IGraphType? graphType = null;
  switch (executionNode)
  {
    case ValueExecutionNode:
      return Array.Empty<IObjectGraphType>();
    case ObjectExecutionNode objectNode:
      graphType = objectNode.GraphType;
      break;
    case ArrayExecutionNode arrayNode:
      {
        graphType = ((ListGraphType)arrayNode.GraphType).ResolvedType;
        break;
      }
  }

  if (graphType is NonNullGraphType nonNullGraphType)
    graphType = nonNullGraphType.ResolvedType;

  return graphType switch
  {
    IInterfaceGraphType interfaceGraphType => interfaceGraphType.PossibleTypes.ToArray(),
    IObjectGraphType objectGraphType => new[] { objectGraphType },
    _ => Array.Empty<IObjectGraphType>()
  };
}
```
It assumes for a pending data loader that it is either an array or an object. For an object we can retrieve the graph type using `GetObjectGraphType`. For the array type we need to identify the item type. This will be the resolved type for the list.

## Determining if a Node Has a Sub Type
The following was also determined from GraphQL.NET source internals:
```csharp
private bool HasChildOfGraphType(ExecutionNode executionNode, ExecutionContext context, ISet<string> searchGraphTypes)
{
  var graphTypes = GetGraphTypes(executionNode);
  if (graphTypes.Length == 0)
    return false;

  return graphTypes
    .Any(graphType => CollectFieldsFrom(context, graphType, executionNode.Field?.SelectionSet, null)
      .Select(x => new
      {
        Field = x.Value,
        FieldDefinition = GetFieldDefinition(context.Schema, graphType, x.Value)
      })
      .Select(x => BuildExecutionNode(executionNode, x.FieldDefinition.ResolvedType, x.Field, x.FieldDefinition))
      .Any(x => GetGraphTypes(x).Any(t => searchGraphTypes.Contains(t.Name)) || HasChildOfGraphType(x, context, searchGraphTypes))
    );
}
```
This requires a newer version of GraphQL.NET, as previously the ExecutionHelper provided CollectFields and GetFieldDefinition.
This is derived from the source from the parent `ExecutionStrategy` class' `SetSubFieldNodes` method, as this takes an execution context and node and expands the selection set from the query into the AST fields, retrieves each field's definition and builds execution nodes. From those child execution nodes, you can determine graph types, allowing you to determine if the query selection has a pending data loader type.