/ Changes On Branch sorter-opt
Login

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

Changes In Branch sorter-opt Excluding Merge-Ins

This is equivalent to a diff from 46e00162 to dd62d2de

2016-11-11
19:08
Avoid storing redundant fields in sorter records when the sort-key and data have fields in common. (check-in: b835cf3e user: drh tags: trunk)
19:01
Enhance the OP_IdxInsert opcode so that it can used unpacked key values if they are available. Update the code generator to take advantage of this new capability. The speedtest1.c test is about 2.6% faster as a result. Later: This also introduced bug [30027b613b]. Bummer. (check-in: 925840cf user: drh tags: trunk)
18:45
Merge trunk with this branch. (Closed-Leaf check-in: dd62d2de user: dan tags: sorter-opt)
18:08
Reenable the SQLITE_EXPR_REF optimization for "SELECT DISTINCT ... ORDER BY" queries. (check-in: 6e2e9d38 user: dan tags: sorter-opt)
17:52
Merge enhancements and bug-fixes from trunk. (check-in: 5515b827 user: drh tags: unpacked-IdxInsert)
17:08
Fix a problem with switching from wal to rollback mode when SQLITE_DBCONFIG_NO_CKPT_ON_CLOSE is configured. (check-in: 46e00162 user: dan tags: trunk)
16:33
Add the test/ossfuzz.c interface adaptor for OSS-FUZZ. Make previsions for testing the adaptor using fuzzcheck.c. (check-in: 119d6ef8 user: drh tags: trunk)

