Dependency graph design

I want to capture here some thoughts about the Dependency graph (see #1409).

One of the main challenges is the dynamic aspects of a query (type conditions).

For exampel for this schema:

type Query{ 
    node: Node
}
interface Animal {
    name: String
    friends: [Friend]
}

union Pet = Dog | Cat

type Friend {
    name: String
    isBirdOwner: Bool
    isCatOwner: Bool
    pets: [Pet] 
}

type Bird implements Animal {
   name: String 
   friends: [Friend]
}

type Cat implements Animal{
   name: String 
   friends: [Friend]
   breed: CatBreed 
}

type Dog implements Animal{
   name: String 
   breed: DogBreed
   friends: [Friend]
}

scalar DogBreed
scalar CatBreed

one can imagine this query:

{
  node
  ... on Cat {
    friends {
      isCatOwner
      name
      pets {
        name
        ... on Cat {
          breed
        }
      }
    }
  }
  ... on Bird {
    name
    friends {
      isBirdOwner
      name
      pets {
        name
        ... on Dog {
          breed
        }
      }
    }
  }
  ... on Dog {
    name
  }
}

The question is now how the dependency graph should capture these dynamic type conditions.
One possible way could be this:

But the value of this kind of dependency graph maybe limited because it doesn't uphold to one fundamental expectation that every field is only present once.
The /node/friends/pets/name field is duplicated because it will only be executed if we have a Bird or a Cat, but not for a Dog.

Same is true for /node/friends/pets and /node/friends/name.

The alternative could maybe look like this:

It doesn't duplicate any fields anymore but now there are complex conditions associated with some nodes. For example /node/friends/pets/breed will only be evaluated if the original node is a Cat and the pet is a Dog.

@gkesler

@gkesler @exbe I would appreciate your thoughts ... thanks

@andimarek

@andimarek
Here is yet another alternative to executing query above.

For the convenience I have color coded nodes that have some condition/predicate in yellow and the nodes without conditions in blue.

When yellow nodes are being resolved, i.e. when these nodes are being visited after all their dependencies have been resolved, the node's result is obtained by applying node's predicate to the source data. This is different from the blue nodes that obtain their result by invoking externally provided resolve method.
PS. It is possible, I think, to optimize the graph to look like your case #2 by combining yellow nodes predicates using boolean operations. However, that optimization wouldn't change the topological ordering mechanism, wile, probably, reduce number of elements in the sequence.

Topological ordering produces a sequence in which nodes need to be evaluated.
Here is simplified pseudo-code. I've made it in 2 nested loops for simplicity. In reality there shall be a breadth-first walk over adjacency sets of source nodes (whose dependencies have been resolved) in order to achieve the maximum efficiency in the query execution.

Set<Node> unresolvedSet = shallow-copy-of-graph
Set<Node> resolvedSet = new HashSet<>();
while (!unresolvedSet.isEmpty()) {
   // find nodes in the unresolved set that have all their dependencies 
   // in the resolved set
   Set<Node> closure = new HashSet<>();
   for (Node node: unresolvedSet) {
      if (resolvedSet.containsAll(node.dependencySet()) {
         // node's dependencies are resolved
         // now this node can be resolved
         closure.add(node);
      }
   }

   for (Node node: closure) {
         if (!autoResolve(node)) {
            resolve(node);
         } else {
            // node is resolved automatically,
            //  i.e. it has obtained its data from its dependencies
         }

         unresolvedSet.remove(node);
         resolvedSet.add(node);
   }
}

Let's see how topological sorting (that's why we need dependency graph here) applies to the example query:

closure: ["/node"]

"/node" is resolved to values: [Cat("Lola"), Bird("Coco"), Dog("Molly")]

closure: ["/node/on Cat", "/node/on Bird", "/node/on Dog"]

"/node/on Cat" is auto resolved to value Cat("Lola") (predicate: isInstanceOf("Cat") on [Cat("Lola"), Bird("Coco"), Dog("Molly")])
"/node/on Bird" is auto resolved to value Bird("Coco") (predicate: isInstanceOf("Bird") on [Cat("Lola"), Bird("Coco"), Dog("Molly")])
"/node/on Dog" is auto resolved to value Dog("Molly") (predicate: isInstanceOf("Dog") on [Cat("Lola"), Bird("Coco"), Dog("Molly")])

closure: ["/node/on Cat/friends", "/node/on Bird/name", "/node/on Bird/friends", "/node/on Dog/name"]

"/node/on Cat/friends" is resolved to [Friend("Andy")]
"/node/on Bird/name" is resolved to "Coco"
"/node/on Bird/friends" is resolved to [Friend("Greg")]
"/node/on Dog/name" is resolved to "Molly"

closure: ["/node/on Cat/friends/isCatOwner", "/node/on cat/friends/name", "/node/on Cat/friends/pets", "/node/on Bird/friends/isBirdOwner", "/node/on Bird/friends/name", "/node/on Bird/friends/pets"]

"/node/on Cat/friends/isCatOwner" is resolved to true
"/node/on Cat/friends/name" is resolved to "Andy"
"/node/on Cat/friends/pets" is resolved to [Cat("Lola"), Dog("Molly")]
"/node/on Bird/friends/isBirdOwner" is resolved to false
"/node/on Bird/friends/name" is resolved to "Greg"
"/node/on Bird/friends/pets" is resolved to []

closure: ["/node/on Cat/friends/pets/on Cat", "/node/on Bird/friends/pets/on Dog"]

"/node/on Cat/friends/pets/on Cat" is auto resolved to Cat("Lola") (predicate: isInstanceOf("Cat") on [Cat("Lola"), Dog("Molly")])
"/node/on Bird/friends/pets/on Dog" is auto resolved to [] (predicate: isInstanceOf("Dog") on [])

closure: ["/node/on Cat/friends/pets/on Cat/breed", "/nodes/on Bird/friends/pets/on Dog/breed"]

"/node/on Cat/friends/pets/on Cat/breed" is resolved to "persian"
"/nodes/on Bird/friends/pets/on Dog/breed" is auto resolved to null or "", does not matter since there is no source data to resolve this field.

Auto resolve mechanism allows to obtain node's result without going after the associated resolver or data fetcher, directly from the data already resolved/cached in the graph.

and ah, I've forgotten to answer the question about field duplication. I think inclusion of "conditional" nodes into the graph will disambiguate what seem to be field duplications.
I would argue that in your example with /node/friends/pets/name duplication, there is no duplication at all, since the paths are different:

/node/on Cat/friends/pets/name
/node/on Bird/friends/pets/name

@andimarek

@andimarek Do you have some particular resolvers on your mind for this example?

I might be overthinking, but dependency graph with resolvers for Dog, Cat and Bird might look different from dependency graph with just two resolvers. One for Animal and another one for Animal with breed. Yes, I am throwing in yet another use case about query optimization. I don't have a good answer whenever generating fully-blown super generic dependency graph (to serve ALL use cases) is better than generating specialized and reduced graph which would consider runtime/execution behaviour during resolution of a given request.

Also, pardon my knowledge for GraphQ SDL, but following schema looks slightly off (spec). Is it or it just my misunderstanding?

type Dog implements Animal{
   name: String 
   breed: DogBreed
  ///  friends: [Friend]   /// <---- must be present, isn't it?
}

I guess I have after all slightly modified the original requirement and provided solution to the query where node field is resolved to array of Animals:)
That's how all 3 variants come together in 1 query.

