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

Changes to src/select.c.

    64     64     ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
    65     65     int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
    66     66     int iECursor;         /* Cursor number for the sorter */
    67     67     int regReturn;        /* Register holding block-output return address */
    68     68     int labelBkOut;       /* Start label for the block-output subroutine */
    69     69     int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
    70     70     int labelDone;        /* Jump here when done, ex: LIMIT reached */
           71  +  int labelOBLopt;      /* Jump here when sorter is full */
    71     72     u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
    72         -  u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
    73     73   #ifdef SQLITE_ENABLE_SORTER_REFERENCES
    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];
................................................................................
   689    689       ** less than LIMIT+OFFSET items or (b) the new record is smaller than 
   690    690       ** the largest record currently in the sorter. If (b) is true and there
   691    691       ** are already LIMIT+OFFSET items in the sorter, delete the largest
   692    692       ** entry before inserting the new one. This way there are never more 
   693    693       ** than LIMIT+OFFSET items in the sorter.
   694    694       **
   695    695       ** If the new record does not need to be inserted into the sorter,
   696         -    ** jump to the next iteration of the loop. Or, if the
   697         -    ** pSort->bOrderedInnerLoop flag is set to indicate that the inner
   698         -    ** loop delivers items in sorted order, jump to the next iteration
   699         -    ** of the outer loop.
          696  +    ** jump to the next iteration of the loop. If the pSort->labelOBLopt
          697  +    ** value is not zero, then it is a label of where to jump.  Otherwise,
          698  +    ** just bypass the row insert logic.  See the header comment on the
          699  +    ** sqlite3WhereOrderByLimitOptLabel() function for additional info.
   700    700       */
   701    701       int iCsr = pSort->iECursor;
   702    702       sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);
   703    703       VdbeCoverage(v);
   704    704       sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);
   705    705       iSkip = sqlite3VdbeAddOp4Int(v, OP_IdxLE,
   706    706                                    iCsr, 0, regBase+nOBSat, nExpr-nOBSat);
................................................................................
   714    714       op = OP_SorterInsert;
   715    715     }else{
   716    716       op = OP_IdxInsert;
   717    717     }
   718    718     sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
   719    719                          regBase+nOBSat, nBase-nOBSat);
   720    720     if( iSkip ){
   721         -    assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 );
   722    721       sqlite3VdbeChangeP2(v, iSkip,
   723         -         sqlite3VdbeCurrentAddr(v) + pSort->bOrderedInnerLoop);
          722  +         pSort->labelOBLopt ? pSort->labelOBLopt : sqlite3VdbeCurrentAddr(v));
   724    723     }
   725    724   }
   726    725   
   727    726   /*
   728    727   ** Add code to implement the OFFSET
   729    728   */
   730    729   static void codeOffset(
................................................................................
  6056   6055         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  6057   6056       }
  6058   6057       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  6059   6058         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  6060   6059       }
  6061   6060       if( sSort.pOrderBy ){
  6062   6061         sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
  6063         -      sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
         6062  +      sSort.labelOBLopt = sqlite3WhereOrderByLimitOptLabel(pWInfo);
  6064   6063         if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
  6065   6064           sSort.pOrderBy = 0;
  6066   6065         }
  6067   6066       }
  6068   6067   
  6069   6068       /* If sorting index that was created by a prior OP_OpenEphemeral 
  6070   6069       ** instruction ended up not being needed, then change the OP_OpenEphemeral

Changes to src/sqliteInt.h.

  3919   3919   void sqlite3Update(Parse*, SrcList*, ExprList*,Expr*,int,ExprList*,Expr*,
  3920   3920                      Upsert*);
  3921   3921   WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  3922   3922   void sqlite3WhereEnd(WhereInfo*);
  3923   3923   LogEst sqlite3WhereOutputRowCount(WhereInfo*);
  3924   3924   int sqlite3WhereIsDistinct(WhereInfo*);
  3925   3925   int sqlite3WhereIsOrdered(WhereInfo*);
  3926         -int sqlite3WhereOrderedInnerLoop(WhereInfo*);
         3926  +int sqlite3WhereOrderByLimitOptLabel(WhereInfo*);
  3927   3927   int sqlite3WhereIsSorted(WhereInfo*);
  3928   3928   int sqlite3WhereContinueLabel(WhereInfo*);
  3929   3929   int sqlite3WhereBreakLabel(WhereInfo*);
  3930   3930   int sqlite3WhereOkOnePass(WhereInfo*, int*);
  3931   3931   #define ONEPASS_OFF      0        /* Use of ONEPASS not allowed */
  3932   3932   #define ONEPASS_SINGLE   1        /* ONEPASS valid for a single row update */
  3933   3933   #define ONEPASS_MULTI    2        /* ONEPASS is valid for multiple rows */

