Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -66,12 +66,12 @@ int iECursor; /* Cursor number for the sorter */ int regReturn; /* Register holding block-output return address */ int labelBkOut; /* Start label for the block-output subroutine */ int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */ int labelDone; /* Jump here when done, ex: LIMIT reached */ + int labelOBLopt; /* Jump here when sorter is full */ u8 sortFlags; /* Zero or more SORTFLAG_* bits */ - u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */ #ifdef SQLITE_ENABLE_SORTER_REFERENCES u8 nDefer; /* Number of valid entries in aDefer[] */ struct DeferredCsr { Table *pTab; /* Table definition */ int iCsr; /* Cursor number for table */ @@ -691,14 +691,14 @@ ** are already LIMIT+OFFSET items in the sorter, delete the largest ** entry before inserting the new one. This way there are never more ** than LIMIT+OFFSET items in the sorter. ** ** If the new record does not need to be inserted into the sorter, - ** jump to the next iteration of the loop. Or, if the - ** pSort->bOrderedInnerLoop flag is set to indicate that the inner - ** loop delivers items in sorted order, jump to the next iteration - ** of the outer loop. + ** jump to the next iteration of the loop. If the pSort->labelOBLopt + ** value is not zero, then it is a label of where to jump. Otherwise, + ** just bypass the row insert logic. See the header comment on the + ** sqlite3WhereOrderByLimitOptLabel() function for additional info. */ int iCsr = pSort->iECursor; sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0); @@ -716,13 +716,12 @@ op = OP_IdxInsert; } sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord, regBase+nOBSat, nBase-nOBSat); if( iSkip ){ - assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 ); sqlite3VdbeChangeP2(v, iSkip, - sqlite3VdbeCurrentAddr(v) + pSort->bOrderedInnerLoop); + pSort->labelOBLopt ? pSort->labelOBLopt : sqlite3VdbeCurrentAddr(v)); } } /* ** Add code to implement the OFFSET @@ -6058,11 +6057,11 @@ if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } if( sSort.pOrderBy ){ sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo); - sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo); + sSort.labelOBLopt = sqlite3WhereOrderByLimitOptLabel(pWInfo); if( sSort.nOBSat==sSort.pOrderBy->nExpr ){ sSort.pOrderBy = 0; } } Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -3921,11 +3921,11 @@ WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); LogEst sqlite3WhereOutputRowCount(WhereInfo*); int sqlite3WhereIsDistinct(WhereInfo*); int sqlite3WhereIsOrdered(WhereInfo*); -int sqlite3WhereOrderedInnerLoop(WhereInfo*); +int sqlite3WhereOrderByLimitOptLabel(WhereInfo*); int sqlite3WhereIsSorted(WhereInfo*); int sqlite3WhereContinueLabel(WhereInfo*); int sqlite3WhereBreakLabel(WhereInfo*); int sqlite3WhereOkOnePass(WhereInfo*, int*); #define ONEPASS_OFF 0 /* Use of ONEPASS not allowed */ Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -65,19 +65,42 @@ int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ return pWInfo->nOBSat; } /* -** Return TRUE if the innermost loop of the WHERE clause implementation -** returns rows in ORDER BY order for complete run of the inner loop. +** In the ORDER BY LIMIT optimization, if the inner-most loop is known +** to emit rows in increasing order, and if the last row emitted by the +** inner-most loop did not fit within the sorter, then we can skip all +** subsequent rows for the current iteration of the inner loop (because they +** will not fit in the sorter either) and continue with the second inner +** loop - the loop immediately outside the inner-most. ** -** Across multiple iterations of outer loops, the output rows need not be -** sorted. As long as rows are sorted for just the innermost loop, this -** routine can return TRUE. +** When a row does not fit in the sorter (because the sorter already +** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the +** label returned by this function. +** +** If the ORDER BY LIMIT optimization applies, the jump destination should +** be the continuation for the second-inner-most loop. If the ORDER BY +** LIMIT optimization does not apply, then the jump destination should +** be the continuation for the inner-most loop. +** +** It is always safe for this routine to return the continuation of the +** inner-most loop, in the sense that a correct answer will result. +** Returning the continuation the second inner loop is an optimization +** that might make the code run a little faster, but should not change +** the final answer. */ -int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){ - return pWInfo->bOrderedInnerLoop; +int sqlite3WhereOrderByLimitOptLabel(WhereInfo *pWInfo){ + WhereLevel *pInner; + if( !pWInfo->bOrderedInnerLoop ){ + /* The ORDER BY LIMIT optimization does not apply. Jump to the + ** continuation of the inner-most loop. */ + return pWInfo->iContinue; + } + pInner = &pWInfo->a[pWInfo->nLevel-1]; + if( pInner->addrNxt ) return pInner->addrNxt; + return pInner->addrBrk; } /* ** Return the VDBE address or label to jump to in order to continue ** immediately with the next row of a WHERE clause. @@ -4246,10 +4269,11 @@ WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used); if( rc==pWInfo->pResultSet->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } } + pWInfo->bOrderedInnerLoop = 0; if( pWInfo->pOrderBy ){ if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } Index: test/limit2.test ================================================================== --- test/limit2.test +++ test/limit2.test @@ -164,7 +164,54 @@ DROP TABLE IF EXISTS t2; CREATE TABLE t2(x, y); INSERT INTO t2 VALUES(1,3); CREATE INDEX t1ab ON t1(a,b); SELECT y FROM t1, t2 WHERE a=x AND b<=y ORDER BY b DESC; } {3} + +# Ticket https://www.sqlite.org/src/info/9936b2fa443fec03 2018-09-08 +# Infinite loop due to the ORDER BY LIMIT optimization. +# +do_execsql_test 700 { + DROP TABLE IF EXISTS t1; + DROP TABLE IF EXISTS t2; + CREATE TABLE t1(aa VARCHAR PRIMARY KEY NOT NULL,bb,cc,x VARCHAR(400)); + INSERT INTO t1(aa,bb,cc) VALUES('maroon','meal','lecture'); + INSERT INTO t1(aa,bb,cc) VALUES('reality','meal','catsear'); + CREATE TABLE t2(aa VARCHAR PRIMARY KEY, dd INT DEFAULT 1, ee, x VARCHAR(100)); + INSERT INTO t2(aa,dd,ee) VALUES('maroon',0,'travel'),('reality',0,'hour'); + CREATE INDEX t2x1 ON t2(dd,ee); + ANALYZE; + DROP TABLE IF EXISTS sqlite_stat4; + DELETE FROM sqlite_stat1; + INSERT INTO sqlite_stat1 VALUES + ('t2','t2x1','3 3 3'), + ('t2','sqlite_autoindex_t2_1','3 1'), + ('t1','sqlite_autoindex_t1_1','2 1'); + ANALYZE sqlite_master; + SELECT * + FROM t1 LEFT JOIN t2 ON t1.aa=t2.aa + WHERE t1.bb='meal' + ORDER BY t2.dd DESC + LIMIT 1; +} {maroon meal lecture {} maroon 0 travel {}} +do_execsql_test 710 { + DROP TABLE t1; + DROP TABLE t2; + CREATE TABLE t1(aa, bb); + INSERT INTO t1 VALUES('maroon','meal'); + CREATE TABLE t2(cc, dd, ee, x VARCHAR(100)); + INSERT INTO t2(cc,dd,ee) VALUES('maroon',1,'one'); + INSERT INTO t2(cc,dd,ee) VALUES('maroon',2,'two'); + INSERT INTO t2(cc,dd,ee) VALUES('maroon',0,'zero'); + CREATE INDEX t2ddee ON t2(dd,ee); + CREATE INDEX t2cc ON t2(cc); + ANALYZE; + SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc + ORDER BY t2.dd LIMIT 1; +} {maroon 0 zero} +do_execsql_test 720 { + SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc + WHERE t1.bb='meal' + ORDER BY t2.dd LIMIT 1; +} {maroon 0 zero} finish_test