In case "node" query is resolved to a single object, that result is just converted into a singletonList and in step 1. and the rest of steps are executed as they are described above.

@exbe

@exbe you are right about the Schema, I fixed it.

After giving it some thought I think we have two different dependencies: one dependency is the source input which means another field/node is required to be resolved before and then we have another dependency type which acts as predicate (similar to the yellow nodes above).

The first dependency is something that can be optimized/changed by the engine. The second dependency can't be changed because it is an external observable property, which can't be changed.

Example:

schema:

type Query {
	issues: [Issue]
}

type Issue {
	id: ID
	author: User
}
type User {
	name: String
	createdIssues: [Issue] @dependOn(sourceType: "Issue")
}

query:

{ issues {
	author {
	   name
   		... on User {
   			createdIssues {
	   			id
				}	
		}
	}
}}

This modeling allows us to do the following optimization:

I am with you on the different kind of dependencies and the optimization scenarios.

Not sure I yet follow the example, perhaps because the schema and the query do not match. Issue type needs to have a field author : User, doesn't it?

Could you please elaborate on how have you come up with the createdIssues having happens-before (source) dependency on issues?

Indeed, dependencies are different:

happens-before (source) dependencies are known at the graph building time and depend only on the schema semantics, i.e. relationships between objects, ID fields, etc.
conditional dependencies have predicates that are evaluated at the execution time based on the results of previous executions. They are built into the graph as happens-before but evaluated conditionally.

PS. One can treat happens-before dependencies as conditional ones with always true predicate.

I've been also thinking that expressing dependencies between fields in a form of graph would allow not only the engine to perform optimizations, but also it will let the client to optimize the execution, if for instance the pre-built dependency graph is provided as an argument to the Instrumentation before the execution starts, the client can optimized it according to his or her knowledge of the schema semantics.

@gkesler

@gkesler you are right: I fixed the schema.

The reason why createdIssues could only depend on issues is: lets imagine you query all issues by making one external call (DB, service, whatever). You get back a list of issues with each Issue having an authorId.
To get an actual author you need to make an extra call, but you could get the list of issues for an author before that because you only need the authorId, not the full User object. This is why you could indicate to the engine (in the example above via directive in the schema) that createdIssues only need an Issue as input (because it contains the authorId, which is all you need). Does that makes sense?

