/ Check-in [0af62fdb]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 (as in "SELECT a FROM t1 ORDER BY 1").
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sorter-opt
Files: files | file ages | folders
SHA1: 0af62fdbd8e2aab14718ff8bcb5934f05463c176
User & Date: dan 2016-11-10 20:14:06
Context
2016-11-11
18:08
Reenable the SQLITE_EXPR_REF optimization for "SELECT DISTINCT ... ORDER BY" queries. check-in: 6e2e9d38 user: dan tags: sorter-opt
2016-11-10
20:14
Avoid storing redundant fields in sorter records when the sort-key and data have fields in common (as in "SELECT a FROM t1 ORDER BY 1"). check-in: 0af62fdb user: dan tags: sorter-opt
2016-11-09
01:46
Fix typo in the CSV extension. check-in: b4889588 user: mistachkin tags: trunk
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.

   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);
   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 */
................................................................................
   730    730       */
   731    731       u8 ecelFlags;
   732    732       if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
   733    733         ecelFlags = SQLITE_ECEL_DUP;
   734    734       }else{
   735    735         ecelFlags = 0;
   736    736       }
   737         -    sqlite3ExprCodeExprList(pParse, pEList, regResult, 0, ecelFlags);
          737  +    if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab && eDest!=SRT_Table ){
          738  +      /* For each expression in pEList that is a copy of an expression in
          739  +      ** the ORDER BY clause (pSort->pOrderBy), set the associated 
          740  +      ** iOrderByCol value to one more than the index of the ORDER BY 
          741  +      ** expression within the sort-key that pushOntoSorter() will generate.
          742  +      ** This allows the pEList field to be omitted from the sorted record,
          743  +      ** saving space and CPU cycles.  */
          744  +      ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
          745  +      for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
          746  +        int j;
          747  +        if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
          748  +          pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
          749  +        }
          750  +      }
          751  +
          752  +      assert( eDest==SRT_Set || eDest==SRT_Mem 
          753  +           || eDest==SRT_Coroutine || eDest==SRT_Output );
          754  +    }
          755  +    nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags);
   738    756     }
   739    757   
   740    758     /* If the DISTINCT keyword was present on the SELECT statement
   741    759     ** and this row has been seen before, then do not make this row
   742    760     ** part of the result.
   743    761     */
   744    762     if( hasDistinct ){
................................................................................
   896    914       }
   897    915   
   898    916       /* If this is a scalar select that is part of an expression, then
   899    917       ** store the results in the appropriate memory cell or array of 
   900    918       ** memory cells and break out of the scan loop.
   901    919       */
   902    920       case SRT_Mem: {
   903         -      assert( nResultCol==pDest->nSdst );
   904    921         if( pSort ){
          922  +        assert( nResultCol<=pDest->nSdst );
   905    923           pushOntoSorter(
   906    924               pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg);
   907    925         }else{
          926  +        assert( nResultCol==pDest->nSdst );
   908    927           assert( regResult==iParm );
   909    928           /* The LIMIT clause will jump out of the loop for us */
   910    929         }
   911    930         break;
   912    931       }
   913    932   #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
   914    933   
................................................................................
  1198   1217     int addrOnce = 0;
  1199   1218     int iTab;
  1200   1219     ExprList *pOrderBy = pSort->pOrderBy;
  1201   1220     int eDest = pDest->eDest;
  1202   1221     int iParm = pDest->iSDParm;
  1203   1222     int regRow;
  1204   1223     int regRowid;
         1224  +  int iCol;
  1205   1225     int nKey;
  1206   1226     int iSortTab;                   /* Sorter cursor to read from */
  1207   1227     int nSortData;                  /* Trailing values to read from sorter */
  1208   1228     int i;
  1209   1229     int bSeq;                       /* True if sorter record includes seq. no. */
  1210         -#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
  1211   1230     struct ExprList_item *aOutEx = p->pEList->a;
  1212         -#endif
  1213   1231   
  1214   1232     assert( addrBreak<0 );
  1215   1233     if( pSort->labelBkOut ){
  1216   1234       sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
  1217   1235       sqlite3VdbeGoto(v, addrBreak);
  1218   1236       sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
  1219   1237     }
................................................................................
  1243   1261       bSeq = 0;
  1244   1262     }else{
  1245   1263       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
  1246   1264       codeOffset(v, p->iOffset, addrContinue);
  1247   1265       iSortTab = iTab;
  1248   1266       bSeq = 1;
  1249   1267     }
  1250         -  for(i=0; i<nSortData; i++){
  1251         -    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, nKey+bSeq+i, regRow+i);
         1268  +  for(i=0, iCol=nKey+bSeq; i<nSortData; i++){
         1269  +    int iRead;
         1270  +    if( aOutEx[i].u.x.iOrderByCol ){
         1271  +      iRead = aOutEx[i].u.x.iOrderByCol-1;
         1272  +    }else{
         1273  +      iRead = iCol++;
         1274  +    }
         1275  +    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
  1252   1276       VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
  1253   1277     }
  1254   1278     switch( eDest ){
  1255   1279       case SRT_EphemTab: {
  1256   1280         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
  1257   1281         sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
  1258   1282         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*);