SQLite

/*
** Return the bitwise-OR of all Expr.flags fields in the given
** ExprList.
*/
u32 sqlite3ExprListFlags(const ExprList *pList){
  int i;
  u32 m = 0;
  if( pList ){
    for(i=0; i<pList->nExpr; i++){
       Expr *pExpr = pList->a[i].pExpr;
       assert( pExpr!=0 );
       m |= pExpr->flags;
  assert( pList!=0 );
  for(i=0; i<pList->nExpr; i++){
     Expr *pExpr = pList->a[i].pExpr;
     assert( pExpr!=0 );
     m |= pExpr->flags;
    }
  }
  return m;
}

/*
** This is a SELECT-node callback for the expression walker that
** always "fails".  By "fail" in this case, we mean set

** The code generated for this simplification gives the same result
** but only has to scan the data once.  And because indices might 
** exist on the table t1, a complete scan of the data might be
** avoided.
**
** Flattening is subject to the following constraints:
**
**  (**)  We no longer attempt to flatten aggregate subqueries. Was:
**   (1)  The subquery and the outer query cannot both be aggregates.
**        The subquery and the outer query cannot both be aggregates.
**
**  (**)  We no longer attempt to flatten aggregate subqueries. Was:
**   (2)  If the subquery is an aggregate then
**        (2) If the subquery is an aggregate then
**        (2a) the outer query must not be a join and
**        (2b) the outer query must not use subqueries
**             other than the one FROM-clause subquery that is a candidate
**             for flattening.  (This is due to ticket [2f7170d73bf9abf80]
**             from 2015-02-09.)
**
**   (3)  If the subquery is the right operand of a LEFT JOIN then
**        (3a) the subquery may not be a join and
**        (3b) the FROM clause of the subquery may not contain a virtual
**             table and
**        (3c) the outer query may not be an aggregate.
**
**   (4)  The subquery can not be DISTINCT.
**
**  (**)  At one point restrictions (4) and (5) defined a subset of DISTINCT
**        sub-queries that were excluded from this optimization. Restriction 
**        (4) has since been expanded to exclude all DISTINCT subqueries.
**
**  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
**   (6)  If the subquery is aggregate, the outer query may not be DISTINCT.
**        If the subquery is aggregate, the outer query may not be DISTINCT.
**
**   (7)  The subquery must have a FROM clause.  TODO:  For subqueries without
**        A FROM clause, consider adding a FROM clause with the special
**        table sqlite_once that consists of a single row containing a
**        single NULL.
**
**   (8)  If the subquery uses LIMIT then the outer query may not be a join.

**  (22)  The subquery may not be a recursive CTE.
**
**  (23)  If the outer query is a recursive CTE, then the sub-query may not be
**        a compound query. This restriction is because transforming the
**        parent to a compound query confuses the code that handles
**        recursive queries in multiSelect().
**
**  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
**  (24)  The subquery may not be an aggregate that uses the built-in min() or 
**        The subquery may not be an aggregate that uses the built-in min() or 
**        or max() functions.  (Without this restriction, a query like:
**        "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
**        return the value X for which Y was maximal.)
**
**
** In this routine, the "p" parameter is a pointer to the outer query.
** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
** uses aggregates.
**
** If flattening is not attempted, this routine is a no-op and returns 0.
** If flattening is attempted this routine returns 1.
**
** All of the expression analysis must occur on both the outer query and
** the subquery before this routine runs.
*/
static int flattenSubquery(
  Parse *pParse,       /* Parsing context */
  Select *p,           /* The parent or outer SELECT statement */
  int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
  int isAgg,           /* True if outer SELECT uses aggregate functions */
  int isAgg            /* True if outer SELECT uses aggregate functions */
  int subqueryIsAgg    /* True if the subquery uses aggregate functions */
){
  const char *zSavedAuthContext = pParse->zAuthContext;
  Select *pParent;    /* Current UNION ALL term of the other query */
  Select *pSub;       /* The inner query or "subquery" */
  Select *pSub1;      /* Pointer to the rightmost select in sub-query */
  SrcList *pSrc;      /* The FROM clause of the outer query */
  SrcList *pSubSrc;   /* The FROM clause of the subquery */

  if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
  pSrc = p->pSrc;
  assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  pSubitem = &pSrc->a[iFrom];
  iParent = pSubitem->iCursor;
  pSub = pSubitem->pSelect;
  assert( pSub!=0 );
  if( subqueryIsAgg ){
    if( isAgg ) return 0;                                /* Restriction (1)   */
    if( pSrc->nSrc>1 ) return 0;                         /* Restriction (2a)  */
    if( (p->pWhere && ExprHasProperty(p->pWhere,EP_Subquery))
     || (sqlite3ExprListFlags(p->pEList) & EP_Subquery)!=0
     || (sqlite3ExprListFlags(p->pOrderBy) & EP_Subquery)!=0
    ){
      return 0;                                          /* Restriction (2b)  */
    }
  }

  pSubSrc = pSub->pSrc;
  assert( pSubSrc );
  /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
  ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
  ** because they could be computed at compile-time.  But when LIMIT and OFFSET
  ** became arbitrary expressions, we were forced to add restrictions (13)
  ** and (14). */
  if( pSub->pLimit && p->pLimit ) return 0;              /* Restriction (13) */
  if( pSub->pOffset ) return 0;                          /* Restriction (14) */
  if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){
    return 0;                                            /* Restriction (15) */
  }
  if( pSubSrc->nSrc==0 ) return 0;                       /* Restriction (7)  */
  if( pSub->selFlags & SF_Distinct ) return 0;           /* Restriction (4)  */
  if( pSub->pLimit && (pSrc->nSrc>1 || isAgg) ){
     return 0;         /* Restrictions (8)(9) */
  }
  if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){
     return 0;         /* Restriction (6)  */
  }
  if( p->pOrderBy && pSub->pOrderBy ){
     return 0;                                           /* Restriction (11) */
  }
  if( isAgg && pSub->pOrderBy ) return 0;                /* Restriction (16) */
  if( pSub->pLimit && p->pWhere ) return 0;              /* Restriction (19) */
  if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){
     return 0;         /* Restriction (21) */
  }
  testcase( pSub->selFlags & SF_Recursive );
  testcase( pSub->selFlags & SF_MinMaxAgg );
  if( pSub->selFlags & (SF_Recursive|SF_MinMaxAgg) ){
    return 0; /* Restrictions (22) and (24) */
  if( pSub->selFlags & (SF_Recursive) ){
    return 0; /* Restrictions (22) */
  }
  if( (p->selFlags & SF_Recursive) && pSub->pPrior ){
    return 0; /* Restriction (23) */
  }

  /*
  ** If the subquery is the right operand of a LEFT JOIN, then the

      pParent->pOrderBy = pOrderBy;
      pSub->pOrderBy = 0;
    }
    pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);
    if( isLeftJoin>0 ){
      setJoinExpr(pWhere, iNewParent);
    }
    if( subqueryIsAgg ){
      assert( pParent->pHaving==0 );
      pParent->pHaving = pParent->pWhere;
      pParent->pWhere = pWhere;
      pParent->pHaving = sqlite3ExprAnd(db, 
          sqlite3ExprDup(db, pSub->pHaving, 0), pParent->pHaving
      );
      assert( pParent->pGroupBy==0 );
      pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy, 0);
    }else{
      pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
    pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
    }
    if( db->mallocFailed==0 ){
      SubstContext x;
      x.pParse = pParse;
      x.iTable = iParent;
      x.iNewTable = iNewParent;
      x.isLeftJoin = isLeftJoin;
      x.pEList = pSub->pEList;

**     WHERE x=5 AND y=10;
**
** The hope is that the terms added to the inner query will make it more
** efficient.
**
** Do not attempt this optimization if:
**
**   (1) The inner query is an aggregate.  (In that case, we'd really want
**       to copy the outer WHERE-clause terms onto the HAVING clause of the
**       inner query.  But they probably won't help there so do not bother.)
**   (1) (** This restriction was removed on 2017-09-29.  We used to
**           disallow this optimization for aggregate subqueries, but now
**           it is allowed by putting the extra terms on the HAVING clause.
**           The added HAVING clause is pointless if the subquery lacks
**           a GROUP BY clause.  But such a HAVING clause is also harmless
**           so there does not appear to be any reason to add extra logic
**           to suppress it. **)
**
**   (2) The inner query is the recursive part of a common table expression.
**
**   (3) The inner query has a LIMIT clause (since the changes to the WHERE
**       close would change the meaning of the LIMIT).
**
**   (4) The inner query is the right operand of a LEFT JOIN.  (The caller

  Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
  Expr *pWhere,         /* The WHERE clause of the outer query */
  int iCursor           /* Cursor number of the subquery */
){
  Expr *pNew;
  int nChng = 0;
  Select *pX;           /* For looping over compound SELECTs in pSubq */
  if( pWhere==0 ) return 0;
  if( pSubq->selFlags & SF_Recursive ) return 0;  /* restriction (2) */

#ifdef SQLITE_DEBUG
  /* Only the first term of a compound can have a WITH clause.  But make
  ** sure no other terms are marked SF_Recursive in case something changes
  ** in the future.
  */
  {
    Select *pX;  
  for(pX=pSubq; pX; pX=pX->pPrior){
    if( (pX->selFlags & (SF_Aggregate|SF_Recursive))!=0 ){
    for(pX=pSubq; pX; pX=pX->pPrior){
      assert( (pX->selFlags & (SF_Recursive))==0 );
      testcase( pX->selFlags & SF_Aggregate );
      testcase( pX->selFlags & SF_Recursive );
      testcase( pX!=pSubq );
      return 0; /* restrictions (1) and (2) */
    }
  }
#endif

  if( pSubq->pLimit!=0 ){
    return 0; /* restriction (3) */
  }
  while( pWhere->op==TK_AND ){
    nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
    pWhere = pWhere->pLeft;
  }
  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction 5 */
  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */
  if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
    nChng++;
    while( pSubq ){
      SubstContext x;
      pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
      x.pParse = pParse;
      x.iTable = iCursor;
      x.iNewTable = iCursor;
      x.isLeftJoin = 0;
      x.pEList = pSubq->pEList;
      pNew = substExpr(&x, pNew);
      if( pSubq->selFlags & SF_Aggregate ){
        pSubq->pHaving = sqlite3ExprAnd(pParse->db, pSubq->pHaving, pNew);
      }else{
      pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
        pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
      }
      pSubq = pSubq->pPrior;
    }
  }
  return nChng;
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

  /* Try to flatten subqueries in the FROM clause up into the main query
  */
#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
    struct SrcList_item *pItem = &pTabList->a[i];
    Select *pSub = pItem->pSelect;
    int isAggSub;
    Table *pTab = pItem->pTab;
    if( pSub==0 ) continue;

    /* Catch mismatch in the declared columns of a view and the number of
    ** columns in the SELECT on the RHS */
    if( pTab->nCol!=pSub->pEList->nExpr ){
      sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
                      pTab->nCol, pTab->zName, pSub->pEList->nExpr);
      goto select_end;
    }

    /* Do not try to flatten an aggregate subquery.
    **
    ** Flattening an aggregate subquery is only possible if the outer query
    ** is not a join.  But if the outer query is not a join, then the subquery
    ** will be implemented as a co-routine and there is no advantage to
    ** flattening in that case.
    */
    isAggSub = (pSub->selFlags & SF_Aggregate)!=0;
    if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
    if( (pSub->selFlags & SF_Aggregate)!=0 ) continue;
    assert( pSub->pGroupBy==0 );

    /* If the subquery contains an ORDER BY clause and if
    ** it will be implemented as a co-routine, then do not flatten.  This
    ** restriction allows SQL constructs like this:
    **
    **  SELECT expensive_function(x)
    **    FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
    **
    ** The expensive_function() is only computed on the 10 rows that
    ** are output, rather than every row of the table.
    */
    if( pSub->pOrderBy!=0
     && i==0
     && (pTabList->nSrc==1
         || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)
    ){
      continue;
    }

    if( flattenSubquery(pParse, p, i, isAgg) ){
      /* This subquery can be absorbed into its parent. */
      if( isAggSub ){
        isAgg = 1;
        p->selFlags |= SF_Aggregate;
      }
      i = -1;
    }
    pTabList = p->pSrc;
    if( db->mallocFailed ) goto select_end;
    if( !IgnorableOrderby(pDest) ){
      sSort.pOrderBy = p->pOrderBy;
    }

    }

    zSavedAuthContext = pParse->zAuthContext;
    pParse->zAuthContext = pItem->zName;

    /* Generate code to implement the subquery
    **
    ** The subquery is implemented as a co-routine if all of these are true:
    **   (1)  The subquery is guaranteed to be the outer loop (so that it
    **        does not need to be computed more than once)
    ** The subquery is implemented as a co-routine if the subquery is
    ** guaranteed to be the outer loop (so that it does not need to be
    ** computed more than once)
    **   (2)  REMOVED (2017-09-28): The ALL keyword after SELECT is omitted.
    **   (3)  Co-routines are not disabled using sqlite3_test_control()
    **        with SQLITE_TESTCTRL_OPTIMIZATIONS.
    **
    ** TODO: Are there other reasons beside (1) to use a co-routine
    ** implementation?
    */
    if( i==0
     && (pTabList->nSrc==1
            || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)  /* (1) */
     /*** constraint removed: && (p->selFlags & SF_All)==0             (2) */
     && OptimizationEnabled(db, SQLITE_SubqCoroutine)               /* (3) */
    ){
      /* Implement a co-routine that will return a single row of the result
      ** set on each invocation.
      */
      int addrTop = sqlite3VdbeCurrentAddr(v)+1;
     
      pItem->regReturn = ++pParse->nMem;

** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface to
** selectively disable various optimizations.
*/
#define SQLITE_QueryFlattener 0x0001   /* Query flattening */
#define SQLITE_ColumnCache    0x0002   /* Column cache */
#define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
#define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
/*                not used    0x0010   // Was: SQLITE_IdxRealAsInt */
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_DistinctOpt    0x0010   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0020   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0040   /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive     0x0200   /* Transitive constraints */
#define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
#define SQLITE_Transitive     0x0080   /* Transitive constraints */
#define SQLITE_OmitNoopJoin   0x0100   /* Omit unused tables in joins */
#define SQLITE_CountOfView    0x0200   /* The count-of-view optimization */
#define SQLITE_CursorHints    0x0400   /* Add OP_CursorHint opcodes */
#define SQLITE_Stat34         0x0800   /* Use STAT3 or STAT4 data */
#define SQLITE_CountOfView    0x1000   /* The count-of-view optimization */
   /* TH3 expects the Stat34  ^^^^^^ value to be 0x0800.  Don't change it */
#define SQLITE_CursorHints    0x2000   /* Add OP_CursorHint opcodes */
#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
#define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)

    { "column-cache",        SQLITE_ColumnCache    },
    { "groupby-order",       SQLITE_GroupByOrder   },
    { "factor-constants",    SQLITE_FactorOutConst },
    { "distinct-opt",        SQLITE_DistinctOpt    },
    { "cover-idx-scan",      SQLITE_CoverIdxScan   },
    { "order-by-idx-join",   SQLITE_OrderByIdxJoin },
    { "transitive",          SQLITE_Transitive     },
    { "subquery-coroutine",  SQLITE_SubqCoroutine  },
    { "omit-noop-join",      SQLITE_OmitNoopJoin   },
    { "stat3",               SQLITE_Stat34         },
    { "stat4",               SQLITE_Stat34         },
  };

  if( objc!=4 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB OPT BOOLEAN");

  2 "SELECT a, sum(b) FROM t1 GROUP BY a HAVING sum(b)>5 AND a=2"
    "SELECT a, sum(b) FROM t1 WHERE a=2 GROUP BY a HAVING sum(b)>5"

  3 "SELECT a, sum(b) FROM t1 GROUP BY a COLLATE binary HAVING a=2"
    "SELECT a, sum(b) FROM t1 WHERE a=2 GROUP BY a COLLATE binary"

  4 {
      SELECT x,y FROM (
        SELECT a AS x, sum(b) AS y FROM t1 
        GROUP BY a
      ) WHERE x BETWEEN 8888 AND 9999
    } {
      SELECT x,y FROM (
        SELECT a AS x, sum(b) AS y FROM t1 
        WHERE x BETWEEN 8888 AND 9999 
        GROUP BY a
      )
    }

  5 "SELECT a, sum(b) FROM t1 GROUP BY a COLLATE binary HAVING 0"
    "SELECT a, sum(b) FROM t1 WHERE 0 GROUP BY a COLLATE binary"

  6 "SELECT count(*) FROM t1,t2 WHERE a=c GROUP BY b, d HAVING b=d"
    "SELECT count(*) FROM t1,t2 WHERE a=c AND b=d GROUP BY b, d"

  7 {
      SELECT count(*) FROM t1,t2 WHERE a=c GROUP BY b, d 
      HAVING b=d COLLATE nocase
    } {
      SELECT count(*) FROM t1,t2 WHERE a=c AND b=d COLLATE nocase 
      GROUP BY b, d
    }

  8 "SELECT a, sum(b) FROM t1 GROUP BY a||b HAVING substr(a||b, 1, 1)='a'"
    "SELECT a, sum(b) FROM t1 WHERE substr(a||b, 1, 1)='a' GROUP BY a||b"
} {
  do_compare_vdbe_test 2.$tn $sql1 $sql2 1
}

# The (4) test in the above set used to generate identical bytecode, but
# that is no longer the case.  The byte code is equivalent, though.
#
do_execsql_test 2.4a {
  SELECT x,y FROM (
    SELECT a AS x, sum(b) AS y FROM t1 
    GROUP BY a
  ) WHERE x BETWEEN 2 AND 9999
} {2 12}
do_execsql_test 2.4b {
  SELECT x,y FROM (
    SELECT a AS x, sum(b) AS y FROM t1 
    WHERE x BETWEEN 2 AND 9999 
    GROUP BY a
  )
} {2 12}


#-------------------------------------------------------------------------
# 1: Test that the optimization is only applied if the GROUP BY term
#    uses BINARY collation.
#
# 2: Not applied if there is a non-deterministic function in the HAVING
#    term.