/ Check-in [d17ef7d1]
Login

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

Overview
Comment:Reactivate query flattening when the result set of the outer query has no function calls or subqueries. This is a partial reversal of check-in [c9104b59]. Co-routines are still preferred if the outer query has a complex result set, but for simple results sets, query flattening is used. Check-in [4464f40ccd7] is completely backed out due to this change.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: d17ef7d153058f7332b3fec421ade42c67e26b06f36fc1629e6799537a5afc5f
User & Date: drh 2017-10-28 20:51:54
Context
2017-10-28
20:54
Increase the version number for the next release - which is still months away but there have been significant query planner enhancements since the previous release. check-in: 457eedfa user: drh tags: trunk
20:51
Reactivate query flattening when the result set of the outer query has no function calls or subqueries. This is a partial reversal of check-in [c9104b59]. Co-routines are still preferred if the outer query has a complex result set, but for simple results sets, query flattening is used. Check-in [4464f40ccd7] is completely backed out due to this change. check-in: d17ef7d1 user: drh tags: trunk
12:20
Add test cases from OSSFuzz to prevent a regression in co-routine processing. check-in: 689743d8 user: drh tags: trunk
2017-10-04
12:06
Turn restriction 20 on the query flattener into an assert since the situation restricted can no longer occur because of the more aggressive use of co-routines. check-in: 4464f40c user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

   948    948     assert( pToken );
   949    949     pNew = sqlite3ExprAlloc(db, TK_FUNCTION, pToken, 1);
   950    950     if( pNew==0 ){
   951    951       sqlite3ExprListDelete(db, pList); /* Avoid memory leak when malloc fails */
   952    952       return 0;
   953    953     }
   954    954     pNew->x.pList = pList;
          955  +  ExprSetProperty(pNew, EP_HasFunc);
   955    956     assert( !ExprHasProperty(pNew, EP_xIsSelect) );
   956    957     sqlite3ExprSetHeightAndFlags(pParse, pNew);
   957    958     return pNew;
   958    959   }
   959    960   
   960    961   /*
   961    962   ** Assign a variable number to an expression that encodes a wildcard

Changes to src/select.c.

  3379   3379   **  (18)  If the sub-query is a compound select, then all terms of the
  3380   3380   **        ORDER BY clause of the parent must be simple references to 
  3381   3381   **        columns of the sub-query.
  3382   3382   **
  3383   3383   **  (19)  If the subquery uses LIMIT then the outer query may not
  3384   3384   **        have a WHERE clause.
  3385   3385   **
  3386         -**  (**)  Subsumed into (17d3).  Was: If the sub-query is a compound select,
  3387         -**        then it must not use an ORDER BY clause - Ticket #3773.  Because
  3388         -**        of (17d3), then only way to have a compound subquery is if it is
  3389         -**        the only term in the FROM clause of the outer query.  But if the
  3390         -**        only term in the FROM clause has an ORDER BY, then it will be
  3391         -**        implemented as a co-routine and the flattener will never be called.
         3386  +**  (20)  If the sub-query is a compound select, then it must not use
         3387  +**        an ORDER BY clause.  Ticket #3773.  We could relax this constraint
         3388  +**        somewhat by saying that the terms of the ORDER BY clause must
         3389  +**        appear as unmodified result columns in the outer query.  But we
         3390  +**        have other optimizations in mind to deal with that case.
  3392   3391   **
  3393   3392   **  (21)  If the subquery uses LIMIT then the outer query may not be
  3394   3393   **        DISTINCT.  (See ticket [752e1646fc]).
  3395   3394   **
  3396   3395   **  (22)  The subquery may not be a recursive CTE.
  3397   3396   **
  3398   3397   **  (**)  Subsumed into restriction (17d3).  Was: If the outer query is
................................................................................
  3518   3517   
  3519   3518     /* Restriction (17): If the sub-query is a compound SELECT, then it must
  3520   3519     ** use only the UNION ALL operator. And none of the simple select queries
  3521   3520     ** that make up the compound SELECT are allowed to be aggregate or distinct
  3522   3521     ** queries.
  3523   3522     */
  3524   3523     if( pSub->pPrior ){
         3524  +    if( pSub->pOrderBy ){
         3525  +      return 0;  /* Restriction (20) */
         3526  +    }
  3525   3527       if( isAgg || (p->selFlags & SF_Distinct)!=0 || pSrc->nSrc!=1 ){
  3526   3528         return 0; /* (17d1), (17d2), or (17d3) */
  3527   3529       }
  3528   3530       for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
  3529   3531         testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
  3530   3532         testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
  3531   3533         assert( pSub->pSrc!=0 );
................................................................................
  3552   3554     ** The only way that the recursive part of a CTE can contain a compound
  3553   3555     ** subquery is for the subquery to be one term of a join.  But if the
  3554   3556     ** subquery is a join, then the flattening has already been stopped by
  3555   3557     ** restriction (17d3)
  3556   3558     */
  3557   3559     assert( (p->selFlags & SF_Recursive)==0 || pSub->pPrior==0 );
  3558   3560   
  3559         -  /* Ex-restriction (20):
  3560         -  ** A compound subquery must be the only term in the FROM clause of the
  3561         -  ** outer query by restriction (17d3).  But if that term also has an
  3562         -  ** ORDER BY clause, then the subquery will be implemented by co-routine
  3563         -  ** and so the flattener will never be invoked.  Hence, it is not possible
  3564         -  ** for the subquery to be a compound and have an ORDER BY clause.
  3565         -  */
  3566         -  assert( pSub->pPrior==0 || pSub->pOrderBy==0 );
  3567         -
  3568   3561     /***** If we reach this point, flattening is permitted. *****/
  3569   3562     SELECTTRACE(1,pParse,p,("flatten %s.%p from term %d\n",
  3570   3563                      pSub->zSelName, pSub, iFrom));
  3571   3564   
  3572   3565     /* Authorize the subquery */
  3573   3566     pParse->zAuthContext = pSubitem->zName;
  3574   3567     TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);
