DRILL-937: Optimize boolean and/or operator with short circuit evaluation in run-time generated code.
Project: http://git-wip-us.apache.org/repos/asf/incubator-drill/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-drill/commit/38dde9e9 Tree: http://git-wip-us.apache.org/repos/asf/incubator-drill/tree/38dde9e9 Diff: http://git-wip-us.apache.org/repos/asf/incubator-drill/diff/38dde9e9 Branch: refs/heads/master Commit: 38dde9e9d780aa3dba6faa1c44d6669e7f4bb202 Parents: 1568fc6 Author: Jinfeng Ni <[email protected]> Authored: Sun Jun 15 14:28:12 2014 -0700 Committer: Jacques Nadeau <[email protected]> Committed: Mon Jun 16 13:50:49 2014 -0700 ---------------------------------------------------------------------- .../apache/drill/exec/expr/ClassGenerator.java | 16 +++ .../drill/exec/expr/EvaluationVisitor.java | 136 +++++++++++++++++++ .../exec/expr/annotations/FunctionTemplate.java | 3 +- .../exec/expr/fn/DrillSCBooleanOPHolder.java | 35 +++++ .../drill/exec/expr/fn/FunctionConverter.java | 6 + .../drill/exec/expr/fn/impl/BitFunctions.java | 4 +- 6 files changed, 197 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/ClassGenerator.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/ClassGenerator.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/ClassGenerator.java index ab3c307..7b1832c 100644 --- a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/ClassGenerator.java +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/ClassGenerator.java @@ -49,6 +49,7 @@ import com.sun.codemodel.JExpr; import com.sun.codemodel.JExpression; import com.sun.codemodel.JFieldRef; import com.sun.codemodel.JInvocation; +import com.sun.codemodel.JLabel; import com.sun.codemodel.JMethod; import com.sun.codemodel.JMod; import com.sun.codemodel.JType; @@ -76,6 +77,7 @@ public class ClassGenerator<T>{ private final JCodeModel model; private int index = 0; + private int labelIndex = 0; private MappingSet mappings; public static MappingSet getDefaultMapping(){ @@ -149,6 +151,20 @@ public class ClassGenerator<T>{ return getBlock(getCurrentMapping().getMethodName(BlockType.CLEANUP)); } + public void nestEvalBlock(JBlock block) { + String methodName = getCurrentMapping().getMethodName(BlockType.EVAL); + this.blocks[sig.get(methodName)].addLast(block); + } + + public void unNestEvalBlock() { + String methodName = getCurrentMapping().getMethodName(BlockType.EVAL); + this.blocks[sig.get(methodName)].removeLast(); + } + + public JLabel getEvalBlockLabel (String prefix) { + return getEvalBlock().label(prefix + labelIndex ++); + } + public JVar declareVectorValueSetupAndMember(String batchName, TypedFieldId fieldId){ return declareVectorValueSetupAndMember( DirectExpression.direct(batchName), fieldId); } http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/EvaluationVisitor.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/EvaluationVisitor.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/EvaluationVisitor.java index 31cc563..efc7259 100644 --- a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/EvaluationVisitor.java +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/EvaluationVisitor.java @@ -55,6 +55,7 @@ import org.apache.drill.exec.compile.sig.ConstantExpressionIdentifier; import org.apache.drill.exec.expr.ClassGenerator.BlockType; import org.apache.drill.exec.expr.ClassGenerator.HoldingContainer; import org.apache.drill.exec.expr.fn.DrillFuncHolder; +import org.apache.drill.exec.expr.fn.DrillSCBooleanOPHolder; import org.apache.drill.exec.expr.fn.FunctionImplementationRegistry; import org.apache.drill.exec.expr.fn.HiveFuncHolder; import org.apache.drill.exec.physical.impl.filter.ReturnValueExpression; @@ -104,6 +105,15 @@ public class EvaluationVisitor { if (holderExpr instanceof DrillFuncHolderExpr) { DrillFuncHolder holder = ((DrillFuncHolderExpr) holderExpr).getHolder(); + + if (holder instanceof DrillSCBooleanOPHolder && holderExpr.getName().equals("booleanAnd")) { + return visitBooleanAnd(holderExpr, generator); + } + + if (holder instanceof DrillSCBooleanOPHolder && holderExpr.getName().equals("booleanOr")) { + return visitBooleanOr(holderExpr, generator); + } + JVar[] workspaceVars = holder.renderStart(generator, null); if (holder.isNested()) @@ -592,6 +602,132 @@ public class EvaluationVisitor { FunctionCall fc = new FunctionCall(convertFunctionName, newArgs, e.getPosition()); return fc.accept(this, value); } + + private HoldingContainer visitBooleanAnd(FunctionHolderExpression holderExpr, + ClassGenerator<?> generator) { + + HoldingContainer out = generator.declare(holderExpr.getMajorType()); + + JLabel label = generator.getEvalBlockLabel("AndOP"); + JBlock eval = generator.getEvalBlock().block(); // enter into nested block + generator.nestEvalBlock(eval); + + HoldingContainer arg = null; + + JExpression e = null; + + // value of boolean "and" when one side is null + // p q p and q + // true null null + // false null false + // null true null + // null false false + // null null null + for (int i = 0; i < holderExpr.args.size(); i++) { + arg = holderExpr.args.get(i).accept(this, generator); + + JBlock earlyExit = null; + if (arg.isOptional()) { + earlyExit = eval._if(arg.getIsSet().eq(JExpr.lit(1)).cand(arg.getValue().ne(JExpr.lit(1))))._then(); + if(e == null){ + e = arg.getIsSet(); + }else{ + e = e.mul(arg.getIsSet()); + } + } else { + earlyExit = eval._if(arg.getValue().ne(JExpr.lit(1)))._then(); + } + + if (out.isOptional()) { + earlyExit.assign(out.getIsSet(), JExpr.lit(1)); + } + + earlyExit.assign(out.getValue(), JExpr.lit(0)); + earlyExit._break(label); + } + + if (out.isOptional()) { + assert (e != null); + + JConditional notSetJC = eval._if(e.eq(JExpr.lit(0))); + notSetJC._then().assign(out.getIsSet(), JExpr.lit(0)); + + JBlock setBlock = notSetJC._else().block(); + setBlock.assign(out.getIsSet(), JExpr.lit(1)); + setBlock.assign(out.getValue(), JExpr.lit(1)); + } else { + assert (e == null); + eval.assign(out.getValue(), JExpr.lit(1)) ; + } + + generator.unNestEvalBlock(); // exit from nested block + + return out; + } + + private HoldingContainer visitBooleanOr(FunctionHolderExpression holderExpr, + ClassGenerator<?> generator) { + + HoldingContainer out = generator.declare(holderExpr.getMajorType()); + + JLabel label = generator.getEvalBlockLabel("OrOP"); + JBlock eval = generator.getEvalBlock().block(); + generator.nestEvalBlock(eval); // enter into nested block. + + HoldingContainer arg = null; + + JExpression e = null; + + // value of boolean "or" when one side is null + // p q p and q + // true null true + // false null null + // null true true + // null false null + // null null null + + for (int i = 0; i < holderExpr.args.size(); i++) { + arg = holderExpr.args.get(i).accept(this, generator); + + JBlock earlyExit = null; + if (arg.isOptional()) { + earlyExit = eval._if(arg.getIsSet().eq(JExpr.lit(1)).cand(arg.getValue().eq(JExpr.lit(1))))._then(); + if(e == null){ + e = arg.getIsSet(); + }else{ + e = e.mul(arg.getIsSet()); + } + } else { + earlyExit = eval._if(arg.getValue().eq(JExpr.lit(1)))._then(); + } + + if (out.isOptional()) { + earlyExit.assign(out.getIsSet(), JExpr.lit(1)); + } + + earlyExit.assign(out.getValue(), JExpr.lit(1)); + earlyExit._break(label); + } + + if (out.isOptional()) { + assert (e != null); + + JConditional notSetJC = eval._if(e.eq(JExpr.lit(0))); + notSetJC._then().assign(out.getIsSet(), JExpr.lit(0)); + + JBlock setBlock = notSetJC._else().block(); + setBlock.assign(out.getIsSet(), JExpr.lit(1)); + setBlock.assign(out.getValue(), JExpr.lit(0)); + } else { + assert (e == null); + eval.assign(out.getValue(), JExpr.lit(0)) ; + } + + generator.unNestEvalBlock(); // exit from nested block. + + return out; + } + } private class ConstantFilter extends EvalVisitor { http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/annotations/FunctionTemplate.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/annotations/FunctionTemplate.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/annotations/FunctionTemplate.java index 9d7091d..b364a4a 100644 --- a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/annotations/FunctionTemplate.java +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/annotations/FunctionTemplate.java @@ -61,6 +61,7 @@ public @interface FunctionTemplate { DECIMAL_CAST, DECIMAL_DIV_SCALE, DECIMAL_SET_SCALE, - DECIMAL_ZERO_SCALE; + DECIMAL_ZERO_SCALE, + SC_BOOLEAN_OPERATOR } } http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/DrillSCBooleanOPHolder.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/DrillSCBooleanOPHolder.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/DrillSCBooleanOPHolder.java new file mode 100644 index 0000000..d6d7037 --- /dev/null +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/DrillSCBooleanOPHolder.java @@ -0,0 +1,35 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.drill.exec.expr.fn; + +import java.util.List; +import java.util.Map; + +import org.apache.drill.exec.expr.annotations.FunctionTemplate.FunctionScope; +import org.apache.drill.exec.expr.annotations.FunctionTemplate.NullHandling; + +public class DrillSCBooleanOPHolder extends DrillSimpleFuncHolder{ + + public DrillSCBooleanOPHolder(FunctionScope scope, NullHandling nullHandling, boolean isBinaryCommutative, boolean isRandom, + String[] registeredNames, ValueReference[] parameters, ValueReference returnValue, WorkspaceReference[] workspaceVars, + Map<String, String> methods, List<String> imports) { + super(scope, nullHandling, isBinaryCommutative, isRandom, registeredNames, parameters, returnValue, workspaceVars, methods, imports); + } + +} http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/FunctionConverter.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/FunctionConverter.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/FunctionConverter.java index 75c3cbb..2107421 100644 --- a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/FunctionConverter.java +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/FunctionConverter.java @@ -235,6 +235,12 @@ public class FunctionConverter { template.isBinaryCommutative(), template.isRandom(), registeredNames, ps, outputField, works, methods, imports); + case SC_BOOLEAN_OPERATOR: + return new DrillSCBooleanOPHolder(template.scope(), template.nulls(), + template.isBinaryCommutative(), + template.isRandom(), registeredNames, + ps, outputField, works, methods, imports); + case DECIMAL_MAX_SCALE: return new DrillDecimalMaxScaleFuncHolder(template.scope(), template.nulls(), template.isBinaryCommutative(), template.isRandom(), registeredNames, ps, outputField, works, methods, imports); http://git-wip-us.apache.org/repos/asf/incubator-drill/blob/38dde9e9/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/BitFunctions.java ---------------------------------------------------------------------- diff --git a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/BitFunctions.java b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/BitFunctions.java index 1ea4988..3ffc682 100644 --- a/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/BitFunctions.java +++ b/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/BitFunctions.java @@ -29,7 +29,7 @@ import org.apache.drill.exec.record.RecordBatch; public class BitFunctions { - @FunctionTemplate(names = {"booleanOr", "or", "||"}, scope = FunctionScope.SIMPLE, nulls = NullHandling.NULL_IF_NULL) + @FunctionTemplate(names = {"booleanOr", "or", "||"}, scope = FunctionScope.SC_BOOLEAN_OPERATOR, nulls = NullHandling.NULL_IF_NULL) public static class BitOr implements DrillSimpleFunc { @Param BitHolder left; @@ -43,7 +43,7 @@ public class BitFunctions { } } - @FunctionTemplate(names = {"booleanAnd", "and", "&&"}, scope = FunctionScope.SIMPLE, nulls = NullHandling.NULL_IF_NULL) + @FunctionTemplate(names = {"booleanAnd", "and", "&&"}, scope = FunctionScope.SC_BOOLEAN_OPERATOR, nulls = NullHandling.NULL_IF_NULL) public static class BitAnd implements DrillSimpleFunc { @Param BitHolder left;