@andimarek

@andimarek yes, it does. I just think that this is exactly a semantic aspect of the schema, without client's help we won't be able to make this kind of optimizations. Directives will certainly help. The more scenarios like this we can think of and provide directions for, the more automatic optimizations we can make without the client to modify/optimize the graph manually.

Similar scenario would be this:

schema

type Query {
   company (id: ID!) : Company
}
type Company {
   id : ID
   name: String
   invoices : [Invoice]
}
type Invoice {
   id : ID
   txnDate : DateTime
   amount: Float     
} @dependsOn (sourceType : "Company", field : "id")

query

query {
   company (id: "1") {
      name
      invoices (first: 5) {
         id
         txnDate
         amount
      }
   }
}

Regular and optimized queries look this way:

The regular query causes 2 sequential remote calls:

fetch Company by id="1"
fetch 5 invoices for the source Company.

In order to fetch Invoices all we need to have is foreign key to the Company, which is actually provided as the id argument to the company field. Therefore we should be able to optimize overall query performance by making these 2 remote calls in parallel.

"green" node represents a graph node created for the argument id. Field company certainly depends on it, that argument must be provided with the query. Since invoices depends on source company and in particular its field id (foreign key), company argument with matching name could be used to change dependency from invoices -> company to invoices -> id=1.

After giving it some more thought and actually implementing it/spiking it, I come up with a design where each node represents always a field of an object type. Fragments/type condition/field on interfaces are all resolved to fields on object types. At execution time only object types matter and which interfaces/union is implemented by which object is statically known by the schema definition.

I created also a small interactive page to play around/visualize this: https://www.graphql-analyzer.com/

A PR which adds this dependency graph to GraphQL Java will follow.

@andimarek

@andimarek absolutely, thanks!

please, let me know if I can contribute to your PR.
Are you still waiting for the DependencyGraph itself?

A quick question on the visualizer.
in query

{ 
  pets {
    name
    ... on Dog {
      dogFriends {
        name
      }
    }
  }
}

field name is declared on the interface Pet. Therefore I would expect that nodes Cat.name and Dog.name had unconditional dependencies on Query.pets rather than conditional ones. The only true conditional dependency I think is Dog.dogFriends on Query.pets.

@gkesler

@gkesler maybe the explanation is not really clear, what I mean is:
Whether Dog.name, Dog.dogFriends or Cat.name will be resolved depends on the actual type returned by Query.pets. If Query.pets contains a Dog then Dog.name and Dog.friends will be resolved. If it contains a Cat, Cat.name will be resolved.

On the other hand we know that Dog.dogFriends always returns Dog, so Dog.name will always be resolved for that (except of course null values, which is not relevant regarding conditional or not).

@andimarek

Thanks for the quick response, @andimarek

I think checking conditions Dog.name or Cat.name depending on the returned pet type is quite redundant, especially if they are all checked at the runtime. Imagine there are more types that implement interface Pet and for each of them the similar condition is checked. I think this redundancy could be removed if instead of nodes Dog.name and Cat.name there was a node Pet.name that would be resolved if the source type is Pet, which is always true in this case.

This way node Query.pets could have only two dependents:

Pet.name with always true predicate since the source is always instance of interface Pet
Dog.dogFriends with predicate that returns true only if the source is instance of type Dog

@gkesler

@gkesler I made the explicit decision to only represent object types fields in the dependency graph.

For once because at the end you have to determine the type anyway: Even if you have an Interface like Pet you still need to determine the object at execution time to get the DataFetcher from the object type.
Also because it is overall simpler to reason about. (for humans at least)

Not saying it is perfect or it must be alway this way. I am sure there are variations of the graph, maybe depending on the use case.

@gkesler

@gkesler as another side note: I would suggest that we close this issue and continue on the PR #1594 once it progressed a bit. Because it is kinda hard to think about all the edge cases without actual code.

@andimarek

@andimarek

I have no objections, let's move on.

@gkesler

closing this now ... thanks a lot @gkesler @exbe for the valuable discussion!

Navigation Menu

Repository navigation

Dependency graph design #1566

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Dependency graph design #1566

Description

Activity

andimarek commented on Jun 10, 2019

gkesler commented on Jun 10, 2019

gkesler commented on Jun 10, 2019

exbe commented on Jun 11, 2019

gkesler commented on Jun 11, 2019

andimarek commented on Jun 29, 2019

andimarek commented on Jun 29, 2019

gkesler commented on Jun 30, 2019

andimarek commented on Jun 30, 2019

gkesler commented on Jul 1, 2019

andimarek commented on Jul 8, 2019

gkesler commented on Jul 8, 2019

andimarek commented on Jul 9, 2019

gkesler commented on Jul 9, 2019

andimarek commented on Jul 10, 2019

andimarek commented on Jul 10, 2019

gkesler commented on Jul 10, 2019

andimarek commented on Jul 11, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions