You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hive.apache.org by gu...@apache.org on 2013/08/12 04:27:34 UTC
svn commit: r1513029 [1/2] - in /hive/trunk: ivy/ ql/
ql/src/java/org/apache/hadoop/hive/ql/io/sarg/
ql/src/test/org/apache/hadoop/hive/ql/io/sarg/
Author: gunther
Date: Mon Aug 12 02:27:33 2013
New Revision: 1513029
URL: http://svn.apache.org/r1513029
Log:
HIVE-4579: Create a SARG interface for RecordReaders (Owen O'Malley via Gunther Hagleitner)
Added:
hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/
hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/PredicateLeaf.java
hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgument.java
hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java
hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/
hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/TestSearchArgumentImpl.java
Modified:
hive/trunk/ivy/libraries.properties
hive/trunk/ql/ivy.xml
Modified: hive/trunk/ivy/libraries.properties
URL: http://svn.apache.org/viewvc/hive/trunk/ivy/libraries.properties?rev=1513029&r1=1513028&r2=1513029&view=diff
==============================================================================
--- hive/trunk/ivy/libraries.properties (original)
+++ hive/trunk/ivy/libraries.properties Mon Aug 12 02:27:33 2013
@@ -67,3 +67,4 @@ velocity.version=1.5
metrics-core.version=2.1.2
zookeeper.version=3.4.3
javolution.version=5.5.1
+mina.version=2.0.0-M5
Modified: hive/trunk/ql/ivy.xml
URL: http://svn.apache.org/viewvc/hive/trunk/ql/ivy.xml?rev=1513029&r1=1513028&r2=1513029&view=diff
==============================================================================
--- hive/trunk/ql/ivy.xml (original)
+++ hive/trunk/ql/ivy.xml Mon Aug 12 02:27:33 2013
@@ -28,6 +28,8 @@
<dependencies>
<dependency org="org.apache.hive" name="hive-metastore" rev="${version}"
conf="compile->default" />
+ <dependency org="org.apache.mina" name="mina-core" rev="${mina.version}"
+ conf="test->default" />
<dependency org="org.apache.hive" name="hive-hbase-handler" rev="${version}"
conf="test->default" transitive="false"/>
<dependency org="org.apache.hive" name="hive-contrib" rev="${version}"
Added: hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/PredicateLeaf.java
URL: http://svn.apache.org/viewvc/hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/PredicateLeaf.java?rev=1513029&view=auto
==============================================================================
--- hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/PredicateLeaf.java (added)
+++ hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/PredicateLeaf.java Mon Aug 12 02:27:33 2013
@@ -0,0 +1,78 @@
+/**
+ * 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.hadoop.hive.ql.io.sarg;
+
+import java.util.List;
+
+/**
+ * The primitive predicates that form a SearchArgument.
+ */
+public interface PredicateLeaf {
+
+ /**
+ * The possible operators for predicates. To get the opposites, construct
+ * an expression with a not operator.
+ */
+ public static enum Operator {
+ EQUALS,
+ NULL_SAFE_EQUALS,
+ LESS_THAN,
+ LESS_THAN_EQUALS,
+ IN,
+ BETWEEN,
+ IS_NULL
+ }
+
+ /**
+ * The possible types for sargs.
+ */
+ public static enum Type {
+ INTEGER, // all of the integer types
+ FLOAT, // float and double
+ STRING
+ }
+
+ /**
+ * Get the operator for the leaf.
+ */
+ public Operator getOperator();
+
+ /**
+ * Get the type of the column and literal.
+ */
+ public Type getType();
+
+ /**
+ * Get the simple column name.
+ * @return the column name
+ */
+ public String getColumnName();
+
+ /**
+ * Get the literal half of the predicate leaf.
+ * @return a Long, Double, or String
+ */
+ public Object getLiteral();
+
+ /**
+ * For operators with multiple literals (IN and BETWEEN), get the literals.
+ * @return the list of literals (Longs, Doubles, or Strings)
+ */
+ public List<Object> getLiteralList();
+}
Added: hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgument.java
URL: http://svn.apache.org/viewvc/hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgument.java?rev=1513029&view=auto
==============================================================================
--- hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgument.java (added)
+++ hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgument.java Mon Aug 12 02:27:33 2013
@@ -0,0 +1,267 @@
+/**
+ * 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.hadoop.hive.ql.io.sarg;
+
+import org.apache.hadoop.hive.ql.plan.ExprNodeDesc;
+
+import java.util.List;
+
+/**
+ * Primary interface for <a href="http://en.wikipedia.org/wiki/Sargable">
+ * SearchArgument</a>, which are the subset of predicates
+ * that can be pushed down to the RecordReader. Each SearchArgument consists
+ * of a series of SearchClauses that must each be true for the row to be
+ * accepted by the filter.
+ *
+ * This requires that the filter be normalized into conjunctive normal form
+ * (<a href="http://en.wikipedia.org/wiki/Conjunctive_normal_form">CNF</a>).
+ */
+public interface SearchArgument {
+
+ /**
+ * The potential result sets of logical operations.
+ */
+ public static enum TruthValue {
+ YES, NO, NULL, YES_NULL, NO_NULL, YES_NO, YES_NO_NULL;
+
+ /**
+ * Compute logical or between the two values.
+ * @param right the other argument or null
+ * @return the result
+ */
+ public TruthValue or(TruthValue right) {
+ if (right == null || right == this) {
+ return this;
+ }
+ if (right == YES || this == YES) {
+ return YES;
+ }
+ if (right == YES_NULL || this == YES_NULL) {
+ return YES_NULL;
+ }
+ if (right == NO) {
+ return this;
+ }
+ if (this == NO) {
+ return right;
+ }
+ if (this == NULL) {
+ if (right == NO_NULL) {
+ return NULL;
+ } else {
+ return YES_NULL;
+ }
+ }
+ if (right == NULL) {
+ if (this == NO_NULL) {
+ return NULL;
+ } else {
+ return YES_NULL;
+ }
+ }
+ return YES_NO_NULL;
+ }
+
+ /**
+ * Compute logical AND between the two values.
+ * @param right the other argument or null
+ * @return the result
+ */
+ public TruthValue and(TruthValue right) {
+ if (right == null || right == this) {
+ return this;
+ }
+ if (right == NO || this == NO) {
+ return NO;
+ }
+ if (right == NO_NULL || this == NO_NULL) {
+ return NO_NULL;
+ }
+ if (right == YES) {
+ return this;
+ }
+ if (this == YES) {
+ return right;
+ }
+ if (this == NULL) {
+ if (right == YES_NULL) {
+ return NULL;
+ } else {
+ return NO_NULL;
+ }
+ }
+ if (right == NULL) {
+ if (this == YES_NULL) {
+ return NULL;
+ } else {
+ return NO_NULL;
+ }
+ }
+ return YES_NO_NULL;
+ }
+
+ public TruthValue not() {
+ switch (this) {
+ case NO:
+ return YES;
+ case YES:
+ return NO;
+ case NULL:
+ case YES_NO:
+ case YES_NO_NULL:
+ return this;
+ case NO_NULL:
+ return YES_NULL;
+ case YES_NULL:
+ return NO_NULL;
+ default:
+ throw new IllegalArgumentException("Unknown value: " + this);
+ }
+ }
+ }
+
+ /**
+ * Get the leaf predicates that are required to evaluate the predicate. The
+ * list will have the duplicates removed.
+ * @return the list of leaf predicates
+ */
+ public List<PredicateLeaf> getLeaves();
+
+ /**
+ * Evaluate the entire predicate based on the values for the leaf predicates.
+ * @param leaves the value of each leaf predicate
+ * @return the value of hte entire predicate
+ */
+ public TruthValue evaluate(TruthValue[] leaves);
+
+ /**
+ * A factory for creating SearchArguments. Java doesn't allow static methods
+ * in interfaces. *DOH*
+ */
+ public static class Factory {
+ public SearchArgument create(ExprNodeDesc expression) {
+ return new SearchArgumentImpl(expression);
+ }
+
+ public Builder newBuilder() {
+ return SearchArgumentImpl.newBuilder();
+ }
+ }
+
+ /**
+ * A builder object for contexts outside of Hive where it isn't easy to
+ * get a ExprNodeDesc. The user must call startOr, startAnd, or startNot
+ * before adding any leaves.
+ */
+ public interface Builder {
+
+ /**
+ * Start building an or operation and push it on the stack.
+ * @return this
+ */
+ public Builder startOr();
+
+ /**
+ * Start building an and operation and push it on the stack.
+ * @return this
+ */
+ public Builder startAnd();
+
+ /**
+ * Start building a not operation and push it on the stack.
+ * @return this
+ */
+ public Builder startNot();
+
+ /**
+ * Finish the current operation and pop it off of the stack. Each start
+ * call must have a matching end.
+ * @return this
+ */
+ public Builder end();
+
+ /**
+ * Add a less than leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param literal the literal
+ * @return this
+ */
+ public Builder lessThan(String column, Object literal);
+
+ /**
+ * Add a less than equals leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param literal the literal
+ * @return this
+ */
+ public Builder lessThanEquals(String column, Object literal);
+
+ /**
+ * Add an equals leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param literal the literal
+ * @return this
+ */
+ public Builder equals(String column, Object literal);
+
+ /**
+ * Add a null safe equals leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param literal the literal
+ * @return this
+ */
+ public Builder nullSafeEquals(String column, Object literal);
+
+ /**
+ * Add an in leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param literal the literal
+ * @return this
+ */
+ public Builder in(String column, Object... literal);
+
+ /**
+ * Add an is null leaf to the current item on the stack.
+ * @param column the name of the column
+ * @return this
+ */
+ public Builder isNull(String column);
+
+ /**
+ * Add a between leaf to the current item on the stack.
+ * @param column the name of the column
+ * @param lower the literal
+ * @param upper the literal
+ * @return this
+ */
+ public Builder between(String column, Object lower, Object upper);
+
+ /**
+ * Build and return the SearchArgument that has been defined. All of the
+ * starts must have been ended before this call.
+ * @return the new SearchArgument
+ */
+ public SearchArgument build();
+ }
+
+ /**
+ * Use this instance to create SearchArgument instances.
+ */
+ public static final Factory FACTORY = new Factory();
+}
Added: hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java
URL: http://svn.apache.org/viewvc/hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java?rev=1513029&view=auto
==============================================================================
--- hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java (added)
+++ hive/trunk/ql/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java Mon Aug 12 02:27:33 2013
@@ -0,0 +1,1026 @@
+/**
+ * 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.hadoop.hive.ql.io.sarg;
+
+import org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFBetween;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFIn;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualNS;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualOrGreaterThan;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualOrLessThan;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPGreaterThan;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPLessThan;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNot;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNotEqual;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNotNull;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNull;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr;
+import org.apache.hadoop.hive.serde2.io.DoubleWritable;
+import org.apache.hadoop.hive.serde2.objectinspector.ObjectInspector;
+import org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo;
+import org.apache.hadoop.hive.serde2.typeinfo.TypeInfo;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.Text;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * The implementation of SearchArguments.
+ */
+final class SearchArgumentImpl implements SearchArgument {
+
+ private static final class PredicateLeafImpl implements PredicateLeaf {
+ private final Operator operator;
+ private final Type type;
+ private final String columnName;
+ private final Object literal;
+ private final List<Object> literalList;
+
+ PredicateLeafImpl(Operator operator,
+ Type type,
+ String columnName,
+ Object literal,
+ List<Object> literalList) {
+ this.operator = operator;
+ this.type = type;
+ this.columnName = columnName;
+ this.literal = literal;
+ this.literalList = literalList;
+ }
+
+ @Override
+ public Operator getOperator() {
+ return operator;
+ }
+
+ @Override
+ public Type getType() {
+ return type;
+ }
+
+ @Override
+ public String getColumnName() {
+ return columnName;
+ }
+
+ @Override
+ public Object getLiteral() {
+ return literal;
+ }
+
+ @Override
+ public List<Object> getLiteralList() {
+ return literalList;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder buffer = new StringBuilder();
+ buffer.append('(');
+ buffer.append(operator);
+ buffer.append(' ');
+ buffer.append(columnName);
+ if (literal != null) {
+ buffer.append(' ');
+ buffer.append(literal);
+ } else if (literalList != null) {
+ for(Object lit: literalList) {
+ buffer.append(' ');
+ buffer.append(lit.toString());
+ }
+ }
+ buffer.append(')');
+ return buffer.toString();
+ }
+
+ private static boolean isEqual(Object left, Object right) {
+ if (left == right) {
+ return true;
+ } else if (left == null || right == null) {
+ return false;
+ } else {
+ return left.equals(right);
+ }
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other == null || other.getClass() != getClass()) {
+ return false;
+ } else if (other == this) {
+ return true;
+ } else {
+ PredicateLeafImpl o = (PredicateLeafImpl) other;
+ return operator == o.operator &&
+ type == o.type &&
+ columnName.equals(o.columnName) &&
+ isEqual(literal, o.literal) &&
+ isEqual(literalList, o.literalList);
+ }
+ }
+
+ @Override
+ public int hashCode() {
+ return operator.hashCode() +
+ type.hashCode() * 17 +
+ columnName.hashCode() * 3 * 17+
+ (literal == null ? 0 : literal.hashCode()) * 101 * 3 * 17 +
+ (literalList == null ? 0 : literalList.hashCode()) *
+ 103 * 101 * 3 * 17;
+ }
+ }
+
+ static class ExpressionTree {
+ static enum Operator {OR, AND, NOT, LEAF, CONSTANT}
+ private final Operator operator;
+ private final List<ExpressionTree> children;
+ private final int leaf;
+ private final TruthValue constant;
+
+ ExpressionTree(Operator op, ExpressionTree... kids) {
+ operator = op;
+ children = new ArrayList<ExpressionTree>();
+ leaf = -1;
+ this.constant = null;
+ Collections.addAll(children, kids);
+ }
+
+ ExpressionTree(int leaf) {
+ operator = Operator.LEAF;
+ children = null;
+ this.leaf = leaf;
+ this.constant = null;
+ }
+
+ ExpressionTree(TruthValue constant) {
+ operator = Operator.CONSTANT;
+ children = null;
+ this.leaf = -1;
+ this.constant = constant;
+ }
+
+ ExpressionTree(ExpressionTree other) {
+ this.operator = other.operator;
+ if (other.children == null) {
+ this.children = null;
+ } else {
+ this.children = new ArrayList<ExpressionTree>();
+ for(ExpressionTree child: other.children) {
+ children.add(new ExpressionTree(child));
+ }
+ }
+ this.leaf = other.leaf;
+ this.constant = other.constant;
+ }
+
+ TruthValue evaluate(TruthValue[] leaves) {
+ TruthValue result = null;
+ switch (operator) {
+ case OR:
+ for(ExpressionTree child: children) {
+ result = child.evaluate(leaves).or(result);
+ }
+ return result;
+ case AND:
+ for(ExpressionTree child: children) {
+ result = child.evaluate(leaves).and(result);
+ }
+ return result;
+ case NOT:
+ return children.get(0).evaluate(leaves).not();
+ case LEAF:
+ return leaves[leaf];
+ case CONSTANT:
+ return constant;
+ default:
+ throw new IllegalStateException("Unknown operator: " + operator);
+ }
+ }
+
+ public String toString() {
+ StringBuilder buffer = new StringBuilder();
+ switch (operator) {
+ case OR:
+ buffer.append("(or");
+ for(ExpressionTree child: children) {
+ buffer.append(' ');
+ buffer.append(child.toString());
+ }
+ buffer.append(')');
+ break;
+ case AND:
+ buffer.append("(and");
+ for(ExpressionTree child: children) {
+ buffer.append(' ');
+ buffer.append(child.toString());
+ }
+ buffer.append(')');
+ break;
+ case NOT:
+ buffer.append("(not ");
+ buffer.append(children.get(0));
+ buffer.append(')');
+ break;
+ case LEAF:
+ buffer.append("leaf-");
+ buffer.append(leaf);
+ break;
+ case CONSTANT:
+ buffer.append(constant);
+ break;
+ }
+ return buffer.toString();
+ }
+
+ Operator getOperator() {
+ return operator;
+ }
+
+ List<ExpressionTree> getChildren() {
+ return children;
+ }
+ }
+
+ static class ExpressionBuilder {
+ private ExpressionTree expression = null;
+ private final List<PredicateLeaf> leaves = new ArrayList<PredicateLeaf>();
+
+ /**
+ * Get the type of the given expression node.
+ * @param expr the expression to get the type of
+ * @return int, string, or float or null if we don't know the type
+ */
+ private static PredicateLeaf.Type getType(ExprNodeDesc expr) {
+ TypeInfo type = expr.getTypeInfo();
+ if (type.getCategory() == ObjectInspector.Category.PRIMITIVE) {
+ switch (((PrimitiveTypeInfo) type).getPrimitiveCategory()) {
+ case BYTE:
+ case SHORT:
+ case INT:
+ case LONG:
+ return PredicateLeaf.Type.INTEGER;
+ case STRING:
+ return PredicateLeaf.Type.STRING;
+ case FLOAT:
+ case DOUBLE:
+ return PredicateLeaf.Type.FLOAT;
+ default:
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Get the column name referenced in the expression. It must be at the top
+ * level of this expression and there must be exactly one column.
+ * @param expr the expression to look in
+ * @param variable the slot the variable is expected in
+ * @return the column name or null if there isn't exactly one column
+ */
+ private static String getColumnName(ExprNodeGenericFuncDesc expr,
+ int variable) {
+ List<ExprNodeDesc> children = expr.getChildren();
+ if (variable < 0 || variable >= children.size()) {
+ return null;
+ }
+ ExprNodeDesc child = children.get(variable);
+ if (child instanceof ExprNodeColumnDesc) {
+ return ((ExprNodeColumnDesc) child).getColumn();
+ }
+ return null;
+ }
+
+ private static Object boxLiteral(ExprNodeConstantDesc lit) {
+ switch (getType(lit)) {
+ case INTEGER:
+ return new LongWritable(((Number) lit.getValue()).longValue());
+ case STRING:
+ return new Text(lit.getValue().toString());
+ case FLOAT:
+ return new DoubleWritable(((Number) lit.getValue()).doubleValue());
+ default:
+ throw new IllegalArgumentException("Unknown literal " + getType(lit));
+ }
+ }
+
+ private static Object getLiteral(ExprNodeGenericFuncDesc expr) {
+ Object result = null;
+ List<ExprNodeDesc> children = expr.getChildren();
+ if (children.size() != 2) {
+ return null;
+ }
+ for(ExprNodeDesc child: children) {
+ if (child instanceof ExprNodeConstantDesc) {
+ if (result != null) {
+ return null;
+ }
+ result = boxLiteral((ExprNodeConstantDesc) child);
+ }
+ }
+ return result;
+ }
+
+ private static List<Object> getLiteralList(ExprNodeGenericFuncDesc expr,
+ int start) {
+ List<Object> result = new ArrayList<Object>();
+ List<ExprNodeDesc> children = expr.getChildren();
+ // ignore the first child, since it is the variable
+ for(ExprNodeDesc child: children.subList(start, children.size())) {
+ if (child instanceof ExprNodeConstantDesc) {
+ result.add(boxLiteral((ExprNodeConstantDesc) child));
+ } else {
+ // if we get some non-literals, we need to punt
+ return null;
+ }
+ }
+ return result;
+ }
+
+ private ExpressionTree createLeaf(PredicateLeaf.Operator operator,
+ ExprNodeGenericFuncDesc expression,
+ List<PredicateLeaf> leafCache,
+ int variable) {
+ String columnName = getColumnName(expression, variable);
+ if (columnName == null) {
+ return new ExpressionTree(TruthValue.YES_NO_NULL);
+ }
+ PredicateLeaf.Type type = getType(expression.getChildren().get(variable));
+ Object literal = null;
+ List<Object> literalList = null;
+ switch (operator) {
+ case IS_NULL:
+ break;
+ case IN:
+ case BETWEEN:
+ literalList = getLiteralList(expression, variable + 1);
+ if (literalList == null) {
+ return new ExpressionTree(TruthValue.YES_NO_NULL);
+ }
+ break;
+ default:
+ literal = getLiteral(expression);
+ if (literal == null) {
+ return new ExpressionTree(TruthValue.YES_NO_NULL);
+ }
+ break;
+ }
+ // if the variable was on the right, we need to swap things around
+ boolean needSwap = false;
+ if (variable != 0) {
+ if (operator == PredicateLeaf.Operator.LESS_THAN) {
+ needSwap = true;
+ operator = PredicateLeaf.Operator.LESS_THAN_EQUALS;
+ } else if (operator == PredicateLeaf.Operator.LESS_THAN_EQUALS) {
+ needSwap = true;
+ operator = PredicateLeaf.Operator.LESS_THAN;
+ }
+ }
+ leafCache.add(new PredicateLeafImpl(operator, type, columnName,
+ literal, literalList));
+ ExpressionTree result = new ExpressionTree(leafCache.size() - 1);
+ if (needSwap) {
+ result = negate(result);
+ }
+ return result;
+ }
+
+ /**
+ * Find the variable in the expression.
+ * @param expr the expression to look in
+ * @return the index of the variable or -1 if there is not exactly one
+ * variable.
+ */
+ private int findVariable(ExprNodeDesc expr) {
+ int result = -1;
+ List<ExprNodeDesc> children = expr.getChildren();
+ for(int i = 0; i < children.size(); ++i) {
+ ExprNodeDesc child = children.get(i);
+ if (child instanceof ExprNodeColumnDesc) {
+ // if we already found a variable, this isn't a sarg
+ if (result != -1) {
+ return -1;
+ } else {
+ result = i;
+ }
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Create a leaf expression when we aren't sure where the variable is
+ * located.
+ * @param operator the operator type that was found
+ * @param expression the expression to check
+ * @param leafCache the list of leaves
+ * @return if the expression is a sarg, return it, otherwise null
+ */
+ private ExpressionTree createLeaf(PredicateLeaf.Operator operator,
+ ExprNodeGenericFuncDesc expression,
+ List<PredicateLeaf> leafCache) {
+ return createLeaf(operator, expression, leafCache,
+ findVariable(expression));
+ }
+
+ private ExpressionTree negate(ExpressionTree expr) {
+ ExpressionTree result = new ExpressionTree(ExpressionTree.Operator.NOT);
+ result.children.add(expr);
+ return result;
+ }
+
+ private void addChildren(ExpressionTree result,
+ ExprNodeGenericFuncDesc node,
+ List<PredicateLeaf> leafCache) {
+ for(ExprNodeDesc child: node.getChildren()) {
+ result.children.add(parse(child, leafCache));
+ }
+ }
+
+ /**
+ * Do the recursive parse of the Hive ExprNodeDesc into our ExpressionTree.
+ * @param expression the Hive ExprNodeDesc
+ * @return the non-normalized ExpressionTree
+ */
+ private ExpressionTree parse(ExprNodeDesc expression,
+ List<PredicateLeaf> leafCache) {
+ // if we don't know the expression, just assume maybe
+ if (expression.getClass() != ExprNodeGenericFuncDesc.class) {
+ return new ExpressionTree(TruthValue.YES_NO_NULL);
+ }
+ // get the kind of expression
+ ExprNodeGenericFuncDesc typed = (ExprNodeGenericFuncDesc) expression;
+ Class<?> op = typed.getGenericUDF().getClass();
+ ExpressionTree result;
+
+ // handle the logical operators
+ if (op == GenericUDFOPOr.class) {
+ result = new ExpressionTree(ExpressionTree.Operator.OR);
+ addChildren(result, typed, leafCache);
+ } else if (op == GenericUDFOPAnd.class) {
+ result = new ExpressionTree(ExpressionTree.Operator.AND);
+ addChildren(result, typed, leafCache);
+ } else if (op == GenericUDFOPNot.class) {
+ result = new ExpressionTree(ExpressionTree.Operator.NOT);
+ addChildren(result, typed, leafCache);
+ } else if (op == GenericUDFOPEqual.class) {
+ result = createLeaf(PredicateLeaf.Operator.EQUALS, typed, leafCache);
+ } else if (op == GenericUDFOPNotEqual.class) {
+ result = negate(createLeaf(PredicateLeaf.Operator.EQUALS, typed,
+ leafCache));
+ } else if (op == GenericUDFOPEqualNS.class) {
+ result = createLeaf(PredicateLeaf.Operator.NULL_SAFE_EQUALS, typed,
+ leafCache);
+ } else if (op == GenericUDFOPGreaterThan.class) {
+ result = negate(createLeaf(PredicateLeaf.Operator.LESS_THAN_EQUALS,
+ typed, leafCache));
+ } else if (op == GenericUDFOPEqualOrGreaterThan.class) {
+ result = negate(createLeaf(PredicateLeaf.Operator.LESS_THAN, typed,
+ leafCache));
+ } else if (op == GenericUDFOPLessThan.class) {
+ result = createLeaf(PredicateLeaf.Operator.LESS_THAN, typed, leafCache);
+ } else if (op == GenericUDFOPEqualOrLessThan.class) {
+ result = createLeaf(PredicateLeaf.Operator.LESS_THAN_EQUALS, typed,
+ leafCache);
+ } else if (op == GenericUDFIn.class) {
+ result = createLeaf(PredicateLeaf.Operator.IN, typed, leafCache, 0);
+ } else if (op == GenericUDFBetween.class) {
+ result = createLeaf(PredicateLeaf.Operator.BETWEEN, typed, leafCache,
+ 1);
+ } else if (op == GenericUDFOPNull.class) {
+ result = createLeaf(PredicateLeaf.Operator.IS_NULL, typed, leafCache,
+ 0);
+ } else if (op == GenericUDFOPNotNull.class) {
+ result = negate(createLeaf(PredicateLeaf.Operator.IS_NULL, typed,
+ leafCache, 0));
+
+ // otherwise, we didn't understand it, so mark it maybe
+ } else {
+ result = new ExpressionTree(TruthValue.YES_NO_NULL);
+ }
+ return result;
+ }
+
+ /**
+ * Push the negations all the way to just before the leaves. Also remove
+ * double negatives.
+ * @param root the expression to normalize
+ * @return the normalized expression, which may share some or all of the
+ * nodes of the original expression.
+ */
+ static ExpressionTree pushDownNot(ExpressionTree root) {
+ if (root.operator == ExpressionTree.Operator.NOT) {
+ ExpressionTree child = root.children.get(0);
+ switch (child.operator) {
+ case NOT:
+ return pushDownNot(child.children.get(0));
+ case CONSTANT:
+ return new ExpressionTree(child.constant.not());
+ case AND:
+ root = new ExpressionTree(ExpressionTree.Operator.OR);
+ for(ExpressionTree kid: child.children) {
+ root.children.add(pushDownNot(new
+ ExpressionTree(ExpressionTree.Operator.NOT, kid)));
+ }
+ break;
+ case OR:
+ root = new ExpressionTree(ExpressionTree.Operator.AND);
+ for(ExpressionTree kid: child.children) {
+ root.children.add(pushDownNot(new ExpressionTree
+ (ExpressionTree.Operator.NOT, kid)));
+ }
+ break;
+ // for leaf, we don't do anything
+ default:
+ break;
+ }
+ } else if (root.children != null) {
+ // iterate through children and push down not for each one
+ for(int i=0; i < root.children.size(); ++i) {
+ root.children.set(i, pushDownNot(root.children.get(i)));
+ }
+ }
+ return root;
+ }
+
+ /**
+ * Remove MAYBE values from the expression. If they are in an AND operator,
+ * they are dropped. If they are in an OR operator, they kill their parent.
+ * This assumes that pushDownNot has already been called.
+ * @param expr The expression to clean up
+ * @return The cleaned up expression
+ */
+ ExpressionTree foldMaybe(ExpressionTree expr) {
+ if (expr.children != null) {
+ for(int i=0; i < expr.children.size(); ++i) {
+ ExpressionTree child = foldMaybe(expr.children.get(i));
+ if (child.constant == TruthValue.YES_NO_NULL) {
+ switch (expr.operator) {
+ case AND:
+ expr.children.remove(i);
+ i -= 1;
+ break;
+ case OR:
+ // a maybe will kill the or condition
+ return child;
+ default:
+ throw new IllegalStateException("Got a maybe as child of " +
+ expr);
+ }
+ } else {
+ expr.children.set(i, child);
+ }
+ }
+ }
+ return expr;
+ }
+
+ /**
+ * Generate all combinations of items on the andList. For each item on the
+ * andList, it generates all combinations of one child from each and
+ * expression. Thus, (and a b) (and c d) will be expanded to: (or a c)
+ * (or a d) (or b c) (or b d). If there are items on the nonAndList, they
+ * are added to each or expression.
+ * @param result a list to put the results onto
+ * @param andList a list of and expressions
+ * @param nonAndList a list of non-and expressions
+ */
+ private static void generateAllCombinations(List<ExpressionTree> result,
+ List<ExpressionTree> andList,
+ List<ExpressionTree> nonAndList
+ ) {
+ List<ExpressionTree> kids = andList.get(0).children;
+ if (result.isEmpty()) {
+ for(ExpressionTree kid: kids) {
+ ExpressionTree or = new ExpressionTree(ExpressionTree.Operator.OR);
+ result.add(or);
+ for(ExpressionTree node: nonAndList) {
+ or.children.add(new ExpressionTree(node));
+ }
+ or.children.add(kid);
+ }
+ } else {
+ List<ExpressionTree> work = new ArrayList<ExpressionTree>(result);
+ result.clear();
+ for(ExpressionTree kid: kids) {
+ for(ExpressionTree or: work) {
+ ExpressionTree copy = new ExpressionTree(or);
+ copy.children.add(kid);
+ result.add(copy);
+ }
+ }
+ }
+ if (andList.size() > 1) {
+ generateAllCombinations(result, andList.subList(1, andList.size()),
+ nonAndList);
+ }
+ }
+
+ /**
+ * Convert an expression so that the top level operator is AND with OR
+ * operators under it. This routine assumes that all of the NOT operators
+ * have been pushed to the leaves via pushdDownNot.
+ * @param root the expression
+ * @return the normalized expression
+ */
+ static ExpressionTree convertToCNF(ExpressionTree root) {
+ if (root.children != null) {
+ // convert all of the children to CNF
+ int size = root.children.size();
+ for(int i=0; i < size; ++i) {
+ root.children.set(i, convertToCNF(root.children.get(i)));
+ }
+ if (root.operator == ExpressionTree.Operator.OR) {
+ // a list of leaves that weren't under AND expressions
+ List<ExpressionTree> nonAndList = new ArrayList<ExpressionTree>();
+ // a list of AND expressions that we need to distribute
+ List<ExpressionTree> andList = new ArrayList<ExpressionTree>();
+ for(ExpressionTree child: root.children) {
+ if (child.operator == ExpressionTree.Operator.AND) {
+ andList.add(child);
+ } else if (child.operator == ExpressionTree.Operator.OR) {
+ // pull apart the kids of the OR expression
+ for(ExpressionTree grandkid: child.children) {
+ nonAndList.add(grandkid);
+ }
+ } else {
+ nonAndList.add(child);
+ }
+ }
+ if (!andList.isEmpty()) {
+ root = new ExpressionTree(ExpressionTree.Operator.AND);
+ generateAllCombinations(root.children, andList, nonAndList);
+ }
+ }
+ }
+ return root;
+ }
+
+ /**
+ * Converts multi-level ands and ors into single level ones.
+ * @param root the expression to flatten
+ * @return the flattened expression, which will always be root with
+ * potentially modified children.
+ */
+ static ExpressionTree flatten(ExpressionTree root) {
+ if (root.children != null) {
+ // iterate through the index, so that if we add more children,
+ // they don't get re-visited
+ for(int i=0; i < root.children.size(); ++i) {
+ ExpressionTree child = flatten(root.children.get(i));
+ // do we need to flatten?
+ if (child.operator == root.operator &&
+ child.operator != ExpressionTree.Operator.NOT) {
+ boolean first = true;
+ for(ExpressionTree grandkid: child.children) {
+ // for the first grandkid replace the original parent
+ if (first) {
+ first = false;
+ root.children.set(i, grandkid);
+ } else {
+ root.children.add(++i, grandkid);
+ }
+ }
+ } else {
+ root.children.set(i, child);
+ }
+ }
+ // if we have a singleton AND or OR, just return the child
+ if ((root.operator == ExpressionTree.Operator.OR ||
+ root.operator == ExpressionTree.Operator.AND) &&
+ root.children.size() == 1) {
+ return root.children.get(0);
+ }
+ }
+ return root;
+ }
+
+ /**
+ * Iterates through the expression, finding all of the leaves. It creates
+ * the leaves list with each unique leaf that is found in the expression.
+ * The expression is updated with the new leaf ids for each leaf.
+ * @param expr the expression to find the leaves in
+ * @param leafCache the list of all of the leaves
+ * @param lookup a map that is used to uniquify the leaves
+ * @return The potentially modified expression
+ */
+ private ExpressionTree buildLeafList(ExpressionTree expr,
+ List<PredicateLeaf> leafCache,
+ Map<PredicateLeaf,
+ ExpressionTree> lookup) {
+ if (expr.children != null) {
+ for(int i=0; i < expr.children.size(); ++i) {
+ expr.children.set(i, buildLeafList(expr.children.get(i), leafCache,
+ lookup));
+ }
+ } else if (expr.operator == ExpressionTree.Operator.LEAF) {
+ PredicateLeaf leaf = leafCache.get(expr.leaf);
+ ExpressionTree val = lookup.get(leaf);
+ if (val == null) {
+ val = new ExpressionTree(leaves.size());
+ lookup.put(leaf, val);
+ leaves.add(leaf);
+ }
+ return val;
+ }
+ return expr;
+ }
+
+ /**
+ * Builds the expression and leaf list from the original predicate.
+ * @param expression the expression to translate
+ * @return The normalized expression.
+ */
+ ExpressionTree expression(ExprNodeDesc expression) {
+ List<PredicateLeaf> leafCache = new ArrayList<PredicateLeaf>();
+ ExpressionTree expr = parse(expression, leafCache);
+ return expression(expr, leafCache);
+ }
+
+ /**
+ * Builds the expression and optimized leaf list from a non-normalized
+ * expression. Sets the leaves field with the unique leaves.
+ * @param expr non-normalized expression
+ * @param leaves non-unique leaves
+ * @return the normalized expression
+ */
+ ExpressionTree expression(ExpressionTree expr,
+ List<PredicateLeaf> leaves) {
+ expr = pushDownNot(expr);
+ expr = foldMaybe(expr);
+ expr = flatten(expr);
+ expr = convertToCNF(expr);
+ expr = flatten(expr);
+ expr = buildLeafList(expr, leaves,
+ new HashMap<PredicateLeaf, ExpressionTree>());
+ return expr;
+ }
+
+ List<PredicateLeaf> getLeaves() {
+ return leaves;
+ }
+ }
+
+ private final List<PredicateLeaf> leaves;
+ private final ExpressionTree expression;
+
+ SearchArgumentImpl(ExprNodeDesc expr) {
+ if (expr == null) {
+ leaves = new ArrayList<PredicateLeaf>();
+ expression = null;
+ } else {
+ ExpressionBuilder builder = new ExpressionBuilder();
+ expression = builder.expression(expr);
+ leaves = builder.getLeaves();
+ }
+ }
+
+ SearchArgumentImpl(ExpressionTree expression, List<PredicateLeaf> leaves) {
+ this.expression = expression;
+ this.leaves = leaves;
+ }
+
+ @Override
+ public List<PredicateLeaf> getLeaves() {
+ return leaves;
+ }
+
+ @Override
+ public TruthValue evaluate(TruthValue[] leaves) {
+ return expression == null ? TruthValue.YES : expression.evaluate(leaves);
+ }
+
+ ExpressionTree getExpression() {
+ return expression;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder buffer = new StringBuilder();
+ for(int i=0; i < leaves.size(); ++i) {
+ buffer.append("leaf-");
+ buffer.append(i);
+ buffer.append(" = ");
+ buffer.append(leaves.get(i).toString());
+ buffer.append('\n');
+ }
+ buffer.append("expr = ");
+ buffer.append(expression);
+ return buffer.toString();
+ }
+
+ private static class BuilderImpl implements Builder {
+ private final Deque<ExpressionTree> currentTree =
+ new ArrayDeque<ExpressionTree>();
+ private final List<PredicateLeaf> leaves = new ArrayList<PredicateLeaf>();
+ private ExpressionTree root = null;
+
+ @Override
+ public Builder startOr() {
+ ExpressionTree node = new ExpressionTree(ExpressionTree.Operator.OR);
+ if (currentTree.size() != 0) {
+ ExpressionTree parent = currentTree.getFirst();
+ parent.children.add(node);
+ }
+ currentTree.addFirst(node);
+ return this;
+ }
+
+ @Override
+ public Builder startAnd() {
+ ExpressionTree node = new ExpressionTree(ExpressionTree.Operator.AND);
+ if (currentTree.size() != 0) {
+ ExpressionTree parent = currentTree.getFirst();
+ parent.children.add(node);
+ }
+ currentTree.addFirst(node);
+ return this;
+ }
+
+ @Override
+ public Builder startNot() {
+ ExpressionTree node = new ExpressionTree(ExpressionTree.Operator.NOT);
+ if (currentTree.size() != 0) {
+ ExpressionTree parent = currentTree.getFirst();
+ parent.children.add(node);
+ }
+ currentTree.addFirst(node);
+ return this;
+ }
+
+ @Override
+ public Builder end() {
+ root = currentTree.removeFirst();
+ if (root.children.size() == 0) {
+ throw new IllegalArgumentException("Can't create expression " + root +
+ " with no children.");
+ }
+ if (root.operator == ExpressionTree.Operator.NOT &&
+ root.children.size() != 1) {
+ throw new IllegalArgumentException("Can't create not expression " +
+ root + " with more than 1 child.");
+ }
+ return this;
+ }
+
+ private static Object boxLiteral(Object literal) {
+ if (literal instanceof String ||
+ literal instanceof Long ||
+ literal instanceof Double) {
+ return literal;
+ } else if (literal instanceof Integer) {
+ return Long.valueOf((Integer) literal);
+ } else if (literal instanceof Float) {
+ return Double.valueOf((Float) literal);
+ } else {
+ throw new IllegalArgumentException("Unknown type for literal " +
+ literal);
+ }
+ }
+
+ private static PredicateLeaf.Type getType(Object literal) {
+ if (literal instanceof Long) {
+ return PredicateLeaf.Type.INTEGER;
+ } else if (literal instanceof String) {
+ return PredicateLeaf.Type.STRING;
+ } else if (literal instanceof Double) {
+ return PredicateLeaf.Type.FLOAT;
+ }
+ throw new IllegalArgumentException("Unknown type for literal " + literal);
+ }
+
+ @Override
+ public Builder lessThan(String column, Object literal) {
+ ExpressionTree parent = currentTree.getFirst();
+ Object box = boxLiteral(literal);
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.LESS_THAN,
+ getType(box), column, box, null);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder lessThanEquals(String column, Object literal) {
+ ExpressionTree parent = currentTree.getFirst();
+ Object box = boxLiteral(literal);
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.LESS_THAN_EQUALS,
+ getType(box), column, box, null);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder equals(String column, Object literal) {
+ ExpressionTree parent = currentTree.getFirst();
+ Object box = boxLiteral(literal);
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.EQUALS,
+ getType(box), column, box, null);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder nullSafeEquals(String column, Object literal) {
+ ExpressionTree parent = currentTree.getFirst();
+ Object box = boxLiteral(literal);
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.NULL_SAFE_EQUALS,
+ getType(box), column, box, null);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder in(String column, Object... literal) {
+ ExpressionTree parent = currentTree.getFirst();
+ if (literal.length == 0) {
+ throw new IllegalArgumentException("Can't create in expression with "
+ + "no arguments");
+ }
+ List<Object> argList = new ArrayList<Object>();
+ for(Object lit: literal){
+ argList.add(boxLiteral(lit));
+ }
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.IN,
+ getType(argList.get(0)), column, null, argList);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder isNull(String column) {
+ ExpressionTree parent = currentTree.getFirst();
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.IS_NULL,
+ PredicateLeaf.Type.STRING, column, null, null);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public Builder between(String column, Object lower, Object upper) {
+ ExpressionTree parent = currentTree.getFirst();
+ List<Object> argList = new ArrayList<Object>();
+ argList.add(boxLiteral(lower));
+ argList.add(boxLiteral(upper));
+ PredicateLeaf leaf =
+ new PredicateLeafImpl(PredicateLeaf.Operator.BETWEEN,
+ getType(argList.get(0)), column, null, argList);
+ leaves.add(leaf);
+ parent.children.add(new ExpressionTree(leaves.size() - 1));
+ return this;
+ }
+
+ @Override
+ public SearchArgument build() {
+ if (currentTree.size() != 0) {
+ throw new IllegalArgumentException("Failed to end " +
+ currentTree.size() + " operations.");
+ }
+ ExpressionBuilder internal = new ExpressionBuilder();
+ ExpressionTree normalized = internal.expression(root, leaves);
+ return new SearchArgumentImpl(normalized, internal.getLeaves());
+ }
+ }
+
+ public static Builder newBuilder() {
+ return new BuilderImpl();
+ }
+}