Impala
Impalaistheopensource,nativeanalyticdatabaseforApacheHadoop.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Static Public Member Functions | Static Private Member Functions | Static Private Attributes | List of all members
com.cloudera.impala.analysis.StmtRewriter Class Reference
Collaboration diagram for com.cloudera.impala.analysis.StmtRewriter:

Static Public Member Functions

static StatementBase rewrite (AnalysisResult analysisResult) throws AnalysisException
 
static void rewriteQueryStatement (QueryStmt stmt, Analyzer analyzer) throws AnalysisException
 

Static Private Member Functions

static void rewriteSelectStatement (SelectStmt stmt, Analyzer analyzer) throws AnalysisException
 
static void rewriteUnionStatement (UnionStmt stmt, Analyzer analyzer) throws AnalysisException
 
static boolean hasSubqueryInDisjunction (Expr expr)
 
static void rewriteWhereClauseSubqueries (SelectStmt stmt, Analyzer analyzer) throws AnalysisException
 
static BoolLiteral replaceExistsPredicate (ExistsPredicate predicate)
 
static Expr replaceBetweenPredicates (Expr expr)
 
static Expr rewriteExpr (Expr expr, Analyzer analyzer) throws AnalysisException
 
static boolean mergeExpr (SelectStmt stmt, Expr expr, Analyzer analyzer) throws AnalysisException
 
static void replaceUnqualifiedStarItems (SelectStmt stmt, int tableIdx)
 
static boolean canEliminate (Expr expr)
 
static ArrayList< Expr > extractCorrelatedPredicates (SelectStmt subqueryStmt) throws AnalysisException
 
static Expr extractCorrelatedPredicates (Expr root, List< TupleId > tupleIds, ArrayList< Expr > matches)
 
static void canRewriteCorrelatedSubquery (Expr expr) throws AnalysisException
 
static void updateInlineView (InlineViewRef inlineView, Expr expr, List< TupleId > parentQueryTids, List< Expr > lhsExprs, List< Expr > rhsExprs, boolean updateGroupBy) throws AnalysisException
 
static boolean canExtractCorrelatedPredicates (Expr expr, List< TupleId > subqueryTupleIds)
 
static boolean containsCorrelatedPredicate (Expr root, List< TupleId > tupleIds)
 
static boolean isCorrelatedPredicate (Expr expr, List< TupleId > tupleIds)
 
static Expr createJoinConjunct (Expr exprWithSubquery, InlineViewRef inlineView, Analyzer analyzer, boolean isCorrelated) throws AnalysisException
 

Static Private Attributes

static final Logger LOG = LoggerFactory.getLogger(StmtRewriter.class)
 

Detailed Description

Class representing a statement rewriter. A statement rewriter performs subquery unnesting on an analyzed parse tree.

Definition at line 34 of file StmtRewriter.java.

Member Function Documentation

static boolean com.cloudera.impala.analysis.StmtRewriter.canEliminate ( Expr  expr)
inlinestaticprivate

Return true if the Expr tree rooted at 'expr' can be safely eliminated, i.e. it only consists of conjunctions of true BoolLiterals.

Definition at line 571 of file StmtRewriter.java.

References com.cloudera.impala.analysis.Expr.getConjuncts(), and com.cloudera.impala.analysis.Expr.IS_TRUE_LITERAL.

Referenced by com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates(), and com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static boolean com.cloudera.impala.analysis.StmtRewriter.canExtractCorrelatedPredicates ( Expr  expr,
List< TupleId >  subqueryTupleIds 
)
inlinestaticprivate

Returns true if we can extract the correlated predicates from 'expr'. A correlated predicate cannot be extracted if it is part of a disjunction.

Definition at line 765 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.containsCorrelatedPredicate(), and com.cloudera.impala.analysis.Expr.IS_OR_PREDICATE.

Referenced by com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates().

static void com.cloudera.impala.analysis.StmtRewriter.canRewriteCorrelatedSubquery ( Expr  expr) throws AnalysisException
inlinestaticprivate