................................................................................
  4339   4332     int i, j, k;
  4340   4333     SrcList *pTabList;
  4341   4334     ExprList *pEList;
  4342   4335     struct SrcList_item *pFrom;
  4343   4336     sqlite3 *db = pParse->db;
  4344   4337     Expr *pE, *pRight, *pExpr;
  4345   4338     u16 selFlags = p->selFlags;
         4339  +  u32 elistFlags = 0;
  4346   4340   
  4347   4341     p->selFlags |= SF_Expanded;
  4348   4342     if( db->mallocFailed  ){
  4349   4343       return WRC_Abort;
  4350   4344     }
  4351   4345     if( NEVER(p->pSrc==0) || (selFlags & SF_Expanded)!=0 ){
  4352   4346       return WRC_Prune;
................................................................................
  4451   4445     */
  4452   4446     for(k=0; k<pEList->nExpr; k++){
  4453   4447       pE = pEList->a[k].pExpr;
  4454   4448       if( pE->op==TK_ASTERISK ) break;
  4455   4449       assert( pE->op!=TK_DOT || pE->pRight!=0 );
  4456   4450       assert( pE->op!=TK_DOT || (pE->pLeft!=0 && pE->pLeft->op==TK_ID) );
  4457   4451       if( pE->op==TK_DOT && pE->pRight->op==TK_ASTERISK ) break;
         4452  +    elistFlags |= pE->flags;
  4458   4453     }
  4459   4454     if( k<pEList->nExpr ){
  4460   4455       /*
  4461   4456       ** If we get here it means the result set contains one or more "*"
  4462   4457       ** operators that need to be expanded.  Loop through each expression
  4463   4458       ** in the result set and expand them one by one.
  4464   4459       */
................................................................................
  4466   4461       ExprList *pNew = 0;
  4467   4462       int flags = pParse->db->flags;
  4468   4463       int longNames = (flags & SQLITE_FullColNames)!=0
  4469   4464                         && (flags & SQLITE_ShortColNames)==0;
  4470   4465   
  4471   4466       for(k=0; k<pEList->nExpr; k++){
  4472   4467         pE = a[k].pExpr;
         4468  +      elistFlags |= pE->flags;
  4473   4469         pRight = pE->pRight;
  4474   4470         assert( pE->op!=TK_DOT || pRight!=0 );
  4475   4471         if( pE->op!=TK_ASTERISK
  4476   4472          && (pE->op!=TK_DOT || pRight->op!=TK_ASTERISK)
  4477   4473         ){
  4478   4474           /* This particular expression does not need to be expanded.
  4479   4475           */
................................................................................
  4595   4591             }
  4596   4592           }
  4597   4593         }
  4598   4594       }
  4599   4595       sqlite3ExprListDelete(db, pEList);
  4600   4596       p->pEList = pNew;
  4601   4597     }
  4602         -  if( p->pEList && p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
  4603         -    sqlite3ErrorMsg(pParse, "too many columns in result set");
  4604         -    return WRC_Abort;
         4598  +  if( p->pEList ){
         4599  +    if( p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
         4600  +      sqlite3ErrorMsg(pParse, "too many columns in result set");
         4601  +      return WRC_Abort;
         4602  +    }
         4603  +    if( (elistFlags & (EP_HasFunc|EP_Subquery))!=0 ){
         4604  +      p->selFlags |= SF_ComplexResult;
         4605  +    }
  4605   4606     }
  4606   4607     return WRC_Continue;
  4607   4608   }
  4608   4609   
  4609   4610   /*
  4610   4611   ** No-op routine for the parse-tree walker.
  4611   4612   **
................................................................................
  5221   5222       ** is not a join.  But if the outer query is not a join, then the subquery
  5222   5223       ** will be implemented as a co-routine and there is no advantage to
  5223   5224       ** flattening in that case.
  5224   5225       */
  5225   5226       if( (pSub->selFlags & SF_Aggregate)!=0 ) continue;
  5226   5227       assert( pSub->pGroupBy==0 );
  5227   5228   
  5228         -    /* If the subquery contains an ORDER BY clause and if
         5229  +    /* If the outer query contains a "complex" result set (that is,
         5230  +    ** if the result set of the outer query uses functions or subqueries)
         5231  +    ** and if the subquery contains an ORDER BY clause and if
  5229   5232       ** it will be implemented as a co-routine, then do not flatten.  This
  5230   5233       ** restriction allows SQL constructs like this:
  5231   5234       **
  5232   5235       **  SELECT expensive_function(x)
  5233   5236       **    FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
  5234   5237       **
  5235   5238       ** The expensive_function() is only computed on the 10 rows that
  5236   5239       ** are output, rather than every row of the table.
         5240  +    **
         5241  +    ** The requirement that the outer query have a complex result set
         5242  +    ** means that flattening does occur on simpler SQL constraints without
         5243  +    ** the expensive_function() like:
         5244  +    **
         5245  +    **  SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
  5237   5246       */
  5238   5247       if( pSub->pOrderBy!=0
  5239   5248        && i==0
         5249  +     && (p->selFlags & SF_ComplexResult)!=0
  5240   5250        && (pTabList->nSrc==1
  5241   5251            || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)
  5242   5252       ){
  5243   5253         continue;
  5244   5254       }
  5245   5255   
  5246   5256       if( flattenSubquery(pParse, p, i, isAgg) ){

Changes to src/sqliteInt.h.

  2398   2398   };
  2399   2399   
  2400   2400   /*
  2401   2401   ** The following are the meanings of bits in the Expr.flags field.
  2402   2402   */
  2403   2403   #define EP_FromJoin  0x000001 /* Originates in ON/USING clause of outer join */
  2404   2404   #define EP_Agg       0x000002 /* Contains one or more aggregate functions */
  2405         -                  /* 0x000004 // available for use */
         2405  +#define EP_HasFunc   0x000004 /* Contains one or more functions of any kind */
  2406   2406                     /* 0x000008 // available for use */
  2407   2407   #define EP_Distinct  0x000010 /* Aggregate function with DISTINCT keyword */
  2408   2408   #define EP_VarSelect 0x000020 /* pSelect is correlated, not constant */
  2409   2409   #define EP_DblQuoted 0x000040 /* token.z was originally in "..." */
  2410   2410   #define EP_InfixFunc 0x000080 /* True for an infix function: LIKE, GLOB, etc */
  2411   2411   #define EP_Collate   0x000100 /* Tree contains a TK_COLLATE operator */
  2412   2412   #define EP_Generic   0x000200 /* Ignore COLLATE or affinity on this tree */
