/ Check-in [6b1651d7]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Always render a subquery that is not part of a join as a co-routine.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | prefer-coroutine-sort-subquery
Files: files | file ages | folders
SHA3-256: 6b1651d711eae6e7c65a191f02ca2439160bcd677099712289e76a0f8422fd37
User & Date: drh 2017-09-29 22:13:24
Context
2017-09-30
01:25
Fix unreachable conditionals and revise a testcase that was made obsolete by the changes on this branch. check-in: 71f0adf7 user: drh tags: prefer-coroutine-sort-subquery
2017-09-29
22:13
Always render a subquery that is not part of a join as a co-routine. check-in: 6b1651d7 user: drh tags: prefer-coroutine-sort-subquery
16:08
Merge the query flattener comment improvements from trunk. check-in: f62cd4d9 user: drh tags: prefer-coroutine-sort-subquery
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  3294   3294   ** The code generated for this simplification gives the same result
  3295   3295   ** but only has to scan the data once.  And because indices might 
  3296   3296   ** exist on the table t1, a complete scan of the data might be
  3297   3297   ** avoided.
  3298   3298   **
  3299   3299   ** Flattening is subject to the following constraints:
  3300   3300   **
  3301         -**   (1)  The subquery and the outer query cannot both be aggregates.
         3301  +**  (**)  We no longer attempt to flatten aggregate subqueries. Was:
         3302  +**        The subquery and the outer query cannot both be aggregates.
  3302   3303   **
  3303         -**   (2)  If the subquery is an aggregate then
         3304  +**  (**)  We no longer attempt to flatten aggregate subqueries. Was:
         3305  +**        (2) If the subquery is an aggregate then
  3304   3306   **        (2a) the outer query must not be a join and
  3305   3307   **        (2b) the outer query must not use subqueries
  3306   3308   **             other than the one FROM-clause subquery that is a candidate
  3307   3309   **             for flattening.  (This is due to ticket [2f7170d73bf9abf80]
  3308   3310   **             from 2015-02-09.)
  3309   3311   **
  3310   3312   **   (3)  If the subquery is the right operand of a LEFT JOIN then
................................................................................
  3315   3317   **
  3316   3318   **   (4)  The subquery can not be DISTINCT.
  3317   3319   **
  3318   3320   **  (**)  At one point restrictions (4) and (5) defined a subset of DISTINCT
  3319   3321   **        sub-queries that were excluded from this optimization. Restriction 
  3320   3322   **        (4) has since been expanded to exclude all DISTINCT subqueries.
  3321   3323   **
  3322         -**   (6)  If the subquery is aggregate, the outer query may not be DISTINCT.
         3324  +**  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
         3325  +**        If the subquery is aggregate, the outer query may not be DISTINCT.
  3323   3326   **
  3324   3327   **   (7)  The subquery must have a FROM clause.  TODO:  For subqueries without
  3325   3328   **        A FROM clause, consider adding a FROM clause with the special
  3326   3329   **        table sqlite_once that consists of a single row containing a
  3327   3330   **        single NULL.
  3328   3331   **
  3329   3332   **   (8)  If the subquery uses LIMIT then the outer query may not be a join.