Checks if an expr containing a correlated subquery is eligible for rewrite by tranforming into a join. Throws an AnalysisException if 'expr' is not eligible for rewrite. TODO: Merge all the rewrite eligibility tests into a single function.

Definition at line 650 of file StmtRewriter.java.

References com.cloudera.impala.analysis.SelectStmt.hasAggInfo(), com.cloudera.impala.analysis.SelectStmt.hasGroupByClause(), com.cloudera.impala.analysis.QueryStmt.hasLimit(), and com.cloudera.impala.analysis.SelectStmt.toSql().

Referenced by com.cloudera.impala.analysis.StmtRewriter.mergeExpr().

static boolean com.cloudera.impala.analysis.StmtRewriter.containsCorrelatedPredicate ( Expr  root,
List< TupleId >  tupleIds 
)
inlinestaticprivate

Return true if the expr tree rooted at 'root' contains a correlated predicate.

Definition at line 783 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.isCorrelatedPredicate().

Referenced by com.cloudera.impala.analysis.StmtRewriter.canExtractCorrelatedPredicates().

static Expr com.cloudera.impala.analysis.StmtRewriter.createJoinConjunct ( Expr  exprWithSubquery,
InlineViewRef  inlineView,
Analyzer  analyzer,
boolean  isCorrelated 
) throws AnalysisException
inlinestaticprivate

Converts an expr containing a subquery into an analyzed conjunct to be used in a join. The conversion is performed in place by replacing the subquery with the first expr from the select list of 'inlineView'. If 'isCorrelated' is true and the first expr from the inline view contains an aggregate function that returns non-null on an empty input, the aggregate function is wrapped into a 'zeroifnull' function.

Definition at line 809 of file StmtRewriter.java.

References com.cloudera.impala.analysis.SelectListItem.getExpr(), com.cloudera.impala.analysis.Expr.IS_BUILTIN_AGG_FN, com.cloudera.impala.analysis.Expr.isScalarSubquery(), com.cloudera.impala.analysis.Expr.NON_NULL_EMPTY_AGG, and com.cloudera.impala.analysis.Expr.toSql().

Referenced by com.cloudera.impala.analysis.StmtRewriter.mergeExpr().

static ArrayList<Expr> com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates ( SelectStmt  subqueryStmt) throws AnalysisException
inlinestaticprivate

Extract all correlated predicates of a subquery.

TODO Handle correlated predicates in a HAVING clause.

Definition at line 583 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.canEliminate(), com.cloudera.impala.analysis.StmtRewriter.canExtractCorrelatedPredicates(), and com.cloudera.impala.analysis.JoinOperator.CROSS_JOIN.

Referenced by com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates(), and com.cloudera.impala.analysis.StmtRewriter.mergeExpr().

static Expr com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates ( Expr  root,
List< TupleId >  tupleIds,
ArrayList< Expr >  matches 
)
inlinestaticprivate

Extract all correlated predicates from the expr tree rooted at 'root' and replace them with true BoolLiterals. The modified expr tree is returned and the extracted correlated predicates are added to 'matches'.

Definition at line 631 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates(), and com.cloudera.impala.analysis.StmtRewriter.isCorrelatedPredicate().

static boolean com.cloudera.impala.analysis.StmtRewriter.hasSubqueryInDisjunction ( Expr  expr)
inlinestaticprivate

Returns true if the Expr tree rooted at 'expr' has at least one subquery that participates in a disjunction.

Definition at line 133 of file StmtRewriter.java.

References com.cloudera.impala.analysis.Expr.IS_OR_PREDICATE.

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement().

static boolean com.cloudera.impala.analysis.StmtRewriter.isCorrelatedPredicate ( Expr  expr,
List< TupleId >  tupleIds 
)
inlinestaticprivate

Returns true if 'expr' is a correlated predicate. A predicate is correlated if at least one of its SlotRefs belongs to an ancestor query block (i.e. is not bound by the given 'tupleIds').

