Hive
  1. Hive
  2. HIVE-1750

Remove Partition Filtering Conditions when Possible

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.7.0
    • Component/s: None
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      Description

      For some simple queries, partition filtering constraints take 8% of CPU time (now 16% since we filter twice) even if the result is always true. When possible, we should remove these constraints to save CPU times.

      1. HIVE-1750.4.patch
        1.33 MB
        Siying Dong
      2. HIVE-1750.3.patch
        1.24 MB
        Siying Dong
      3. HIVE-1750.2.patch
        1.09 MB
        Siying Dong
      4. HIVE-1750.1.patch
        1.10 MB
        Siying Dong

        Issue Links

          Activity

          Hide
          Namit Jain added a comment -

          Committed. Thanks Siying

          Show
          Namit Jain added a comment - Committed. Thanks Siying
          Hide
          Namit Jain added a comment -
          Show
          Namit Jain added a comment - +1 will commit after https://issues.apache.org/jira/browse/HIVE-1751
          Hide
          Namit Jain added a comment -

          Do you think it might be simpler to update opToParts list in PartitionPruner.prune() itself - reduces the possibility of bugs.
          It can definitely be done in a follow-up

          Show
          Namit Jain added a comment - Do you think it might be simpler to update opToParts list in PartitionPruner.prune() itself - reduces the possibility of bugs. It can definitely be done in a follow-up
          Hide
          Siying Dong added a comment -

          1. fix two small bugs
          2. add test cases Namit mentioned
          3. addressing Amareshwari's comment: add put() after PartitionPruner.prune() in SemanticAnalyzer.java

          Show
          Siying Dong added a comment - 1. fix two small bugs 2. add test cases Namit mentioned 3. addressing Amareshwari's comment: add put() after PartitionPruner.prune() in SemanticAnalyzer.java
          Hide
          Amareshwari Sriramadasu added a comment -

          SemanticAnalyzer.java still has code without a 'put' after PartitionPruner.prune().

          Show
          Amareshwari Sriramadasu added a comment - SemanticAnalyzer.java still has code without a 'put' after PartitionPruner.prune().
          Hide
          Namit Jain added a comment -

          Amareshwari, can you also confirm the changes ?

          Show
          Namit Jain added a comment - Amareshwari, can you also confirm the changes ?
          Hide
          Namit Jain added a comment - - edited

          The code changes look good to me.
          Can you add some tests and do a explain plan for all kinds of scenarios:

          ds < 10 and x > 5
          ds < 10 or x > 5
          ds < 10 and x > 5 and y > 10
          (ds < 10 and x > 5) or (ds > 10 and y > 5)
          (ds < 10 and x > 5) or (ds > 5 and y > 5)
          (ds < 10 or x > 5) and (ds > 5 or y > 5)

          Show
          Namit Jain added a comment - - edited The code changes look good to me. Can you add some tests and do a explain plan for all kinds of scenarios: ds < 10 and x > 5 ds < 10 or x > 5 ds < 10 and x > 5 and y > 10 (ds < 10 and x > 5) or (ds > 10 and y > 5) (ds < 10 and x > 5) or (ds > 5 and y > 5) (ds < 10 or x > 5) and (ds > 5 or y > 5)
          Hide
          Siying Dong added a comment -

          1. fix the bug of opOr -> opAnd
          2. remove walkEvalExpr, as it is not really needed
          3. Instead of removing operator after walking its expression tree, save the operator and remove them one by one after walking the operation tree. It is to handle the case like:
          from src_tbl
          insert overwrite table tbl1 where ds='1'
          insert overwrite table tbl2 where ds='1';
          Removing operators when walking the tree is dangerous in these cases.
          4. fix comments and add some. Fix variable name.
          5. rename classes for partition condition remover to be different from ppr
          6. add some queries in the test: 1. cover opAnd case; 2. cover multiple insert from the same partition
          7. always put pruned partitions into the hash map. (we cannot remove to calling calling partition pruners multiple places for PartitionConditionRemover is not guaranteed to prune partitions, for cases like table is not partitioned)
          8. PartitionPruner and PartitionConditonRemover to share some codes for evaluating the expression with partition columns
          9. some other code cleaning up

          ran the test pcr.q but still running the whole test suites. Will "submit patch" when other tests pass.

          Show
          Siying Dong added a comment - 1. fix the bug of opOr -> opAnd 2. remove walkEvalExpr, as it is not really needed 3. Instead of removing operator after walking its expression tree, save the operator and remove them one by one after walking the operation tree. It is to handle the case like: from src_tbl insert overwrite table tbl1 where ds='1' insert overwrite table tbl2 where ds='1'; Removing operators when walking the tree is dangerous in these cases. 4. fix comments and add some. Fix variable name. 5. rename classes for partition condition remover to be different from ppr 6. add some queries in the test: 1. cover opAnd case; 2. cover multiple insert from the same partition 7. always put pruned partitions into the hash map. (we cannot remove to calling calling partition pruners multiple places for PartitionConditionRemover is not guaranteed to prune partitions, for cases like table is not partitioned) 8. PartitionPruner and PartitionConditonRemover to share some codes for evaluating the expression with partition columns 9. some other code cleaning up ran the test pcr.q but still running the whole test suites. Will "submit patch" when other tests pass.
          Hide
          Siying Dong added a comment -

          Namit, sorry I misunderstood. Yes, maybe evalExprWithPart() can share some codes with PartitionPruner.

          Show
          Siying Dong added a comment - Namit, sorry I misunderstood. Yes, maybe evalExprWithPart() can share some codes with PartitionPruner.
          Hide
          Siying Dong added a comment -

          Mostly the codes can share are walking rule settings and finding out filter operator following table scans. Kind of framework-like codes, instead of util functions. Need some efforts if we want to share them.

          By the way, Operator.removeChild() doesn't do the same thing as what we want to. We want to append children of the deleted filter operator to its parent but Operator.removeChild() is just a simple removing. I'll write another function in Operator to do the job.

          Show
          Siying Dong added a comment - Mostly the codes can share are walking rule settings and finding out filter operator following table scans. Kind of framework-like codes, instead of util functions. Need some efforts if we want to share them. By the way, Operator.removeChild() doesn't do the same thing as what we want to. We want to append children of the deleted filter operator to its parent but Operator.removeChild() is just a simple removing. I'll write another function in Operator to do the job.
          Hide
          Namit Jain added a comment -

          Add comments for evalExprWithPart.
          Also, do you think you can share/merge this code with PartitionPruner.prune()

          Show
          Namit Jain added a comment - Add comments for evalExprWithPart. Also, do you think you can share/merge this code with PartitionPruner.prune()
          Hide
          Namit Jain added a comment -

          1. More comments for NodeInfoWrapper
          2. Why is it public ?
          3. Why do you need wlkEvalExpr

          Line 294: ExprProcFactory
          ExprNodeConstantDesc falseDesc = new ExprNodeConstantDesc(
          wrapper.outExpr.getTypeInfo(), Boolean.TRUE);
          return new NodeInfoWrapper(WalkState.TRUE, null, falseDesc, falseDesc);

          Change variable name

          313:
          for (Object child : nodeOutputs) {
          NodeInfoWrapper child_nd = (NodeInfoWrapper) child;
          if (c == 0)

          { c1 = (NodeInfoWrapper) child; c = 1; }

          c2 = (NodeInfoWrapper) child;
          }

          This code is way more complicated than:

          c1 = nodeOutputs[0]
          c2 = nodeOutputs[1]

          334:
          for (int i = 0; i < ctx.getPartList().size(); i++) {
          results[i] = opOr(c1.ResultVector[i], c2.ResultVector[i]);

          shouldn't it be opAnd()

          OpProcFactory:153
          if (wrapper.state == ExprProcFactory.WalkState.TRUE) {
          //top.setChildOperators(fop.getChildOperators());

          You can use Operator.removeChild()

          Show
          Namit Jain added a comment - 1. More comments for NodeInfoWrapper 2. Why is it public ? 3. Why do you need wlkEvalExpr Line 294: ExprProcFactory ExprNodeConstantDesc falseDesc = new ExprNodeConstantDesc( wrapper.outExpr.getTypeInfo(), Boolean.TRUE); return new NodeInfoWrapper(WalkState.TRUE, null, falseDesc, falseDesc); Change variable name 313: for (Object child : nodeOutputs) { NodeInfoWrapper child_nd = (NodeInfoWrapper) child; if (c == 0) { c1 = (NodeInfoWrapper) child; c = 1; } c2 = (NodeInfoWrapper) child; } This code is way more complicated than: c1 = nodeOutputs [0] c2 = nodeOutputs [1] 334: for (int i = 0; i < ctx.getPartList().size(); i++) { results [i] = opOr(c1.ResultVector [i] , c2.ResultVector [i] ); shouldn't it be opAnd() OpProcFactory:153 if (wrapper.state == ExprProcFactory.WalkState.TRUE) { //top.setChildOperators(fop.getChildOperators()); You can use Operator.removeChild()
          Hide
          Siying Dong added a comment -

          Addressing the comments and do some code cleaning up.

          Show
          Siying Dong added a comment - Addressing the comments and do some code cleaning up.
          Hide
          Siying Dong added a comment -

          In the case that at least one partition is a table, the result can be unpredictable. I return for the corner case since I think it is safer.

          Show
          Siying Dong added a comment - In the case that at least one partition is a table, the result can be unpredictable. I return for the corner case since I think it is safer.
          Hide
          Siying Dong added a comment -

          Amareshwari, it's a good catch. I'll make a put there. Will submit a patch later.

          Show
          Siying Dong added a comment - Amareshwari, it's a good catch. I'll make a put there. Will submit a patch later.
          Hide
          Ted Yu added a comment -

          In ExprProcFactory.java, GenericFuncExprProcessor.process():
          + ExprNodeConstantDesc falseDesc = new ExprNodeConstantDesc(
          + wrapper.outExpr.getTypeInfo(), Boolean.TRUE);
          variable name should be changed.

          Show
          Ted Yu added a comment - In ExprProcFactory.java, GenericFuncExprProcessor.process(): + ExprNodeConstantDesc falseDesc = new ExprNodeConstantDesc( + wrapper.outExpr.getTypeInfo(), Boolean.TRUE); variable name should be changed.
          Hide
          Amareshwari Sriramadasu added a comment -

          A couple of minor comments:

          • javadoc for isOpNot and isOpOr in FunctionRegistry is wrong. Do you want to correct it?
          • For the below code change in many optimizers :
            +          prunedParts = pGraphContext.getOpToPartList().get(tso);
            +          if (prunedParts == null) {
            +            prunedParts = PartitionPruner.prune(....);
            +          }
            

            I was expecting a pGraphContext.getOpToPartList().put().
            Is PartitonPruner.prune call really needed in all those places, because PartitionConditionRemover already does a put if it is not null ? Correct me if I'm wrong.

          Show
          Amareshwari Sriramadasu added a comment - A couple of minor comments: javadoc for isOpNot and isOpOr in FunctionRegistry is wrong. Do you want to correct it? For the below code change in many optimizers : + prunedParts = pGraphContext.getOpToPartList().get(tso); + if (prunedParts == null ) { + prunedParts = PartitionPruner.prune(....); + } I was expecting a pGraphContext.getOpToPartList().put(). Is PartitonPruner.prune call really needed in all those places, because PartitionConditionRemover already does a put if it is not null ? Correct me if I'm wrong.
          Hide
          Namit Jain added a comment -

          OpProcFactory:

          for (Partition p: prunedPartList.getConfirmedPartns()) {
          if (!p.getTable().isPartitioned())

          { return null; }
          }
          for (Partition p: prunedPartList.getUnknownPartns()) {
          if (!p.getTable().isPartitioned()) { return null; }

          }

          Why are the above changes needed ?

          The overall approach looks good - still looking in detail.

          Show
          Namit Jain added a comment - OpProcFactory: for (Partition p: prunedPartList.getConfirmedPartns()) { if (!p.getTable().isPartitioned()) { return null; } } for (Partition p: prunedPartList.getUnknownPartns()) { if (!p.getTable().isPartitioned()) { return null; } } Why are the above changes needed ? The overall approach looks good - still looking in detail.
          Hide
          Siying Dong added a comment -

          Remove #PartitionConditionRemover.java# and some files that were not seriously modified.

          Show
          Siying Dong added a comment - Remove #PartitionConditionRemover.java# and some files that were not seriously modified.
          Hide
          Ted Yu added a comment -

          Should #PartitionConditionRemover.java# be removed from the patch ?

          Show
          Ted Yu added a comment - Should #PartitionConditionRemover.java# be removed from the patch ?
          Hide
          Siying Dong added a comment -

          After generating partition predicates, we add another step to prune partitions and according to the list of pruned partitions, remove partition predicates when possible. A new optimizer (PartitionConditionRemover) is created for it, which walks the operator tree and the expression tree for target filter operator. For every expression including partition column, we evaluate the value for every partition pruned. If the result agrees for all partitions, we replace expression to be the constant result. We further remove the nodes when possible. Finally, if the whole expression tree is always to return true, we remove the filter operator.

          We only handle the filter pushed down to near the table scan operators. We'll reply on HIVE-1538 to remove the original one.

          Fix the unit test results accordingly and add a new unit test.

          Show
          Siying Dong added a comment - After generating partition predicates, we add another step to prune partitions and according to the list of pruned partitions, remove partition predicates when possible. A new optimizer (PartitionConditionRemover) is created for it, which walks the operator tree and the expression tree for target filter operator. For every expression including partition column, we evaluate the value for every partition pruned. If the result agrees for all partitions, we replace expression to be the constant result. We further remove the nodes when possible. Finally, if the whole expression tree is always to return true, we remove the filter operator. We only handle the filter pushed down to near the table scan operators. We'll reply on HIVE-1538 to remove the original one. Fix the unit test results accordingly and add a new unit test.
          Hide
          Siying Dong added a comment -

          How about doing this (something is much more expensive but should be right):

          We go throught the whole expression tree, for every node, we keep a vector of results. Each result is for one partition, being true, false or null.
          When doing logical expression, we do logical expression for every vector. Every for any node, all the result of the element is all true or all false, we can replace it with the constant true or false, and potentially remove its parent logical operator.

          Since we only replace nodes when we know the results for sure, this algorithm will guarantee to be correct.

          Show
          Siying Dong added a comment - How about doing this (something is much more expensive but should be right): We go throught the whole expression tree, for every node, we keep a vector of results. Each result is for one partition, being true, false or null. When doing logical expression, we do logical expression for every vector. Every for any node, all the result of the element is all true or all false, we can replace it with the constant true or false, and potentially remove its parent logical operator. Since we only replace nodes when we know the results for sure, this algorithm will guarantee to be correct.
          Hide
          He Yongqiang added a comment -

          Under a 'or', if we see a non-partitioning column, they can not be removed.
          Otherwise, it can be removed.

          Show
          He Yongqiang added a comment - Under a 'or', if we see a non-partitioning column, they can not be removed. Otherwise, it can be removed.
          Hide
          Siying Dong added a comment -

          How about:
          (ds=1 and c='1) or (ds=2 or ds=3)

          (ds=2 or ds=3) is moved?

          Show
          Siying Dong added a comment - How about: (ds=1 and c='1) or (ds=2 or ds=3) (ds=2 or ds=3) is moved?
          Hide
          John Sichi added a comment -

          This is the same logic I have in IndexPredicateAnalyzer.analyzePredicate. And it can be configured with the specific set of columns to allow. So you might be able to reuse it as is.

          Show
          John Sichi added a comment - This is the same logic I have in IndexPredicateAnalyzer.analyzePredicate. And it can be configured with the specific set of columns to allow. So you might be able to reuse it as is.
          Hide
          Namit Jain added a comment -

          I think we can use the following rules:

          If the predicates contain only ANDs, remove the predicate containing partitioning columns

          In case of any UDF (including OR):
          Get the columns used as arguments

          If all columns in the parameters are partitioning columns, we can remove the partitioning predicate.
          If a column in the partitioning predicate contains a non-partitioning column, we cannot remove it,

          for eg:

          If the condition is:

          ds=1 or ds=2

          ds=1 and x=1

          we can remove the conditions for partitioning columns.

          However, if the condition is:

          ds = 1 or x = 1

          we cannot modify the condition.

          We can go over all UDFs and add them in the category of UDFs which behave like AND.
          Any unknowns behave like OR

          Show
          Namit Jain added a comment - I think we can use the following rules: If the predicates contain only ANDs, remove the predicate containing partitioning columns In case of any UDF (including OR): Get the columns used as arguments If all columns in the parameters are partitioning columns, we can remove the partitioning predicate. If a column in the partitioning predicate contains a non-partitioning column, we cannot remove it, for eg: If the condition is: ds=1 or ds=2 ds=1 and x=1 we can remove the conditions for partitioning columns. However, if the condition is: ds = 1 or x = 1 we cannot modify the condition. We can go over all UDFs and add them in the category of UDFs which behave like AND. Any unknowns behave like OR
          Hide
          Namit Jain added a comment -

          Note that it is different from HIVE-1538.

          For eg, if T is partitioned on ds,
          and the query is:

          select c1 from T where ds = '1' and c2 > 10;

          There is no reason to apply the filter ds='1' for each row. Partition pruning has already taken care of it.

          However, for a query like:

          select .. from T where (ds='1' and x >1) or (ds='2' and x < 10);

          We need the predicates on partitioning column 'ds'.

          Show
          Namit Jain added a comment - Note that it is different from HIVE-1538 . For eg, if T is partitioned on ds, and the query is: select c1 from T where ds = '1' and c2 > 10; There is no reason to apply the filter ds='1' for each row. Partition pruning has already taken care of it. However, for a query like: select .. from T where (ds='1' and x >1) or (ds='2' and x < 10); We need the predicates on partitioning column 'ds'.

            People

            • Assignee:
              Siying Dong
              Reporter:
              Siying Dong
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development