[Hadoop Wiki] Update of "Hive/FilterPushdownDev" by JohnSichi

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hadoop Wiki" for change notification.

The "Hive/FilterPushdownDev" page has been changed by JohnSichi.
http://wiki.apache.org/hadoop/Hive/FilterPushdownDev?action=diff&rev1=1&rev2=2

--------------------------------------------------

  
  As mentioned above, we want to avoid duplication in code which
  interprets the filter string (e.g. parsing).  As a first cut, we will
- provide access to the `ExprNodeDesc` tree (either via a utility
+ provide access to the `ExprNodeDesc` tree by passing it along in
+ serialized form as an optional companion to the filter string.  In followups, we will provide parsing utilities for the string form.
- which parses the filter string, or perhaps by passing it along in
- serialized form as an optional companion to the filter string).
  
- In followups, we can provide utilities for analyzing an expression
- tree to identify [[http://en.wikipedia.org/wiki/Sargable|sargable]]
- subexpressions.
+ We will also provide an IndexPredicateAnalyzer class capable of detecting simple [[http://en.wikipedia.org/wiki/Sargable|sargable]]
+ subexpressions in an `ExprNodeDesc` tree.  In followups, we will provide support for discriminating and combining more complex indexable subexpressions.
+ 
+ {{{
+ public class IndexPredicateAnalyzer
+ {
+   public IndexPredicateAnalyzer();
+ 
+   /**
+    * Registers a comparison operator as one which can be satisfied
+    * by an index search.  Unless this is called, analyzePredicate
+    * will never find any indexable conditions.
+    *
+    * @param udfName name of comparison operator as returned
+    * by either {@link GenericUDFBridge#getUdfName} (for simple UDF's)
+    * or udf.getClass().getName() (for generic UDF's).
+    */
+   public void addComparisonOp(String udfName);
+ 
+   /**
+    * Clears the set of column names allowed in comparisons.  (Initially, all
+    * column names are allowed.)
+    */
+   public void clearAllowedColumnNames();
+ 
+   /**
+    * Adds a column name to the set of column names allowed.
+    *
+    * @param columnName name of column to be allowed
+    */
+   public void allowColumnName(String columnName);
+ 
+   /**
+    * Analyzes a predicate.
+    *
+    * @param predicate predicate to be analyzed
+    *
+    * @param searchConditions receives conditions produced by analysis
+    *
+    * @return residual predicate which could not be translated to
+    * searchConditions
+    */
+   public ExprNodeDesc analyzePredicate(
+     ExprNodeDesc predicate,
+     final List<IndexSearchCondition> searchConditions);
+ 
+   /**
+    * Translates search conditions back to ExprNodeDesc form (as
+    * a left-deep conjunction).
+    *
+    * @param searchConditions (typically produced by analyzePredicate)
+    *
+    * @return ExprNodeDesc form of search conditions
+    */
+   public ExprNodeDesc translateSearchConditions(
+     List<IndexSearchCondition> searchConditions);
+ }
+ 
+ public class IndexSearchCondition
+ {
+   /**
+    * Constructs a search condition, which takes the form
+    * <pre>column-ref comparison-op constant-value</pre>.
+    *
+    * @param columnDesc column being compared
+    *
+    * @param comparisonOp comparison operator, e.g. "="
+    * (taken from GenericUDFBridge.getUdfName())
+    *
+    * @param constantDesc constant value to search for
+    *
+    * @Param comparisonExpr the original comparison expression
+    */
+   public IndexSearchCondition(
+     ExprNodeColumnDesc columnDesc,
+     String comparisonOp,
+     ExprNodeConstantDesc constantDesc,
+     ExprNodeDesc comparisonExpr);
+ }
+ 
+ 
+ }}}
  
  == Filter Passing ==
  
@@ -83, +161 @@

   * classes such as `HiveInputFormat` call `ColumnProjectionUtils` to set the projection pushdown property (READ_COLUMN_IDS_CONF_STR) on a jobConf before instantiating a `RecordReader`
   * the factory method for the `RecordReader` calls `ColumnProjectionUtils` to access this property
  
- There are a few differences for filter pushdown:
+ For filter pushdown:
  
-  * the utility methods should be somewhere other than serde (maybe ql)
-  * the filter needs to be available to getSplits as well since the selectivity of the filter may alter the splits needed (actually this is true in theory for column projection also)
+  * `HiveInputFormat` sets properties `hive.io.filter.text` (string form) and `hive.io.filter.expr.serialized` (serialized form of ExprNodeDesc) in the job conf before calling getSplits as well as before instantiating a record reader
+  * the storage handler's input format reads these properties and processes the filter expression
-  * additional interaction for negotiation of filter decomposition (described in a later section)
+  * there is a separate optimizer interaction for negotiation of filter decomposition (described in a later section)
+ 
+ Note that getSplits needs to be involved since the selectivity of the filter may prune away some of the splits which would otherwise be accessed.  (In theory column projection could also influence the split boundaries, but we'll leave that for a followup.)
  
  == Filter Collection ==
  
- So, where will `HiveInputFormat` and friends get the filter string to be
+ So, where will `HiveInputFormat` get the filter expression to be
  passed down?  Again, we can start with the pattern for column projections:
  
   * during optimization, `org.apache.hadoop.hive.ql.optimizer.ColumnPrunerProcFactory's` `ColumnPrunerTableScanProc` populates the pushdown information in `TableScanOperator`
@@ -103, +183 @@

  called condn, and then sticks that on a new `FilterOperator`.  We can
  call condn.getExprString() and store the result on `TableScanOperator`.
  
- For getSplits, some more mucking around is going to be required (TBD).
+ Hive configuration parameter `hive.optimize.ppd.storage` can be used to enable or disable pushing filters down to the storage handler.  This will be enabled by default.  However, if `hive.optimize.ppd` is disabled, then this implicitly prevents pushdown to storage handlers as well.
+ 
+ We are starting with non-native tables only; we'll revisit this for pushing filters down to indexes and builtin storage formats such as RCFile.
  
  == Filter Decomposition ==
  
@@ -122, +204 @@

  In order for this to be possible, the storage handler needs to be able
  to negotiate the decomposition with Hive.  This means that Hive gives
  the storage handler the entire filter, and the storage handler passes
+ back a "residual":  the portion that needs to be evaluated by Hive.  A null residual indicates that the storage handler was able to deal with the entire
+ filter on its own (in which case no `FilterOperator` is needed).
- back just the portion that needs to be evaluated by Hive (or null to
- indicate that the storage handler was able to deal with the entire
- filter on its own).
  
+ In order to support this interaction, we will introduce a new (optional) interface to be implemented by storage handlers:
- The mechanism for this communication remains TBD.  Until it is worked
- out, we will start with a sub-optimal approach whereby the storage
- handler analyzes the filter and implements the portion it understands,
- and Hive re-evaluates the entire filter (implying redundant effort for
- the portion already taken care of by the storage handler).
  
+ {{{
+ public interface HiveStoragePredicateHandler {
+   public DecomposedPredicate decomposePredicate(
+     JobConf jobConf,
+     Deserializer deserializer,
+     ExprNodeDesc predicate);
+ 
+   public static class DecomposedPredicate {
+     public ExprNodeDesc pushedPredicate;
+     public ExprNodeDesc residualPredicate;
+   }
+ }
+ 
+ }}}
+ 
+ Hive's optimizer (during predicate pushdown) calls the decomposePredicate method, passing in the full expression and receiving back the decomposition (or null to indicate that no pushdown was possible).  The `pushedPredicate` gets passed back to the storage handler's input format later, and the `residualPredicate` is attached to the `FilterOperator`.
+ 
+ It is assumed that storage handlers which are sophisticated enough to implement this interface are suitable for tight coupling to the `ExprNodeDesc` representation.
+ 
+ Again, this interface is optional, and pushdown is still possible even without it.  If the storage handler does not implement this interface, Hive will always implement the entire expression in the `FilterOperator`, but it will still provide the expression to the storage handler's input format; the storage handler is free to implement as much or as little as it wants.
+