Definition at line 796 of file StmtRewriter.java.

Referenced by com.cloudera.impala.analysis.StmtRewriter.containsCorrelatedPredicate(), and com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates().

static boolean com.cloudera.impala.analysis.StmtRewriter.mergeExpr ( SelectStmt  stmt,
Expr  expr,
Analyzer  analyzer 
) throws AnalysisException
inlinestaticprivate

Merge an expr containing a subquery with a SelectStmt 'stmt' by converting the subquery stmt of the former into an inline view and creating a join between the new inline view and the right-most table from 'stmt'. Return true if the rewrite introduced a new visible tuple due to a CROSS JOIN or a LEFT OUTER JOIN.

This process works as follows:

  1. Create a new inline view with the subquery as the view's stmt. Changes made to the subquery's stmt will affect the inline view.
  2. Extract all correlated predicates from the subquery's WHERE clause; the subquery's select list may be extended with new items and a GROUP BY clause may be added.
  3. Add the inline view to stmt's tableRefs and create a join (left semi join, anti-join, left outer join for agg functions that return a non-NULL value for an empty input, or cross-join) with stmt's right-most table.
  4. Initialize the ON clause of the new join from the original subquery predicate and the new inline view.
  5. Apply expr substitutions such that the extracted correlated predicates refer to columns of the new inline view.
  6. Add all extracted correlated predicates to the ON clause.

Definition at line 332 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.canRewriteCorrelatedSubquery(), com.cloudera.impala.analysis.InlineViewRef.clone(), com.cloudera.impala.analysis.StmtRewriter.createJoinConjunct(), com.cloudera.impala.analysis.JoinOperator.CROSS_JOIN, com.cloudera.impala.analysis.StmtRewriter.extractCorrelatedPredicates(), com.cloudera.impala.analysis.Expr.getConjuncts(), com.cloudera.impala.analysis.TableRef.getDesc(), com.cloudera.impala.analysis.SelectStmt.getSelectList(), com.cloudera.impala.analysis.InlineViewRef.getViewStmt(), com.cloudera.impala.analysis.Expr.isBoundByTupleIds(), com.cloudera.impala.analysis.JoinOperator.LEFT_ANTI_JOIN, com.cloudera.impala.analysis.JoinOperator.LEFT_OUTER_JOIN, com.cloudera.impala.analysis.JoinOperator.LEFT_SEMI_JOIN, com.cloudera.impala.analysis.Expr.NON_NULL_EMPTY_AGG, com.cloudera.impala.analysis.JoinOperator.NULL_AWARE_LEFT_ANTI_JOIN, com.cloudera.impala.analysis.QueryStmt.setLimit(), com.cloudera.impala.analysis.SelectStmt.toSql(), and com.cloudera.impala.analysis.StmtRewriter.updateInlineView().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static Expr com.cloudera.impala.analysis.StmtRewriter.replaceBetweenPredicates ( Expr  expr)
inlinestaticprivate

Replace all BetweenPredicates containing subqueries with their equivalent compound predicates from the expr tree rooted at 'expr'. The modified expr tree is returned.

Definition at line 280 of file StmtRewriter.java.

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static BoolLiteral com.cloudera.impala.analysis.StmtRewriter.replaceExistsPredicate ( ExistsPredicate  predicate)
inlinestaticprivate

Replace an ExistsPredicate that contains a subquery with a BoolLiteral if we can determine its result without evaluating it. Return null if the result of the ExistsPredicate can only be determined at run-time.

Definition at line 261 of file StmtRewriter.java.

References com.cloudera.impala.analysis.Subquery.getStatement(), and com.cloudera.impala.analysis.ExistsPredicate.isNotExists().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static void com.cloudera.impala.analysis.StmtRewriter.replaceUnqualifiedStarItems ( SelectStmt  stmt,
int  tableIdx 
)
inlinestaticprivate

