/ Check-in [ce4ef460]
Login

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

Overview
Comment:Defer loading result column values into registers on an ORDER BY LIMIT until we know that the LIMIT does not exclude the current row.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | faster-order-by-limit
Files: files | file ages | folders
SHA3-256:ce4ef46058f4aaea6623a41255a2e4b69bb24f16a287391df48f6bacdb4c4989
User & Date: drh 2018-04-30 19:32:49
Context
2018-05-03
23:20
In ORDER BY LIMIT queries, try to evaluate the ORDER BY terms first, and it it becomes clear that the row will not come in under the LIMIT, then skip evaluation of the other columns. check-in: c381f0ea user: drh tags: trunk
2018-04-30
19:32
Defer loading result column values into registers on an ORDER BY LIMIT until we know that the LIMIT does not exclude the current row. Closed-Leaf check-in: ce4ef460 user: drh tags: faster-order-by-limit
2018-04-28
19:08
Test cases added for SQLITE_DBCONFIG_RESET_DATABASE. check-in: 08665a9e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

    74     74     u8 nDefer;            /* Number of valid entries in aDefer[] */
    75     75     struct DeferredCsr {
    76     76       Table *pTab;        /* Table definition */
    77     77       int iCsr;           /* Cursor number for table */
    78     78       int nKey;           /* Number of PK columns for table pTab (>=1) */
    79     79     } aDefer[4];
    80     80   #endif
           81  +  struct RowLoadInfo *pDeferredRowLoad;  /* Deferred row loading info or NULL */
    81     82   };
    82     83   #define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
    83     84   
    84     85   /*
    85     86   ** Delete all the content of a Select structure.  Deallocate the structure
    86     87   ** itself only if bFree is true.
    87     88   */