................................................................................
  3402   3405   **        or max() functions.  (Without this restriction, a query like:
  3403   3406   **        "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
  3404   3407   **        return the value X for which Y was maximal.)
  3405   3408   **
  3406   3409   **
  3407   3410   ** In this routine, the "p" parameter is a pointer to the outer query.
  3408   3411   ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
  3409         -** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
         3412  +** uses aggregates.
  3410   3413   **
  3411   3414   ** If flattening is not attempted, this routine is a no-op and returns 0.
  3412   3415   ** If flattening is attempted this routine returns 1.
  3413   3416   **
  3414   3417   ** All of the expression analysis must occur on both the outer query and
  3415   3418   ** the subquery before this routine runs.
  3416   3419   */
  3417   3420   static int flattenSubquery(
  3418   3421     Parse *pParse,       /* Parsing context */
  3419   3422     Select *p,           /* The parent or outer SELECT statement */
  3420   3423     int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
  3421         -  int isAgg,           /* True if outer SELECT uses aggregate functions */
  3422         -  int subqueryIsAgg    /* True if the subquery uses aggregate functions */
         3424  +  int isAgg            /* True if outer SELECT uses aggregate functions */
  3423   3425   ){
  3424   3426     const char *zSavedAuthContext = pParse->zAuthContext;
  3425   3427     Select *pParent;    /* Current UNION ALL term of the other query */
  3426   3428     Select *pSub;       /* The inner query or "subquery" */
  3427   3429     Select *pSub1;      /* Pointer to the rightmost select in sub-query */
  3428   3430     SrcList *pSrc;      /* The FROM clause of the outer query */
  3429   3431     SrcList *pSubSrc;   /* The FROM clause of the subquery */
................................................................................
  3442   3444     if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
  3443   3445     pSrc = p->pSrc;
  3444   3446     assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  3445   3447     pSubitem = &pSrc->a[iFrom];
  3446   3448     iParent = pSubitem->iCursor;
  3447   3449     pSub = pSubitem->pSelect;
  3448   3450     assert( pSub!=0 );
  3449         -  if( subqueryIsAgg ){
  3450         -    if( isAgg ) return 0;                                /* Restriction (1)   */
  3451         -    if( pSrc->nSrc>1 ) return 0;                         /* Restriction (2a)  */
  3452         -    if( (p->pWhere && ExprHasProperty(p->pWhere,EP_Subquery))
  3453         -     || (sqlite3ExprListFlags(p->pEList) & EP_Subquery)!=0
  3454         -     || (sqlite3ExprListFlags(p->pOrderBy) & EP_Subquery)!=0
  3455         -    ){
  3456         -      return 0;                                          /* Restriction (2b)  */
  3457         -    }
  3458         -  }
  3459   3451   
  3460   3452     pSubSrc = pSub->pSrc;
  3461   3453     assert( pSubSrc );
  3462   3454     /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
  3463   3455     ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
  3464   3456     ** because they could be computed at compile-time.  But when LIMIT and OFFSET
  3465   3457     ** became arbitrary expressions, we were forced to add restrictions (13)
................................................................................
  3470   3462       return 0;                                            /* Restriction (15) */
  3471   3463     }
  3472   3464     if( pSubSrc->nSrc==0 ) return 0;                       /* Restriction (7)  */
  3473   3465     if( pSub->selFlags & SF_Distinct ) return 0;           /* Restriction (4)  */
  3474   3466     if( pSub->pLimit && (pSrc->nSrc>1 || isAgg) ){
  3475   3467        return 0;         /* Restrictions (8)(9) */
  3476   3468     }
  3477         -  if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){
  3478         -     return 0;         /* Restriction (6)  */
  3479         -  }
  3480   3469     if( p->pOrderBy && pSub->pOrderBy ){
  3481   3470        return 0;                                           /* Restriction (11) */
  3482   3471     }
  3483   3472     if( isAgg && pSub->pOrderBy ) return 0;                /* Restriction (16) */
  3484   3473     if( pSub->pLimit && p->pWhere ) return 0;              /* Restriction (19) */
  3485   3474     if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){
  3486   3475        return 0;         /* Restriction (21) */
................................................................................
  3774   3763         pParent->pOrderBy = pOrderBy;
  3775   3764         pSub->pOrderBy = 0;
  3776   3765       }
  3777   3766       pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);
  3778   3767       if( isLeftJoin>0 ){
  3779   3768         setJoinExpr(pWhere, iNewParent);
  3780   3769       }
  3781         -    if( subqueryIsAgg ){
  3782         -      assert( pParent->pHaving==0 );
  3783         -      pParent->pHaving = pParent->pWhere;
  3784         -      pParent->pWhere = pWhere;
  3785         -      pParent->pHaving = sqlite3ExprAnd(db, 
  3786         -          sqlite3ExprDup(db, pSub->pHaving, 0), pParent->pHaving
  3787         -      );
  3788         -      assert( pParent->pGroupBy==0 );
  3789         -      pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy, 0);
  3790         -    }else{
  3791         -      pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
  3792         -    }
         3770  +    pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
  3793   3771       if( db->mallocFailed==0 ){
  3794   3772         SubstContext x;
  3795   3773         x.pParse = pParse;
  3796   3774         x.iTable = iParent;
  3797   3775         x.iNewTable = iNewParent;
  3798   3776         x.isLeftJoin = isLeftJoin;
  3799   3777         x.pEList = pSub->pEList;
................................................................................
  3848   3826   **     WHERE x=5 AND y=10;
  3849   3827   **
  3850   3828   ** The hope is that the terms added to the inner query will make it more
  3851   3829   ** efficient.
  3852   3830   **
  3853   3831   ** Do not attempt this optimization if:
  3854   3832   **
  3855         -**   (1) The inner query is an aggregate.  (In that case, we'd really want
  3856         -**       to copy the outer WHERE-clause terms onto the HAVING clause of the
  3857         -**       inner query.  But they probably won't help there so do not bother.)
         3833  +**   (1) (** This restriction was removed on 2017-09-29.  We used to
         3834  +**           disallow this optimization for aggregate subqueries, but now
         3835  +**           it is allowed by putting the extra terms on the HAVING clause **)
  3858   3836   **
  3859   3837   **   (2) The inner query is the recursive part of a common table expression.
  3860   3838   **
  3861   3839   **   (3) The inner query has a LIMIT clause (since the changes to the WHERE
  3862   3840   **       close would change the meaning of the LIMIT).
  3863   3841   **
  3864   3842   **   (4) The inner query is the right operand of a LEFT JOIN.  (The caller
................................................................................
  3878   3856     int iCursor           /* Cursor number of the subquery */
  3879   3857   ){
  3880   3858     Expr *pNew;
  3881   3859     int nChng = 0;
  3882   3860     Select *pX;           /* For looping over compound SELECTs in pSubq */
  3883   3861     if( pWhere==0 ) return 0;
  3884   3862     for(pX=pSubq; pX; pX=pX->pPrior){
  3885         -    if( (pX->selFlags & (SF_Aggregate|SF_Recursive))!=0 ){
  3886         -      testcase( pX->selFlags & SF_Aggregate );
  3887         -      testcase( pX->selFlags & SF_Recursive );
         3863  +    if( (pX->selFlags & (SF_Recursive))!=0 ){
  3888   3864         testcase( pX!=pSubq );
  3889         -      return 0; /* restrictions (1) and (2) */
         3865  +      return 0; /* restriction (2) */
  3890   3866       }
  3891   3867     }
  3892   3868     if( pSubq->pLimit!=0 ){
  3893   3869       return 0; /* restriction (3) */
  3894   3870     }
  3895   3871     while( pWhere->op==TK_AND ){
  3896   3872       nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
  3897   3873       pWhere = pWhere->pLeft;
  3898   3874     }
  3899         -  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction 5 */
         3875  +  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */
  3900   3876     if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
  3901   3877       nChng++;
  3902   3878       while( pSubq ){
  3903   3879         SubstContext x;
  3904   3880         pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
  3905   3881         x.pParse = pParse;
  3906   3882         x.iTable = iCursor;
  3907   3883         x.iNewTable = iCursor;
  3908   3884         x.isLeftJoin = 0;
  3909   3885         x.pEList = pSubq->pEList;
  3910   3886         pNew = substExpr(&x, pNew);
  3911         -      pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
         3887  +      if( pSubq->selFlags & SF_Aggregate ){
         3888  +        pSubq->pHaving = sqlite3ExprAnd(pParse->db, pSubq->pHaving, pNew);
         3889  +      }else{
         3890  +        pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
         3891  +      }
  3912   3892         pSubq = pSubq->pPrior;
  3913   3893       }
  3914   3894     }
  3915   3895     return nChng;
  3916   3896   }
  3917   3897   #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
  3918   3898   
................................................................................
  5198   5178   
  5199   5179     /* Try to flatten subqueries in the FROM clause up into the main query
  5200   5180     */
  5201   5181   #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  5202   5182     for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
  5203   5183       struct SrcList_item *pItem = &pTabList->a[i];
  5204   5184       Select *pSub = pItem->pSelect;
  5205         -    int isAggSub;
  5206   5185       Table *pTab = pItem->pTab;
  5207   5186       if( pSub==0 ) continue;
  5208   5187   
  5209   5188       /* Catch mismatch in the declared columns of a view and the number of
  5210   5189       ** columns in the SELECT on the RHS */
  5211   5190       if( pTab->nCol!=pSub->pEList->nExpr ){
  5212   5191         sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
  5213   5192                         pTab->nCol, pTab->zName, pSub->pEList->nExpr);
  5214   5193         goto select_end;
  5215   5194       }
  5216   5195   
  5217         -    /* If the subquery contains an ORDER BY or GROUP BY clause and if
         5196  +    /* Do not try to flatten an aggregate subquery.
         5197  +    **
         5198  +    ** Flattening an aggregate subquery is only possible if the outer query
         5199  +    ** is not a join.  But if the outer query is not a join, then the subquery
         5200  +    ** will be implemented as a co-routine and there is no advantage to
         5201  +    ** flattening in that case.
         5202  +    */
         5203  +    if( (pSub->selFlags & SF_Aggregate)!=0 ) continue;
         5204  +    assert( pSub->pGroupBy==0 );
         5205  +
         5206  +    /* If the subquery contains an ORDER BY clause and if
  5218   5207       ** it will be implemented as a co-routine, then do not flatten.  This
  5219   5208       ** restriction allows SQL constructs like this:
  5220   5209       **
  5221   5210       **  SELECT expensive_function(x)
  5222   5211       **    FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
  5223   5212       **
  5224   5213       ** The expensive_function() is only computed on the 10 rows that
  5225   5214       ** are output, rather than every row of the table.
  5226   5215       */
  5227         -    if( (pSub->pOrderBy!=0 || pSub->pGroupBy!=0)
         5216  +    if( pSub->pOrderBy!=0
  5228   5217        && i==0
  5229   5218        && (pTabList->nSrc==1
  5230   5219            || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)
  5231         -     && OptimizationEnabled(db, SQLITE_SubqCoroutine)
  5232   5220       ){
  5233   5221         continue;
  5234   5222       }
  5235   5223   
  5236         -    isAggSub = (pSub->selFlags & SF_Aggregate)!=0;
  5237         -    if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
         5224  +    if( flattenSubquery(pParse, p, i, isAgg) ){
  5238   5225         /* This subquery can be absorbed into its parent. */
  5239         -      if( isAggSub ){
  5240         -        isAgg = 1;
  5241         -        p->selFlags |= SF_Aggregate;
  5242         -      }
  5243   5226         i = -1;
  5244   5227       }
  5245   5228       pTabList = p->pSrc;
  5246   5229       if( db->mallocFailed ) goto select_end;
  5247   5230       if( !IgnorableOrderby(pDest) ){
  5248   5231         sSort.pOrderBy = p->pOrderBy;
  5249   5232       }
................................................................................
  5344   5327       }
  5345   5328   
  5346   5329       zSavedAuthContext = pParse->zAuthContext;
  5347   5330       pParse->zAuthContext = pItem->zName;
  5348   5331   
  5349   5332       /* Generate code to implement the subquery
  5350   5333       **
  5351         -    ** The subquery is implemented as a co-routine if all of these are true:
  5352         -    **   (1)  The subquery is guaranteed to be the outer loop (so that it
  5353         -    **        does not need to be computed more than once)
  5354         -    **   (2)  REMOVED (2017-09-28): The ALL keyword after SELECT is omitted.
  5355         -    **   (3)  Co-routines are not disabled using sqlite3_test_control()
  5356         -    **        with SQLITE_TESTCTRL_OPTIMIZATIONS.
         5334  +    ** The subquery is implemented as a co-routine if the subquery is
         5335  +    ** guaranteed to be the outer loop (so that it does not need to be
         5336  +    ** computed more than once)
  5357   5337       **
  5358   5338       ** TODO: Are there other reasons beside (1) to use a co-routine
  5359   5339       ** implementation?
  5360   5340       */
  5361   5341       if( i==0
  5362   5342        && (pTabList->nSrc==1
  5363   5343               || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)  /* (1) */
  5364         -     /*** constraint removed: && (p->selFlags & SF_All)==0             (2) */
  5365         -     && OptimizationEnabled(db, SQLITE_SubqCoroutine)               /* (3) */
  5366   5344       ){
  5367   5345         /* Implement a co-routine that will return a single row of the result
  5368   5346         ** set on each invocation.
  5369   5347         */
  5370   5348         int addrTop = sqlite3VdbeCurrentAddr(v)+1;
  5371   5349        
  5372   5350         pItem->regReturn = ++pParse->nMem;

Changes to src/sqliteInt.h.

  1502   1502   ** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface to
  1503   1503   ** selectively disable various optimizations.
  1504   1504   */
  1505   1505   #define SQLITE_QueryFlattener 0x0001   /* Query flattening */
  1506   1506   #define SQLITE_ColumnCache    0x0002   /* Column cache */
  1507   1507   #define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
  1508   1508   #define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
  1509         -/*                not used    0x0010   // Was: SQLITE_IdxRealAsInt */
  1510         -#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
  1511         -#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
  1512         -#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
  1513         -#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
  1514         -#define SQLITE_Transitive     0x0200   /* Transitive constraints */
  1515         -#define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
  1516         -#define SQLITE_Stat34         0x0800   /* Use STAT3 or STAT4 data */
  1517         -#define SQLITE_CountOfView    0x1000   /* The count-of-view optimization */
  1518         -#define SQLITE_CursorHints    0x2000   /* Add OP_CursorHint opcodes */
         1509  +#define SQLITE_DistinctOpt    0x0010   /* DISTINCT using indexes */
         1510  +#define SQLITE_CoverIdxScan   0x0020   /* Covering index scans */
         1511  +#define SQLITE_OrderByIdxJoin 0x0040   /* ORDER BY of joins via index */
         1512  +#define SQLITE_Transitive     0x0080   /* Transitive constraints */
         1513  +#define SQLITE_OmitNoopJoin   0x0100   /* Omit unused tables in joins */
         1514  +#define SQLITE_Stat34         0x0200   /* Use STAT3 or STAT4 data */
         1515  +#define SQLITE_CountOfView    0x0400   /* The count-of-view optimization */
         1516  +#define SQLITE_CursorHints    0x0800   /* Add OP_CursorHint opcodes */
  1519   1517   #define SQLITE_AllOpts        0xffff   /* All optimizations */
  1520   1518   
  1521   1519   /*
  1522   1520   ** Macros for testing whether or not optimizations are enabled or disabled.
  1523   1521   */
  1524   1522   #define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
  1525   1523   #define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)

Changes to src/test1.c.

  6897   6897       { "column-cache",        SQLITE_ColumnCache    },
  6898   6898       { "groupby-order",       SQLITE_GroupByOrder   },
  6899   6899       { "factor-constants",    SQLITE_FactorOutConst },
  6900   6900       { "distinct-opt",        SQLITE_DistinctOpt    },
  6901   6901       { "cover-idx-scan",      SQLITE_CoverIdxScan   },
  6902   6902       { "order-by-idx-join",   SQLITE_OrderByIdxJoin },
  6903   6903       { "transitive",          SQLITE_Transitive     },
  6904         -    { "subquery-coroutine",  SQLITE_SubqCoroutine  },
  6905   6904       { "omit-noop-join",      SQLITE_OmitNoopJoin   },
  6906   6905       { "stat3",               SQLITE_Stat34         },
  6907   6906       { "stat4",               SQLITE_Stat34         },
  6908   6907     };
  6909   6908   
  6910   6909     if( objc!=4 ){
  6911   6910       Tcl_WrongNumArgs(interp, 1, objv, "DB OPT BOOLEAN");