/ Check-in [f62cd4d9]
Login

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

Overview
Comment:Merge the query flattener comment improvements from trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | prefer-coroutine-sort-subquery
Files: files | file ages | folders
SHA3-256: f62cd4d940506c39db82e83ff3df8ab1856f1fb91ffda835ae2d727263ee9b0b
User & Date: drh 2017-09-29 16:08:46
Context
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
16:07
Clean up the comments on the query flattener to more clearly and accurately express the conditions under which the flattener is able to run. check-in: 0840f9f8 user: drh tags: trunk
14:31
Merge changes from trunk. check-in: 06f432fb user: drh tags: prefer-coroutine-sort-subquery
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  3292   3292   **     SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
  3293   3293   **
  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         -** Flattening is only attempted if all of the following are true:
         3299  +** Flattening is subject to the following constraints:
  3300   3300   **
  3301         -**   (1)  The subquery and the outer query do not both use aggregates.
         3301  +**   (1)  The subquery and the outer query cannot both be aggregates.
  3302   3302   **
  3303         -**   (2)  The subquery is not an aggregate or (2a) the outer query is not a join
  3304         -**        and (2b) the outer query does not use subqueries other than the one
  3305         -**        FROM-clause subquery that is a candidate for flattening.  (2b is
  3306         -**        due to ticket [2f7170d73bf9abf80] from 2015-02-09.)
         3303  +**   (2)  If the subquery is an aggregate then
         3304  +**        (2a) the outer query must not be a join and
         3305  +**        (2b) the outer query must not use subqueries
         3306  +**             other than the one FROM-clause subquery that is a candidate
         3307  +**             for flattening.  (This is due to ticket [2f7170d73bf9abf80]
         3308  +**             from 2015-02-09.)
  3307   3309   **
  3308         -**   (3)  The subquery is not the right operand of a LEFT JOIN
  3309         -**        or (a) the subquery is not itself a join and (b) the FROM clause
  3310         -**        of the subquery does not contain a virtual table and (c) the 
  3311         -**        outer query is not an aggregate.
         3310  +**   (3)  If the subquery is the right operand of a LEFT JOIN then
         3311  +**        (3a) the subquery may not be a join and
         3312  +**        (3b) the FROM clause of the subquery may not contain a virtual
         3313  +**             table and
         3314  +**        (3c) the outer query may not be an aggregate.
  3312   3315   **
  3313         -**   (4)  The subquery is not DISTINCT.
         3316  +**   (4)  The subquery can not be DISTINCT.
  3314   3317   **
  3315   3318   **  (**)  At one point restrictions (4) and (5) defined a subset of DISTINCT
  3316   3319   **        sub-queries that were excluded from this optimization. Restriction 
  3317   3320   **        (4) has since been expanded to exclude all DISTINCT subqueries.
  3318   3321   **
  3319         -**   (6)  The subquery does not use aggregates or the outer query is not
  3320         -**        DISTINCT.
         3322  +**   (6)  If the subquery is aggregate, the outer query may not be DISTINCT.
  3321   3323   **
  3322         -**   (7)  The subquery has a FROM clause.  TODO:  For subqueries without
         3324  +**   (7)  The subquery must have a FROM clause.  TODO:  For subqueries without
  3323   3325   **        A FROM clause, consider adding a FROM clause with the special
  3324   3326   **        table sqlite_once that consists of a single row containing a
  3325   3327   **        single NULL.
  3326   3328   **
  3327         -**   (8)  The subquery does not use LIMIT or the outer query is not a join.
         3329  +**   (8)  If the subquery uses LIMIT then the outer query may not be a join.
  3328   3330   **
  3329         -**   (9)  The subquery does not use LIMIT or the outer query does not use
  3330         -**        aggregates.
         3331  +**   (9)  If the subquery uses LIMIT then the outer query may not be aggregate.
  3331   3332   **
  3332   3333   **  (**)  Restriction (10) was removed from the code on 2005-02-05 but we
  3333   3334   **        accidently carried the comment forward until 2014-09-15.  Original
  3334         -**        text: "The subquery does not use aggregates or the outer query 
  3335         -**        does not use LIMIT."
         3335  +**        constraint: "If the subquery is aggregate then the outer query 
         3336  +**        may not use LIMIT."
  3336   3337   **
  3337         -**  (11)  The subquery and the outer query do not both have ORDER BY clauses.
         3338  +**  (11)  The subquery and the outer query may not both have ORDER BY clauses.
  3338   3339   **
  3339   3340   **  (**)  Not implemented.  Subsumed into restriction (3).  Was previously
  3340   3341   **        a separate restriction deriving from ticket #350.
  3341   3342   **
  3342         -**  (13)  The subquery and outer query do not both use LIMIT.
         3343  +**  (13)  The subquery and outer query may not both use LIMIT.
  3343   3344   **
  3344         -**  (14)  The subquery does not use OFFSET.
         3345  +**  (14)  The subquery may not use OFFSET.
  3345   3346   **
  3346         -**  (15)  The outer query is not part of a compound select or the
  3347         -**        subquery does not have a LIMIT clause.
         3347  +**  (15)  If the outer query is part of a compound select, then the
         3348  +**        subquery may not use LIMIT.
  3348   3349   **        (See ticket #2339 and ticket [02a8e81d44]).
  3349   3350   **
  3350         -**  (16)  The outer query is not an aggregate or the subquery does
  3351         -**        not contain ORDER BY.  (Ticket #2942)  This used to not matter
         3351  +**  (16)  If the outer query is aggregate, then the subquery may not
         3352  +**        use ORDER BY.  (Ticket #2942)  This used to not matter
  3352   3353   **        until we introduced the group_concat() function.  
  3353   3354   **
  3354         -**  (17)  The sub-query is not a compound select, or it is a UNION ALL 
  3355         -**        compound clause made up entirely of non-aggregate queries, and 
  3356         -**        the parent query:
  3357         -**
  3358         -**          * is not itself part of a compound select,
  3359         -**          * is not an aggregate or DISTINCT query, and
  3360         -**          * is not a join
         3355  +**  (17)  If the subquery is a compound select, then
         3356  +**        (17a) all compound operators must be a UNION ALL, and
         3357  +**        (17b) no terms within the subquery compound may be aggregate
         3358  +**              or DISTINT, and
         3359  +**        (17c) every term within the subquery compound must have a FROM clause
         3360  +**        (17d) the outer query may not be
         3361  +**              (17d1) aggregate, or
         3362  +**              (17d2) DISTINCT, or
         3363  +**              (17d3) a join.
  3361   3364   **
  3362   3365   **        The parent and sub-query may contain WHERE clauses. Subject to
  3363   3366   **        rules (11), (13) and (14), they may also contain ORDER BY,
  3364   3367   **        LIMIT and OFFSET clauses.  The subquery cannot use any compound
  3365   3368   **        operator other than UNION ALL because all the other compound
  3366   3369   **        operators have an implied DISTINCT which is disallowed by
  3367   3370   **        restriction (4).
................................................................................
  3369   3372   **        Also, each component of the sub-query must return the same number
  3370   3373   **        of result columns. This is actually a requirement for any compound
  3371   3374   **        SELECT statement, but all the code here does is make sure that no
  3372   3375   **        such (illegal) sub-query is flattened. The caller will detect the
  3373   3376   **        syntax error and return a detailed message.
  3374   3377   **
  3375   3378   **  (18)  If the sub-query is a compound select, then all terms of the
  3376         -**        ORDER by clause of the parent must be simple references to 
         3379  +**        ORDER BY clause of the parent must be simple references to 
  3377   3380   **        columns of the sub-query.
  3378   3381   **
  3379         -**  (19)  The subquery does not use LIMIT or the outer query does not
         3382  +**  (19)  If the subquery uses LIMIT then the outer query may not
  3380   3383   **        have a WHERE clause.
  3381   3384   **
  3382   3385   **  (20)  If the sub-query is a compound select, then it must not use
  3383   3386   **        an ORDER BY clause.  Ticket #3773.  We could relax this constraint
  3384   3387   **        somewhat by saying that the terms of the ORDER BY clause must
  3385   3388   **        appear as unmodified result columns in the outer query.  But we
  3386   3389   **        have other optimizations in mind to deal with that case.
  3387   3390   **
  3388         -**  (21)  The subquery does not use LIMIT or the outer query is not
         3391  +**  (21)  If the subquery uses LIMIT then the outer query may not be
  3389   3392   **        DISTINCT.  (See ticket [752e1646fc]).
  3390   3393   **
  3391         -**  (22)  The subquery is not a recursive CTE.
         3394  +**  (22)  The subquery may not be a recursive CTE.
  3392   3395   **
  3393         -**  (23)  The parent is not a recursive CTE, or the sub-query is not a
  3394         -**        compound query. This restriction is because transforming the
         3396  +**  (23)  If the outer query is a recursive CTE, then the sub-query may not be
         3397  +**        a compound query. This restriction is because transforming the
  3395   3398   **        parent to a compound query confuses the code that handles
  3396   3399   **        recursive queries in multiSelect().
  3397   3400   **
  3398         -**  (24)  The subquery is not an aggregate that uses the built-in min() or 
         3401  +**  (24)  The subquery may not be an aggregate that uses the built-in min() or 
  3399   3402   **        or max() functions.  (Without this restriction, a query like:
  3400   3403   **        "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
  3401   3404   **        return the value X for which Y was maximal.)
  3402   3405   **
  3403   3406   **
  3404   3407   ** In this routine, the "p" parameter is a pointer to the outer query.
  3405   3408   ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
................................................................................
  3431   3434     Expr *pWhere;                    /* The WHERE clause */
  3432   3435     struct SrcList_item *pSubitem;   /* The subquery */
  3433   3436     sqlite3 *db = pParse->db;
  3434   3437   
  3435   3438     /* Check to see if flattening is permitted.  Return 0 if not.
  3436   3439     */
  3437   3440     assert( p!=0 );
  3438         -  assert( p->pPrior==0 );  /* Unable to flatten compound queries */
         3441  +  assert( p->pPrior==0 );
  3439   3442     if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
  3440   3443     pSrc = p->pSrc;
  3441   3444     assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  3442   3445     pSubitem = &pSrc->a[iFrom];
  3443   3446     iParent = pSubitem->iCursor;
  3444   3447     pSub = pSubitem->pSelect;
  3445   3448     assert( pSub!=0 );
................................................................................
  3463   3466     ** and (14). */
  3464   3467     if( pSub->pLimit && p->pLimit ) return 0;              /* Restriction (13) */
  3465   3468     if( pSub->pOffset ) return 0;                          /* Restriction (14) */
  3466   3469     if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){
  3467   3470       return 0;                                            /* Restriction (15) */
  3468   3471     }
  3469   3472     if( pSubSrc->nSrc==0 ) return 0;                       /* Restriction (7)  */
  3470         -  if( pSub->selFlags & SF_Distinct ) return 0;           /* Restriction (5)  */
         3473  +  if( pSub->selFlags & SF_Distinct ) return 0;           /* Restriction (4)  */
  3471   3474     if( pSub->pLimit && (pSrc->nSrc>1 || isAgg) ){
  3472   3475        return 0;         /* Restrictions (8)(9) */
  3473   3476     }
  3474   3477     if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){
  3475   3478        return 0;         /* Restriction (6)  */
  3476   3479     }
  3477   3480     if( p->pOrderBy && pSub->pOrderBy ){
................................................................................
  3489   3492     }
  3490   3493     if( (p->selFlags & SF_Recursive) && pSub->pPrior ){
  3491   3494       return 0; /* Restriction (23) */
  3492   3495     }
  3493   3496   
  3494   3497     /*
  3495   3498     ** If the subquery is the right operand of a LEFT JOIN, then the
  3496         -  ** subquery may not be a join itself.  Example of why this is not allowed:
         3499  +  ** subquery may not be a join itself (3a). Example of why this is not
         3500  +  ** allowed:
  3497   3501     **
  3498   3502     **         t1 LEFT OUTER JOIN (t2 JOIN t3)
  3499   3503     **
  3500   3504     ** If we flatten the above, we would get
  3501   3505     **
  3502   3506     **         (t1 LEFT OUTER JOIN t2) JOIN t3
  3503   3507     **
  3504   3508     ** which is not at all the same thing.
  3505   3509     **
  3506   3510     ** If the subquery is the right operand of a LEFT JOIN, then the outer
  3507         -  ** query cannot be an aggregate.  This is an artifact of the way aggregates
  3508         -  ** are processed - there is no mechanism to determine if the LEFT JOIN
  3509         -  ** table should be all-NULL.
         3511  +  ** query cannot be an aggregate. (3c)  This is an artifact of the way
         3512  +  ** aggregates are processed - there is no mechanism to determine if
         3513  +  ** the LEFT JOIN table should be all-NULL.
  3510   3514     **
  3511   3515     ** See also tickets #306, #350, and #3300.
  3512   3516     */
  3513   3517     if( (pSubitem->fg.jointype & JT_OUTER)!=0 ){
  3514   3518       isLeftJoin = 1;
  3515   3519       if( pSubSrc->nSrc>1 || isAgg || IsVirtual(pSubSrc->a[0].pTab) ){
  3516         -      return 0; /* Restriction (3) */
         3520  +      /*  (3a)             (3c)     (3b) */
         3521  +      return 0;
  3517   3522       }
  3518   3523     }
  3519   3524   #ifdef SQLITE_EXTRA_IFNULLROW
  3520   3525     else if( iFrom>0 && !isAgg ){
  3521   3526       /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
  3522   3527       ** every reference to any result column from subquery in a join, even
  3523   3528       ** though they are not necessary.  This will stress-test the OP_IfNullRow 
  3524   3529       ** opcode. */
  3525   3530       isLeftJoin = -1;
  3526   3531     }
  3527   3532   #endif
  3528   3533   
  3529         -  /* Restriction 17: If the sub-query is a compound SELECT, then it must
         3534  +  /* Restriction (17): If the sub-query is a compound SELECT, then it must
  3530   3535     ** use only the UNION ALL operator. And none of the simple select queries
  3531   3536     ** that make up the compound SELECT are allowed to be aggregate or distinct
  3532   3537     ** queries.
  3533   3538     */
  3534   3539     if( pSub->pPrior ){
  3535   3540       if( pSub->pOrderBy ){
  3536         -      return 0;  /* Restriction 20 */
         3541  +      return 0;  /* Restriction (20) */
  3537   3542       }
  3538   3543       if( isAgg || (p->selFlags & SF_Distinct)!=0 || pSrc->nSrc!=1 ){
  3539         -      return 0;
         3544  +      return 0; /* (17d1), (17d2), or (17d3) */
  3540   3545       }
  3541   3546       for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
  3542   3547         testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
  3543   3548         testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
  3544   3549         assert( pSub->pSrc!=0 );
  3545   3550         assert( pSub->pEList->nExpr==pSub1->pEList->nExpr );
  3546         -      if( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))!=0
  3547         -       || (pSub1->pPrior && pSub1->op!=TK_ALL) 
  3548         -       || pSub1->pSrc->nSrc<1
         3551  +      if( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))!=0    /* (17b) */
         3552  +       || (pSub1->pPrior && pSub1->op!=TK_ALL)                 /* (17a) */
         3553  +       || pSub1->pSrc->nSrc<1                                  /* (17c) */
  3549   3554         ){
  3550   3555           return 0;
  3551   3556         }
  3552   3557         testcase( pSub1->pSrc->nSrc>1 );
  3553   3558       }
  3554   3559   
  3555         -    /* Restriction 18. */
         3560  +    /* Restriction (18). */
  3556   3561       if( p->pOrderBy ){
  3557   3562         int ii;
  3558   3563         for(ii=0; ii<p->pOrderBy->nExpr; ii++){
  3559   3564           if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;
  3560   3565         }
  3561   3566       }
  3562   3567     }