Changes to src/expr.c.

  4082   4082     assert( pList!=0 );
  4083   4083     assert( target>0 );
  4084   4084     assert( pParse->pVdbe!=0 );  /* Never gets this far otherwise */
  4085   4085     n = pList->nExpr;
  4086   4086     if( !ConstFactorOk(pParse) ) flags &= ~SQLITE_ECEL_FACTOR;
  4087   4087     for(pItem=pList->a, i=0; i<n; i++, pItem++){
  4088   4088       Expr *pExpr = pItem->pExpr;
  4089         -    if( (flags & SQLITE_ECEL_REF)!=0 && (j = pList->a[i].u.x.iOrderByCol)>0 ){
  4090         -      sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i);
         4089  +    if( (flags & SQLITE_ECEL_REF)!=0 && (j = pItem->u.x.iOrderByCol)>0 ){
         4090  +      if( flags & SQLITE_ECEL_OMITREF ){
         4091  +        i--;
         4092  +        n--;
         4093  +      }else{
         4094  +        sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i);
         4095  +      }
  4091   4096       }else if( (flags & SQLITE_ECEL_FACTOR)!=0 && sqlite3ExprIsConstant(pExpr) ){
  4092   4097         sqlite3ExprCodeAtInit(pParse, pExpr, target+i, 0);
  4093   4098       }else{
  4094   4099         int inReg = sqlite3ExprCodeTarget(pParse, pExpr, target+i);
  4095   4100         if( inReg!=target+i ){
  4096   4101           VdbeOp *pOp;
  4097   4102           if( copyOp==OP_Copy

Changes to src/select.c.

   517    517     int regBase;                                     /* Regs for sorter record */
   518    518     int regRecord = ++pParse->nMem;                  /* Assembled sorter record */
   519    519     int nOBSat = pSort->nOBSat;                      /* ORDER BY terms to skip */
   520    520     int op;                            /* Opcode to add sorter record to sorter */
   521    521     int iLimit;                        /* LIMIT counter */
   522    522   
   523    523     assert( bSeq==0 || bSeq==1 );
   524         -  assert( nData==1 || regData==regOrigData );
          524  +  assert( nData==1 || regData==regOrigData || regOrigData==0 );
   525    525     if( nPrefixReg ){
   526    526       assert( nPrefixReg==nExpr+bSeq );
   527    527       regBase = regData - nExpr - bSeq;
   528    528     }else{
   529    529       regBase = pParse->nMem + 1;
   530    530       pParse->nMem += nBase;
   531    531     }
   532    532     assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
   533    533     iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
   534    534     pSort->labelDone = sqlite3VdbeMakeLabel(v);
   535    535     sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,
   536         -                          SQLITE_ECEL_DUP|SQLITE_ECEL_REF);
          536  +                          SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
   537    537     if( bSeq ){
   538    538       sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
   539    539     }
   540         -  if( nPrefixReg==0 ){
          540  +  if( nPrefixReg==0 && nData>0 ){
   541    541       sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
   542    542     }
   543    543     sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
   544    544     if( nOBSat>0 ){
   545    545       int regPrevKey;   /* The first nOBSat columns of the previous row */
   546    546       int addrFirst;    /* Address of the OP_IfNot opcode */
   547    547       int addrJmp;      /* Address of the OP_Jump opcode */
................................................................................
   662    662   /*
   663    663   ** This routine generates the code for the inside of the inner loop
   664    664   ** of a SELECT.
   665    665   **
   666    666   ** If srcTab is negative, then the pEList expressions
   667    667   ** are evaluated in order to get the data for this row.  If srcTab is
   668    668   ** zero or more, then data is pulled from srcTab and pEList is used only 
   669         -** to get number columns and the datatype for each column.
          669  +** to get the number of columns and the collation sequence for each column.
   670    670   */
   671    671   static void selectInnerLoop(
   672    672     Parse *pParse,          /* The parser context */
   673    673     Select *p,              /* The complete select statement being coded */
   674    674     ExprList *pEList,       /* List of values being extracted */
   675    675     int srcTab,             /* Pull data from this table */
   676    676     SortCtx *pSort,         /* If not NULL, info on how to process ORDER BY */
................................................................................
   677    677     DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
   678    678     SelectDest *pDest,      /* How to dispose of the results */
   679    679     int iContinue,          /* Jump here to continue with next row */
   680    680     int iBreak              /* Jump here to break out of the inner loop */
   681    681   ){
   682    682     Vdbe *v = pParse->pVdbe;
   683    683     int i;
   684         -  int hasDistinct;        /* True if the DISTINCT keyword is present */
   685         -  int regResult;              /* Start of memory holding result set */
          684  +  int hasDistinct;            /* True if the DISTINCT keyword is present */
   686    685     int eDest = pDest->eDest;   /* How to dispose of results */
   687    686     int iParm = pDest->iSDParm; /* First argument to disposal method */
   688    687     int nResultCol;             /* Number of result columns */
   689    688     int nPrefixReg = 0;         /* Number of extra registers before regResult */
   690    689   
          690  +  /* Usually, regResult is the first cell in an array of memory cells
          691  +  ** containing the current result row. In this case regOrig is set to the
          692  +  ** same value. However, if the results are being sent to the sorter, the
          693  +  ** values for any expressions that are also part of the sort-key are omitted
          694  +  ** from this array. In this case regOrig is set to zero.  */
          695  +  int regResult;              /* Start of memory holding current results */
          696  +  int regOrig;                /* Start of memory holding full result (or 0) */
          697  +
   691    698     assert( v );
   692    699     assert( pEList!=0 );
   693    700     hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
   694    701     if( pSort && pSort->pOrderBy==0 ) pSort = 0;
   695    702     if( pSort==0 && !hasDistinct ){
   696    703       assert( iContinue!=0 );
   697    704       codeOffset(v, p->iOffset, iContinue);
................................................................................
   714    721       ** on the right-hand side of an INSERT contains more result columns than
   715    722       ** there are columns in the table on the left.  The error will be caught
   716    723       ** and reported later.  But we need to make sure enough memory is allocated
   717    724       ** to avoid other spurious errors in the meantime. */
   718    725       pParse->nMem += nResultCol;
   719    726     }
   720    727     pDest->nSdst = nResultCol;
   721         -  regResult = pDest->iSdst;
          728  +  regOrig = regResult = pDest->iSdst;
   722    729     if( srcTab>=0 ){
   723    730       for(i=0; i<nResultCol; i++){
   724    731         sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
   725    732         VdbeComment((v, "%s", pEList->a[i].zName));
   726    733       }
   727    734     }else if( eDest!=SRT_Exists ){
   728    735       /* If the destination is an EXISTS(...) expression, the actual
................................................................................
   730    737       */
   731    738       u8 ecelFlags;
   732    739       if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
   733    740         ecelFlags = SQLITE_ECEL_DUP;
   734    741       }else{
   735    742         ecelFlags = 0;
   736    743       }
   737         -    sqlite3ExprCodeExprList(pParse, pEList, regResult, 0, ecelFlags);
          744  +    assert( eDest!=SRT_Table || pSort==0 );
          745  +    if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab ){
          746  +      /* For each expression in pEList that is a copy of an expression in
          747  +      ** the ORDER BY clause (pSort->pOrderBy), set the associated 
          748  +      ** iOrderByCol value to one more than the index of the ORDER BY 
          749  +      ** expression within the sort-key that pushOntoSorter() will generate.
          750  +      ** This allows the pEList field to be omitted from the sorted record,
          751  +      ** saving space and CPU cycles.  */
          752  +      ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
          753  +      for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
          754  +        int j;
          755  +        if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
          756  +          pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
          757  +        }
          758  +      }
          759  +      regOrig = 0;
          760  +      assert( eDest==SRT_Set || eDest==SRT_Mem 
          761  +           || eDest==SRT_Coroutine || eDest==SRT_Output );
          762  +    }
          763  +    nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags);
   738    764     }
   739    765   
   740    766     /* If the DISTINCT keyword was present on the SELECT statement
   741    767     ** and this row has been seen before, then do not make this row
   742    768     ** part of the result.
   743    769     */
   744    770     if( hasDistinct ){
................................................................................
   870    896       case SRT_Set: {
   871    897         if( pSort ){
   872    898           /* At first glance you would think we could optimize out the
   873    899           ** ORDER BY in this case since the order of entries in the set
   874    900           ** does not matter.  But there might be a LIMIT clause, in which
   875    901           ** case the order does matter */
   876    902           pushOntoSorter(
   877         -            pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg);
          903  +            pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
   878    904         }else{
   879    905           int r1 = sqlite3GetTempReg(pParse);
   880    906           assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
   881    907           sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol, 
   882    908               r1, pDest->zAffSdst, nResultCol);
   883    909           sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
   884    910           sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
................................................................................
   896    922       }
   897    923   
   898    924       /* If this is a scalar select that is part of an expression, then
   899    925       ** store the results in the appropriate memory cell or array of 
   900    926       ** memory cells and break out of the scan loop.
   901    927       */
   902    928       case SRT_Mem: {
   903         -      assert( nResultCol==pDest->nSdst );
   904    929         if( pSort ){
          930  +        assert( nResultCol<=pDest->nSdst );
   905    931           pushOntoSorter(
   906         -            pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg);
          932  +            pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
   907    933         }else{
          934  +        assert( nResultCol==pDest->nSdst );
   908    935           assert( regResult==iParm );
   909    936           /* The LIMIT clause will jump out of the loop for us */
   910    937         }
   911    938         break;
   912    939       }
   913    940   #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
   914    941   
   915    942       case SRT_Coroutine:       /* Send data to a co-routine */
   916    943       case SRT_Output: {        /* Return the results */
   917    944         testcase( eDest==SRT_Coroutine );
   918    945         testcase( eDest==SRT_Output );
   919    946         if( pSort ){
   920         -        pushOntoSorter(pParse, pSort, p, regResult, regResult, nResultCol,
          947  +        pushOntoSorter(pParse, pSort, p, regResult, regOrig, nResultCol,
   921    948                          nPrefixReg);
   922    949         }else if( eDest==SRT_Coroutine ){
   923    950           sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
   924    951         }else{
   925    952           sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
   926    953           sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
   927    954         }
................................................................................
  1198   1225     int addrOnce = 0;
  1199   1226     int iTab;
  1200   1227     ExprList *pOrderBy = pSort->pOrderBy;
  1201   1228     int eDest = pDest->eDest;
  1202   1229     int iParm = pDest->iSDParm;
  1203   1230     int regRow;
  1204   1231     int regRowid;
         1232  +  int iCol;
  1205   1233     int nKey;
  1206   1234     int iSortTab;                   /* Sorter cursor to read from */
  1207   1235     int nSortData;                  /* Trailing values to read from sorter */
  1208   1236     int i;
  1209   1237     int bSeq;                       /* True if sorter record includes seq. no. */
  1210         -#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
  1211   1238     struct ExprList_item *aOutEx = p->pEList->a;
  1212         -#endif
  1213   1239   
  1214   1240     assert( addrBreak<0 );
  1215   1241     if( pSort->labelBkOut ){
  1216   1242       sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
  1217   1243       sqlite3VdbeGoto(v, addrBreak);
  1218   1244       sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
  1219   1245     }
................................................................................
  1243   1269       bSeq = 0;
  1244   1270     }else{
  1245   1271       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
  1246   1272       codeOffset(v, p->iOffset, addrContinue);
  1247   1273       iSortTab = iTab;
  1248   1274       bSeq = 1;
  1249   1275     }
  1250         -  for(i=0; i<nSortData; i++){
  1251         -    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, nKey+bSeq+i, regRow+i);
         1276  +  for(i=0, iCol=nKey+bSeq; i<nSortData; i++){
         1277  +    int iRead;
         1278  +    if( aOutEx[i].u.x.iOrderByCol ){
         1279  +      iRead = aOutEx[i].u.x.iOrderByCol-1;
         1280  +    }else{
         1281  +      iRead = iCol++;
         1282  +    }
         1283  +    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
  1252   1284       VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
  1253   1285     }
  1254   1286     switch( eDest ){
  1255   1287       case SRT_EphemTab: {
  1256   1288         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
  1257   1289         sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
  1258   1290         sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

Changes to src/sqliteInt.h.

  3702   3702   int sqlite3ExprCodeTemp(Parse*, Expr*, int*);
  3703   3703   int sqlite3ExprCodeTarget(Parse*, Expr*, int);
  3704   3704   void sqlite3ExprCodeAndCache(Parse*, Expr*, int);
  3705   3705   int sqlite3ExprCodeExprList(Parse*, ExprList*, int, int, u8);
  3706   3706   #define SQLITE_ECEL_DUP      0x01  /* Deep, not shallow copies */
  3707   3707   #define SQLITE_ECEL_FACTOR   0x02  /* Factor out constant terms */
  3708   3708   #define SQLITE_ECEL_REF      0x04  /* Use ExprList.u.x.iOrderByCol */
         3709  +#define SQLITE_ECEL_OMITREF  0x08  /* Omit if ExprList.u.x.iOrderByCol */
  3709   3710   void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
  3710   3711   void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
  3711   3712   void sqlite3ExprIfFalseDup(Parse*, Expr*, int, int);
  3712   3713   Table *sqlite3FindTable(sqlite3*,const char*, const char*);
  3713   3714   #define LOCATE_VIEW    0x01
  3714   3715   #define LOCATE_NOERR   0x02
  3715   3716   Table *sqlite3LocateTable(Parse*,u32 flags,const char*, const char*);