/ Check-in [8dc5c76c]
Login

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

Overview
Comment:Rework the logic that factors constant expressions out of inner loops, making it both simpler and faster.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | expr-codegen-enhancement
Files: files | file ages | folders
SHA1: 8dc5c76c766828d7c28090bec30ff48227e7b140
User & Date: drh 2013-11-15 01:10:18
Context
2013-11-15
03:30
Merge EXPLAIN fixes from trunk. check-in: cd579727 user: drh tags: expr-codegen-enhancement
01:10
Rework the logic that factors constant expressions out of inner loops, making it both simpler and faster. check-in: 8dc5c76c user: drh tags: expr-codegen-enhancement
2013-11-14
23:59
Adjust the command-line shell EXPLAIN indentation logic to handle the second loop of an UPDATE that reads out a RowSet. check-in: ea141a9b user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/backup.c.

    92     92       }else{
    93     93         pParse->db = pDb;
    94     94         if( sqlite3OpenTempDatabase(pParse) ){
    95     95           sqlite3Error(pErrorDb, pParse->rc, "%s", pParse->zErrMsg);
    96     96           rc = SQLITE_ERROR;
    97     97         }
    98     98         sqlite3DbFree(pErrorDb, pParse->zErrMsg);
           99  +      sqlite3ParserReset(pParse);
    99    100         sqlite3StackFree(pErrorDb, pParse);
   100    101       }
   101    102       if( rc ){
   102    103         return 0;
   103    104       }
   104    105     }
   105    106   