................................................................................
   531    532   /* Forward reference */
   532    533   static KeyInfo *keyInfoFromExprList(
   533    534     Parse *pParse,       /* Parsing context */
   534    535     ExprList *pList,     /* Form the KeyInfo object from this ExprList */
   535    536     int iStart,          /* Begin with this column of pList */
   536    537     int nExtra           /* Add this many extra columns to the end */
   537    538   );
          539  +
          540  +/*
          541  +** An instance of this object holds information (beyond pParse and pSelect)
          542  +** needed to load the next result row that is to be added to the sorter.
          543  +*/
          544  +typedef struct RowLoadInfo RowLoadInfo;
          545  +struct RowLoadInfo {
          546  +  int regResult;               /* Store results in array of registers here */
          547  +  u8 ecelFlags;                /* Flag argument to ExprCodeExprList() */
          548  +#ifdef SQLITE_ENABLE_SORTER_REFERENCES
          549  +  ExprList *pExtra;            /* Extra columns needed by sorter refs */
          550  +  int regExtraResult;          /* Where to load the extra columns */
          551  +#endif
          552  +};
          553  +
          554  +/*
          555  +** This routine does the work of loading query data into an array of
          556  +** registers so that it can be added to the sorter.
          557  +*/
          558  +static void innerLoopLoadRow(
          559  +  Parse *pParse,             /* Statement under construction */
          560  +  Select *pSelect,           /* The query being coded */
          561  +  RowLoadInfo *pInfo         /* Info needed to complete the row load */
          562  +){
          563  +  sqlite3ExprCodeExprList(pParse, pSelect->pEList, pInfo->regResult,
          564  +                          0, pInfo->ecelFlags);
          565  +#ifdef SQLITE_ENABLE_SORTER_REFERENCES
          566  +  if( pInfo->pExtra ){
          567  +    sqlite3ExprCodeExprList(pParse, pInfo->pExtra, pInfo->regExtraResult, 0, 0);
          568  +    sqlite3ExprListDelete(pParse->db, pInfo->pExtra);
          569  +  }
          570  +#endif
          571  +}
          572  +
          573  +/*
          574  +** Code the OP_MakeRecord instruction that generates the entry to be
          575  +** added into the sorter.
          576  +**
          577  +** Return the register in which the result is stored.
          578  +*/
          579  +static int makeSorterRecord(
          580  +  Parse *pParse,
          581  +  SortCtx *pSort,
          582  +  Select *pSelect,
          583  +  int regBase,
          584  +  int nBase
          585  +){
          586  +  int nOBSat = pSort->nOBSat;
          587  +  Vdbe *v = pParse->pVdbe;
          588  +  int regOut = ++pParse->nMem;
          589  +  if( pSort->pDeferredRowLoad ){
          590  +    innerLoopLoadRow(pParse, pSelect, pSort->pDeferredRowLoad);
          591  +  }
          592  +  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regOut);
          593  +  return regOut;
          594  +}
   538    595   
   539    596   /*
   540    597   ** Generate code that will push the record in registers regData
   541    598   ** through regData+nData-1 onto the sorter.
   542    599   */
   543    600   static void pushOntoSorter(
   544    601     Parse *pParse,         /* Parser context */
   545    602     SortCtx *pSort,        /* Information about the ORDER BY clause */
   546    603     Select *pSelect,       /* The whole SELECT statement */
   547    604     int regData,           /* First register holding data to be sorted */
   548    605     int regOrigData,       /* First register holding data before packing */
   549         -  int nData,             /* Number of elements in the data array */
          606  +  int nData,             /* Number of elements in the regData data array */
   550    607     int nPrefixReg         /* No. of reg prior to regData available for use */
   551    608   ){
   552    609     Vdbe *v = pParse->pVdbe;                         /* Stmt under construction */
   553    610     int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0);
   554    611     int nExpr = pSort->pOrderBy->nExpr;              /* No. of ORDER BY terms */
   555    612     int nBase = nExpr + bSeq + nData;                /* Fields in sorter record */
   556    613     int regBase;                                     /* Regs for sorter record */
   557         -  int regRecord = ++pParse->nMem;                  /* Assembled sorter record */
          614  +  int regRecord = 0;                               /* Assembled sorter record */
   558    615     int nOBSat = pSort->nOBSat;                      /* ORDER BY terms to skip */
   559    616     int op;                            /* Opcode to add sorter record to sorter */
   560    617     int iLimit;                        /* LIMIT counter */
          618  +  int iSkip = 0;                     /* End of the sorter insert loop */
   561    619   
   562    620     assert( bSeq==0 || bSeq==1 );
          621  +
          622  +  /* Three cases:
          623  +  **   (1) The data to be sorted has already been packed into a Record
          624  +  **       by a prior OP_MakeRecord.  In this case nData==1 and regData
          625  +  **       will be completely unrelated to regOrigData.
          626  +  **   (2) All output columns are included in the sort record.  In that
          627  +  **       case regData==regOrigData.
          628  +  **   (3) Some output columns are omitted from the sort record due to
          629  +  **       the SQLITE_ENABLE_SORTER_REFERENCE optimization, or due to the
          630  +  **       SQLITE_ECEL_OMITREF optimization.  In that case, regOrigData==0
          631  +  **       to prevent this routine from trying to copy values that might
          632  +  **       not exist.
          633  +  */
   563    634     assert( nData==1 || regData==regOrigData || regOrigData==0 );
          635  +
   564    636     if( nPrefixReg ){
   565    637       assert( nPrefixReg==nExpr+bSeq );
   566         -    regBase = regData - nExpr - bSeq;
          638  +    regBase = regData - nPrefixReg;
   567    639     }else{
   568    640       regBase = pParse->nMem + 1;
   569    641       pParse->nMem += nBase;
   570    642     }
   571    643     assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
   572    644     iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
   573    645     pSort->labelDone = sqlite3VdbeMakeLabel(v);