................................................................................
  2422   2422   #define EP_ConstFunc 0x080000 /* A SQLITE_FUNC_CONSTANT or _SLOCHNG function */
  2423   2423   #define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */
  2424   2424   #define EP_Subquery  0x200000 /* Tree contains a TK_SELECT operator */
  2425   2425   #define EP_Alias     0x400000 /* Is an alias for a result set column */
  2426   2426   #define EP_Leaf      0x800000 /* Expr.pLeft, .pRight, .u.pSelect all NULL */
  2427   2427   
  2428   2428   /*
  2429         -** Combinations of two or more EP_* flags
         2429  +** The EP_Propagate mask is a set of properties that automatically propagate
         2430  +** upwards into parent nodes.
  2430   2431   */
  2431         -#define EP_Propagate (EP_Collate|EP_Subquery) /* Propagate these bits up tree */
         2432  +#define EP_Propagate (EP_Collate|EP_Subquery|EP_HasFunc)
  2432   2433   
  2433   2434   /*
  2434   2435   ** These macros can be used to test, set, or clear bits in the
  2435   2436   ** Expr.flags field.
  2436   2437   */
  2437   2438   #define ExprHasProperty(E,P)     (((E)->flags&(P))!=0)
  2438   2439   #define ExprHasAllProperty(E,P)  (((E)->flags&(P))==(P))
