omalley commented on a change in pull request #647: URL: https://github.com/apache/orc/pull/647#discussion_r586816241
########## File path: java/core/src/java/org/apache/orc/OrcFilterContext.java ########## @@ -0,0 +1,90 @@ +/* + * 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.orc; + +import org.apache.hadoop.hive.ql.exec.vector.ColumnVector; +import org.apache.hadoop.hive.ql.exec.vector.ListColumnVector; +import org.apache.hadoop.hive.ql.exec.vector.MapColumnVector; +import org.apache.hadoop.hive.ql.exec.vector.VectorizedRowBatch; +import org.apache.hadoop.hive.ql.io.filter.MutableFilterContext; + +/** + * This defines the input for any filter operation. This is an extension of + * [[{@link VectorizedRowBatch}]] with schema. + * <p> + * This offers a convenience method of finding the column vector from a given column name + * that the filters can invoke to get access to the column vector. + */ +public interface OrcFilterContext extends MutableFilterContext { + /** + * Retrieves the column vector that matches the specified name. Allows support for nested struct + * references e.g. order.date where date is a field in a struct called order. + * + * @param name The column name whose vector should be retrieved + * @return The column vectors from the root to the column name. The array levels match the name + * levels with Array[0] referring to the top level, followed by the subsequent levels. For + * example of order.date Array[0] refers to order and Array[1] refers to date + * @throws IllegalArgumentException if the field is not found or if the nested field is not part + * of a struct + */ + ColumnVector[] findColumnVector(String name); + + /** + * Utility method for determining if the leaf vector of the branch can be treated as having + * noNulls. + * This method navigates from the top to the leaf and checks if we have nulls anywhere in the + * branch as compared to checking just the leaf vector. + * + * @param vectorBranch The input vector branch from the root to the leaf + * @return true if the entire branch satisfies noNull else false + */ + static boolean noNulls(ColumnVector[] vectorBranch) { + for (ColumnVector v : vectorBranch) { + if (!v.noNulls) { + return false; + } + } + return true; + } + + /** + * Utility method for determining if a particular row element in the vector branch is null. + * This method navigates from the top to the leaf and checks if we have nulls anywhere in the + * branch as compared to checking just the leaf vector. + * + * @param vectorBranch The input vector branch from the root to the leaf + * @param idx The row index being tested + * @return true if the entire branch is not null for the idx otherwise false + * @throws IllegalArgumentException If a multivalued vector such as List or Map is encountered in + * the branch. + */ + static boolean isNull(ColumnVector[] vectorBranch, int idx) throws IllegalArgumentException { + for (ColumnVector v : vectorBranch) { + if (v instanceof ListColumnVector || v instanceof MapColumnVector) { + throw new IllegalArgumentException(String.format( + "Found vector: %s in branch. List and Map vectors are not supported in isNull " + + "determination", v)); + } + if (!v.noNulls && (v.isRepeating || v.isNull[idx])) { Review comment: This should be if (!v.noNulls && v.isNull[v.isRepeating ? 0 : idx]) { ... } ########## File path: java/core/src/java/org/apache/orc/impl/ParserUtils.java ########## @@ -249,75 +255,210 @@ public static TypeDescription findSubtype(TypeDescription schema, return findSubtype(schema, source, true); } + + public interface TypeVisitor { + /** + * As we navigate to the column, call this on each level + * @param type new level we are moving to + * @param posn the position relative to the parent + */ + void visit(TypeDescription type, int posn); + } + + public static class TypeFinder implements TypeVisitor { + public TypeDescription current; + + public TypeFinder(TypeDescription schema) { + current = schema; + } + + @Override + public void visit(TypeDescription type, int posn) { + current = type; + } + } + public static TypeDescription findSubtype(TypeDescription schema, ParserUtils.StringPosition source, boolean isSchemaEvolutionCaseAware) { - List<String> names = ParserUtils.splitName(source); + TypeFinder result = new TypeFinder(removeAcid(schema)); + findColumn(result.current, source, isSchemaEvolutionCaseAware, result); + return result.current; + } + + private static TypeDescription removeAcid(TypeDescription schema) { + return SchemaEvolution.checkAcidSchema(schema) + ? SchemaEvolution.getBaseRow(schema) : schema; + } + + private static int findCaseInsensitive(List<String> list, String goal) { + for (int i = 0; i < list.size(); i++) { + if (list.get(i).equalsIgnoreCase(goal)) { + return i; + } + } + return -1; + } + + public static void findSubtype(TypeDescription schema, + int goal, + TypeVisitor visitor) { + TypeDescription current = schema; + int id = schema.getId(); + if (goal < id || goal > schema.getMaximumId()) { + throw new IllegalArgumentException("Unknown type id " + id + " in " + + current.toJson()); + } + while (id != goal) { + List<TypeDescription> children = current.getChildren(); + for(int i=0; i < children.size(); ++i) { + TypeDescription child = children.get(i); + if (goal <= child.getMaximumId()) { + current = child; + visitor.visit(current, i); + break; + } + } + id = current.getId(); + } + } + + /** + * Find a column in a schema by walking down the type tree to find the right column. + * @param schema the schema to look in + * @param source the name of the column + * @param isSchemaEvolutionCaseAware should the string compare be case sensitive + * @param visitor The visitor, which is called on each level + */ + public static void findColumn(TypeDescription schema, + ParserUtils.StringPosition source, + boolean isSchemaEvolutionCaseAware, + TypeVisitor visitor) { + findColumn(schema, ParserUtils.splitName(source), isSchemaEvolutionCaseAware, visitor); + } + + /** + * Find a column in a schema by walking down the type tree to find the right column. + * @param schema the schema to look in + * @param names the name of the column broken into a list of names per level + * @param isSchemaEvolutionCaseAware should the string compare be case sensitive + * @param visitor The visitor, which is called on each level + */ + public static void findColumn(TypeDescription schema, + List<String> names, + boolean isSchemaEvolutionCaseAware, + TypeVisitor visitor) { if (names.size() == 1 && INTEGER_PATTERN.matcher(names.get(0)).matches()) { - return schema.findSubtype(Integer.parseInt(names.get(0))); + findSubtype(schema, Integer.parseInt(names.get(0)), visitor); + return; } - TypeDescription current = SchemaEvolution.checkAcidSchema(schema) - ? SchemaEvolution.getBaseRow(schema) : schema; + TypeDescription current = schema; + int posn; while (names.size() > 0) { String first = names.remove(0); switch (current.getCategory()) { case STRUCT: { - int posn = -1; - if (isSchemaEvolutionCaseAware) { - posn = current.getFieldNames().indexOf(first); - } else { - // Case-insensitive search like ORC 1.5 - for (int i = 0; i < current.getFieldNames().size(); i++) { - if (current.getFieldNames().get(i).equalsIgnoreCase(first)) { - posn = i; - break; - } - } - } - if (posn == -1) { - throw new IllegalArgumentException("Field " + first + - " not found in " + current.toString()); - } - current = current.getChildren().get(posn); + posn = isSchemaEvolutionCaseAware + ? current.getFieldNames().indexOf(first) + : findCaseInsensitive(current.getFieldNames(), first); break; } case LIST: if (first.equals("_elem")) { - current = current.getChildren().get(0); + posn = 0; } else { - throw new IllegalArgumentException("Field " + first + - "not found in " + current.toString()); + posn = -1; } break; case MAP: if (first.equals("_key")) { - current = current.getChildren().get(0); + posn = 0; } else if (first.equals("_value")) { - current = current.getChildren().get(1); + posn = 1; } else { - throw new IllegalArgumentException("Field " + first + - "not found in " + current.toString()); + posn = -1; } break; case UNION: { try { - int posn = Integer.parseInt(first); + posn = Integer.parseInt(first); if (posn < 0 || posn >= current.getChildren().size()) { throw new NumberFormatException("off end of union"); } - current = current.getChildren().get(posn); } catch (NumberFormatException e) { throw new IllegalArgumentException("Field " + first + Review comment: We could simplify this code by just setting posn to -1 here. ########## File path: java/core/src/java/org/apache/orc/impl/ParserUtils.java ########## @@ -249,75 +255,210 @@ public static TypeDescription findSubtype(TypeDescription schema, return findSubtype(schema, source, true); } + + public interface TypeVisitor { + /** + * As we navigate to the column, call this on each level + * @param type new level we are moving to + * @param posn the position relative to the parent + */ + void visit(TypeDescription type, int posn); + } + + public static class TypeFinder implements TypeVisitor { + public TypeDescription current; + + public TypeFinder(TypeDescription schema) { + current = schema; + } + + @Override + public void visit(TypeDescription type, int posn) { + current = type; + } + } + public static TypeDescription findSubtype(TypeDescription schema, ParserUtils.StringPosition source, boolean isSchemaEvolutionCaseAware) { - List<String> names = ParserUtils.splitName(source); + TypeFinder result = new TypeFinder(removeAcid(schema)); + findColumn(result.current, source, isSchemaEvolutionCaseAware, result); + return result.current; + } + + private static TypeDescription removeAcid(TypeDescription schema) { + return SchemaEvolution.checkAcidSchema(schema) + ? SchemaEvolution.getBaseRow(schema) : schema; + } + + private static int findCaseInsensitive(List<String> list, String goal) { + for (int i = 0; i < list.size(); i++) { + if (list.get(i).equalsIgnoreCase(goal)) { + return i; + } + } + return -1; + } + + public static void findSubtype(TypeDescription schema, + int goal, + TypeVisitor visitor) { + TypeDescription current = schema; + int id = schema.getId(); + if (goal < id || goal > schema.getMaximumId()) { + throw new IllegalArgumentException("Unknown type id " + id + " in " + + current.toJson()); + } + while (id != goal) { + List<TypeDescription> children = current.getChildren(); + for(int i=0; i < children.size(); ++i) { + TypeDescription child = children.get(i); + if (goal <= child.getMaximumId()) { + current = child; + visitor.visit(current, i); + break; + } + } + id = current.getId(); + } + } + + /** + * Find a column in a schema by walking down the type tree to find the right column. + * @param schema the schema to look in + * @param source the name of the column + * @param isSchemaEvolutionCaseAware should the string compare be case sensitive + * @param visitor The visitor, which is called on each level + */ + public static void findColumn(TypeDescription schema, + ParserUtils.StringPosition source, + boolean isSchemaEvolutionCaseAware, + TypeVisitor visitor) { + findColumn(schema, ParserUtils.splitName(source), isSchemaEvolutionCaseAware, visitor); + } + + /** + * Find a column in a schema by walking down the type tree to find the right column. + * @param schema the schema to look in + * @param names the name of the column broken into a list of names per level + * @param isSchemaEvolutionCaseAware should the string compare be case sensitive + * @param visitor The visitor, which is called on each level + */ + public static void findColumn(TypeDescription schema, + List<String> names, + boolean isSchemaEvolutionCaseAware, + TypeVisitor visitor) { if (names.size() == 1 && INTEGER_PATTERN.matcher(names.get(0)).matches()) { - return schema.findSubtype(Integer.parseInt(names.get(0))); + findSubtype(schema, Integer.parseInt(names.get(0)), visitor); + return; } - TypeDescription current = SchemaEvolution.checkAcidSchema(schema) - ? SchemaEvolution.getBaseRow(schema) : schema; + TypeDescription current = schema; + int posn; while (names.size() > 0) { String first = names.remove(0); switch (current.getCategory()) { case STRUCT: { - int posn = -1; - if (isSchemaEvolutionCaseAware) { - posn = current.getFieldNames().indexOf(first); - } else { - // Case-insensitive search like ORC 1.5 - for (int i = 0; i < current.getFieldNames().size(); i++) { - if (current.getFieldNames().get(i).equalsIgnoreCase(first)) { - posn = i; - break; - } - } - } - if (posn == -1) { - throw new IllegalArgumentException("Field " + first + - " not found in " + current.toString()); - } - current = current.getChildren().get(posn); + posn = isSchemaEvolutionCaseAware + ? current.getFieldNames().indexOf(first) + : findCaseInsensitive(current.getFieldNames(), first); break; } case LIST: if (first.equals("_elem")) { - current = current.getChildren().get(0); + posn = 0; } else { - throw new IllegalArgumentException("Field " + first + - "not found in " + current.toString()); + posn = -1; } break; case MAP: if (first.equals("_key")) { - current = current.getChildren().get(0); + posn = 0; } else if (first.equals("_value")) { - current = current.getChildren().get(1); + posn = 1; } else { - throw new IllegalArgumentException("Field " + first + - "not found in " + current.toString()); + posn = -1; } break; case UNION: { try { - int posn = Integer.parseInt(first); + posn = Integer.parseInt(first); if (posn < 0 || posn >= current.getChildren().size()) { throw new NumberFormatException("off end of union"); } - current = current.getChildren().get(posn); } catch (NumberFormatException e) { throw new IllegalArgumentException("Field " + first + "not found in " + current.toString(), e); } break; } default: - throw new IllegalArgumentException("Field " + first + - "not found in " + current.toString()); + posn = -1; + } + if (posn < 0) { + throw new IllegalArgumentException("Field " + first + + " not found in " + current.toString()); + } + current = current.getChildren().get(posn); + visitor.visit(current, posn); + } + } + + static class ColumnFinder implements TypeVisitor { + private ColumnVector[] top; + private ColumnVector current = null; + private final ColumnVector[] result; + private int resultIdx = 0; + + ColumnFinder(TypeDescription schema, VectorizedRowBatch batch, List<String> levels) { Review comment: Instead of passing in the List of strings, I think I'd pass in the levels as an int. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