................................................................................
   583    655       int regPrevKey;   /* The first nOBSat columns of the previous row */
   584    656       int addrFirst;    /* Address of the OP_IfNot opcode */
   585    657       int addrJmp;      /* Address of the OP_Jump opcode */
   586    658       VdbeOp *pOp;      /* Opcode that opens the sorter */
   587    659       int nKey;         /* Number of sorting key columns, including OP_Sequence */
   588    660       KeyInfo *pKI;     /* Original KeyInfo on the sorter table */
   589    661   
   590         -    sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat,regRecord);
          662  +    regRecord = makeSorterRecord(pParse, pSort, pSelect, regBase, nBase);
   591    663       regPrevKey = pParse->nMem+1;
   592    664       pParse->nMem += pSort->nOBSat;
   593    665       nKey = nExpr - pSort->nOBSat + bSeq;
   594    666       if( bSeq ){
   595    667         addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); 
   596    668       }else{
   597    669         addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);
................................................................................
   634    706       ** If the new record does not need to be inserted into the sorter,
   635    707       ** jump to the next iteration of the loop. Or, if the
   636    708       ** pSort->bOrderedInnerLoop flag is set to indicate that the inner
   637    709       ** loop delivers items in sorted order, jump to the next iteration
   638    710       ** of the outer loop.
   639    711       */
   640    712       int iCsr = pSort->iECursor;
   641         -    int iJmp = sqlite3VdbeCurrentAddr(v)+5+(nOBSat<=0)+pSort->bOrderedInnerLoop;
   642         -    assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 );
   643    713       sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);
   644    714       VdbeCoverage(v);
   645    715       sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);
   646         -    sqlite3VdbeAddOp4Int(v, OP_IdxLE, iCsr, iJmp, regBase+nOBSat, nExpr-nOBSat);
          716  +    iSkip = sqlite3VdbeAddOp4Int(v, OP_IdxLE,
          717  +                                 iCsr, 0, regBase+nOBSat, nExpr-nOBSat);
   647    718       VdbeCoverage(v);
   648    719       sqlite3VdbeAddOp1(v, OP_Delete, iCsr);
   649    720     }
   650         -  if( nOBSat<=0 ){
   651         -    sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat,regRecord);
          721  +  if( regRecord==0 ){
          722  +    regRecord = makeSorterRecord(pParse, pSort, pSelect, regBase, nBase);
   652    723     }
   653    724     if( pSort->sortFlags & SORTFLAG_UseSorter ){
   654    725       op = OP_SorterInsert;
   655    726     }else{
   656    727       op = OP_IdxInsert;
   657    728     }
   658    729     sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
   659    730                          regBase+nOBSat, nBase-nOBSat);
          731  +  if( iSkip ){
          732  +    assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 );
          733  +    sqlite3VdbeChangeP2(v, iSkip,
          734  +         sqlite3VdbeCurrentAddr(v) + pSort->bOrderedInnerLoop);
          735  +  }
   660    736   }
   661    737   
   662    738   /*
   663    739   ** Add code to implement the OFFSET
   664    740   */
   665    741   static void codeOffset(
   666    742     Vdbe *v,          /* Generate code into this VM */
................................................................................
   738    814     for(i=0; i<pEList->nExpr; i++){
   739    815       struct ExprList_item *pItem = &pEList->a[i];
   740    816       if( pItem->u.x.iOrderByCol==0 ){
   741    817         Expr *pExpr = pItem->pExpr;
   742    818         Table *pTab = pExpr->pTab;
   743    819         if( pExpr->op==TK_COLUMN && pTab && !IsVirtual(pTab)
   744    820          && (pTab->aCol[pExpr->iColumn].colFlags & COLFLAG_SORTERREF)
   745         -#if 0
   746         -          && pTab->pSchema && pTab->pSelect==0 && !IsVirtual(pTab)
   747         -#endif
   748    821         ){
   749    822           int j;
   750    823           for(j=0; j<nDefer; j++){
   751    824             if( pSort->aDefer[j].iCsr==pExpr->iTable ) break;
   752    825           }
   753    826           if( j==nDefer ){
   754    827             if( nDefer==ArraySize(pSort->aDefer) ){
................................................................................
   807    880     Vdbe *v = pParse->pVdbe;
   808    881     int i;
   809    882     int hasDistinct;            /* True if the DISTINCT keyword is present */
   810    883     int eDest = pDest->eDest;   /* How to dispose of results */
   811    884     int iParm = pDest->iSDParm; /* First argument to disposal method */
   812    885     int nResultCol;             /* Number of result columns */
   813    886     int nPrefixReg = 0;         /* Number of extra registers before regResult */
          887  +  RowLoadInfo sRowLoadInfo;   /* Info for deferred row loading */
   814    888   
   815    889     /* Usually, regResult is the first cell in an array of memory cells
   816    890     ** containing the current result row. In this case regOrig is set to the
   817    891     ** same value. However, if the results are being sent to the sorter, the
   818    892     ** values for any expressions that are also part of the sort-key are omitted
   819    893     ** from this array. In this case regOrig is set to zero.  */
   820    894     int regResult;              /* Start of memory holding current results */
................................................................................
   859    933     }else if( eDest!=SRT_Exists ){
   860    934   #ifdef SQLITE_ENABLE_SORTER_REFERENCES
   861    935       ExprList *pExtra = 0;
   862    936   #endif
   863    937       /* If the destination is an EXISTS(...) expression, the actual
   864    938       ** values returned by the SELECT are not required.
   865    939       */
   866         -    u8 ecelFlags;
          940  +    u8 ecelFlags;    /* "ecel" is an abbreviation of "ExprCodeExprList" */
          941  +    ExprList *pEList;
   867    942       if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
   868    943         ecelFlags = SQLITE_ECEL_DUP;
   869    944       }else{
   870    945         ecelFlags = 0;
   871    946       }
   872    947       if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab && eDest!=SRT_Table ){
   873    948         /* For each expression in p->pEList that is a copy of an expression in
   874    949         ** the ORDER BY clause (pSort->pOrderBy), set the associated 
   875    950         ** iOrderByCol value to one more than the index of the ORDER BY 
   876    951         ** expression within the sort-key that pushOntoSorter() will generate.
   877    952         ** This allows the p->pEList field to be omitted from the sorted record,
   878    953         ** saving space and CPU cycles.  */
   879    954         ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
          955  +
   880    956         for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
   881    957           int j;
   882    958           if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
   883    959             p->pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
   884    960           }
   885    961         }
   886    962   #ifdef SQLITE_ENABLE_SORTER_REFERENCES
................................................................................
   893    969           ** composite primary keys in the SortCtx.aDefer[] array.  */
   894    970           VdbeOp *pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
   895    971           pOp->p2 += (pExtra->nExpr - pSort->nDefer);
   896    972           pOp->p4.pKeyInfo->nAllField += (pExtra->nExpr - pSort->nDefer);
   897    973           pParse->nMem += pExtra->nExpr;
   898    974         }
   899    975   #endif
   900         -      regOrig = 0;
          976  +
          977  +      /* Adjust nResultCol to account for columns that are omitted
          978  +      ** from the sorter by the optimizations in this branch */
          979  +      pEList = p->pEList;
          980  +      for(i=0; i<pEList->nExpr; i++){
          981  +        if( pEList->a[i].u.x.iOrderByCol>0
          982  +#ifdef SQLITE_ENABLE_SORTER_REFERENCES
          983  +         || pEList->a[i].bSorterRef
          984  +#endif
          985  +        ){
          986  +          nResultCol--;
          987  +          regOrig = 0;
          988  +        }
          989  +      }
          990  +
          991  +      testcase( regOrig );
          992  +      testcase( eDest==SRT_Set );
          993  +      testcase( eDest==SRT_Mem );
          994  +      testcase( eDest==SRT_Coroutine );
          995  +      testcase( eDest==SRT_Output );
   901    996         assert( eDest==SRT_Set || eDest==SRT_Mem 
   902    997              || eDest==SRT_Coroutine || eDest==SRT_Output );
   903    998       }
   904         -    nResultCol = sqlite3ExprCodeExprList(pParse,p->pEList,regResult,
   905         -                                         0,ecelFlags);
          999  +    sRowLoadInfo.regResult = regResult;
         1000  +    sRowLoadInfo.ecelFlags = ecelFlags;
   906   1001   #ifdef SQLITE_ENABLE_SORTER_REFERENCES
   907         -    if( pExtra ){
   908         -      nResultCol += sqlite3ExprCodeExprList(
   909         -          pParse, pExtra, regResult + nResultCol, 0, 0
   910         -      );
   911         -      sqlite3ExprListDelete(pParse->db, pExtra);
         1002  +    sRowLoadInfo.pExtra = pExtra;
         1003  +    sRowLoadInfo.regExtraResult = regResult + nResultCol;
         1004  +    if( pExtra ) nResultCol += pExtra->nExpr;
         1005  +#endif
         1006  +    if( p->iLimit
         1007  +     && (ecelFlags & SQLITE_ECEL_OMITREF)!=0 
         1008  +     && nPrefixReg>0
         1009  +    ){
         1010  +      assert( pSort!=0 );
         1011  +      assert( hasDistinct==0 );
         1012  +      pSort->pDeferredRowLoad = &sRowLoadInfo;
         1013  +    }else{
         1014  +      innerLoopLoadRow(pParse, p, &sRowLoadInfo);
   912   1015       }
   913         -#endif
   914   1016     }
   915   1017   
   916   1018     /* If the DISTINCT keyword was present on the SELECT statement
   917   1019     ** and this row has been seen before, then do not make this row
   918   1020     ** part of the result.
   919   1021     */
   920   1022     if( hasDistinct ){
................................................................................
  1022   1124           sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);
  1023   1125           VdbeCoverage(v);
  1024   1126           sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm+1, r1,regResult,nResultCol);
  1025   1127           assert( pSort==0 );
  1026   1128         }
  1027   1129   #endif
  1028   1130         if( pSort ){
  1029         -        pushOntoSorter(pParse, pSort, p, r1+nPrefixReg,regResult,1,nPrefixReg);
         1131  +        assert( regResult==regOrig );
         1132  +        pushOntoSorter(pParse, pSort, p, r1+nPrefixReg, regOrig, 1, nPrefixReg);
  1030   1133         }else{
  1031   1134           int r2 = sqlite3GetTempReg(pParse);
  1032   1135           sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
  1033   1136           sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
  1034   1137           sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
  1035   1138           sqlite3ReleaseTempReg(pParse, r2);
  1036   1139         }