Changes to src/where.c.

    63     63   ** Return FALSE if the output needs to be sorted.
    64     64   */
    65     65   int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
    66     66     return pWInfo->nOBSat;
    67     67   }
    68     68   
    69     69   /*
    70         -** Return TRUE if the innermost loop of the WHERE clause implementation
    71         -** returns rows in ORDER BY order for complete run of the inner loop.
           70  +** In the ORDER BY LIMIT optimization, if the inner-most loop is known
           71  +** to emit rows in increasing order, and if the last row emitted by the
           72  +** inner-most loop did not fit within the sorter, then we can skip all
           73  +** subsequent rows for the current iteration of the inner loop (because they
           74  +** will not fit in the sorter either) and continue with the second inner
           75  +** loop - the loop immediately outside the inner-most.
    72     76   **
    73         -** Across multiple iterations of outer loops, the output rows need not be
    74         -** sorted.  As long as rows are sorted for just the innermost loop, this
    75         -** routine can return TRUE.
           77  +** When a row does not fit in the sorter (because the sorter already
           78  +** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
           79  +** label returned by this function.
           80  +**
           81  +** If the ORDER BY LIMIT optimization applies, the jump destination should
           82  +** be the continuation for the second-inner-most loop.  If the ORDER BY
           83  +** LIMIT optimization does not apply, then the jump destination should
           84  +** be the continuation for the inner-most loop.
           85  +**
           86  +** It is always safe for this routine to return the continuation of the
           87  +** inner-most loop, in the sense that a correct answer will result.  
           88  +** Returning the continuation the second inner loop is an optimization
           89  +** that might make the code run a little faster, but should not change
           90  +** the final answer.
    76     91   */
    77         -int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){
    78         -  return pWInfo->bOrderedInnerLoop;
           92  +int sqlite3WhereOrderByLimitOptLabel(WhereInfo *pWInfo){
           93  +  WhereLevel *pInner;
           94  +  if( !pWInfo->bOrderedInnerLoop ){
           95  +    /* The ORDER BY LIMIT optimization does not apply.  Jump to the 
           96  +    ** continuation of the inner-most loop. */
           97  +    return pWInfo->iContinue;
           98  +  }
           99  +  pInner = &pWInfo->a[pWInfo->nLevel-1];
          100  +  if( pInner->addrNxt ) return pInner->addrNxt;
          101  +  return pInner->addrBrk;
    79    102   }
    80    103   
    81    104   /*
    82    105   ** Return the VDBE address or label to jump to in order to continue
    83    106   ** immediately with the next row of a WHERE clause.
    84    107   */
    85    108   int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
  4244   4267       Bitmask notUsed;
  4245   4268       int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
  4246   4269                    WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
  4247   4270       if( rc==pWInfo->pResultSet->nExpr ){
  4248   4271         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  4249   4272       }
  4250   4273     }
         4274  +  pWInfo->bOrderedInnerLoop = 0;
  4251   4275     if( pWInfo->pOrderBy ){
  4252   4276       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  4253   4277         if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
  4254   4278           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  4255   4279         }
  4256   4280       }else{
  4257   4281         pWInfo->nOBSat = pFrom->isOrdered;

Changes to test/limit2.test.

   162    162     DROP TABLE IF EXISTS t1;
   163    163     CREATE TABLE t1(a, b);  INSERT INTO t1 VALUES(1,2);
   164    164     DROP TABLE IF EXISTS t2;
   165    165     CREATE TABLE t2(x, y);  INSERT INTO t2 VALUES(1,3);
   166    166     CREATE INDEX t1ab ON t1(a,b);
   167    167     SELECT y FROM t1, t2 WHERE a=x AND b<=y ORDER BY b DESC;
   168    168   } {3}
          169  +
          170  +# Ticket https://www.sqlite.org/src/info/9936b2fa443fec03 2018-09-08
          171  +# Infinite loop due to the ORDER BY LIMIT optimization.
          172  +#
          173  +do_execsql_test 700 {
          174  +  DROP TABLE IF EXISTS t1;
          175  +  DROP TABLE IF EXISTS t2;
          176  +  CREATE TABLE t1(aa VARCHAR PRIMARY KEY NOT NULL,bb,cc,x VARCHAR(400));
          177  +  INSERT INTO t1(aa,bb,cc) VALUES('maroon','meal','lecture');
          178  +  INSERT INTO t1(aa,bb,cc) VALUES('reality','meal','catsear');
          179  +  CREATE TABLE t2(aa VARCHAR PRIMARY KEY, dd INT DEFAULT 1, ee, x VARCHAR(100));
          180  +  INSERT INTO t2(aa,dd,ee) VALUES('maroon',0,'travel'),('reality',0,'hour');
          181  +  CREATE INDEX t2x1 ON t2(dd,ee);
          182  +  ANALYZE;
          183  +  DROP TABLE IF EXISTS sqlite_stat4;
          184  +  DELETE FROM sqlite_stat1;
          185  +  INSERT INTO sqlite_stat1 VALUES
          186  +    ('t2','t2x1','3 3 3'),
          187  +    ('t2','sqlite_autoindex_t2_1','3 1'),
          188  +    ('t1','sqlite_autoindex_t1_1','2 1');
          189  +  ANALYZE sqlite_master;
          190  +  SELECT *
          191  +    FROM t1 LEFT JOIN t2 ON t1.aa=t2.aa
          192  +   WHERE t1.bb='meal'
          193  +   ORDER BY t2.dd DESC
          194  +   LIMIT 1;
          195  +} {maroon meal lecture {} maroon 0 travel {}}
          196  +do_execsql_test 710 {
          197  +  DROP TABLE t1;
          198  +  DROP TABLE t2;
          199  +  CREATE TABLE t1(aa, bb);
          200  +  INSERT INTO t1 VALUES('maroon','meal');
          201  +  CREATE TABLE t2(cc, dd, ee, x VARCHAR(100));
          202  +  INSERT INTO t2(cc,dd,ee) VALUES('maroon',1,'one');
          203  +  INSERT INTO t2(cc,dd,ee) VALUES('maroon',2,'two');
          204  +  INSERT INTO t2(cc,dd,ee) VALUES('maroon',0,'zero');
          205  +  CREATE INDEX t2ddee ON t2(dd,ee);
          206  +  CREATE INDEX t2cc ON t2(cc);
          207  +   ANALYZE;
          208  +  SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
          209  +  ORDER BY t2.dd LIMIT 1;
          210  +} {maroon 0 zero}
          211  +do_execsql_test 720 {
          212  +  SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
          213  +  WHERE t1.bb='meal'
          214  +  ORDER BY t2.dd LIMIT 1;
          215  +} {maroon 0 zero}
   169    216   
   170    217   finish_test