/ Check-in [b835cf3e]
Login

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

Overview
Comment:Avoid storing redundant fields in sorter records when the sort-key and data have fields in common.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:b835cf3e507b910b6a3e0f802ce2c40a72d0c227
User & Date: drh 2016-11-11 19:08:00
Context
2016-11-11
20:37
Fix harmless compiler warnings in test code for MSVC. check-in: 7b76be41 user: drh tags: trunk
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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