Scale By The Bay 2020: Greg Kesler, Query Planning in GraphQL

Scale By The Bay 2020: Greg Kesler, Query Planning in GraphQL

Recording: Scale By The Bay 2020: Greg Kesler, Query Planning in GraphQL

[Music] hello everyone thank you for attending the query planner for graphql talk my name is jack kessler and i have been working with graphql since spec was out in 2015. i have contributed uh to the um with the critical performance improvements and algorithms to the graphql java project mysim and i we've been working on the project with the goal to automate over a large ultimate orchestration over a large set of the capability services across the company we had design discussions also with the uh graphql java folks with respect to the query analysis and query planning capabilities and my team is currently working on implementing query planner for graphql java that we plan to open source uh hopefully in march next year and in this talk i will share uh some of the ideas that we are building into the qa plan for graphql so this is the agenda we will look at the standard graphql query execution then we will introduce the qa plan we'll discuss the key query analysis components that need to be built into the query plan we will uh see how to plan simplify security cost analysis and finally we will discuss other two or cool capabilities provided by the query plan beyond graphql spec in order to start uh looking into the examples i would like to introduce or imagine a schema that we will build the examples the actual examples around for imagine that we have a pet store or pet club uh that uh where we can keep the animals each symbol has a name where each animal can have friends and we have the um we have the uh three concrete animal types dog cat and birth all of them implement the animal interface uh also we can you know we can have the special union type pet which is which combines doctors and cats just for demonstration purposes but again this is imaginary schema that helps me that will help me to walk you through the examples and also finally we have the type friend that is uh that that also has names it could be it could have the certain attributes and also the list of pets that this friend is friend with so let's assume that we have a query uh that creates for a one single animal uh we specify the name of the animal uh in the argument for the animal field and we are asking for the bunch of fields of the uh of the uh of the animal and in case the return animal is a dog we want the dog specific fields in case the animal is a cat we want the cat specific fields in case they birth we want the board specific fields and also we want we want to create for the friends for that anymore so let's let's let's look how the standard clear execution goes so so the execution begins from collecting the fields in the topmost uh selection set in our case the topmost selection set is the selection under the under the query uh okay under the query element of the query and we have one field to collect which is animal so imagine that we have collected that animal field now we need to resolve that field the graphical engine goes ahead and invokes the animal field resolver and animal field resolver creates the animals data so data source an animal data source finds the animal with the name toby and sends response back to the to the to the server in our case this is the dock the next step in the query uh execution will be to collect the fields from for in the animal selection set and there are a bunch of them there are fields and of the animal interface name owner name and fee and friends there are fields in the um under the specific type the for the dog or for the care for the character work in our case the dog fields need to be included into the collection so the jockey engine collects the all fields that are relevant to the dog type returned in the previous query in the animal field and they are name owner name bray uh breed barks uh friends and then it needs to uh perform the same operation again it needs to resolve the fields so some of the fields are resolved against the uh with using the result uh produced by the previous query but some of the fields in our case friends need to uh again create a different data source and uh imagine the different data source returns back a list of friends and the next step in the execution will be to collect the fields for the uh in the friend selection set and in this case their uh name dog name uh i'm sorry name is dog owner is cat owner or is bird owner and these of them so the query engine collects all the fields and then there's also the fields and i would also uh point that uh it will invoke this uh resolution or resolvers as many times as many uh elements were returned in the friends list by by the frenzy zone so this is the uh just illustration uh of the standard uh graphical query execution as it is uh described in the spec so as you see uh during that process uh the engine um performs a lot of redundant work it needs to collect the fields it needs to merge the fields it needs to resolve types and uh in case the same query or the same query type i would say is received by the server multiple times that it becomes even more relevant because every time the engine would do the same it doesn't work work over and over again it also when uh we walked through the uh graphical query execution uh one could notice that uh there is a specific order in the jerk in the query execution the fields need to be executed after their parents so the execution or resolution of the children fields depends on the resolution of the creativity so this all makes us make it possible to separate the qa analysis uh from the query execution and the query analysis where we connect the fields detect the fields that need to be executed when we when we um could be recorded into the uh into the graph in our case it is the uh and the best suitable case would be the uh directed a cyclograph or dependency graph if you will and as you see uh each merged and collected field could be represented in the graph as the id vertex for the fields that have the abstract type like in our case the animal field we can also and we should in order to continue with the field discovery we should detect all possible very very concrete variants of that abstract type and to record them into the in into the graph and these uh vertices are indicated on the graph with a slightly different color with the green color to represent the special vertices that are concrete representation that associated with the types that are concrete types of the animal interface so uh the relationship or the dependencies between field between parent fields and the children fields are recorded via as edges so as you see in the query selection set there was an animal field and there is an edge between the query and the animal vertices uh for the uh for the dog type there are there are fields name owner name barks breed and friends they are also recorded into the world into into the into as edges into this graph so each edge represent a possible uh parent child dependency relationship between between the fields so why it is important uh first of all uh we can we could we could say that execution of the graphical query is a process of enumerating the edges between the vertices and then executing the field resolver or actions if you if you will associated with the edges according to that order in order to uh collect the uh or build the sequence of edges the uh graph structure allows us to first topologically sort the vertices and topological order means that the vertices with the least dependencies appear in the sequence before the vertices with the most dependencies so the this way we can you can see that the uh the least dependent field or least dependent vertices that that is that represents the the the topmost selection set query appears first in the sequence and for instance the field uh like is dog owner is cat owner that depends on their parent field friends the the corresponding vertices are represented in this sequence at the end of the sequence so this is the first step in uh building the the the sequence of edges from after enumerating the the vertices we can find all the incoming edges into each vertices and we can group those edges into the separate buckets in order to collect the edges that could be so resolved independently and this table represents the the buckets of the independently global resolvable edges from left to right first we start with h zero to one that's the age between the qa and animal vertices the the next bucket would be the edges between animal and uh animal dog animal cat and animal birth vertices the next bucket would be the uh the all edges that are outgrowing from the uh from the vertices animal dog animal cat and animal birth and the last bucket will be all edges outgoing from the from the uh virtuous friend uh you also can notice here that some of the edges are painted in red and the corresponding um elements in the tables are also painted the red uh these edges while they are they still exist in the query plan or in the graph these edges are executed uh they're they're they are not executed during this particular uh uh kind of query because uh uh the graph represents the statically as a result of the static analysis of the query not all of the patterns in the graph get executed at the runtime and they depend on the actual data in our case the actual data for the for the for uh during the graph execution resolution query resolution was the animal of type doc and therefore all edges that are related to other concrete types like cat or bird they are not executed in this case and uh it is also worth mentioning that as we evaluate the query plan the each vertex in the plan is associated with the uh with its own data we accumulate the data for each workers and they need to be separated from each other because the query plan is reusable across multiple queries multiple requests with the the same query type whereas the uh data for each vertex is request specific that's why for each request we need to create an instance of the qa plan data store where we can keep track of the accumulated data for that particular request so uh this is mostly uh you can represent that as a map with the key uh the vertex id or the vertex and the value for each entry would be the accumulated data for that vertex so uh then let's see what the key components of the uh of the static query analysis should be built into the query plan first uh component is the merging fields imagine that we have the query with the uh with the fields uh repeated in multiple play with the same field repeated in multiple places like for instance the field name there is a field name under the animal selection set then there is field name under the kit fragment then we have this field name under the dock fragment similarly the field friends we have under the cat fragment we have the field friends listed twice under the birth fragment this is allowed by the spec and uh when the uh this these spec defined algorithms demands that these need to be discovered and merged at the time of the execution with the creative plan we don't have to do this we can do this once when we build the query plan and each field uh um merges to the the the this field uh the same field with the same name and label under the same type condition and that merged field is represented as a separate vertex in the in the in in the query plan so uh to be uh to be uh more specific or to be uh mostly correct we can say that each vertex in the k plan is not one single field as it is defined described in the grave in in the query it is actually a merged field uh obtained by merging the fields of the same uh with the same name under the same type condition uh and that is that that case the that creates the vertex and again after we key the after we build the uh set of vertices we can build a set of edges and in this particular case for this particular query the only executable set of edges would be in the first bucket zero to one that is resolving the field animal to uh to toby we know that toby was a dog and then uh resolving the age one to five uh uh because the in this case h1 to five acts like a filter selecting from the set of animals they turned in uh in the previous step into into the vertex data the vertex 5 data only docs and then executing the h52 that produces the docs names so the result would be just result of executing this path uh with the with the result would be um would be the name of the of the dog that was there that was created the next uh component that need to be considered when we build a query plan is the abstract fields abstract fields again those fields that uh have the type of interface or a union and in order to do the static analysis of the query we need to provide a record in the plan uh all possible variants for that interface of the query uh hopefully they are known from the uh fortunately they are known from the from the schema in our schema the uh animal interface has three country types dog birth and cat in case of you in case of unions the all components of the unions are also known so the plan should contain all uh possible cases of the country type in order to not to make these decisions on at the runtime the third component is the conditional fields the conditional fields are fields that have directives include or skip in this case i place the directive include if uh directly if if directly has very true the field is included if the field is has the value false it is excluded and this conditional error conditions represent the edges that would that should be conditionally either evaluated or conditionally skipped during the execution uh in case of the static bindings like like this one the edges that should be excluded from the from the from the plan they could or even not be recorded in the plan at all but in some cases where the uh values uh argument values for the include or skip directives are provided via variables it is better to record uh these edges as they are and then evaluate them on the at the run time depending on the actual value of the arguments uh one of the interesting uh consequences of having query plan is a different way of realization of the execution strategy for the mutations the spec demands that mutation fields need to be executed sequentially and for that graphql java for instance has a separate edition strategy that ensures that the mutation fields are executed one after another in the order they are provided in the created and then after the mutation fields are resolved the results of those that that's a clear part of the mutation they could be resolved using the standard standard edition strategy that just provides a synchronous resolution of the fields with the query plan it is not necessary because we can control with the query plan the sequence execution sequence by providing additional edges between fields these edges need not be actionable functional but just having the edge between uh in in our case we have the mutation fields at doc and atkit ed doc is labeled as lab labrador and kit is labeled as sphinx and in order to ensure that the uh the field sphinx is resolved after the field labrador we just need to provide an edge between the field labrador and sphinx and this and this and presence of this edge will will ensure that the field or vertex sphinx will be will be placed in the topological sequence after the after the labrador and therefore the resolution the field resolver for these things will be executed after the field is over for labrador so just like in our case the first stage to resolve will be zero one zero the add animals that's the topmost query uh selection set to labrador the next one would be labrador to name uh animals to sphinx and labrador to sphinx and alberta these things that's not actual age it is placed here just to ensure the order of the operations it doesn't have to it it doesn't produce anything but the effect would be that the uh h02 3 uh the uh that invokes the resolver for the fuel sphinx will be executed after the h021 that uh that invokes the resolver for the for the field labrador uh the one of the important uh tasks to uh when executing the the graphql query is to perform the query cost analysis q a gross analysis is important to prevent the very complex queries from execution because they can either destroy the system or by producing some sort of ddos attack or they can uh take too long time to execute and the client will not be will not will not be satisfied with the results so therefore it is important to be able to upfront somehow estimate uh how how costly uh the query is and in many cases uh there are separate systems in or there are separate components in the jfk engines that calculate the query cost analysis simply because the graphql spec does not provide any uh mechanism for or for the for for the critical analysis based on the query execution with equity plan as you see the qa the cost analysis could be performed over the same uh query plan and it is again it consists of the same steps as if the as if we were needed we were we re-executed the query the only difference is that during the query during the cost analysis all we need to do is to uh to obtain the cost of evaluating of a particular age each age could be associated with the cost versus in the case of the uh execution each age is associated with the field resolver that obtains data so in the query course analysis we use exactly the same uh standard mechanism we're working with the same source which is create plan uh and uh that makes it very accurate comparing to other uh methods because the other methods could go easily out of sync with the actual query execution so in our case again uh i will not walk through uh the way how the query is executed but just to notice that the h021 uh is calculated based on the uh based on the most of the costs for the uh for the actual types because the animal type is the abstract and we have the uh we have the cost associated with dissolving to bird cat of or dog and the uh the cost of this of this uh resolution is the highest cost of the associated with the with the type that is derived from the from the animal and also uh the third bucket of the edges where the edges are resolved in parallel uh when you resolve the edges in parallel the cost is calculated as the at the cost of the uh the highest cost of the h in that bucket in our case uh in that bucket we have the uh we have h um uh two or three or four to france and resolving to france that's that's the uh 212th t12 and 412 and the cost of relating to france is 10 and therefore the whole bucket evaluates costs the the 10 points and therefore the total cost of the offset query is 16 points uh what else could be done is uh with the query plan that's already beyond the spec imagine the situation where we need to evaluate some fields or resolve some fields only after the other fields of the same type have been evaluated and it doesn't matter to make them it doesn't make sense to make it that feel dependent on uh um in the different reaction set it belongs to the to the same parent type but it needs to be related after the other fields for instance in this case this is this is imaginary situation but it would be very easy implemented imagine that i want to add a field espat owner to my friend type and the espat owner is a calculated field it is not the field that is fetched from the data source but it is calculated based on the expression provided in the uh evol directive and it evaluated to true in case this this friend is dog owner or it is a cat owner in this case the uh after parsing uh the expression uh the person can figure out that in order to uh resolve the field is pat owner the fields is cat owner or is dog owner have to be resolved first and that goes against this pack because in the spec the fields that on the same level under the same payment or are in the same selection set need to be executed in parallel so we need to somehow make them make fields is pet is dog owner and his cat owner executed before the field is pet owner and uh in order to do that we can record additional dependencies in the in the query plan between the field between the vertices or fields uh is the owner and his pet owner is cat owner and is pet owner uh they are indicated uh with different color on the on the on the plan and that will ensure that the field is pet owner will appear in the topological sequence after the field is dog owner and is cat owner and therefore the edge the edge incoming h for inspect owner that would which is one to six that would invoke the resolver for that field could be bucketed in the different in different bucket after the edges that dissolve the is dog owner and is his birth owner [Music] another another interesting uh case uh or advantage of using a query plan is optimizing the query execution imagine that we have the field in the in the under the animal type few friends this query asks for the friends and friends field depends only on the on the foreign key on the name of the animal and the name of the animal is already provided in the as the argument to the animal field so uh therefore just like in the previous example in the um the the normally the the field france would be executed or resolved after the field animal is resolved and that would produce the cost 16 as we saw during the q a cost analysis uh slide that it would produce the code 16 for this query but uh we can do so we can do smarter than that we can create a new vertex in the plan that represents the um the the that that that would contain or would be associated with the data for the for the friends of animal with name black and that could be uh recorded in the plan in such a way that we create the edge between the we can place basically it in the same selection set as the animal field we can create the edge between the top most selection set query with that field and that edge will guarantee or will place the exec or will be executed uh in parallel with execution of the field of the field animal and imagine that we can associate that edge with the with the function that resolves uh that that goes against the friends data source and reads the all friends of the of the animal friend or of the animal black i'm sorry so that edge will be executed in parallel with the h021 which resolves the animal itself so by the time when the execution comes to the h c 12 that should return all the friends for the animal the data uh for the for the for that effort of those friends have been already executed in the previous step so the the resolver for the hc12 could simply go and fetch the data that was prefetched before and that drastically simplified uh simplifies the query or makes it makes it executed faster because take a look at the at the resolution order so the first edges to resolve would be ages 0 to 1 and 0 to 17 and we know that the coast of the uh h0 to 1 was the highest cost of the resolving the one of the animal types which was six but the zero to 17 cost would be 10. so in this case the overall cost of this step would be just 10. and then uh on the uh on the third back in the third bucket where the where the h c to 12 need to be executed uh in that case the h3-12 instead of going and disordering for that age instead of going against the friends data source it will just get the friends from the from the uh from the cache because it was already fetched and that costs nothing and therefore the overall total cost for this qa would be just 10 instead of 16 as it was in previous case just translate this close to the milliseconds imagine that each point is actually let's say 100 milliseconds and then you can easily see that instead of sixteen hundred milliseconds the executions that has created can go to just ten hundred meters and uh with the create plan we can do more much more and we plan to build that i don't have the slides to show that i can just simply you know describe what else could be there could could be could be done with the query plan complex criteria uh this is uh usually quite helpful when you need to orchestrate over a set of the uh various independent data sources and the criteria might contain the criteria the liquidity criteria might contain the uh filters against various data sources and in order and therefore we can we can we can decompose that criteria and we can schedule the execution of the queries applying the filters against various data sources and still use the same qa plan with the same topological nhh sequence to produce the result cascade mutations is kind of similar in case we want to have a we want to create a mutation of the object across multiple data sources where some fields belong to one the source some fields belong to another this source we can also decompose that that object onto the set of smaller objects and execute the smaller mutations across across particular data sources and then produce the results and again the qa plan is suitable to do this because the uh fundamental mechanism how to execute queries is doesn't change it all depends on how we record the vertices and edges into the plan uh another thought that we we can we want to explore would be the testing and optimizing outlier fields that means that we can shuffle around fields in the in the in the plan by introducing additional intermediate vertices and edges in such a way that we can uh place the edges that cost most in the different buckets where the impact of the of that cost will be uh will be compared to impact of the other edges in the same buckets so this uh we sort of see saw that when we discuss the prefetched field analysis but there could be more complex scenarios where this could be useful we need to add subscription support based on the query plan and subscriptions are also a good example of uh value of the query plan because why because we will build the query plan only once and only executed with every data change in order to produce the the notifications uh instead of evaluating the same query over and over again as the uh as the data get changed and also we can provide the different stream support directive support they are not parts of the graphql spec yet but they are coming soon and that also could be quite easily built using a query plot so and that would be the last slide in my talk and thank you very much for listening in case you need to contact me this is my email and github handle twitter and linkedin please feel free to reach me out and i will be happy to help your answer to your questions thank you