hive-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From gunt...@apache.org
Subject svn commit: r1513029 [2/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/
Date Mon, 12 Aug 2013 02:27:34 GMT
Added: hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/TestSearchArgumentImpl.java
URL: http://svn.apache.org/viewvc/hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/TestSearchArgumentImpl.java?rev=1513029&view=auto
==============================================================================
--- hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/TestSearchArgumentImpl.java (added)
+++ hive/trunk/ql/src/test/org/apache/hadoop/hive/ql/io/sarg/TestSearchArgumentImpl.java Mon Aug 12 02:27:33 2013
@@ -0,0 +1,2779 @@
+/**
+ * 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.conf.Configuration;
+import org.apache.hadoop.hive.ql.exec.Utilities;
+import org.apache.hadoop.hive.ql.io.sarg.SearchArgument.TruthValue;
+import org.apache.hadoop.hive.ql.io.sarg.SearchArgumentImpl.ExpressionBuilder;
+import org.apache.hadoop.hive.ql.io.sarg.SearchArgumentImpl.ExpressionTree;
+import org.apache.hadoop.hive.ql.plan.ExprNodeDesc;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.Text;
+import org.apache.mina.util.IdentityHashSet;
+import org.junit.Test;
+
+import java.util.List;
+
+import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertTrue;
+
+/**
+ * These test the SARG implementation.
+ * The xml files were generated by setting hive.optimize.index.filter
+ * to true and using a custom record reader that prints out the value of
+ * hive.io.filter.expr.serialized in createRecordReader. This should be
+ * replaced by generating the AST using the API and passing that in.
+ */
+public class TestSearchArgumentImpl {
+
+  private ExpressionTree not(ExpressionTree arg) {
+    return new ExpressionTree(ExpressionTree.Operator.NOT, arg);
+  }
+
+  private ExpressionTree and(ExpressionTree... arg) {
+    return new ExpressionTree(ExpressionTree.Operator.AND, arg);
+  }
+
+  private ExpressionTree or(ExpressionTree... arg) {
+    return new ExpressionTree(ExpressionTree.Operator.OR, arg);
+  }
+
+  private ExpressionTree leaf(int leaf) {
+    return new ExpressionTree(leaf);
+  }
+
+  private ExpressionTree constant(TruthValue val) {
+    return new ExpressionTree(val);
+  }
+
+  @Test
+  public void testNotPushdown() throws Exception {
+    assertEquals("leaf-1", ExpressionBuilder.pushDownNot(leaf(1)).toString());
+    assertEquals("(not leaf-1)",
+        ExpressionBuilder.pushDownNot(not(leaf(1))).toString());
+    assertEquals("leaf-1",
+        ExpressionBuilder.pushDownNot(not(not(leaf(1)))).toString());
+    assertEquals("(not leaf-1)",
+        ExpressionBuilder.pushDownNot(not(not(not(leaf(1))))).toString());
+    assertEquals("(or leaf-1 (not leaf-2))",
+        ExpressionBuilder.pushDownNot(not(and(not(leaf(1)),
+            leaf(2)))).toString());
+    assertEquals("(and (not leaf-1) leaf-2)",
+        ExpressionBuilder.pushDownNot(not(or(leaf(1),
+            not(leaf(2))))).toString());
+    assertEquals("(or (or (not leaf-1) leaf-2) leaf-3)",
+        ExpressionBuilder.pushDownNot(or(not(and(leaf(1), not(leaf(2)))),
+            not(not(leaf(3))))).toString());
+    assertEquals("NO", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.YES))).toString());
+    assertEquals("YES", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.NO))).toString());
+    assertEquals("NULL", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.NULL))).toString());
+    assertEquals("YES_NO", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.YES_NO))).toString());
+    assertEquals("YES_NULL", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.NO_NULL))).toString());
+    assertEquals("NO_NULL", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.YES_NULL))).toString());
+    assertEquals("YES_NO_NULL", ExpressionBuilder.pushDownNot(
+        not(constant(TruthValue.YES_NO_NULL))).toString());
+  }
+
+  @Test
+  public void testFlatten() throws Exception {
+    assertEquals("leaf-1", ExpressionBuilder.flatten(leaf(1)).toString());
+    assertEquals("NO",
+        ExpressionBuilder.flatten(constant(TruthValue.NO)).toString());
+    assertEquals("(not (not leaf-1))",
+        ExpressionBuilder.flatten(not(not(leaf(1)))).toString());
+    assertEquals("(and leaf-1 leaf-2)",
+        ExpressionBuilder.flatten(and(leaf(1), leaf(2))).toString());
+    assertEquals("(and (or leaf-1 leaf-2) leaf-3)",
+        ExpressionBuilder.flatten(and(or(leaf(1), leaf(2)), leaf(3))
+        ).toString());
+    assertEquals("(and leaf-1 leaf-2 leaf-3 leaf-4)",
+        ExpressionBuilder.flatten(and(and(leaf(1), leaf(2)),
+            and(leaf(3),leaf(4)))).toString());
+    assertEquals("(or leaf-1 leaf-2 leaf-3 leaf-4)",
+        ExpressionBuilder.flatten(or(leaf(1), or(leaf(2), or(leaf(3),
+            leaf(4))))).toString());
+    assertEquals("(or leaf-1 leaf-2 leaf-3 leaf-4)",
+        ExpressionBuilder.flatten(or(or(or(leaf(1), leaf(2)), leaf(3)),
+            leaf(4))).toString());
+    assertEquals("(or leaf-1 leaf-2 leaf-3 leaf-4 leaf-5 leaf-6)",
+        ExpressionBuilder.flatten(or(or(leaf(1), or(leaf(2), leaf(3))),
+            or(or(leaf(4),leaf(5)), leaf(6)))).toString());
+    assertEquals("(and (not leaf-1) leaf-2 (not leaf-3) leaf-4 (not leaf-5) leaf-6)",
+        ExpressionBuilder.flatten(and(and(not(leaf(1)), and(leaf(2),
+            not(leaf(3)))), and(and(leaf(4), not(leaf(5))), leaf(6)))
+            ).toString());
+    assertEquals("(not (and leaf-1 leaf-2 leaf-3))",
+        ExpressionBuilder.flatten(not(and(leaf(1), and(leaf(2), leaf(3))))
+        ).toString());
+  }
+
+  @Test
+  public void testCNF() throws Exception {
+    assertEquals("leaf-1", ExpressionBuilder.convertToCNF(leaf(1)).toString());
+    assertEquals("NO", ExpressionBuilder.convertToCNF(
+        constant(TruthValue.NO)).toString());
+    assertEquals("(not leaf-1)", ExpressionBuilder.convertToCNF(
+        not(leaf(1))).toString());
+    assertEquals("(and leaf-1 leaf-2)", ExpressionBuilder.convertToCNF(
+        and(leaf(1), leaf(2))).toString());
+    assertEquals("(or (not leaf-1) leaf-2)", ExpressionBuilder.convertToCNF(
+        or(not(leaf(1)), leaf(2))).toString());
+    assertEquals("(and (or leaf-1 leaf-2) (not leaf-3))",
+        ExpressionBuilder.convertToCNF(
+            and(or(leaf(1), leaf(2)), not(leaf(3)))).toString());
+    assertEquals("(and (or leaf-1 leaf-3) (or leaf-2 leaf-3)" +
+        " (or leaf-1 leaf-4) (or leaf-2 leaf-4))",
+        ExpressionBuilder.convertToCNF(
+            or(and(leaf(1), leaf(2)), and(leaf(3), leaf(4)))).toString());
+    assertEquals("(and" +
+        " (or leaf-1 leaf-5) (or leaf-2 leaf-5)" +
+        " (or leaf-3 leaf-5) (or leaf-4 leaf-5)" +
+        " (or leaf-1 leaf-6) (or leaf-2 leaf-6)" +
+        " (or leaf-3 leaf-6) (or leaf-4 leaf-6))",
+        ExpressionBuilder.convertToCNF(
+            or(and(leaf(1), leaf(2), leaf(3), leaf(4)),
+                and(leaf(5), leaf(6)))).toString());
+    assertEquals("(and" +
+        " (or leaf-5 leaf-6 (not leaf-7) leaf-1 leaf-3)" +
+        " (or leaf-5 leaf-6 (not leaf-7) leaf-2 leaf-3)" +
+        " (or leaf-5 leaf-6 (not leaf-7) leaf-1 leaf-4)" +
+        " (or leaf-5 leaf-6 (not leaf-7) leaf-2 leaf-4))",
+        ExpressionBuilder.convertToCNF(
+            or(and(leaf(1), leaf(2)),
+                and(leaf(3), leaf(4)),
+                or(leaf(5), leaf(6)),
+                not(leaf(7)))).toString());
+    assertEquals("(and" +
+        " (or leaf-8 leaf-0 leaf-3 leaf-6)" +
+        " (or leaf-8 leaf-1 leaf-3 leaf-6)" +
+        " (or leaf-8 leaf-2 leaf-3 leaf-6)" +
+        " (or leaf-8 leaf-0 leaf-4 leaf-6)" +
+        " (or leaf-8 leaf-1 leaf-4 leaf-6)" +
+        " (or leaf-8 leaf-2 leaf-4 leaf-6)" +
+        " (or leaf-8 leaf-0 leaf-5 leaf-6)" +
+        " (or leaf-8 leaf-1 leaf-5 leaf-6)" +
+        " (or leaf-8 leaf-2 leaf-5 leaf-6)" +
+        " (or leaf-8 leaf-0 leaf-3 leaf-7)" +
+        " (or leaf-8 leaf-1 leaf-3 leaf-7)" +
+        " (or leaf-8 leaf-2 leaf-3 leaf-7)" +
+        " (or leaf-8 leaf-0 leaf-4 leaf-7)" +
+        " (or leaf-8 leaf-1 leaf-4 leaf-7)" +
+        " (or leaf-8 leaf-2 leaf-4 leaf-7)" +
+        " (or leaf-8 leaf-0 leaf-5 leaf-7)" +
+        " (or leaf-8 leaf-1 leaf-5 leaf-7)" +
+        " (or leaf-8 leaf-2 leaf-5 leaf-7))",
+        ExpressionBuilder.convertToCNF(or(and(leaf(0), leaf(1), leaf(2)),
+            and(leaf(3), leaf(4), leaf(5)),
+            and(leaf(6), leaf(7)),
+            leaf(8))).toString());
+    assertNoSharedNodes(ExpressionBuilder.convertToCNF(or(and(leaf(0), leaf(1), leaf(2)),
+        and(leaf(3), leaf(4), leaf(5)),
+        and(leaf(6), leaf(7)),
+        leaf(8))), new IdentityHashSet<ExpressionTree>());
+  }
+
+  private static void assertNoSharedNodes(ExpressionTree tree,
+                                          IdentityHashSet<ExpressionTree> seen
+                                         ) throws Exception {
+    if (seen.contains(tree) &&
+        tree.getOperator() != ExpressionTree.Operator.LEAF) {
+      assertTrue("repeated node in expression " + tree, false);
+    }
+    seen.add(tree);
+    if (tree.getChildren() != null) {
+      for(ExpressionTree child: tree.getChildren()) {
+        assertNoSharedNodes(child, seen);
+      }
+    }
+  }
+
+  @Test
+  public void testExpression1() throws Exception {
+    // first_name = 'john' or
+    //  'greg' < first_name or
+    //  'alan' > first_name or
+    //  id > 12 or
+    //  13 < id or
+    //  id < 15 or
+    //  16 > id or
+    //  (id <=> 30 and first_name <=> 'owen')
+    String exprStr = "<?xml version=\"1.0\" encoding=\"UTF-8\"?> \n" +
+        "<java version=\"1.6.0_31\" class=\"java.beans.XMLDecoder\"> \n" +
+        " <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "  <void property=\"childExprs\"> \n" +
+        "   <object class=\"java.util.ArrayList\"> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                  <void property=\"childExprs\"> \n" +
+        "                   <object class=\"java.util.ArrayList\"> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                      <void property=\"childExprs\"> \n" +
+        "                       <object class=\"java.util.ArrayList\"> \n" +
+        "                        <void method=\"add\"> \n" +
+        "                         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                          <void property=\"childExprs\"> \n" +
+        "                           <object class=\"java.util.ArrayList\"> \n" +
+        "                            <void method=\"add\"> \n" +
+        "                             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                              <void property=\"childExprs\"> \n" +
+        "                               <object class=\"java.util.ArrayList\"> \n" +
+        "                                <void method=\"add\"> \n" +
+        "                                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                                  <void property=\"column\"> \n" +
+        "                                   <string>first_name</string> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"tabAlias\"> \n" +
+        "                                   <string>orc_people</string> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"typeInfo\"> \n" +
+        "                                   <object id=\"PrimitiveTypeInfo0\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                                    <void property=\"typeName\"> \n" +
+        "                                     <string>string</string> \n" +
+        "                                    </void> \n" +
+        "                                   </object> \n" +
+        "                                  </void> \n" +
+        "                                 </object> \n" +
+        "                                </void> \n" +
+        "                                <void method=\"add\"> \n" +
+        "                                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                                  <void property=\"typeInfo\"> \n" +
+        "                                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"value\"> \n" +
+        "                                   <string>john</string> \n" +
+        "                                  </void> \n" +
+        "                                 </object> \n" +
+        "                                </void> \n" +
+        "                               </object> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"genericUDF\"> \n" +
+        "                               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual\"/> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"typeInfo\"> \n" +
+        "                               <object id=\"PrimitiveTypeInfo1\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                                <void property=\"typeName\"> \n" +
+        "                                 <string>boolean</string> \n" +
+        "                                </void> \n" +
+        "                               </object> \n" +
+        "                              </void> \n" +
+        "                             </object> \n" +
+        "                            </void> \n" +
+        "                            <void method=\"add\"> \n" +
+        "                             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                              <void property=\"childExprs\"> \n" +
+        "                               <object class=\"java.util.ArrayList\"> \n" +
+        "                                <void method=\"add\"> \n" +
+        "                                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                                  <void property=\"typeInfo\"> \n" +
+        "                                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"value\"> \n" +
+        "                                   <string>greg</string> \n" +
+        "                                  </void> \n" +
+        "                                 </object> \n" +
+        "                                </void> \n" +
+        "                                <void method=\"add\"> \n" +
+        "                                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                                  <void property=\"column\"> \n" +
+        "                                   <string>first_name</string> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"tabAlias\"> \n" +
+        "                                   <string>orc_people</string> \n" +
+        "                                  </void> \n" +
+        "                                  <void property=\"typeInfo\"> \n" +
+        "                                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                                  </void> \n" +
+        "                                 </object> \n" +
+        "                                </void> \n" +
+        "                               </object> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"genericUDF\"> \n" +
+        "                               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPLessThan\"/> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"typeInfo\"> \n" +
+        "                               <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                              </void> \n" +
+        "                             </object> \n" +
+        "                            </void> \n" +
+        "                           </object> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"genericUDF\"> \n" +
+        "                           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"typeInfo\"> \n" +
+        "                           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                          </void> \n" +
+        "                         </object> \n" +
+        "                        </void> \n" +
+        "                        <void method=\"add\"> \n" +
+        "                         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                          <void property=\"childExprs\"> \n" +
+        "                           <object class=\"java.util.ArrayList\"> \n" +
+        "                            <void method=\"add\"> \n" +
+        "                             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                              <void property=\"typeInfo\"> \n" +
+        "                               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"value\"> \n" +
+        "                               <string>alan</string> \n" +
+        "                              </void> \n" +
+        "                             </object> \n" +
+        "                            </void> \n" +
+        "                            <void method=\"add\"> \n" +
+        "                             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                              <void property=\"column\"> \n" +
+        "                               <string>first_name</string> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"tabAlias\"> \n" +
+        "                               <string>orc_people</string> \n" +
+        "                              </void> \n" +
+        "                              <void property=\"typeInfo\"> \n" +
+        "                               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                              </void> \n" +
+        "                             </object> \n" +
+        "                            </void> \n" +
+        "                           </object> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"genericUDF\"> \n" +
+        "                           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPGreaterThan\"/> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"typeInfo\"> \n" +
+        "                           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                          </void> \n" +
+        "                         </object> \n" +
+        "                        </void> \n" +
+        "                       </object> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"genericUDF\"> \n" +
+        "                       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                      <void property=\"childExprs\"> \n" +
+        "                       <object class=\"java.util.ArrayList\"> \n" +
+        "                        <void method=\"add\"> \n" +
+        "                         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                          <void property=\"column\"> \n" +
+        "                           <string>id</string> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"tabAlias\"> \n" +
+        "                           <string>orc_people</string> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"typeInfo\"> \n" +
+        "                           <object id=\"PrimitiveTypeInfo2\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                            <void property=\"typeName\"> \n" +
+        "                             <string>int</string> \n" +
+        "                            </void> \n" +
+        "                           </object> \n" +
+        "                          </void> \n" +
+        "                         </object> \n" +
+        "                        </void> \n" +
+        "                        <void method=\"add\"> \n" +
+        "                         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                          <void property=\"typeInfo\"> \n" +
+        "                           <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                          </void> \n" +
+        "                          <void property=\"value\"> \n" +
+        "                           <int>12</int> \n" +
+        "                          </void> \n" +
+        "                         </object> \n" +
+        "                        </void> \n" +
+        "                       </object> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"genericUDF\"> \n" +
+        "                       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPGreaterThan\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"genericUDF\"> \n" +
+        "                   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                  <void property=\"childExprs\"> \n" +
+        "                   <object class=\"java.util.ArrayList\"> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <int>13</int> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                      <void property=\"column\"> \n" +
+        "                       <string>id</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"tabAlias\"> \n" +
+        "                       <string>orc_people</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"genericUDF\"> \n" +
+        "                   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPLessThan\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                  <void property=\"column\"> \n" +
+        "                   <string>id</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"tabAlias\"> \n" +
+        "                   <string>orc_people</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"value\"> \n" +
+        "                   <int>15</int> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPLessThan\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <int>16</int> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>id</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPGreaterThan\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>id</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <int>30</int> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualNS\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>first_name</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <string>owen</string> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualNS\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "   </object> \n" +
+        "  </void> \n" +
+        "  <void property=\"genericUDF\"> \n" +
+        "   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "  </void> \n" +
+        "  <void property=\"typeInfo\"> \n" +
+        "   <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "  </void> \n" +
+        " </object> \n" +
+        "</java> \n";
+    Configuration conf = new Configuration();
+    ExprNodeDesc expr = Utilities.deserializeExpression(exprStr, conf);
+    SearchArgumentImpl sarg =
+        (SearchArgumentImpl) SearchArgument.FACTORY.create(expr);
+    List<PredicateLeaf> leaves = sarg.getLeaves();
+    assertEquals(9, leaves.size());
+
+    PredicateLeaf leaf = leaves.get(0);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.EQUALS, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("john"), leaf.getLiteral());
+
+    leaf = leaves.get(1);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN_EQUALS, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("greg"), leaf.getLiteral());
+
+    leaf = leaves.get(2);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("alan"), leaf.getLiteral());
+
+    leaf = leaves.get(3);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN_EQUALS, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(12), leaf.getLiteral());
+
+    leaf = leaves.get(4);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN_EQUALS, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(13), leaf.getLiteral());
+
+    leaf = leaves.get(5);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(15), leaf.getLiteral());
+
+    leaf = leaves.get(6);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(16), leaf.getLiteral());
+
+    leaf = leaves.get(7);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.NULL_SAFE_EQUALS, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(30), leaf.getLiteral());
+
+    leaf = leaves.get(8);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.NULL_SAFE_EQUALS, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("owen"), leaf.getLiteral());
+
+    assertEquals("(and (or leaf-0 (not leaf-1) leaf-2 (not leaf-3)" +
+        " (not leaf-4) leaf-5 leaf-6 leaf-7)" +
+        " (or leaf-0 (not leaf-1) leaf-2 (not leaf-3)" +
+        " (not leaf-4) leaf-5 leaf-6 leaf-8))",
+        sarg.getExpression().toString());
+    assertNoSharedNodes(sarg.getExpression(),
+        new IdentityHashSet<ExpressionTree>());
+  }
+
+  @Test
+  public void testExpression2() throws Exception {
+    /* first_name is null or
+       first_name <> 'sue' or
+       id >= 12 or
+       id <= 4; */
+    String exprStr = "<?xml version=\"1.0\" encoding=\"UTF-8\"?> \n" +
+        "<java version=\"1.6.0_31\" class=\"java.beans.XMLDecoder\"> \n" +
+        " <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "  <void property=\"childExprs\"> \n" +
+        "   <object class=\"java.util.ArrayList\"> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                  <void property=\"column\"> \n" +
+        "                   <string>first_name</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"tabAlias\"> \n" +
+        "                   <string>orc_people</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object id=\"PrimitiveTypeInfo0\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                    <void property=\"typeName\"> \n" +
+        "                     <string>string</string> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNull\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object id=\"PrimitiveTypeInfo1\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                <void property=\"typeName\"> \n" +
+        "                 <string>boolean</string> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                  <void property=\"column\"> \n" +
+        "                   <string>first_name</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"tabAlias\"> \n" +
+        "                   <string>orc_people</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"value\"> \n" +
+        "                   <string>sue</string> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNotEqual\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>id</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object id=\"PrimitiveTypeInfo2\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                <void property=\"typeName\"> \n" +
+        "                 <string>int</string> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <int>12</int> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualOrGreaterThan\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "          <void property=\"column\"> \n" +
+        "           <string>id</string> \n" +
+        "          </void> \n" +
+        "          <void property=\"tabAlias\"> \n" +
+        "           <string>orc_people</string> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"value\"> \n" +
+        "           <int>4</int> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqualOrLessThan\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "   </object> \n" +
+        "  </void> \n" +
+        "  <void property=\"genericUDF\"> \n" +
+        "   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPOr\"/> \n" +
+        "  </void> \n" +
+        "  <void property=\"typeInfo\"> \n" +
+        "   <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "  </void> \n" +
+        " </object> \n" +
+        "</java> \n";
+    Configuration conf = new Configuration();
+    ExprNodeDesc expr = Utilities.deserializeExpression(exprStr, conf);
+    SearchArgumentImpl sarg =
+        (SearchArgumentImpl) SearchArgument.FACTORY.create(expr);
+    List<PredicateLeaf> leaves = sarg.getLeaves();
+    assertEquals(4, leaves.size());
+
+    PredicateLeaf leaf = leaves.get(0);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.IS_NULL, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(null, leaf.getLiteral());
+    assertEquals(null, leaf.getLiteralList());
+
+    leaf = leaves.get(1);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.EQUALS, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("sue"), leaf.getLiteral());
+
+    leaf = leaves.get(2);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(12), leaf.getLiteral());
+
+    leaf = leaves.get(3);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.LESS_THAN_EQUALS, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(4), leaf.getLiteral());
+
+    assertEquals("(or leaf-0 (not leaf-1) (not leaf-2) leaf-3)",
+        sarg.getExpression().toString());
+    assertNoSharedNodes(sarg.getExpression(),
+        new IdentityHashSet<ExpressionTree>());
+    assertEquals(TruthValue.NO,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.YES,
+            TruthValue.NO)));
+    assertEquals(TruthValue.YES,
+        sarg.evaluate(values(TruthValue.YES, TruthValue.YES, TruthValue.YES,
+            TruthValue.NO)));
+    assertEquals(TruthValue.YES,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.NO, TruthValue.YES,
+            TruthValue.NO)));
+    assertEquals(TruthValue.YES,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.NO,
+            TruthValue.NO)));
+    assertEquals(TruthValue.YES,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.YES,
+            TruthValue.YES)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NULL, TruthValue.YES, TruthValue.YES,
+            TruthValue.NO)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.NULL, TruthValue.YES,
+            TruthValue.NO)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.NULL,
+            TruthValue.NO)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.YES,
+            TruthValue.NULL)));
+    assertEquals(TruthValue.YES_NO,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES_NO, TruthValue.YES,
+            TruthValue.YES_NO)));
+    assertEquals(TruthValue.NO_NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES_NULL, TruthValue.YES,
+            TruthValue.NO_NULL)));
+    assertEquals(TruthValue.YES_NULL,
+        sarg.evaluate(values(TruthValue.YES_NULL, TruthValue.YES_NO_NULL,
+            TruthValue.YES, TruthValue.NULL)));
+    assertEquals(TruthValue.YES_NO_NULL,
+        sarg.evaluate(values(TruthValue.NO_NULL, TruthValue.YES_NO_NULL,
+            TruthValue.YES, TruthValue.NO)));
+  }
+
+  @Test
+  public void testExpression3() throws Exception {
+    /* (id between 23 and 45) and
+       first_name = 'alan' and
+       substr('xxxxx', 3) == first_name and
+       'smith' = last_name and
+       substr(first_name, 3) == 'yyy' */
+    String exprStr = "<?xml version=\"1.0\" encoding=\"UTF-8\"?> \n" +
+        "<java version=\"1.6.0_31\" class=\"java.beans.XMLDecoder\"> \n" +
+        " <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "  <void property=\"childExprs\"> \n" +
+        "   <object class=\"java.util.ArrayList\"> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                  <void property=\"childExprs\"> \n" +
+        "                   <object class=\"java.util.ArrayList\"> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object id=\"PrimitiveTypeInfo0\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                        <void property=\"typeName\"> \n" +
+        "                         <string>boolean</string> \n" +
+        "                        </void> \n" +
+        "                       </object> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <boolean>false</boolean> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                      <void property=\"column\"> \n" +
+        "                       <string>id</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"tabAlias\"> \n" +
+        "                       <string>orc_people</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object id=\"PrimitiveTypeInfo1\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                        <void property=\"typeName\"> \n" +
+        "                         <string>int</string> \n" +
+        "                        </void> \n" +
+        "                       </object> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <int>23</int> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <int>45</int> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"genericUDF\"> \n" +
+        "                   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFBetween\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                  <void property=\"childExprs\"> \n" +
+        "                   <object class=\"java.util.ArrayList\"> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                      <void property=\"column\"> \n" +
+        "                       <string>first_name</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"tabAlias\"> \n" +
+        "                       <string>orc_people</string> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object id=\"PrimitiveTypeInfo2\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                        <void property=\"typeName\"> \n" +
+        "                         <string>string</string> \n" +
+        "                        </void> \n" +
+        "                       </object> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <string>alan</string> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"genericUDF\"> \n" +
+        "                   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual\"/> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "              <void property=\"childExprs\"> \n" +
+        "               <object class=\"java.util.ArrayList\"> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "                  <void property=\"childExprs\"> \n" +
+        "                   <object class=\"java.util.ArrayList\"> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <string>xxxxx</string> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                    <void method=\"add\"> \n" +
+        "                     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "                      <void property=\"typeInfo\"> \n" +
+        "                       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "                      </void> \n" +
+        "                      <void property=\"value\"> \n" +
+        "                       <int>3</int> \n" +
+        "                      </void> \n" +
+        "                     </object> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"genericUDF\"> \n" +
+        "                   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFBridge\"> \n" +
+        "                    <void property=\"udfClass\"> \n" +
+        "                     <class>org.apache.hadoop.hive.ql.udf.UDFSubstr</class> \n" +
+        "                    </void> \n" +
+        "                    <void property=\"udfClassName\"> \n" +
+        "                     <string>org.apache.hadoop.hive.ql.udf.UDFSubstr</string> \n" +
+        "                    </void> \n" +
+        "                    <void property=\"udfName\"> \n" +
+        "                     <string>substr</string> \n" +
+        "                    </void> \n" +
+        "                   </object> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "                <void method=\"add\"> \n" +
+        "                 <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "                  <void property=\"column\"> \n" +
+        "                   <string>first_name</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"tabAlias\"> \n" +
+        "                   <string>orc_people</string> \n" +
+        "                  </void> \n" +
+        "                  <void property=\"typeInfo\"> \n" +
+        "                   <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "                  </void> \n" +
+        "                 </object> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "              <void property=\"genericUDF\"> \n" +
+        "               <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <string>smith</string> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>last_name</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>first_name</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <int>3</int> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFBridge\"> \n" +
+        "            <void property=\"udfClass\"> \n" +
+        "             <class>org.apache.hadoop.hive.ql.udf.UDFSubstr</class> \n" +
+        "            </void> \n" +
+        "            <void property=\"udfClassName\"> \n" +
+        "             <string>org.apache.hadoop.hive.ql.udf.UDFSubstr</string> \n" +
+        "            </void> \n" +
+        "            <void property=\"udfName\"> \n" +
+        "             <string>substr</string> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"value\"> \n" +
+        "           <string>yyy</string> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPEqual\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "   </object> \n" +
+        "  </void> \n" +
+        "  <void property=\"genericUDF\"> \n" +
+        "   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "  </void> \n" +
+        "  <void property=\"typeInfo\"> \n" +
+        "   <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "  </void> \n" +
+        " </object> \n" +
+        "</java> \n";
+    Configuration conf = new Configuration();
+    ExprNodeDesc expr = Utilities.deserializeExpression(exprStr, conf);
+    SearchArgumentImpl sarg =
+        (SearchArgumentImpl) SearchArgument.FACTORY.create(expr);
+    List<PredicateLeaf> leaves = sarg.getLeaves();
+    assertEquals(3, leaves.size());
+
+    PredicateLeaf leaf = leaves.get(0);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.BETWEEN, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(null, leaf.getLiteral());
+    assertEquals(new LongWritable(23), leaf.getLiteralList().get(0));
+    assertEquals(new LongWritable(45), leaf.getLiteralList().get(1));
+
+    leaf = leaves.get(1);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.EQUALS, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("alan"), leaf.getLiteral());
+
+    leaf = leaves.get(2);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.EQUALS, leaf.getOperator());
+    assertEquals("last_name", leaf.getColumnName());
+    assertEquals(new Text("smith"), leaf.getLiteral());
+
+    assertEquals("(and leaf-0 leaf-1 leaf-2)",
+        sarg.getExpression().toString());
+    assertNoSharedNodes(sarg.getExpression(),
+        new IdentityHashSet<ExpressionTree>());
+  }
+
+  @Test
+  public void testExpression4() throws Exception {
+    /* id <> 12 and
+       first_name in ('john', 'sue') and
+       id in (34,50) */
+    String exprStr = "<?xml version=\"1.0\" encoding=\"UTF-8\"?> \n" +
+        "<java version=\"1.6.0_31\" class=\"java.beans.XMLDecoder\"> \n" +
+        " <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "  <void property=\"childExprs\"> \n" +
+        "   <object class=\"java.util.ArrayList\"> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>id</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object id=\"PrimitiveTypeInfo0\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                <void property=\"typeName\"> \n" +
+        "                 <string>int</string> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <int>12</int> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPNotEqual\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object id=\"PrimitiveTypeInfo1\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "            <void property=\"typeName\"> \n" +
+        "             <string>boolean</string> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "          <void property=\"childExprs\"> \n" +
+        "           <object class=\"java.util.ArrayList\"> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "              <void property=\"column\"> \n" +
+        "               <string>first_name</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"tabAlias\"> \n" +
+        "               <string>orc_people</string> \n" +
+        "              </void> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object id=\"PrimitiveTypeInfo2\" class=\"org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo\"> \n" +
+        "                <void property=\"typeName\"> \n" +
+        "                 <string>string</string> \n" +
+        "                </void> \n" +
+        "               </object> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <string>john</string> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "            <void method=\"add\"> \n" +
+        "             <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "              <void property=\"typeInfo\"> \n" +
+        "               <object idref=\"PrimitiveTypeInfo2\"/> \n" +
+        "              </void> \n" +
+        "              <void property=\"value\"> \n" +
+        "               <string>sue</string> \n" +
+        "              </void> \n" +
+        "             </object> \n" +
+        "            </void> \n" +
+        "           </object> \n" +
+        "          </void> \n" +
+        "          <void property=\"genericUDF\"> \n" +
+        "           <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFIn\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc\"> \n" +
+        "          <void property=\"column\"> \n" +
+        "           <string>id</string> \n" +
+        "          </void> \n" +
+        "          <void property=\"tabAlias\"> \n" +
+        "           <string>orc_people</string> \n" +
+        "          </void> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"value\"> \n" +
+        "           <int>34</int> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "        <void method=\"add\"> \n" +
+        "         <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc\"> \n" +
+        "          <void property=\"typeInfo\"> \n" +
+        "           <object idref=\"PrimitiveTypeInfo0\"/> \n" +
+        "          </void> \n" +
+        "          <void property=\"value\"> \n" +
+        "           <int>50</int> \n" +
+        "          </void> \n" +
+        "         </object> \n" +
+        "        </void> \n" +
+        "       </object> \n" +
+        "      </void> \n" +
+        "      <void property=\"genericUDF\"> \n" +
+        "       <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFIn\"/> \n" +
+        "      </void> \n" +
+        "      <void property=\"typeInfo\"> \n" +
+        "       <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "      </void> \n" +
+        "     </object> \n" +
+        "    </void> \n" +
+        "   </object> \n" +
+        "  </void> \n" +
+        "  <void property=\"genericUDF\"> \n" +
+        "   <object class=\"org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPAnd\"/> \n" +
+        "  </void> \n" +
+        "  <void property=\"typeInfo\"> \n" +
+        "   <object idref=\"PrimitiveTypeInfo1\"/> \n" +
+        "  </void> \n" +
+        " </object> \n" +
+        "</java> \n" +
+        "\n";
+    Configuration conf = new Configuration();
+    ExprNodeDesc expr = Utilities.deserializeExpression(exprStr, conf);
+    SearchArgumentImpl sarg =
+        (SearchArgumentImpl) SearchArgument.FACTORY.create(expr);
+    List<PredicateLeaf> leaves = sarg.getLeaves();
+    assertEquals(3, leaves.size());
+
+    PredicateLeaf leaf = leaves.get(0);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.EQUALS, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(12), leaf.getLiteral());
+
+    leaf = leaves.get(1);
+    assertEquals(PredicateLeaf.Type.STRING, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.IN, leaf.getOperator());
+    assertEquals("first_name", leaf.getColumnName());
+    assertEquals(new Text("john"), leaf.getLiteralList().get(0));
+    assertEquals(new Text("sue"), leaf.getLiteralList().get(1));
+
+    leaf = leaves.get(2);
+    assertEquals(PredicateLeaf.Type.INTEGER, leaf.getType());
+    assertEquals(PredicateLeaf.Operator.IN, leaf.getOperator());
+    assertEquals("id", leaf.getColumnName());
+    assertEquals(new LongWritable(34), leaf.getLiteralList().get(0));
+    assertEquals(new LongWritable(50), leaf.getLiteralList().get(1));
+
+    assertEquals("(and (not leaf-0) leaf-1 leaf-2)",
+        sarg.getExpression().toString());
+    assertNoSharedNodes(sarg.getExpression(),
+        new IdentityHashSet<ExpressionTree>());
+    assertEquals(TruthValue.YES,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.YES)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NULL, TruthValue.YES, TruthValue.YES)));
+    assertEquals(TruthValue.NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.NULL, TruthValue.YES)));
+    assertEquals(TruthValue.NO,
+        sarg.evaluate(values(TruthValue.YES, TruthValue.YES, TruthValue.YES)));
+    assertEquals(TruthValue.NO,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.NO)));
+    assertEquals(TruthValue.NO,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES_NULL, TruthValue.NO)));
+    assertEquals(TruthValue.NO_NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.NULL, TruthValue.YES_NO_NULL)));
+    assertEquals(TruthValue.NO_NULL,
+        sarg.evaluate(values(TruthValue.NO, TruthValue.YES, TruthValue.NO_NULL)));
+  }
+
+  @Test
+  public void testExpression5() throws Exception {
+    /* (first_name < 'owen' or 'foobar' = substr(last_name, 4)) and
+    first_name between 'david' and 'greg' */
+    String exprStr = "<?xml version=\"1.0\" encoding=\"UTF-8\"?> \n" +
+        "<java version=\"1.6.0_31\" class=\"java.beans.XMLDecoder\"> \n" +
+        " <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "  <void property=\"childExprs\"> \n" +
+        "   <object class=\"java.util.ArrayList\"> \n" +
+        "    <void method=\"add\"> \n" +
+        "     <object class=\"org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc\"> \n" +
+        "      <void property=\"childExprs\"> \n" +
+        "       <object class=\"java.util.ArrayList\"> \n" +

[... 1132 lines stripped ...]


Mime
View raw message