Hacking the Query Planner, Again
Guo, Richard
This talk will focus on how the planner works from a developer’s view and elaborate on the process of converting a query tree to a plan tree in details. We can divide the planning process into 4 phases: preprocessing, scan/join planning, post scan/join planning and postprocessing. In this talk, I will explain what stuff is performed in each phase and what is the motivation to perform that. Topics will include: transforming ANY/EXISTS SubLinks into joins, flattening sub-selects, preprocessing expressions, reducing outer joins to inner joins, distributing quals to rels, collecting join ordering restrictions, removing useless joins, join searching process, upper planner path-ification, cost estimation, etc. Tom Lane's 2011 talk "Hacking the Query Planner” talked about the overview of query planner. In this talk, I will cover the internals of query planner with more details and in a way more close to planner codes. I hope this will be helpful in understanding the internals of PostgreSQL's planner and in hacking the planner codes to improve it.
 Good morning, everyone. Thank you for coming to this session. Today my topic is hacking the query planner again. Before getting started, I'd like to introduce myself a little bit. My name is Richard Guo and I'm from Beijing, China. I'm now working at VMware on Green Plum. This is the agenda of my talk. First, I will introduce a little bit about what does planner do. And then the second part is about the different phases of planning. So let's get started. This is the overall backend structure. First, we have the password to determine the semantic meaning of our query stream. And then the rewriters to perform view and raw expansion. Next is the planner who designs an execution plan for the query. And last is the executor to run the plan. So what planner does is to find a correct execution plan that has a low VSA cost for gaming query. Actually, for gaming query, it can be executed in many different ways. Some may be faster and some may be slower. So if it is computationally feasible, the planner would examine each of these possible ways. Each way is represented by path data structure. And at the end of the, and at the end, the planner would select the cheapest path and it can be added to a full-fledged plan. So now let's move on to the second part, different phases of planning. Although the planning process can be divided into four phases, the first phase is pre-processing. At this phase, we simplify the query if possible. Also, we collect the information, such as the join ordering restrictions. And the second part is is scan-join planning, which is to decide how to implement from and where paths are required. And the third phase is poster scan-join planning, which is to deal with plan steps that are not scans or joints, such as aggregation, distinct or group by. And the last phase is poster processing, which is to convert the results into form that the executor wants. Okay, now let's go through each phase one by one. At early pre-processing, we try to simplify the query by several kinds of path-three transformations, including simplified scalar expressions, in line simple SQL functions, and simplified join tree. So to simplify scalar expressions, we reduce any recognizably constant sub-expressions of the given expression tree. So for example, for function calls, if the function is strict and has any constant null inputs, actually we can reduce it to a constant null. And if the function is immutable and has all constant inputs, then we can hand it to the executor to execute. So for building expressions, we can do such simplification as reduce x or true to constant true, and reduce x and false to constant false. Our assumption here is that the sub-expression x, we are not having important side effects. For key expressions, we also can do simplification if there are constant condition clauses, such as for this expression, we return x plus 1, not the error message. So while we are simplifying, by simplifying, we can do computations only once, not once per row. And also we can exploit constant footing opportunities, exposed by real expansion and the single function in line. Expand simple single functions in line. Here is an example. We have a function increase4 defined as argument plus 2 plus 2. So for this query, select increase4a from full. We inline the function and transform it to select a plus 4 from full. So please note that we also perform the constant footing within the function, right? We can read 2 plus 2 to 4. So by inlining single functions, we can avoid the rather high per call overhead of the single functions. And also we can expose opportunities for constant footing within the function expression. And simplify joint trade. There are several cases that we can transform the joint trade into a more efficient form. But in this step, we don't have any statistics in for to use. So we do the transformation based on some predefined rules. For any and exists sublinks in VR and join on clauses, we can try to transform them into semi-joints. And for subqueries in the joint trade, we can try to merge them into parent query. We also try to reduce joint strengths by reducing other joints to inner joints or anti joints. So here is a query with exists sublink. The query is select stuff from full. We are exists select one from bar. We are 4.8 equals 8.6. Actually, we can transform it into semi-joints since it's correlated with parent query. And also we are able to discard is target list. So it can be transformed to query select stuff from full semi-joint bar 4.8 equals 5.6. And here is a joint trade before the transformation. As we can see, the subselects exists as a real core clause in this joint trade. And so this is a joint trade after the transformation. And the sublink has become a semi-joint. Okay, here is another query containing a sub query. So the query is select stuff from full join select bar.c from bar join bar on true as sub on 4.8 equals sub.c. So actually, this sub query is simple enough that we can pull it up into the parent query. So it can be changed to this query select stuff from full join bar join bar on true on 4.8 equals 5.c. Note that for the transformer query, actually we can join the three base tables full bar and bars in any order. And considering that there is a joint clause between full and bar. So most likely joining them first would give us a better plan. But for the original and transformed query, actually we will have two join bar and bars first if we don't do the plow. So here is a joint trade before the transformation. And as we can see, the sub query exists in the range table list of the parent query. And it would be planned independently if we don't do the plow. And now this is a joint trade after the transformation. And the sub query has been merged into the parent query. So by pulling up sub queries, we may produce a better plan as we consider it as part of the entire plan search space. Otherwise, the sub query would be planned independently and traded as a black box during planning of the outer query. Or reduce joint strength. Okay, let's look at this example first. So here is a query. The query is select something from full left join bar on something where bar point D equals 42. Actually we know the equal operator in where is streaks. So for any row where the left join failed in nonce for bar column, the streaks operator will always retain now causing the outer wear to fail. Therefore, there is no need for the join to produce the now extended rows in the first place. So which makes it a plain inner join, not an outer join. So we can conclude that if there is a strict call about the outer join that constraints a var from the non-nullable side of the join to be known. Now, then we can reduce the outer join to inner join. And now let's look at another example. So here is another query and the query is select stuff from full left join bar on full point A equals bar point C where bar point C is known. Okay, for this query, actually we know the join clause full point A equals bar point C is streaks for bar point C, right? So only now extended rows can pass the upper wear. So the bar point C is known. And we can conclude that what the query is really specifying is the anti-joint. So that is to say if the out joins all in calls are streaks for any nullable var that was for the null by higher call levels, then we can reduce the outer join to anti-joints. So until now what we are talking about is all about the pass three transformations. And at a later pre-processing, we would distribute all kinds of call clauses and build the equivalence classes, gather information about the join ordering restrictions, remove useless joins and so on. So first let's look how we distribute the call clauses. In general, we want to use each call as low as possible join level. When dealing with inner joins only, we can push a call down to its natural semantic level. So here by natural semantic level, I mean the level associated with just the base real user in this call. However, when dealing with out joins, a call may be delayed and cannot be pushed down to its natural semantic level. And for this kind of outer join delayed calls, we mark them with required real IDs, which includes all the required reals in the outer join. So by pretending that the call references all the reals required to form the outer join, actually we prevent it from being evaluated below the outer join. And usually there are two cases that our call can be out of the join delay. And so for the first case, let's look at this query. So the query is see let's start from full left join bar on 4.8 equals 42. So it's a left join, right? And it has a join call, 4.8 equals 42. The join call mentions the nullable side real, which is full. And if we push this call down below the outer join, then it will become a filter on full. And it will remove all the rules that it is not equal to 42 before the join. So as a result, we might lose some non-extended rules that should have been in the final result set. So we can lose that. And out joins all join on calls mentioning nullable side reals cannot be pushed down below the outer join. And for the second case, let's look at this query. So the query is see let's start from full left join bar on 4.8 equals 8.4. Where call less 8.4 when equals 42. Okay, it's a left join. And there is a call about this outer join, which is call less 8.4 when equals 42. And this call references the nullable while 8.4. So if we push this call down below the outer join, then it would become a filter on bar and it would reject the rules before the outer join. So as a result, it might cause the outer join to emit non-extended rules that should not have been formed or that should have been rejected by the calls. So we can conclude that cause a parallel in where or in your join above the outer join cannot be pushed down below the outer join if the reference and the nullable was. Okay, let's move on. So in equivalence classes, for multiple join bar equality clauses a equals b that are not out of the joint delay. We use equivalence classes to record this knowledge. So in equivalence class represents several values that are no at all transitively equal to each other. And in equivalence clauses are removed from the standard call distribution process. Instead, e-class based call clauses are generated dynamically when needed. And the equivalence class is also represents the value that pass key orders by. So the logic here is since since we know x equals y. So order by x should be the same as order by y. Okay, now let's talk about joint order restrictions. So if we have outer joins, actually we cannot perform the joint in any order. Outer joins induce joint order restrictions. And one side outer joins like left join or right join constraints the order of joining partially, but not completely. And in general, non-full joins can be freely associated associated into the left hand side or outer join. But in some cases, they cannot be associated into the right hand side. So let's look at two examples below. For the first example, a left join b predicate p a b and then in the joint c on P a c. So this inner join can be associated into the left hand side of the left side. So we can we can get a inner join c on P a c and then left join b on P a b. And let's look at the oh sorry, let's look at the second example. So a a left join b p a b and then inner join c on P b c. So for this time, this inner join cannot be associated into the right hand side of the left join. So even though there is a joint clause between b and c, actually we cannot join them first because it's illegal joint order. And and for for the non-full joins, we flatten them to the top level join list so that they can participate fully in the joint order search. And meanwhile, we record information about each other join in order to avoid generating illegal joint orders. So another thing we do as a little pre-processing is to remove useless joins. For left join, if it's inner real is a single b-strain and the inner real attributes are not used above the join, and the join condition cannot match more than one inner side row. Actually, the join we are just duplicate is left input. So in this case, actually, we can remove this join altogether. So for example, here we have a query and the query is selected 4.8 from full left to join. A sub query is a sub query is selected this thing to c as c from bar sub 4.8 equals sub point c. So so so for this query, the inner real is a is a single b-strain or sub query, and the join condition cannot match more than one inner side row since attribute c is unique because here we are using distinct. So this left join can be removed. Okay, now let's move on to the second phase scan joint planning. So at this phase, we deal with the from and the where path of the query. And also we know about all the by so that we can we can design more joints and to avoid a final thought if possible. So for example, for this query and the query is select stuff from full join bar on 4.8 equals bar point c and full point b equals bar point d all the by b and a. So when generating the merge join, actually, we can start table full by a and b. We can also start table full by b and a right. But since we know that the final output is is requested to be sorted by d and a. So we chose a sort key d and a for table full so that we can avoid the final thought. And the second phase is basically driven by cost estimates. So for scan joint planning, basically, what we do here is to first identify feasible scan methods for these relations, estimate their cost and the result sizes, and then search the joint orders base using a dynamic programming or heuristic genetic query optimizer method to identify feasible plans for joint relations. And meanwhile, we all know how to join ordering restrictions to avoid generating illegal joint orders. And the and here and here for each relation base real or join real, we produce one or more passes. So so multi multi joins have to be built up from pairwise joints. Because that's all the executor knows how to do. So for any given pairwise joint step, we can identify the the best input passes and the joint methods such as nested loop or merge or hash join. While three forward cost of comparations resulting in a lethal passes much as for the for for the base relation. And finding the best ordering of the pairwise joints is a hard part. So usually we have many choices of joint order for multi we join query and some others will be cheaper than others. So if the query contains only inner joints, we can join the base relations in any order. But with other joints, as we have talked about, they can be reordered in some but not all cases. So we handle that by checking whether each proposed joint step is legal. And this standard joint search method, we construct the joint tree level by level using a dynamic programming algorithm. So first, assume assumes that we have already generated passes for each base relation. Then we generate the passes for each possible two-way joint and then for each possible three-way joint and then four-way joint until all base relations are joined into into a single joint relation. So here is a demo about how we construct the joint tree. So the query for the demo is select stuff from a joint, b joint c, b point g, equals c point g, a point i equals b point i. And as a first step, we generate the passes for each base relation. And then we generate the passes for two-way joint. For a joint b, we create two passes, one is, for example, hash joint and one is merge joint. And then we figure out that the possible hash joint is in inferior to, so we just discard it. And here for a joint c, actually we don't try to make joints with them because we found that there is no joint clause between them. And then for b joint c, we create two passes and discard the inferior one. And as in we generate the passes for three-way joint. So for joint real a, b and base real c, we create two passes and discard the inferior one. And for joint real bc and base real a, we also create two passes, but then both are discarded. So both are discarded when we're competing with the existing pass. So at last we pick this pass, which is merge joint a and b first and then merge joint bc. And joint searching is expensive. So actually an a-way joint problem can potentially be implemented in any factorial different joint orders. So usually it's not feasible to consider all possibilities. And what we do here is to just to use a few heuristics, like as Shoyin said, demo, we don't consider clause less joints. And with too many relations, by default it's 12. We fall back to the genetic query optimizer. Heuristics use in joint search. So as we said, we don't join relations that are not connected by any joint clause, unless first two by joining all the restrictions. And also for large joint problems, we try to break it down into sub problems according to some collapse limits. For example, here we have a query and we have 10 tables joining together. So by setting the joint collapse limits back to four, we can break it down into sub problems that's no more than four we join. And then we can handle each sub problem independently. Okay, so now let's move to the third phase post scan joint planning. So at this phase, we deal with group by aggregation, window functions, distinct. We also deal with set operations like uni, intersect and accepts. And then we apply final sort if needed by order by. And for each of our steps, we produce one or more passes. And at the last we add lock rules, limit modified table steps to each surviving pass. So this is a third phase. And the last phase is post processing, where we expand the best pass to plan. And then we adjust some representational details of the plan. So such as we flatten sub query range tables into a single list. We label was in upper plan those as outer one or inner one to refer to the outputs of their sub plans. And we also remove unnecessary sub queries again, the pain and the module plan knows if we figure out that they are not doing anything useful. So this is the first the last phase. And this is all for my talk. Thank you. you you
 Good morning, everyone. Thank you for coming to this session. Today my topic is hacking  the query planner again. Before getting started, I'd like to introduce myself a little bit.  My name is Richard Guo and I'm from Beijing, China. I'm now working at VMware on Green Plum.  This is the agenda of my talk. First, I will introduce a little bit about what does planner do.  And then the second part is about the different phases of planning. So let's get started.  This is the overall backend structure. First, we have the password to determine the  semantic meaning of our query stream. And then the rewriters to perform view and  raw expansion. Next is the planner who designs an execution plan for the query.  And last is the executor to run the plan.  So what planner does is to find a correct execution plan that has a low VSA cost for  gaming query. Actually, for gaming query, it can be executed in many different ways.  Some may be faster and some may be slower. So if it is computationally feasible,  the planner would examine each of these possible ways. Each way is represented by path data structure.  And at the end of the, and at the end, the planner would select the cheapest path and  it can be added to a full-fledged plan. So now let's move on to the second part,  different phases of planning. Although the planning process can be divided into four phases,  the first phase is pre-processing. At this phase, we simplify the query if possible.  Also, we collect the information, such as the join ordering restrictions. And the second part is  is scan-join planning, which is to decide how to implement from and where paths are required.  And the third phase is poster scan-join planning, which is to deal with plan steps that are not  scans or joints, such as aggregation, distinct or group by. And the last phase is poster processing,  which is to convert the results into form that the executor wants.  Okay, now let's go through each phase one by one. At early pre-processing, we try to simplify the  query by several kinds of path-three transformations, including simplified scalar expressions,  in line simple SQL functions, and simplified join tree. So to simplify scalar expressions,  we reduce any recognizably constant sub-expressions of the given expression tree. So for example,  for function calls, if the function is strict and has any constant null inputs,  actually we can reduce it to a constant null. And if the function is immutable and has all  constant inputs, then we can hand it to the executor to execute.  So for building expressions, we can do such simplification as reduce x or true to constant  true, and reduce x and false to constant false. Our assumption here is that the sub-expression x,  we are not having important side effects. For key expressions, we also can do simplification if  there are constant condition clauses, such as for this expression, we return x plus 1, not the error  message. So while we are simplifying, by simplifying, we can do computations only once,  not once per row. And also we can exploit constant footing opportunities,  exposed by real expansion and the single function in line. Expand simple single functions in line.  Here is an example. We have a function increase4 defined as argument plus 2 plus 2. So for this  query, select increase4a from full. We inline the function and transform it to select a plus 4  from full. So please note that we also perform the constant footing within the function, right?  We can read 2 plus 2 to 4.  So by inlining single functions, we can avoid the rather high per call overhead of the single  functions. And also we can expose opportunities for constant footing within the function expression.  And simplify joint trade. There are several cases that we can transform the joint trade into a more  efficient form. But in this step, we don't have any statistics in for to use. So we do the transformation  based on some predefined rules. For any and exists sublinks in VR and join on clauses, we can try  to transform them into semi-joints. And for subqueries in the joint trade, we can try to  merge them into parent query. We also try to reduce joint strengths by reducing other joints to  inner joints or anti joints. So here is a query with exists sublink. The query is  select stuff from full. We are exists select one from bar. We are 4.8 equals 8.6.  Actually, we can transform it into semi-joints since it's correlated with parent query. And also we  are able to discard is target list. So it can be transformed to query select stuff from full  semi-joint bar 4.8 equals 5.6. And here is a joint trade before the transformation. As we can see,  the subselects exists as a real core clause in this joint trade. And so this is a joint trade  after the transformation. And the sublink has become a semi-joint.  Okay, here is another query containing a sub query. So the query is select stuff from full  join select bar.c from bar join bar on true as sub on 4.8 equals sub.c.  So actually, this sub query is simple enough that we can pull it up into the parent query.  So it can be changed to this query select stuff from full join bar join bar on true on 4.8 equals  5.c. Note that for the transformer query, actually we can join the three base tables full bar and  bars in any order. And considering that there is a joint clause between full and bar. So most  likely joining them first would give us a better plan. But for the original and transformed query,  actually we will have two join bar and bars first if we don't do the plow.  So here is a joint trade before the transformation. And as we can see, the sub query exists in the  range table list of the parent query. And it would be planned independently if we don't do the plow.  And now this is a joint trade after the transformation. And the sub query has been merged  into the parent query. So by pulling up sub queries, we may produce a better plan as we  consider it as part of the entire plan search space. Otherwise, the sub query would be planned  independently and traded as a black box during planning of the outer query.  Or reduce joint strength. Okay, let's look at this example first. So here is a query. The query is  select something from full left join bar on something where bar point D equals 42.  Actually we know the equal operator in where is streaks. So for any row where the left join  failed in nonce for bar column, the streaks operator will always retain now causing the  outer wear to fail. Therefore, there is no need for the join to produce the now extended rows  in the first place. So which makes it a plain inner join, not an outer join. So we can conclude  that if there is a strict call about the outer join that constraints a var from the non-nullable  side of the join to be known. Now, then we can reduce the outer join to inner join.  And now let's look at another example. So here is another query and the query is  select stuff from full left join bar on full point A equals bar point C where bar point C is known.  Okay, for this query, actually we know the join clause full point A equals bar point C  is streaks for bar point C, right? So only now extended rows can pass the upper wear.  So the bar point C is known. And we can conclude that what the query is really specifying  is the anti-joint. So that is to say if the out joins all in calls are streaks for any  nullable var that was for the null by higher call levels, then we can reduce the outer join to anti-joints.  So until now what we are talking about is all about the pass three transformations.  And at a later pre-processing, we would distribute all kinds of call clauses and  build the equivalence classes, gather information about the join ordering restrictions, remove  useless joins and so on. So first let's look how we distribute the call clauses.  In general, we want to use each call as low as possible join level. When dealing with  inner joins only, we can push a call down to its natural semantic level. So here by natural  semantic level, I mean the level associated with just the base real user in this call.  However, when dealing with out joins, a call may be delayed and cannot be pushed down to its  natural semantic level. And for this kind of outer join delayed calls, we mark them with  required real IDs, which includes all the required reals in the outer join. So by pretending that  the call references all the reals required to form the outer join, actually we prevent  it from being evaluated below the outer join.  And usually there are two cases that our call can be out of the join delay.  And so for the first case, let's look at this query. So the query is see let's start from full  left join bar on 4.8 equals 42. So it's a left join, right? And it has a join call,  4.8 equals 42. The join call mentions the nullable side real, which is full. And if we push this  call down below the outer join, then it will become a filter on full. And it will remove all  the rules that it is not equal to 42 before the join. So as a result, we might lose some non-extended  rules that should have been in the final result set. So we can lose that. And out joins all  join on calls mentioning nullable side reals cannot be pushed down below the outer join.  And for the second case, let's look at this query. So the query is see let's start from full left  join bar on 4.8 equals 8.4. Where call less 8.4 when equals 42. Okay, it's a left join.  And there is a call about this outer join, which is call less 8.4 when equals 42.  And this call references the nullable while 8.4. So if we push this call down below the outer join,  then it would become a filter on bar and it would reject the rules before the outer join.  So as a result, it might cause the outer join to emit non-extended rules that should not have been  formed or that should have been rejected by the calls. So we can conclude that cause a parallel  in where or in your join above the outer join cannot be pushed down below the outer join if the  reference and the nullable was. Okay, let's move on. So in equivalence classes, for multiple  join bar equality clauses a equals b that are not out of the joint delay. We use equivalence classes  to record this knowledge. So in equivalence class represents several values that are no  at all transitively equal to each other. And in equivalence clauses are removed from the standard  call distribution process. Instead, e-class based call clauses are generated dynamically when needed.  And the equivalence class is also represents the value that pass key orders by. So the logic here is  since since we know x equals y. So order by x should be the same as order by y.  Okay, now let's talk about joint order restrictions. So if we have outer joins,  actually we cannot perform the joint in any order. Outer joins induce joint order restrictions.  And one side outer joins like left join or right join constraints the order of joining partially,  but not completely. And in general, non-full joins can be freely associated associated into the  left hand side or outer join. But in some cases, they cannot be associated into the right hand side.  So let's look at two examples below. For the first example, a left join b predicate p a b  and then in the joint c on P a c. So this inner join can be associated into the left hand side  of the left side. So we can we can get a inner join c on P a c and then left join b on P a b.  And let's look at the oh sorry, let's look at the second example. So a a left join b  p a b and then inner join c on P b c. So for this time, this inner join cannot be associated  into the right hand side of the left join. So even though there is a joint clause between b and c,  actually we cannot join them first because it's illegal joint order.  And and for for the non-full joins, we flatten them to the top level join list so that they can  participate fully in the joint order search. And meanwhile, we record information about  each other join in order to avoid generating illegal joint orders.  So another thing we do as a little pre-processing is to remove useless joins. For left join, if it's  inner real is a single b-strain and the inner real attributes are not used above the join,  and the join condition cannot match more than one inner side row. Actually, the join we are just  duplicate is left input. So in this case, actually, we can remove this join altogether.  So for example, here we have a query and the query is selected 4.8 from full left to join.  A sub query is a sub query is selected this thing to c as c from bar sub 4.8 equals sub point c.  So so so for this query, the inner real is a is a single b-strain or sub query,  and the join condition cannot match more than one inner side row since attribute c is unique  because here we are using distinct. So this left join can be removed. Okay, now let's move on to the  second phase scan joint planning. So at this phase, we deal with the from and the where path  of the query. And also we know about all the by so that we can we can design more joints and to  avoid a final thought if possible. So for example, for this query and the query is select stuff from  full join bar on 4.8 equals bar point c and full point b equals bar point d all the by b and a.  So when generating the merge join, actually, we can start table full by a and b. We can also  start table full by b and a right. But since we know that the final output is is requested to be  sorted by d and a. So we chose a sort key d and a for table full so that we can avoid the final thought.  And the second phase is basically driven by cost estimates.  So for scan joint planning, basically, what we do here is to first identify feasible scan  methods for these relations, estimate their cost and the result sizes, and then search the  joint orders base using a dynamic programming or heuristic genetic query optimizer method  to identify feasible plans for joint relations. And meanwhile, we all know how to join ordering  restrictions to avoid generating illegal joint orders. And the and here and here for each relation  base real or join real, we produce one or more passes.  So so multi multi joins have to be built up from pairwise joints. Because that's all the executor  knows how to do. So for any given pairwise joint step, we can identify the the best input passes  and the joint methods such as nested loop or merge or hash join. While three forward cost  of comparations resulting in a lethal passes much as for the for for the base relation.  And finding the best ordering of the pairwise joints is a hard part.  So usually we have many choices of joint order for multi we join query and some others will be  cheaper than others. So if the query contains only inner joints, we can join the base  relations in any order. But with other joints, as we have talked about, they can be reordered in  some but not all cases. So we handle that by checking whether each proposed joint step is legal.  And this standard joint search method, we construct the joint tree level by level using a  dynamic programming algorithm. So first, assume assumes that we have already generated passes  for each base relation. Then we generate the passes for each possible two-way joint and then for  each possible three-way joint and then four-way joint until all base relations are joined into  into a single joint relation. So here is a demo about how we construct the joint tree. So the  query for the demo is select stuff from a joint, b joint c, b point g, equals c point g, a point i  equals b point i. And as a first step, we generate the passes for each base relation.  And then we generate the passes for two-way joint. For a joint b, we create two passes, one is,  for example, hash joint and one is merge joint. And then we figure out that the possible hash  joint is in inferior to, so we just discard it. And here for a joint c, actually we don't try to  make joints with them because we found that there is no joint clause between them.  And then for b joint c, we create two passes and discard the inferior one.  And as in we generate the passes for three-way joint. So for joint real a, b and base real c,  we create two passes and discard the inferior one.  And for joint real bc and base real a, we also create two passes, but  then both are discarded. So both are discarded when we're competing with the existing pass.  So at last we pick this pass, which is merge joint a and b first and then merge joint bc.  And joint searching is expensive. So actually an a-way joint problem can potentially be  implemented in any factorial different joint orders. So usually it's not feasible to consider all  possibilities. And what we do here is to just to use a few heuristics, like as Shoyin said,  demo, we don't consider clause less joints. And with too many relations, by default it's 12.  We fall back to the genetic query optimizer.  Heuristics use in joint search. So as we said, we don't join relations that are not connected by  any joint clause, unless first two by joining all the restrictions. And also for large joint  problems, we try to break it down into sub problems according to some collapse limits.  For example, here we have a query and we have 10 tables joining together. So by setting the  joint collapse limits back to four, we can break it down into sub problems that's no more than four  we join. And then we can handle each sub problem independently.  Okay, so now let's move to the third phase post scan joint planning. So at this phase, we deal with  group by aggregation, window functions, distinct. We also deal with set operations like uni,  intersect and accepts. And then we apply final sort if needed by order by. And for each of our steps,  we produce one or more passes. And at the last we add lock rules, limit modified table steps to  each surviving pass. So this is a third phase. And the last phase is post processing, where we  expand the best pass to plan. And then we adjust some representational details of the plan. So  such as we flatten sub query range tables into a single list. We label was in upper plan those as  outer one or inner one to refer to the outputs of their sub plans. And we also remove unnecessary  sub queries again, the pain and the module plan knows if we figure out that they are not doing  anything useful. So this is the first the last phase. And this is all for my talk. Thank you.  you  you
Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_0_107.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_108_215.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_216_743.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_744_1151.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_1152_1667.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_1668_2999.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_3000_3179.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_3180_5891.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_5892_6155.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_6156_6527.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_6528_6659.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_6660_7295.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_7296_7895.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_7896_8315.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_8316_8447.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_8448_8951.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_8952_9983.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_9984_11003.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_11004_11663.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_11664_11999.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_12000_12299.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_12300_14675.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_14676_15011.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_15012_19151.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_19152_19799.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_19800_21767.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_21768_27467.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_27468_31079.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_31080_35111.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_35112_36479.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_36480_38543.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_38544_39683.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_39684_40067.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_40068_40847.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_40848_42059.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_42060_42779.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_42780_45383.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_45384_46703.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_46704_48287.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48288_48347.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48348_48491.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48492_48635.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48636_48767.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48768_48983.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_48984_49475.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_49476_49535.png Hacking_the_Query_Planner__Again_-_Richard_Guo__PG_wTg02tniO2A_49536_49630.png
Good morning, everyone. Thank you for coming to this session. Today my topic is hacking the query planner again. Before getting started, I'd like to introduce myself a little bit. My name is Richard Guo and I'm from Beijing, China. I'm now working at VMware on Green Plum. This is the agenda of my talk. First, I will introduce a little bit about what does planner do. And then the second part is about the different phases of planning. So let's get started. This is the overall backend structure. First, we have the password to determine the semantic meaning of our query stream. And then the rewriters to perform view and raw expansion. Next is the planner who designs an execution plan for the query. And last is the executor to run the plan. So what planner does is to find a correct execution plan that has a low VSA cost for gaming query. Actually, for gaming query, it can be executed in many different ways. Some may be faster and some may be slower. So if it is computationally feasible, the planner would examine each of these possible ways. Each way is represented by path data structure. And at the end of the, and at the end, the planner would select the cheapest path and it can be added to a full-fledged plan. So now let's move on to the second part, different phases of planning. Although the planning process can be divided into four phases, the first phase is pre-processing. At this phase, we simplify the query if possible. Also, we collect the information, such as the join ordering restrictions. And the second part is is scan-join planning, which is to decide how to implement from and where paths are required. And the third phase is poster scan-join planning, which is to deal with plan steps that are not scans or joints, such as aggregation, distinct or group by. And the last phase is poster processing, which is to convert the results into form that the executor wants. Okay, now let's go through each phase one by one. At early pre-processing, we try to simplify the query by several kinds of path-three transformations, including simplified scalar expressions, in line simple SQL functions, and simplified join tree. So to simplify scalar expressions, we reduce any recognizably constant sub-expressions of the given expression tree. So for example, for function calls, if the function is strict and has any constant null inputs, actually we can reduce it to a constant null. And if the function is immutable and has all constant inputs, then we can hand it to the executor to execute. So for building expressions, we can do such simplification as reduce x or true to constant true, and reduce x and false to constant false. Our assumption here is that the sub-expression x, we are not having important side effects. For key expressions, we also can do simplification if there are constant condition clauses, such as for this expression, we return x plus 1, not the error message. So while we are simplifying, by simplifying, we can do computations only once, not once per row. And also we can exploit constant footing opportunities, exposed by real expansion and the single function in line. Expand simple single functions in line. Here is an example. We have a function increase4 defined as argument plus 2 plus 2. So for this query, select increase4a from full. We inline the function and transform it to select a plus 4 from full. So please note that we also perform the constant footing within the function, right? We can read 2 plus 2 to 4. So by inlining single functions, we can avoid the rather high per call overhead of the single functions. And also we can expose opportunities for constant footing within the function expression. And simplify joint trade. There are several cases that we can transform the joint trade into a more efficient form. But in this step, we don't have any statistics in for to use. So we do the transformation based on some predefined rules. For any and exists sublinks in VR and join on clauses, we can try to transform them into semi-joints. And for subqueries in the joint trade, we can try to merge them into parent query. We also try to reduce joint strengths by reducing other joints to inner joints or anti joints. So here is a query with exists sublink. The query is select stuff from full. We are exists select one from bar. We are 4.8 equals 8.6. Actually, we can transform it into semi-joints since it's correlated with parent query. And also we are able to discard is target list. So it can be transformed to query select stuff from full semi-joint bar 4.8 equals 5.6. And here is a joint trade before the transformation. As we can see, the subselects exists as a real core clause in this joint trade. And so this is a joint trade after the transformation. And the sublink has become a semi-joint. Okay, here is another query containing a sub query. So the query is select stuff from full join select bar.c from bar join bar on true as sub on 4.8 equals sub.c. So actually, this sub query is simple enough that we can pull it up into the parent query. So it can be changed to this query select stuff from full join bar join bar on true on 4.8 equals 5.c. Note that for the transformer query, actually we can join the three base tables full bar and bars in any order. And considering that there is a joint clause between full and bar. So most likely joining them first would give us a better plan. But for the original and transformed query, actually we will have two join bar and bars first if we don't do the plow. So here is a joint trade before the transformation. And as we can see, the sub query exists in the range table list of the parent query. And it would be planned independently if we don't do the plow. And now this is a joint trade after the transformation. And the sub query has been merged into the parent query. So by pulling up sub queries, we may produce a better plan as we consider it as part of the entire plan search space. Otherwise, the sub query would be planned independently and traded as a black box during planning of the outer query. Or reduce joint strength. Okay, let's look at this example first. So here is a query. The query is select something from full left join bar on something where bar point D equals 42. Actually we know the equal operator in where is streaks. So for any row where the left join failed in nonce for bar column, the streaks operator will always retain now causing the outer wear to fail. Therefore, there is no need for the join to produce the now extended rows in the first place. So which makes it a plain inner join, not an outer join. So we can conclude that if there is a strict call about the outer join that constraints a var from the non-nullable side of the join to be known. Now, then we can reduce the outer join to inner join. And now let's look at another example. So here is another query and the query is select stuff from full left join bar on full point A equals bar point C where bar point C is known. Okay, for this query, actually we know the join clause full point A equals bar point C is streaks for bar point C, right? So only now extended rows can pass the upper wear. So the bar point C is known. And we can conclude that what the query is really specifying is the anti-joint. So that is to say if the out joins all in calls are streaks for any nullable var that was for the null by higher call levels, then we can reduce the outer join to anti-joints. So until now what we are talking about is all about the pass three transformations. And at a later pre-processing, we would distribute all kinds of call clauses and build the equivalence classes, gather information about the join ordering restrictions, remove useless joins and so on. So first let's look how we distribute the call clauses. In general, we want to use each call as low as possible join level. When dealing with inner joins only, we can push a call down to its natural semantic level. So here by natural semantic level, I mean the level associated with just the base real user in this call. However, when dealing with out joins, a call may be delayed and cannot be pushed down to its natural semantic level. And for this kind of outer join delayed calls, we mark them with required real IDs, which includes all the required reals in the outer join. So by pretending that the call references all the reals required to form the outer join, actually we prevent it from being evaluated below the outer join. And usually there are two cases that our call can be out of the join delay. And so for the first case, let's look at this query. So the query is see let's start from full left join bar on 4.8 equals 42. So it's a left join, right? And it has a join call, 4.8 equals 42. The join call mentions the nullable side real, which is full. And if we push this call down below the outer join, then it will become a filter on full. And it will remove all the rules that it is not equal to 42 before the join. So as a result, we might lose some non-extended rules that should have been in the final result set. So we can lose that. And out joins all join on calls mentioning nullable side reals cannot be pushed down below the outer join. And for the second case, let's look at this query. So the query is see let's start from full left join bar on 4.8 equals 8.4. Where call less 8.4 when equals 42. Okay, it's a left join. And there is a call about this outer join, which is call less 8.4 when equals 42. And this call references the nullable while 8.4. So if we push this call down below the outer join, then it would become a filter on bar and it would reject the rules before the outer join. So as a result, it might cause the outer join to emit non-extended rules that should not have been formed or that should have been rejected by the calls. So we can conclude that cause a parallel in where or in your join above the outer join cannot be pushed down below the outer join if the reference and the nullable was. Okay, let's move on. So in equivalence classes, for multiple join bar equality clauses a equals b that are not out of the joint delay. We use equivalence classes to record this knowledge. So in equivalence class represents several values that are no at all transitively equal to each other. And in equivalence clauses are removed from the standard call distribution process. Instead, e-class based call clauses are generated dynamically when needed. And the equivalence class is also represents the value that pass key orders by. So the logic here is since since we know x equals y. So order by x should be the same as order by y. Okay, now let's talk about joint order restrictions. So if we have outer joins, actually we cannot perform the joint in any order. Outer joins induce joint order restrictions. And one side outer joins like left join or right join constraints the order of joining partially, but not completely. And in general, non-full joins can be freely associated associated into the left hand side or outer join. But in some cases, they cannot be associated into the right hand side. So let's look at two examples below. For the first example, a left join b predicate p a b and then in the joint c on P a c. So this inner join can be associated into the left hand side of the left side. So we can we can get a inner join c on P a c and then left join b on P a b. And let's look at the oh sorry, let's look at the second example. So a a left join b p a b and then inner join c on P b c. So for this time, this inner join cannot be associated into the right hand side of the left join. So even though there is a joint clause between b and c, actually we cannot join them first because it's illegal joint order. And and for for the non-full joins, we flatten them to the top level join list so that they can participate fully in the joint order search. And meanwhile, we record information about each other join in order to avoid generating illegal joint orders. So another thing we do as a little pre-processing is to remove useless joins. For left join, if it's inner real is a single b-strain and the inner real attributes are not used above the join, and the join condition cannot match more than one inner side row. Actually, the join we are just duplicate is left input. So in this case, actually, we can remove this join altogether. So for example, here we have a query and the query is selected 4.8 from full left to join. A sub query is a sub query is selected this thing to c as c from bar sub 4.8 equals sub point c. So so so for this query, the inner real is a is a single b-strain or sub query, and the join condition cannot match more than one inner side row since attribute c is unique because here we are using distinct. So this left join can be removed. Okay, now let's move on to the second phase scan joint planning. So at this phase, we deal with the from and the where path of the query. And also we know about all the by so that we can we can design more joints and to avoid a final thought if possible. So for example, for this query and the query is select stuff from full join bar on 4.8 equals bar point c and full point b equals bar point d all the by b and a. So when generating the merge join, actually, we can start table full by a and b. We can also start table full by b and a right. But since we know that the final output is is requested to be sorted by d and a. So we chose a sort key d and a for table full so that we can avoid the final thought. And the second phase is basically driven by cost estimates. So for scan joint planning, basically, what we do here is to first identify feasible scan methods for these relations, estimate their cost and the result sizes, and then search the joint orders base using a dynamic programming or heuristic genetic query optimizer method to identify feasible plans for joint relations. And meanwhile, we all know how to join ordering restrictions to avoid generating illegal joint orders. And the and here and here for each relation base real or join real, we produce one or more passes. So so multi multi joins have to be built up from pairwise joints. Because that's all the executor knows how to do. So for any given pairwise joint step, we can identify the the best input passes and the joint methods such as nested loop or merge or hash join. While three forward cost of comparations resulting in a lethal passes much as for the for for the base relation. And finding the best ordering of the pairwise joints is a hard part. So usually we have many choices of joint order for multi we join query and some others will be cheaper than others. So if the query contains only inner joints, we can join the base relations in any order. But with other joints, as we have talked about, they can be reordered in some but not all cases. So we handle that by checking whether each proposed joint step is legal. And this standard joint search method, we construct the joint tree level by level using a dynamic programming algorithm. So first, assume assumes that we have already generated passes for each base relation. Then we generate the passes for each possible two-way joint and then for each possible three-way joint and then four-way joint until all base relations are joined into into a single joint relation. So here is a demo about how we construct the joint tree. So the query for the demo is select stuff from a joint, b joint c, b point g, equals c point g, a point i equals b point i. And as a first step, we generate the passes for each base relation. And then we generate the passes for two-way joint. For a joint b, we create two passes, one is, for example, hash joint and one is merge joint. And then we figure out that the possible hash joint is in inferior to, so we just discard it. And here for a joint c, actually we don't try to make joints with them because we found that there is no joint clause between them. And then for b joint c, we create two passes and discard the inferior one. And as in we generate the passes for three-way joint. So for joint real a, b and base real c, we create two passes and discard the inferior one. And for joint real bc and base real a, we also create two passes, but then both are discarded. So both are discarded when we're competing with the existing pass. So at last we pick this pass, which is merge joint a and b first and then merge joint bc. And joint searching is expensive. So actually an a-way joint problem can potentially be implemented in any factorial different joint orders. So usually it's not feasible to consider all possibilities. And what we do here is to just to use a few heuristics, like as Shoyin said, demo, we don't consider clause less joints. And with too many relations, by default it's 12. We fall back to the genetic query optimizer. Heuristics use in joint search. So as we said, we don't join relations that are not connected by any joint clause, unless first two by joining all the restrictions. And also for large joint problems, we try to break it down into sub problems according to some collapse limits. For example, here we have a query and we have 10 tables joining together. So by setting the joint collapse limits back to four, we can break it down into sub problems that's no more than four we join. And then we can handle each sub problem independently. Okay, so now let's move to the third phase post scan joint planning. So at this phase, we deal with group by aggregation, window functions, distinct. We also deal with set operations like uni, intersect and accepts. And then we apply final sort if needed by order by. And for each of our steps, we produce one or more passes. And at the last we add lock rules, limit modified table steps to each surviving pass. So this is a third phase. And the last phase is post processing, where we expand the best pass to plan. And then we adjust some representational details of the plan. So such as we flatten sub query range tables into a single list. We label was in upper plan those as outer one or inner one to refer to the outputs of their sub plans. And we also remove unnecessary sub queries again, the pain and the module plan knows if we figure out that they are not doing anything useful. So this is the first the last phase. And this is all for my talk. Thank you. you you
this session. Today my topic is hacking the query agenda of my talk. First, I will introduce a the second part is about the different phases of query stream. And then the rewriters to perform view and raw expansion. Next is the planner who planning. Although the planning process can be phase is poster scan-join planning, which is to each phase one by one. At early pre-processing, expressions, we reduce any recognizably constant actually we can reduce it to a constant null. And trade into a more efficient form. But in this reducing other joints to inner joints or anti joints. So here is a query with exists sublink. The query is select stuff from full. We are that what the query is really specifying is the restrictions, remove useless joins and so on. So restrictions. So if we have outer joins, actually how to join ordering restrictions to avoid joints, as we have talked about, they can be was in upper plan those as outer one or inner one