Replace all unqualified star exprs ('*') from stmt's select list with qualified ones, i.e. tbl_1.*,...,tbl_n.*, where tbl_1,...,tbl_n are the visible tablerefs in stmt. 'tableIndx' indicates the maximum tableRef ordinal to consider when replacing an unqualified star item.

Definition at line 540 of file StmtRewriter.java.

References com.cloudera.impala.analysis.TableRef.getJoinOp(), com.cloudera.impala.analysis.SelectList.getPlanHints(), com.cloudera.impala.analysis.SelectListItem.isStar(), com.cloudera.impala.analysis.JoinOperator.LEFT_ANTI_JOIN, and com.cloudera.impala.analysis.SelectStmt.selectList_.

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static StatementBase com.cloudera.impala.analysis.StmtRewriter.rewrite ( AnalysisResult  analysisResult) throws AnalysisException
inlinestatic

Rewrite the statement of an analysis result. The unanalyzed rewritten statement is returned.

Definition at line 41 of file StmtRewriter.java.

References com.cloudera.impala.analysis.QueryStmt.getAnalyzer(), and com.cloudera.impala.analysis.StmtRewriter.rewriteQueryStatement().

static Expr com.cloudera.impala.analysis.StmtRewriter.rewriteExpr ( Expr  expr,
Analyzer  analyzer 
) throws AnalysisException
inlinestaticprivate

Modifies in place an expr that contains a subquery by rewriting its subquery stmt. The modified analyzed expr is returned.

Definition at line 294 of file StmtRewriter.java.

References com.cloudera.impala.analysis.Subquery.getStatement(), and com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

static void com.cloudera.impala.analysis.StmtRewriter.rewriteQueryStatement ( QueryStmt  stmt,
Analyzer  analyzer 
) throws AnalysisException
inlinestatic

Calls the appropriate rewrite method based on the specific type of query stmt. See rewriteSelectStatement() and rewriteUnionStatement() documentation.

Definition at line 72 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement(), and com.cloudera.impala.analysis.StmtRewriter.rewriteUnionStatement().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewrite(), and com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement().

static void com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement ( SelectStmt  stmt,
Analyzer  analyzer 
) throws AnalysisException
inlinestaticprivate

Rewrite all the subqueries of a SelectStmt in place. Subqueries are currently supported in FROM and WHERE clauses. The rewrite is performed in place and not in a clone of SelectStmt because it requires the stmt to be analyzed.

Definition at line 90 of file StmtRewriter.java.

References com.cloudera.impala.analysis.InlineViewRef.getViewStmt(), com.cloudera.impala.analysis.StmtRewriter.hasSubqueryInDisjunction(), com.cloudera.impala.analysis.StmtRewriter.rewriteQueryStatement(), and com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteExpr(), and com.cloudera.impala.analysis.StmtRewriter.rewriteQueryStatement().

static void com.cloudera.impala.analysis.StmtRewriter.rewriteUnionStatement ( UnionStmt  stmt,
Analyzer  analyzer 
) throws AnalysisException
inlinestaticprivate

Rewrite all operands in a UNION. The conditions that apply to SelectStmt rewriting also apply here.

Definition at line 120 of file StmtRewriter.java.

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteQueryStatement().

static void com.cloudera.impala.analysis.StmtRewriter.rewriteWhereClauseSubqueries ( SelectStmt  stmt,
Analyzer  analyzer 
) throws AnalysisException
inlinestaticprivate

Rewrite all subqueries of a stmt's WHERE clause. Initially, all the conjuncts containing subqueries are extracted from the WHERE clause and are replaced with true BoolLiterals. Subsequently, each extracted conjunct is merged into its parent select block by converting it into a join. Conjuncts with subqueries that themselves contain conjuncts with subqueries are recursively rewritten in a bottom up fashion.

The following example illustrates the bottom up rewriting of nested queries. Suppose we have the following three level nested query Q0:

SELECT * FROM T1 : Q0 WHERE T1.a IN (SELECT a FROM T2 WHERE T2.b IN (SELECT b FROM T3)) AND T1.c < 10;

