/ Check-in [c1adf959]
Login

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

Overview
Comment:Add an optimization to OP_Column to speed up sequential OP_Column instructions that read earlier fields from the same cursor. Attempt to reorder OP_Column opcodes so as to take advantage of this.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | sort-column-opcodes
Files: files | file ages | folders
SHA1: c1adf95958d5210bf9f89fc86d0f6fc6ce32c480
User & Date: dan 2017-02-18 20:05:05
Context
2017-02-18
20:05
Add an optimization to OP_Column to speed up sequential OP_Column instructions that read earlier fields from the same cursor. Attempt to reorder OP_Column opcodes so as to take advantage of this. Leaf check-in: c1adf959 user: dan tags: sort-column-opcodes
13:47
Add the SQLITE_BUG_COMPATIBLE_20160819 compile-time option to omit the error message when an unrecognized argument is provided to the VACUUM command. check-in: 49181427 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  4147   4147     assert( target>0 );
  4148   4148     assert( pExpr->op!=TK_REGISTER );
  4149   4149     sqlite3ExprCode(pParse, pExpr, target);
  4150   4150     iMem = ++pParse->nMem;
  4151   4151     sqlite3VdbeAddOp2(v, OP_Copy, target, iMem);
  4152   4152     exprToRegister(pExpr, iMem);
  4153   4153   }
         4154  +
         4155  +/*
         4156  +** Return the value of (*p1) - (*p2), as defined by the sort order described
         4157  +** in the comment above reorderColumnFetch(). 
         4158  +*/
         4159  +static int compareOpCode(VdbeOp *p1, VdbeOp *p2){
         4160  +  int res;
         4161  +
         4162  +  assert( p1->opcode==OP_Column || p1->opcode==OP_VColumn
         4163  +       || p1->opcode==OP_Copy   || p1->opcode==OP_SCopy
         4164  +       || p1->opcode==OP_Rowid  || p1->opcode==OP_RealAffinity
         4165  +  );
         4166  +  assert( p2->opcode==OP_Column || p2->opcode==OP_VColumn
         4167  +       || p2->opcode==OP_Copy   || p2->opcode==OP_SCopy
         4168  +       || p2->opcode==OP_Rowid  || p2->opcode==OP_RealAffinity
         4169  +  );
         4170  +
         4171  +  assert( OP_VColumn>OP_Column && OP_Rowid>OP_Column );
         4172  +  assert( OP_Column>OP_RealAffinity );
         4173  +  assert( OP_RealAffinity>OP_Copy && OP_RealAffinity>OP_SCopy );
         4174  +
         4175  +  res = (int)(p2->opcode) - (int)(p1->opcode);
         4176  +  if( res==0 ){
         4177  +    res = p1->p1 - p2->p1;
         4178  +    if( res==0 ){
         4179  +      res = p2->p2 - p1->p2;
         4180  +    }
         4181  +  }
         4182  +  return res;
         4183  +}
         4184  +
         4185  +/*
         4186  +** The VM instructions from iFirst to the current address were generated
         4187  +** in order to populate an array of registers with the results of a series
         4188  +** of TK_COLUMN expressions. This guarantees that the specified range 
         4189  +** contains opcodes of the following types only:
         4190  +**
         4191  +**   Rowid
         4192  +**   Column
         4193  +**   VColumn
         4194  +**   RealAffinity
         4195  +**   Copy
         4196  +**   SCopy
         4197  +**
         4198  +** This function sorts the opcodes so all of the OP_Column appear in a
         4199  +** contiguous block, sorted by (p1, p2 DESC). The VDBE layer processes
         4200  +** OP_Column instructions in this order more efficiently.
         4201  +**
         4202  +** In practice, the array is sorted so that all instructions of each type 
         4203  +** of opcode are arranged into a contiguous group. Given the following,
         4204  +** this is a safe re-ordering:
         4205  +**
         4206  +**   * All Rowid, VColumn and Column instructions appear before all 
         4207  +**     RealAffinity instructions (that might operate on the result of
         4208  +**     a VColumn or Column), and
         4209  +**
         4210  +**   * All RealAffinity instructions occur before all Copy and SCopy
         4211  +**     instructions (which might read a column-cache entry populated
         4212  +**     by a prior Column+RealAffinity).
         4213  +*/
         4214  +static void reorderColumnFetch(sqlite3 *db, Vdbe *v, int iFirst){
         4215  +  int iEnd = sqlite3VdbeCurrentAddr(v);
         4216  +  int nOp = iEnd-iFirst;
         4217  +  if( nOp>1 ){
         4218  +    VdbeOp *aSpace = (VdbeOp*)sqlite3StackAllocRaw(db, sizeof(VdbeOp) * nOp);
         4219  +    if( aSpace ){
         4220  +      int sz;
         4221  +      VdbeOp *aOp = sqlite3VdbeGetOp(v, iFirst);
         4222  +      VdbeOp *a1 = aOp;
         4223  +      VdbeOp *a2 = aSpace;
         4224  +      for(sz=1; sz<nOp; sz=sz*2){
         4225  +        int i;
         4226  +        for(i=0; i<nOp; i+=(sz*2)){
         4227  +          /* Merge the two lists of sz elements each starting at a1[i] and 
         4228  +          ** a1[i+sz] into a sz element list at a2[i].  */
         4229  +          int e1 = MIN(i+sz, nOp);
         4230  +          int e2 = MIN(i+sz*2, nOp);
         4231  +          int i2 = i+sz;
         4232  +          int i1 = i;
         4233  +          int iOut = i;
         4234  +
         4235  +          while( i1<e1 || i2<e2 ){
         4236  +            if( i1>=e1 || (i2<e2 && compareOpCode(&a1[i2], &a1[i1])<0) ){
         4237  +              a2[iOut++] = a1[i2++];
         4238  +            }else{
         4239  +              a2[iOut++] = a1[i1++];
         4240  +            }
         4241  +          }
         4242  +        }
         4243  +        SWAP(VdbeOp*, a1, a2);
         4244  +      }
         4245  +      if( a1!=aOp ){
         4246  +        memcpy(aOp, a1, sizeof(VdbeOp)*nOp);
         4247  +      }
         4248  +      sqlite3StackFree(db, aSpace);
         4249  +    }
         4250  +  }
         4251  +}
  4154   4252   
  4155   4253   /*
  4156   4254   ** Generate code that pushes the value of every element of the given
  4157   4255   ** expression list into a sequence of registers beginning at target.
  4158   4256   **
  4159   4257   ** Return the number of elements evaluated.
  4160   4258   **
................................................................................
  4173   4271     ExprList *pList,   /* The expression list to be coded */
  4174   4272     int target,        /* Where to write results */
  4175   4273     int srcReg,        /* Source registers if SQLITE_ECEL_REF */
  4176   4274     u8 flags           /* SQLITE_ECEL_* flags */
  4177   4275   ){
  4178   4276     struct ExprList_item *pItem;
  4179   4277     int i, j, n;
         4278  +  int iFirst = -1;
  4180   4279     u8 copyOp = (flags & SQLITE_ECEL_DUP) ? OP_Copy : OP_SCopy;
  4181   4280     Vdbe *v = pParse->pVdbe;
  4182   4281     assert( pList!=0 );
  4183   4282     assert( target>0 );
  4184   4283     assert( pParse->pVdbe!=0 );  /* Never gets this far otherwise */
  4185   4284     n = pList->nExpr;
  4186   4285     if( !ConstFactorOk(pParse) ) flags &= ~SQLITE_ECEL_FACTOR;
  4187   4286     for(pItem=pList->a, i=0; i<n; i++, pItem++){
  4188   4287       Expr *pExpr = pItem->pExpr;
         4288  +    if( iFirst>0 ){
         4289  +      if( pExpr->op!=TK_COLUMN ){
         4290  +        reorderColumnFetch(pParse->db, v, iFirst);
         4291  +        iFirst = -1;
         4292  +      }
         4293  +    }else{
         4294  +      if( pExpr->op==TK_COLUMN ) iFirst = sqlite3VdbeCurrentAddr(v);
         4295  +    }
  4189   4296       if( (flags & SQLITE_ECEL_REF)!=0 && (j = pItem->u.x.iOrderByCol)>0 ){
  4190   4297         if( flags & SQLITE_ECEL_OMITREF ){
  4191   4298           i--;
  4192   4299           n--;
  4193   4300         }else{
  4194   4301           sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i);
  4195   4302         }
................................................................................
  4207   4314             pOp->p3++;
  4208   4315           }else{
  4209   4316             sqlite3VdbeAddOp2(v, copyOp, inReg, target+i);
  4210   4317           }
  4211   4318         }
  4212   4319       }
  4213   4320     }
         4321  +  if( iFirst>0 ) reorderColumnFetch(pParse->db, v, iFirst);
  4214   4322     return n;
  4215   4323   }
  4216   4324   
  4217   4325   /*
  4218   4326   ** Generate code for a BETWEEN operator.
  4219   4327   **
  4220   4328   **    x BETWEEN y AND z

Changes to src/select.c.

  1270   1270       bSeq = 0;
  1271   1271     }else{
  1272   1272       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
  1273   1273       codeOffset(v, p->iOffset, addrContinue);
  1274   1274       iSortTab = iTab;
  1275   1275       bSeq = 1;
  1276   1276     }
  1277         -  for(i=0, iCol=nKey+bSeq; i<nSortData; i++){
  1278         -    int iRead;
         1277  +  iCol = nKey+bSeq;
         1278  +  for(i=0; i<nSortData; i++){
         1279  +    if( aOutEx[i].u.x.iOrderByCol==0 ) iCol++;
         1280  +  }
         1281  +  for(i=nSortData-1; i>=0; i--){
         1282  +    if( aOutEx[i].u.x.iOrderByCol==0 ){
         1283  +      sqlite3VdbeAddOp3(v, OP_Column, iSortTab, --iCol, regRow+i);
         1284  +      VdbeComment((v, "%s", aOutEx[i].zName?aOutEx[i].zName:aOutEx[i].zSpan));
         1285  +    }
         1286  +  }
         1287  +  for(i=nSortData-1; i>=0; i--){
  1279   1288       if( aOutEx[i].u.x.iOrderByCol ){
  1280         -      iRead = aOutEx[i].u.x.iOrderByCol-1;
  1281         -    }else{
  1282         -      iRead = iCol++;
         1289  +      int iRead = aOutEx[i].u.x.iOrderByCol-1;
         1290  +      sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
         1291  +      VdbeComment((v, "%s", aOutEx[i].zName?aOutEx[i].zName:aOutEx[i].zSpan));
  1283   1292       }
  1284         -    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
  1285         -    VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
  1286   1293     }
  1287   1294     switch( eDest ){
  1288   1295       case SRT_Table:
  1289   1296       case SRT_EphemTab: {
  1290   1297         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
  1291   1298         sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
  1292   1299         sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

Changes to src/sqliteInt.h.

  3076   3076   #define OPFLAG_BULKCSR       0x01    /* OP_Open** used to open bulk cursor */
  3077   3077   #define OPFLAG_SEEKEQ        0x02    /* OP_Open** cursor uses EQ seek only */
  3078   3078   #define OPFLAG_FORDELETE     0x08    /* OP_Open should use BTREE_FORDELETE */
  3079   3079   #define OPFLAG_P2ISREG       0x10    /* P2 to OP_Open** is a register number */
  3080   3080   #define OPFLAG_PERMUTE       0x01    /* OP_Compare: use the permutation */
  3081   3081   #define OPFLAG_SAVEPOSITION  0x02    /* OP_Delete/Insert: save cursor pos */
  3082   3082   #define OPFLAG_AUXDELETE     0x04    /* OP_Delete: index in a DELETE op */
         3083  +
         3084  +#define OPFLAG_CONTINUE      0x01
  3083   3085   
  3084   3086   /*
  3085   3087    * Each trigger present in the database schema is stored as an instance of
  3086   3088    * struct Trigger.
  3087   3089    *
  3088   3090    * Pointers to instances of struct Trigger are stored in two ways.
  3089   3091    * 1. In the "trigHash" hash table (part of the sqlite3* that represents the

Changes to src/update.c.

   543    543     ** the database after the BEFORE triggers are fired anyway (as the trigger 
   544    544     ** may have modified them). So not loading those that are not going to
   545    545     ** be used eliminates some redundant opcodes.
   546    546     */
   547    547     newmask = sqlite3TriggerColmask(
   548    548         pParse, pTrigger, pChanges, 1, TRIGGER_BEFORE, pTab, onError
   549    549     );
          550  +#if 1
          551  +  for(i=pTab->nCol-1; i>=0; i--){
          552  +#else
   550    553     for(i=0; i<pTab->nCol; i++){
          554  +#endif
   551    555       if( i==pTab->iPKey ){
   552    556         sqlite3VdbeAddOp2(v, OP_Null, 0, regNew+i);
   553    557       }else{
   554    558         j = aXRef[i];
   555    559         if( j>=0 ){
   556    560           sqlite3ExprCode(pParse, pChanges->a[j].pExpr, regNew+i);
   557    561         }else if( 0==(tmask&TRIGGER_BEFORE) || i>31 || (newmask & MASKBIT32(i)) ){

Changes to src/vdbe.c.

   549    549       return out2PrereleaseWithClear(pOut);
   550    550     }else{
   551    551       pOut->flags = MEM_Int;
   552    552       return pOut;
   553    553     }
   554    554   }
   555    555   
   556         -
   557    556   /*
   558    557   ** Execute as much of a VDBE program as we can.
   559    558   ** This is the core of sqlite3_step().  
   560    559   */
   561    560   int sqlite3VdbeExec(
   562    561     Vdbe *p                    /* The VDBE */
   563    562   ){
................................................................................
  2623   2622     if( VdbeMemDynamic(pDest) ){
  2624   2623       sqlite3VdbeMemSetNull(pDest);
  2625   2624     }
  2626   2625     assert( t==pC->aType[p2] );
  2627   2626     if( pC->szRow>=aOffset[p2+1] ){
  2628   2627       /* This is the common case where the desired content fits on the original
  2629   2628       ** page - where the content is not on an overflow page */
  2630         -    zData = pC->aRow + aOffset[p2];
  2631         -    if( t<12 ){
  2632         -      sqlite3VdbeSerialGet(zData, t, pDest);
  2633         -    }else{
  2634         -      /* If the column value is a string, we need a persistent value, not
  2635         -      ** a MEM_Ephem value.  This branch is a fast short-cut that is equivalent
  2636         -      ** to calling sqlite3VdbeSerialGet() and sqlite3VdbeDeephemeralize().
  2637         -      */
  2638         -      static const u16 aFlag[] = { MEM_Blob, MEM_Str|MEM_Term };
  2639         -      pDest->n = len = (t-12)/2;
  2640         -      pDest->enc = encoding;
  2641         -      if( pDest->szMalloc < len+2 ){
  2642         -        pDest->flags = MEM_Null;
  2643         -        if( sqlite3VdbeMemGrow(pDest, len+2, 0) ) goto no_mem;
         2629  +    while( 1 ){
         2630  +      zData = pC->aRow + aOffset[p2];
         2631  +      if( t<12 ){
         2632  +        sqlite3VdbeSerialGet(zData, t, pDest);
  2644   2633         }else{
  2645         -        pDest->z = pDest->zMalloc;
         2634  +        /* If the column value is a string, we need a persistent value, not
         2635  +        ** a MEM_Ephem value.  This branch is a fast short-cut that is
         2636  +        ** equivalent to calling sqlite3VdbeSerialGet() and
         2637  +        ** sqlite3VdbeDeephemeralize().
         2638  +        */
         2639  +        static const u16 aFlag[] = { MEM_Blob, MEM_Str|MEM_Term };
         2640  +        pDest->n = len = (t-12)/2;
         2641  +        pDest->enc = encoding;
         2642  +        if( pDest->szMalloc < len+2 ){
         2643  +          pDest->flags = MEM_Null;
         2644  +          if( sqlite3VdbeMemGrow(pDest, len+2, 0) ) goto no_mem;
         2645  +        }else{
         2646  +          pDest->z = pDest->zMalloc;
         2647  +        }
         2648  +        memcpy(pDest->z, zData, len);
         2649  +        pDest->z[len] = 0;
         2650  +        pDest->z[len+1] = 0;
         2651  +        pDest->flags = aFlag[t&1];
  2646   2652         }
  2647         -      memcpy(pDest->z, zData, len);
  2648         -      pDest->z[len] = 0;
  2649         -      pDest->z[len+1] = 0;
  2650         -      pDest->flags = aFlag[t&1];
         2653  +
         2654  +      if( (pOp->p5 & OPFLAG_CONTINUE)==0 ) break;
         2655  +      UPDATE_MAX_BLOBSIZE(pDest);
         2656  +      REGISTER_TRACE(pOp->p3, pDest);
         2657  +      pOp++;
         2658  +      p2 = pOp->p2;
         2659  +      t = pC->aType[p2];
         2660  +      pDest = &aMem[pOp->p3];
         2661  +      memAboutToChange(p, pDest);
         2662  +      if( VdbeMemDynamic(pDest) ){
         2663  +        sqlite3VdbeMemSetNull(pDest);
         2664  +      }
  2651   2665       }
  2652   2666     }else{
  2653   2667       pDest->enc = encoding;
  2654   2668       /* This branch happens only when content is on overflow pages */
  2655   2669       if( ((pOp->p5 & (OPFLAG_LENGTHARG|OPFLAG_TYPEOFARG))!=0
  2656   2670             && ((t>=12 && (t&1)==0) || (pOp->p5 & OPFLAG_TYPEOFARG)!=0))
  2657   2671        || (len = sqlite3VdbeSerialTypeLen(t))==0

Changes to src/vdbe.h.

   222    222   void sqlite3VdbeCountChanges(Vdbe*);
   223    223   sqlite3 *sqlite3VdbeDb(Vdbe*);
   224    224   void sqlite3VdbeSetSql(Vdbe*, const char *z, int n, int);
   225    225   void sqlite3VdbeSwap(Vdbe*,Vdbe*);
   226    226   VdbeOp *sqlite3VdbeTakeOpArray(Vdbe*, int*, int*);
   227    227   sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8);
   228    228   void sqlite3VdbeSetVarmask(Vdbe*, int);
          229  +void sqlite3VdbeUsesAltMap(Vdbe*);
   229    230   #ifndef SQLITE_OMIT_TRACE
   230    231     char *sqlite3VdbeExpandSql(Vdbe*, const char*);
   231    232   #endif
   232    233   int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
   233    234   
   234    235   void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*);
   235    236   int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*);

Changes to src/vdbeInt.h.

   386    386     bft explain:2;          /* True if EXPLAIN present on SQL command */
   387    387     bft changeCntOn:1;      /* True to update the change-counter */
   388    388     bft runOnlyOnce:1;      /* Automatically expire on reset */
   389    389     bft usesStmtJournal:1;  /* True if uses a statement journal */
   390    390     bft readOnly:1;         /* True for statements that do not write */
   391    391     bft bIsReader:1;        /* True for statements that read */
   392    392     bft isPrepareV2:1;      /* True if prepared with prepare_v2() */
          393  +  bft usesAltMap:1;       /* True if uses VdbeCursor.aAltMap[] */
   393    394     yDbMask btreeMask;      /* Bitmask of db->aDb[] entries referenced */
   394    395     yDbMask lockMask;       /* Subset of btreeMask that requires a lock */
   395    396     u32 aCounter[5];        /* Counters used by sqlite3_stmt_status() */
   396    397     char *zSql;             /* Text of the SQL statement that generated this */
   397    398     void *pFree;            /* Free this when deleting the vdbe */
   398    399     VdbeFrame *pFrame;      /* Parent frame */
   399    400     VdbeFrame *pDelFrame;   /* List of frame objects to free on VM reset */

Changes to src/vdbeaux.c.

   614    614         if( (sqlite3OpcodeProperty[pOp->opcode] & OPFLG_JUMP)!=0 && pOp->p2<0 ){
   615    615           assert( ADDR(pOp->p2)<pParse->nLabel );
   616    616           pOp->p2 = aLabel[ADDR(pOp->p2)];
   617    617         }
   618    618       }
   619    619       if( pOp==p->aOp ) break;
   620    620       pOp--;
          621  +
          622  +    if( p->usesAltMap==0 
          623  +     && pOp[0].opcode==OP_Column && pOp[1].opcode==OP_Column
          624  +     && pOp[0].p1==pOp[1].p1 && pOp[0].p2>=pOp[1].p2
          625  +    ){
          626  +      pOp->p5 |= OPFLAG_CONTINUE;
          627  +    }
   621    628     }
   622    629     sqlite3DbFree(p->db, pParse->aLabel);
   623    630     pParse->aLabel = 0;
   624    631     pParse->nLabel = 0;
   625    632     *pMaxFuncArgs = nMaxArgs;
   626    633     assert( p->bIsReader!=0 || DbMaskAllZero(p->btreeMask) );
   627    634   }
................................................................................
  4553   4560     if( iVar>32 ){
  4554   4561       v->expmask = 0xffffffff;
  4555   4562     }else{
  4556   4563       v->expmask |= ((u32)1 << (iVar-1));
  4557   4564     }
  4558   4565   }
  4559   4566   
         4567  +/*
         4568  +** Set the "uses-alt-map" flag.
         4569  +*/
         4570  +void sqlite3VdbeUsesAltMap(Vdbe *v){
         4571  +  v->usesAltMap = 1;
         4572  +}
  4560   4573   #ifndef SQLITE_OMIT_VIRTUALTABLE
  4561   4574   /*
  4562   4575   ** Transfer error message text from an sqlite3_vtab.zErrMsg (text stored
  4563   4576   ** in memory obtained from sqlite3_malloc) into a Vdbe.zErrMsg (text stored
  4564   4577   ** in memory obtained from sqlite3DbMalloc).
  4565   4578   */
  4566   4579   void sqlite3VtabImportErrmsg(Vdbe *p, sqlite3_vtab *pVtab){

Changes to src/wherecode.c.

   999    999         ai[0] = pTab->nCol;
  1000   1000         for(i=0; i<pIdx->nColumn-1; i++){
  1001   1001           assert( pIdx->aiColumn[i]<pTab->nCol );
  1002   1002           if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]+1] = i+1;
  1003   1003         }
  1004   1004         sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
  1005   1005       }
         1006  +    sqlite3VdbeUsesAltMap(v);
  1006   1007     }
  1007   1008   }
  1008   1009   
  1009   1010   /*
  1010   1011   ** If the expression passed as the second argument is a vector, generate
  1011   1012   ** code to write the first nReg elements of the vector into an array
  1012   1013   ** of registers starting with iReg.