Changes to src/build.c.

   146    146       ** (Bit 0 is for main, bit 1 is for temp, and so forth.)  Bits are
   147    147       ** set for each database that is used.  Generate code to start a
   148    148       ** transaction on each used database and to verify the schema cookie
   149    149       ** on each used database.
   150    150       */
   151    151       if( pParse->cookieGoto>0 ){
   152    152         yDbMask mask;
   153         -      int iDb;
          153  +      int iDb, i, addr;
   154    154         sqlite3VdbeJumpHere(v, pParse->cookieGoto-1);
   155    155         for(iDb=0, mask=1; iDb<db->nDb; mask<<=1, iDb++){
   156    156           if( (mask & pParse->cookieMask)==0 ) continue;
   157    157           sqlite3VdbeUsesBtree(v, iDb);
   158    158           sqlite3VdbeAddOp2(v,OP_Transaction, iDb, (mask & pParse->writeMask)!=0);
   159    159           if( db->init.busy==0 ){
   160    160             assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
   161    161             sqlite3VdbeAddOp3(v, OP_VerifyCookie,
   162    162                               iDb, pParse->cookieValue[iDb],
   163    163                               db->aDb[iDb].pSchema->iGeneration);
   164    164           }
   165    165         }
   166    166   #ifndef SQLITE_OMIT_VIRTUALTABLE
   167         -      {
   168         -        int i;
   169         -        for(i=0; i<pParse->nVtabLock; i++){
   170         -          char *vtab = (char *)sqlite3GetVTable(db, pParse->apVtabLock[i]);
   171         -          sqlite3VdbeAddOp4(v, OP_VBegin, 0, 0, 0, vtab, P4_VTAB);
   172         -        }
   173         -        pParse->nVtabLock = 0;
          167  +      for(i=0; i<pParse->nVtabLock; i++){
          168  +        char *vtab = (char *)sqlite3GetVTable(db, pParse->apVtabLock[i]);
          169  +        sqlite3VdbeAddOp4(v, OP_VBegin, 0, 0, 0, vtab, P4_VTAB);
   174    170         }
          171  +      pParse->nVtabLock = 0;
   175    172   #endif
   176    173   
   177    174         /* Once all the cookies have been verified and transactions opened, 
   178    175         ** obtain the required table-locks. This is a no-op unless the 
   179    176         ** shared-cache feature is enabled.
   180    177         */
   181    178         codeTableLocks(pParse);
   182    179   
   183    180         /* Initialize any AUTOINCREMENT data structures required.
   184    181         */
   185    182         sqlite3AutoincrementBegin(pParse);
          183  +
          184  +      /* Code constant expressions that where factored out of inner loops */
          185  +      addr = pParse->cookieGoto;
          186  +      if( pParse->pConstExpr ){
          187  +        ExprList *pEL = pParse->pConstExpr;
          188  +        pParse->cookieGoto = 0;
          189  +        for(i=0; i<pEL->nExpr; i++){
          190  +          sqlite3ExprCode(pParse, pEL->a[i].pExpr, pEL->a[i].iAlias);
          191  +        }
          192  +      }
   186    193   
   187    194         /* Finally, jump back to the beginning of the executable code. */
   188         -      sqlite3VdbeAddOp2(v, OP_Goto, 0, pParse->cookieGoto);
          195  +      sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
   189    196       }
   190    197     }
   191    198   
   192    199   
   193    200     /* Get the VDBE program ready for execution
   194    201     */
   195    202     if( v && ALWAYS(pParse->nErr==0) && !db->mallocFailed ){

Changes to src/expr.c.

  2985   2985   ** Generate code to evaluate an expression and store the results
  2986   2986   ** into a register.  Return the register number where the results
  2987   2987   ** are stored.
  2988   2988   **
  2989   2989   ** If the register is a temporary register that can be deallocated,
  2990   2990   ** then write its number into *pReg.  If the result register is not
  2991   2991   ** a temporary, then set *pReg to zero.
         2992  +**
         2993  +** If pExpr is a constant, then this routine might generate this
         2994  +** code to fill the register in the initialization section of the
         2995  +** VDBE program, in order to factor it out of the evaluation loop.
  2992   2996   */
  2993   2997   int sqlite3ExprCodeTemp(Parse *pParse, Expr *pExpr, int *pReg){
  2994         -  int r1 = sqlite3GetTempReg(pParse);
  2995         -  int r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
  2996         -  if( r2==r1 ){
  2997         -    *pReg = r1;
         2998  +  int r2;
         2999  +  pExpr = sqlite3ExprSkipCollate(pExpr);
         3000  +  if( pParse->cookieGoto>0
         3001  +   && pParse->nMem<32768
         3002  +   && pExpr->op!=TK_REGISTER
         3003  +   && sqlite3ExprIsConstantNotJoin(pExpr)
         3004  +  ){
         3005  +    ExprList *p = pParse->pConstExpr;
         3006  +    int i;
         3007  +    *pReg  = 0;
         3008  +    if( p ){
         3009  +      for(i=0; i<p->nExpr; i++){
         3010  +        if( sqlite3ExprCompare(p->a[i].pExpr, pExpr, -1)==0 ){
         3011  +          return p->a[i].iAlias;
         3012  +        }
         3013  +      }
         3014  +    }
         3015  +    p = sqlite3ExprListAppend(pParse, p, sqlite3ExprDup(pParse->db, pExpr, 0));
         3016  +    pParse->pConstExpr = p;
         3017  +    r2 = ++pParse->nMem;
         3018  +    if( p ) p->a[p->nExpr-1].iAlias = r2;
  2998   3019     }else{
  2999         -    sqlite3ReleaseTempReg(pParse, r1);
  3000         -    *pReg = 0;
         3020  +    int r1 = sqlite3GetTempReg(pParse);
         3021  +    r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
         3022  +    if( r2==r1 ){
         3023  +      *pReg = r1;
         3024  +    }else{
         3025  +      sqlite3ReleaseTempReg(pParse, r1);
         3026  +      *pReg = 0;
         3027  +    }
  3001   3028     }
  3002   3029     return r2;
  3003   3030   }
  3004   3031   
  3005   3032   /*
  3006   3033   ** Generate code that will evaluate expression pExpr and store the
  3007   3034   ** results in register target.  The results are guaranteed to appear
................................................................................
  3323   3350           sqlite3ExplainNL(pOut);
  3324   3351         }
  3325   3352       }
  3326   3353       sqlite3ExplainPop(pOut);
  3327   3354     }
  3328   3355   }
  3329   3356   #endif /* SQLITE_DEBUG */
  3330         -
  3331         -/*
  3332         -** Return TRUE if pExpr is an constant expression that is appropriate
  3333         -** for factoring out of a loop.  Appropriate expressions are:
  3334         -**
  3335         -**    *  Any expression that evaluates to two or more opcodes.
  3336         -**
  3337         -**    *  Any OP_Integer, OP_Real, OP_String, OP_Blob, OP_Null, 
  3338         -**       or OP_Variable that does not need to be placed in a 
  3339         -**       specific register.
  3340         -**
  3341         -** There is no point in factoring out single-instruction constant
  3342         -** expressions that need to be placed in a particular register.  
  3343         -** We could factor them out, but then we would end up adding an
  3344         -** OP_SCopy instruction to move the value into the correct register
  3345         -** later.  We might as well just use the original instruction and
  3346         -** avoid the OP_SCopy.
  3347         -*/
  3348         -static int isAppropriateForFactoring(Expr *p){
  3349         -  if( !sqlite3ExprIsConstantNotJoin(p) ){
  3350         -    return 0;  /* Only constant expressions are appropriate for factoring */
  3351         -  }
  3352         -  if( (p->flags & EP_FixedDest)==0 ){
  3353         -    return 1;  /* Any constant without a fixed destination is appropriate */
  3354         -  }
  3355         -  while( p->op==TK_UPLUS ) p = p->pLeft;
  3356         -  switch( p->op ){
  3357         -#ifndef SQLITE_OMIT_BLOB_LITERAL
  3358         -    case TK_BLOB:
  3359         -#endif
  3360         -    case TK_VARIABLE:
  3361         -    case TK_INTEGER:
  3362         -    case TK_FLOAT:
  3363         -    case TK_NULL:
  3364         -    case TK_STRING: {
  3365         -      testcase( p->op==TK_BLOB );
  3366         -      testcase( p->op==TK_VARIABLE );
  3367         -      testcase( p->op==TK_INTEGER );
  3368         -      testcase( p->op==TK_FLOAT );
  3369         -      testcase( p->op==TK_NULL );
  3370         -      testcase( p->op==TK_STRING );
  3371         -      /* Single-instruction constants with a fixed destination are
  3372         -      ** better done in-line.  If we factor them, they will just end
  3373         -      ** up generating an OP_SCopy to move the value to the destination
  3374         -      ** register. */
  3375         -      return 0;
  3376         -    }
  3377         -    case TK_UMINUS: {
  3378         -      if( p->pLeft->op==TK_FLOAT || p->pLeft->op==TK_INTEGER ){
  3379         -        return 0;
  3380         -      }
  3381         -      break;
  3382         -    }
  3383         -    default: {
  3384         -      break;
  3385         -    }
  3386         -  }
  3387         -  return 1;
  3388         -}
  3389         -
  3390         -/*
  3391         -** If pExpr is a constant expression that is appropriate for
  3392         -** factoring out of a loop, then evaluate the expression
  3393         -** into a register and convert the expression into a TK_REGISTER
  3394         -** expression.
  3395         -*/
  3396         -static int evalConstExpr(Walker *pWalker, Expr *pExpr){
  3397         -  Parse *pParse = pWalker->pParse;
  3398         -  switch( pExpr->op ){
  3399         -    case TK_IN:
  3400         -    case TK_REGISTER: {
  3401         -      return WRC_Prune;
  3402         -    }
  3403         -    case TK_COLLATE: {
  3404         -      return WRC_Continue;
  3405         -    }
  3406         -    case TK_FUNCTION:
  3407         -    case TK_AGG_FUNCTION:
  3408         -    case TK_CONST_FUNC: {
  3409         -      /* The arguments to a function have a fixed destination.
  3410         -      ** Mark them this way to avoid generated unneeded OP_SCopy
  3411         -      ** instructions. 
  3412         -      */
  3413         -      ExprList *pList = pExpr->x.pList;
  3414         -      assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
  3415         -      if( pList ){
  3416         -        int i = pList->nExpr;
  3417         -        struct ExprList_item *pItem = pList->a;
  3418         -        for(; i>0; i--, pItem++){
  3419         -          if( ALWAYS(pItem->pExpr) ) pItem->pExpr->flags |= EP_FixedDest;
  3420         -        }
  3421         -      }
  3422         -      break;
  3423         -    }
  3424         -  }
  3425         -  if( isAppropriateForFactoring(pExpr) ){
  3426         -    int r1 = ++pParse->nMem;
  3427         -    int r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
  3428         -    /* If r2!=r1, it means that register r1 is never used.  That is harmless
  3429         -    ** but suboptimal, so we want to know about the situation to fix it.
  3430         -    ** Hence the following assert: */
  3431         -    assert( r2==r1 );
  3432         -    exprToRegister(pExpr, r2);
  3433         -    return WRC_Prune;
  3434         -  }
  3435         -  return WRC_Continue;
  3436         -}
  3437         -
  3438         -/*
  3439         -** Preevaluate constant subexpressions within pExpr and store the
  3440         -** results in registers.  Modify pExpr so that the constant subexpresions
  3441         -** are TK_REGISTER opcodes that refer to the precomputed values.
  3442         -**
  3443         -** This routine is a no-op if the jump to the cookie-check code has
  3444         -** already occur.  Since the cookie-check jump is generated prior to
  3445         -** any other serious processing, this check ensures that there is no
  3446         -** way to accidently bypass the constant initializations.
  3447         -**
  3448         -** This routine is also a no-op if the SQLITE_FactorOutConst optimization
  3449         -** is disabled via the sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS)
  3450         -** interface.  This allows test logic to verify that the same answer is
  3451         -** obtained for queries regardless of whether or not constants are
  3452         -** precomputed into registers or if they are inserted in-line.
  3453         -*/
  3454         -void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
  3455         -  Walker w;
  3456         -  if( pParse->cookieGoto ) return;
  3457         -  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;
  3458         -  memset(&w, 0, sizeof(w));
  3459         -  w.xExprCallback = evalConstExpr;
  3460         -  w.pParse = pParse;
  3461         -  sqlite3WalkExpr(&w, pExpr);
  3462         -}
  3463         -
  3464   3357   
  3465   3358   /*
  3466   3359   ** Generate code that pushes the value of every element of the given
  3467   3360   ** expression list into a sequence of registers beginning at target.
  3468   3361   **
  3469   3362   ** Return the number of elements evaluated.
  3470   3363   */
................................................................................
  3859   3752     }
  3860   3753     if( sqlite3ExprCompare(pA->pLeft, pB->pLeft, iTab) ) return 2;
  3861   3754     if( sqlite3ExprCompare(pA->pRight, pB->pRight, iTab) ) return 2;
  3862   3755     if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2;
  3863   3756     if( pA->iColumn!=pB->iColumn ) return 2;
  3864   3757     if( pA->iTable!=pB->iTable 
  3865   3758      && pA->op!=TK_REGISTER
  3866         -   && (pA->iTable!=iTab || NEVER(pB->iTable>=0)) ) return 2;
         3759  +   && (pA->iTable!=iTab || pB->iTable>=0) ) return 2;
  3867   3760     if( ExprHasProperty(pA, EP_IntValue) ){
  3868   3761       if( !ExprHasProperty(pB, EP_IntValue) || pA->u.iValue!=pB->u.iValue ){
  3869   3762         return 2;
  3870   3763       }
  3871   3764     }else if( pA->op!=TK_COLUMN && ALWAYS(pA->op!=TK_AGG_COLUMN) && pA->u.zToken){
  3872   3765       if( ExprHasProperty(pB, EP_IntValue) || NEVER(pB->u.zToken==0) ) return 2;
  3873   3766       if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){

Changes to src/prepare.c.

   519    519           break;
   520    520         }
   521    521       }
   522    522       assert( i>=0 && i<db->nDb );
   523    523     }
   524    524     return i;
   525    525   }
          526  +
          527  +/*
          528  +** Free all memory allocations in the pParse object
          529  +*/
          530  +void sqlite3ParserReset(Parse *pParse){
          531  +  if( pParse ) sqlite3ExprListDelete(pParse->db, pParse->pConstExpr);
          532  +}
   526    533   
   527    534   /*
   528    535   ** Compile the UTF-8 encoded SQL statement zSql into a statement handle.
   529    536   */
   530    537   static int sqlite3Prepare(
   531    538     sqlite3 *db,              /* Database handle. */
   532    539     const char *zSql,         /* UTF-8 encoded SQL statement. */
................................................................................
   677    684       TriggerPrg *pT = pParse->pTriggerPrg;
   678    685       pParse->pTriggerPrg = pT->pNext;
   679    686       sqlite3DbFree(db, pT);
   680    687     }
   681    688   
   682    689   end_prepare:
   683    690   
          691  +  sqlite3ParserReset(pParse);
   684    692     sqlite3StackFree(db, pParse);
   685    693     rc = sqlite3ApiExit(db, rc);
   686    694     assert( (rc&db->errMask)==rc );
   687    695     return rc;
   688    696   }
   689    697   static int sqlite3LockAndPrepare(
   690    698     sqlite3 *db,              /* Database handle. */

Changes to src/sqliteInt.h.

  2274   2274       int iTable;           /* Table cursor number */
  2275   2275       int iColumn;          /* Table column number */
  2276   2276       u8 tempReg;           /* iReg is a temp register that needs to be freed */
  2277   2277       int iLevel;           /* Nesting level */
  2278   2278       int iReg;             /* Reg with value of this column. 0 means none. */
  2279   2279       int lru;              /* Least recently used entry has the smallest value */
  2280   2280     } aColCache[SQLITE_N_COLCACHE];  /* One for each column cache entry */
         2281  +  ExprList *pConstExpr;/* Constant expressions */
  2281   2282     yDbMask writeMask;   /* Start a write transaction on these databases */
  2282   2283     yDbMask cookieMask;  /* Bitmask of schema verified databases */
  2283   2284     int cookieGoto;      /* Address of OP_Goto to cookie verifier subroutine */
  2284   2285     int cookieValue[SQLITE_MAX_ATTACHED+2];  /* Values of cookies to verify */
  2285   2286     int regRowid;        /* Register holding rowid of CREATE TABLE entry */
  2286   2287     int regRoot;         /* Register holding root page number for new objects */
  2287   2288     int nMaxArg;         /* Max args passed to user function by sub-program */