Changes to src/sqliteInt.h.

  2755   2755     int iIdxCur;              /* Index of the first index cursor */
  2756   2756   };
  2757   2757   
  2758   2758   /*
  2759   2759   ** An instance of the following structure contains all information
  2760   2760   ** needed to generate code for a single SELECT statement.
  2761   2761   **
  2762         -** nLimit is set to -1 if there is no LIMIT clause.  nOffset is set to 0.
  2763         -** If there is a LIMIT clause, the parser sets nLimit to the value of the
  2764         -** limit and nOffset to the value of the offset (or 0 if there is not
  2765         -** offset).  But later on, nLimit and nOffset become the memory locations
  2766         -** in the VDBE that record the limit and offset counters.
         2762  +** See the header comment on the computeLimitRegisters() routine for a
         2763  +** detailed description of the meaning of the iLimit and iOffset fields.
  2767   2764   **
  2768   2765   ** addrOpenEphm[] entries contain the address of OP_OpenEphemeral opcodes.
  2769   2766   ** These addresses must be stored so that we can go back and fill in
  2770   2767   ** the P4_KEYINFO and P2 parameters later.  Neither the KeyInfo nor
  2771   2768   ** the number of columns in P2 can be computed at the same time
  2772   2769   ** as the OP_OpenEphm instruction is coded because not
  2773   2770   ** enough information about the compound query is known at that point.