................................................................................
  2704   2705   #define NC_PartIdx   0x0002  /* True if resolving a partial index WHERE */
  2705   2706   #define NC_IsCheck   0x0004  /* True if resolving names in a CHECK constraint */
  2706   2707   #define NC_InAggFunc 0x0008  /* True if analyzing arguments to an agg func */
  2707   2708   #define NC_HasAgg    0x0010  /* One or more aggregate functions seen */
  2708   2709   #define NC_IdxExpr   0x0020  /* True if resolving columns of CREATE INDEX */
  2709   2710   #define NC_VarSelect 0x0040  /* A correlated subquery has been seen */
  2710   2711   #define NC_MinMaxAgg 0x1000  /* min/max aggregates seen.  See note above */
         2712  +#define NC_Complex   0x2000  /* True if a function or subquery seen */
  2711   2713   
  2712   2714   /*
  2713   2715   ** An instance of the following structure contains all information
  2714   2716   ** needed to generate code for a single SELECT statement.
  2715   2717   **
  2716   2718   ** nLimit is set to -1 if there is no LIMIT clause.  nOffset is set to 0.
  2717   2719   ** If there is a LIMIT clause, the parser sets nLimit to the value of the
................................................................................
  2774   2776   #define SF_NestedFrom     0x00800  /* Part of a parenthesized FROM clause */
  2775   2777   #define SF_MinMaxAgg      0x01000  /* Aggregate containing min() or max() */
  2776   2778   #define SF_Recursive      0x02000  /* The recursive part of a recursive CTE */
  2777   2779   #define SF_FixedLimit     0x04000  /* nSelectRow set by a constant LIMIT */
  2778   2780   #define SF_MaybeConvert   0x08000  /* Need convertCompoundSelectToSubquery() */
  2779   2781   #define SF_Converted      0x10000  /* By convertCompoundSelectToSubquery() */
  2780   2782   #define SF_IncludeHidden  0x20000  /* Include hidden columns in output */
         2783  +#define SF_ComplexResult  0x40000  /* Result set contains subquery or function */
  2781   2784   
  2782   2785   
  2783   2786   /*
  2784   2787   ** The results of a SELECT can be distributed in several ways, as defined
  2785   2788   ** by one of the following macros.  The "SRT" prefix means "SELECT Result
  2786   2789   ** Type".
  2787   2790   **