................................................................................
  2887   2888   void sqlite3ExprCacheRemove(Parse*, int, int);
  2888   2889   void sqlite3ExprCacheClear(Parse*);
  2889   2890   void sqlite3ExprCacheAffinityChange(Parse*, int, int);
  2890   2891   int sqlite3ExprCode(Parse*, Expr*, int);
  2891   2892   int sqlite3ExprCodeTemp(Parse*, Expr*, int*);
  2892   2893   int sqlite3ExprCodeTarget(Parse*, Expr*, int);
  2893   2894   int sqlite3ExprCodeAndCache(Parse*, Expr*, int);
  2894         -void sqlite3ExprCodeConstants(Parse*, Expr*);
  2895   2895   int sqlite3ExprCodeExprList(Parse*, ExprList*, int, int);
  2896   2896   void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
  2897   2897   void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
  2898   2898   Table *sqlite3FindTable(sqlite3*,const char*, const char*);
  2899   2899   Table *sqlite3LocateTable(Parse*,int isView,const char*, const char*);
  2900   2900   Table *sqlite3LocateTableItem(Parse*,int isView,struct SrcList_item *);
  2901   2901   Index *sqlite3FindIndex(sqlite3*,const char*, const char*);
................................................................................
  3255   3255   int sqlite3VtabCallDestroy(sqlite3*, int, const char *);
  3256   3256   int sqlite3VtabBegin(sqlite3 *, VTable *);
  3257   3257   FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*);
  3258   3258   void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
  3259   3259   sqlite3_int64 sqlite3StmtCurrentTime(sqlite3_context*);
  3260   3260   int sqlite3VdbeParameterIndex(Vdbe*, const char*, int);
  3261   3261   int sqlite3TransferBindings(sqlite3_stmt *, sqlite3_stmt *);
         3262  +void sqlite3ParserReset(Parse*);
  3262   3263   int sqlite3Reprepare(Vdbe*);
  3263   3264   void sqlite3ExprListCheckLength(Parse*, ExprList*, const char*);
  3264   3265   CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *);
  3265   3266   int sqlite3TempInMemory(const sqlite3*);
  3266   3267   const char *sqlite3JournalModename(int);
  3267   3268   #ifndef SQLITE_OMIT_WAL
  3268   3269     int sqlite3Checkpoint(sqlite3*, int, int, int*, int*);

Changes to src/trigger.c.

   920    920       pPrg->aColmask[0] = pSubParse->oldmask;
   921    921       pPrg->aColmask[1] = pSubParse->newmask;
   922    922       sqlite3VdbeDelete(v);
   923    923     }
   924    924   
   925    925     assert( !pSubParse->pAinc       && !pSubParse->pZombieTab );
   926    926     assert( !pSubParse->pTriggerPrg && !pSubParse->nMaxArg );
          927  +  sqlite3ParserReset(pSubParse);
   927    928     sqlite3StackFree(db, pSubParse);
   928    929   
   929    930     return pPrg;
   930    931   }
   931    932       
   932    933   /*
   933    934   ** Return a pointer to a TriggerPrg object containing the sub-program for

Changes to src/vdbeblob.c.

   324    324       *ppBlob = (sqlite3_blob *)pBlob;
   325    325     }else{
   326    326       if( pBlob && pBlob->pStmt ) sqlite3VdbeFinalize((Vdbe *)pBlob->pStmt);
   327    327       sqlite3DbFree(db, pBlob);
   328    328     }
   329    329     sqlite3Error(db, rc, (zErr ? "%s" : 0), zErr);
   330    330     sqlite3DbFree(db, zErr);
          331  +  sqlite3ParserReset(pParse);
   331    332     sqlite3StackFree(db, pParse);
   332    333     rc = sqlite3ApiExit(db, rc);
   333    334     sqlite3_mutex_leave(db->mutex);
   334    335     return rc;
   335    336   }
   336    337   
   337    338   /*

Changes to src/vtab.c.

   734    734       }
   735    735       pParse->declareVtab = 0;
   736    736     
   737    737       if( pParse->pVdbe ){
   738    738         sqlite3VdbeFinalize(pParse->pVdbe);
   739    739       }
   740    740       sqlite3DeleteTable(db, pParse->pNewTable);
          741  +    sqlite3ParserReset(pParse);
   741    742       sqlite3StackFree(db, pParse);
   742    743     }
   743    744   
   744    745     assert( (rc&0xff)==rc );
   745    746     rc = sqlite3ApiExit(db, rc);
   746    747     sqlite3_mutex_leave(db->mutex);
   747    748     return rc;

Changes to src/where.c.

  5422   5422   #endif
  5423   5423   
  5424   5424     /* Split the WHERE clause into separate subexpressions where each
  5425   5425     ** subexpression is separated by an AND operator.
  5426   5426     */
  5427   5427     initMaskSet(pMaskSet);
  5428   5428     whereClauseInit(&pWInfo->sWC, pWInfo);
  5429         -  sqlite3ExprCodeConstants(pParse, pWhere);
  5430   5429     whereSplit(&pWInfo->sWC, pWhere, TK_AND);
  5431   5430     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  5432   5431       
  5433   5432     /* Special case: a WHERE clause that is constant.  Evaluate the
  5434   5433     ** expression and either jump over all of the code or fall thru.
  5435   5434     */
  5436   5435     if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){