This query will be rewritten as follows. Initially, the IN predicate T1.a IN (SELECT a FROM T2 WHERE T2.b IN (SELECT b FROM T3)) is extracted from the top level block (Q0) since it contains a subquery and is replaced by a true BoolLiteral, resulting in the following query Q1:

SELECT * FROM T1 WHERE TRUE : Q1

Since the stmt in the extracted predicate contains a conjunct with a subquery, it is also rewritten. As before, rewriting stmt SELECT a FROM T2 WHERE T2.b IN (SELECT b FROM T3) works by first extracting the conjunct that contains the subquery (T2.b IN (SELECT b FROM T3)) and substituting it with a true BoolLiteral, producing the following stmt Q2:

SELECT a FROM T2 WHERE TRUE : Q2

The predicate T2.b IN (SELECT b FROM T3) is then merged with Q2, producing the following unnested query Q3:

SELECT a FROM T2 LEFT SEMI JOIN (SELECT b FROM T3) $a$1 ON T2.b = $a$1.b : Q3

The extracted IN predicate becomes:

T1.a IN (SELECT a FROM T2 LEFT SEMI JOIN (SELECT b FROM T3) $a$1 ON T2.b = $a$1.b)

Finally, the rewritten IN predicate is merged with query block Q1, producing the following unnested query (WHERE clauses that contain only conjunctions of true BoolLiterals are eliminated):

SELECT * FROM T1 LEFT SEMI JOIN (SELECT a FROM T2 LEFT SEMI JOIN (SELECT b FROM T3) $a$1 ON T2.b = $a$1.b) $a$1 ON $a$1.a = T1.a WHERE T1.c < 10;

Definition at line 198 of file StmtRewriter.java.

References com.cloudera.impala.analysis.StmtRewriter.canEliminate(), com.cloudera.impala.analysis.Expr.getConjuncts(), com.cloudera.impala.analysis.Expr.IS_SCALAR_SUBQUERY, com.cloudera.impala.analysis.StmtRewriter.mergeExpr(), com.cloudera.impala.analysis.StmtRewriter.replaceBetweenPredicates(), com.cloudera.impala.analysis.StmtRewriter.replaceExistsPredicate(), com.cloudera.impala.analysis.StmtRewriter.replaceUnqualifiedStarItems(), and com.cloudera.impala.analysis.StmtRewriter.rewriteExpr().

Referenced by com.cloudera.impala.analysis.StmtRewriter.rewriteSelectStatement().

static void com.cloudera.impala.analysis.StmtRewriter.updateInlineView ( InlineViewRef  inlineView,
Expr  expr,
List< TupleId >  parentQueryTids,
List< Expr >  lhsExprs,
List< Expr >  rhsExprs,
boolean  updateGroupBy 
) throws AnalysisException
inlinestaticprivate

Update the subquery within an inline view by expanding its select list with exprs from a correlated predicate 'expr' that will be 'moved' to an ON clause in the subquery's parent query block. We need to make sure that every expr extracted from the subquery references an item in the subquery's select list. If 'updateGroupBy' is true, the exprs extracted from 'expr' are also added in stmt's GROUP BY clause. Throws an AnalysisException if we need to update the GROUP BY clause but both the lhs and rhs of 'expr' reference a tuple of the subquery stmt.

Definition at line 686 of file StmtRewriter.java.

References com.cloudera.impala.analysis.SelectList.getPlanHints(), com.cloudera.impala.analysis.SelectStmt.hasGroupByClause(), and com.cloudera.impala.analysis.SelectStmt.selectList_.

Referenced by com.cloudera.impala.analysis.StmtRewriter.mergeExpr().

Member Data Documentation

final Logger com.cloudera.impala.analysis.StmtRewriter.LOG = LoggerFactory.getLogger(StmtRewriter.class)
staticprivate

Definition at line 35 of file StmtRewriter.java.

The documentation for this class was generated from the following file: