Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -54,10 +54,11 @@ 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 */ u8 sortFlags; /* Zero or more SORTFLAG_* bits */ + u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */ }; #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */ /* ** Delete all the content of a Select structure. Deallocate the structure @@ -587,13 +588,34 @@ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( iLimit ){ int addr; + int r1 = 0; + /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit + ** register is initialized with value of LIMIT+OFFSET.) After the sorter + ** fills up, delete the least entry in the sorter after each insert. + ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */ addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, 1); VdbeCoverage(v); sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); + if( pSort->bOrderedInnerLoop ){ + r1 = ++pParse->nMem; + sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1); + VdbeComment((v, "seq")); + } sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); + if( pSort->bOrderedInnerLoop ){ + /* If the inner loop is driven by an index such that values from + ** the same iteration of the inner loop are in sorted order, then + ** immediately jump to the next iteration of an inner loop if the + ** entry from the current iteration does not fit into the top + ** LIMIT+OFFSET entries of the sorter. */ + int iBrk = sqlite3VdbeCurrentAddr(v) + 2; + sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1); + sqlite3VdbeChangeP5(v, SQLITE_NULLEQ); + VdbeCoverage(v); + } sqlite3VdbeJumpHere(v, addr); } } /* @@ -5174,10 +5196,11 @@ if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } if( sSort.pOrderBy ){ sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo); + sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo); if( sSort.nOBSat==sSort.pOrderBy->nExpr ){ sSort.pOrderBy = 0; } } Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -2538,11 +2538,11 @@ #define WHERE_GROUPBY 0x0040 /* pOrderBy is really a GROUP BY */ #define WHERE_DISTINCTBY 0x0080 /* pOrderby is really a DISTINCT clause */ #define WHERE_WANT_DISTINCT 0x0100 /* All output needs to be distinct */ #define WHERE_SORTBYGROUP 0x0200 /* Support sqlite3WhereIsSorted() */ #define WHERE_SEEK_TABLE 0x0400 /* Do not defer seeks on main table */ - /* 0x0800 not currently used */ +#define WHERE_ORDERBY_LIMIT 0x0800 /* ORDERBY+LIMIT on the inner loop */ /* 0x1000 not currently used */ /* 0x2000 not currently used */ #define WHERE_USE_LIMIT 0x4000 /* Use the LIMIT in cost estimates */ /* 0x8000 not currently used */ @@ -3635,10 +3635,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 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 @@ -48,10 +48,22 @@ ** Return FALSE if the output needs to be sorted. */ 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. +** +** 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. +*/ +int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){ + return pWInfo->bOrderedInnerLoop; +} /* ** Return the VDBE address or label to jump to in order to continue ** immediately with the next row of a WHERE clause. */ @@ -3248,11 +3260,11 @@ */ static i8 wherePathSatisfiesOrderBy( WhereInfo *pWInfo, /* The WHERE clause */ ExprList *pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */ WherePath *pPath, /* The WherePath to check */ - u16 wctrlFlags, /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */ + u16 wctrlFlags, /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */ u16 nLoop, /* Number of entries in pPath->aLoop[] */ WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ Bitmask *pRevMask /* OUT: Mask of WhereLoops to run in reverse order */ ){ u8 revSet; /* True if rev is known */ @@ -3259,10 +3271,11 @@ u8 rev; /* Composite sort order */ u8 revIdx; /* Index sort order */ u8 isOrderDistinct; /* All prior WhereLoops are order-distinct */ u8 distinctColumns; /* True if the loop has UNIQUE NOT NULL columns */ u8 isMatch; /* iColumn matches a term of the ORDER BY clause */ + u16 eqOpMask; /* Allowed equality operators */ u16 nKeyCol; /* Number of key columns in pIndex */ u16 nColumn; /* Total number of ordered columns in the index */ u16 nOrderBy; /* Number terms in the ORDER BY clause */ int iLoop; /* Index of WhereLoop in pPath being processed */ int i, j; /* Loop counters */ @@ -3309,13 +3322,20 @@ if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */ isOrderDistinct = 1; obDone = MASKBIT(nOrderBy)-1; orderDistinctMask = 0; ready = 0; + eqOpMask = WO_EQ | WO_IS | WO_ISNULL; + if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN; for(iLoop=0; isOrderDistinct && obSat0 ) ready |= pLoop->maskSelf; - pLoop = iLoopaLoop[iLoop] : pLast; + if( iLoopaLoop[iLoop]; + if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue; + }else{ + pLoop = pLast; + } if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){ if( pLoop->u.vtab.isOrdered ) obSat = obDone; break; } iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; @@ -3329,11 +3349,11 @@ if( MASKBIT(i) & obSat ) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if( pOBExpr->op!=TK_COLUMN ) continue; if( pOBExpr->iTable!=iCur ) continue; pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn, - ~ready, WO_EQ|WO_ISNULL|WO_IS, 0); + ~ready, eqOpMask, 0); if( pTerm==0 ) continue; if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){ const char *z1, *z2; pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr); if( !pColl ) pColl = db->pDfltColl; @@ -3369,14 +3389,16 @@ rev = revSet = 0; distinctColumns = 0; for(j=0; ju.btree.nEq && pLoop->nSkip==0 - && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL|WO_IS))!=0 + && ((i = pLoop->aLTerm[j]->eOperator) & eqOpMask)!=0 ){ if( i & WO_ISNULL ){ testcase( isOrderDistinct ); isOrderDistinct = 0; } @@ -3896,12 +3918,23 @@ if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } }else{ pWInfo->nOBSat = pFrom->isOrdered; - if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0; pWInfo->revMask = pFrom->revLoop; + if( pWInfo->nOBSat<=0 ){ + pWInfo->nOBSat = 0; + if( nLoop>0 ){ + Bitmask m; + int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, + WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m); + if( rc==pWInfo->pOrderBy->nExpr ){ + pWInfo->bOrderedInnerLoop = 1; + pWInfo->revMask = m; + } + } + } } if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP) && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0 ){ Bitmask revMask = 0; Index: src/whereInt.h ================================================================== --- src/whereInt.h +++ src/whereInt.h @@ -416,12 +416,13 @@ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ u8 sorted; /* True if really sorted (not just grouped) */ u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */ u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ - u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ + u8 eDistinct; /* One of the WHERE_DISTINCT_* values */ u8 nLevel; /* Number of nested loop */ + u8 bOrderedInnerLoop; /* True if only the inner-most loop is ordered */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ int iBreak; /* Jump here to break out of the loop */ int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */ ADDED test/limit2.test Index: test/limit2.test ================================================================== --- /dev/null +++ test/limit2.test @@ -0,0 +1,82 @@ +# 2016-05-20 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing the LIMIT in combination with ORDER BY +# and in particular, the optimizations in the inner loop that cause an +# early exit of the inner loop when the LIMIT is reached and the inner +# loop is emitting rows in ORDER BY order. + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +do_execsql_test limit2-100 { + CREATE TABLE t1(a,b); + WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<1000) + INSERT INTO t1(a,b) SELECT 1, (x*17)%1000 + 1000 FROM c; + INSERT INTO t1(a,b) VALUES(2,2),(3,1006),(4,4),(5,9999); + CREATE INDEX t1ab ON t1(a,b); +} +set sqlite_search_count 0 +do_execsql_test limit2-100.1 { + SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY b LIMIT 5; +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |} +set fast_count $sqlite_search_count +set sqlite_search_count 0 +do_execsql_test limit2-100.2 { + SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY +b LIMIT 5; +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |} +do_test limit2-100.3 { + set slow_count $sqlite_search_count + expr {$fast_count < 0.02*$slow_count} +} {1} + +do_execsql_test limit2-110 { + CREATE TABLE t2(x,y); + INSERT INTO t2(x,y) VALUES('a',1),('a',2),('a',3),('a',4); + INSERT INTO t2(x,y) VALUES('b',1),('c',2),('d',3),('e',4); + CREATE INDEX t2xy ON t2(x,y); +} +set sqlite_search_count 0 +do_execsql_test limit2-110.1 { + SELECT a, b, '|' FROM t2, t1 WHERE t2.x='a' AND t1.a=t2.y ORDER BY t1.b LIMIT 5; +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |} +set fast_count $sqlite_search_count +set sqlite_search_count 0 +do_execsql_test limit2-110.2 { + SELECT a, b, '|' FROM t2, t1 WHERE t2.x='a' AND t1.a=t2.y ORDER BY +t1.b LIMIT 5; +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |} +set slow_count $sqlite_search_count +do_test limit2-110.3 { + expr {$fast_count < 0.02*$slow_count} +} {1} + +do_execsql_test limit2-120 { + DROP INDEX t1ab; + CREATE INDEX t1ab ON t1(a,b DESC); +} +set sqlite_search_count 0 +do_execsql_test limit2-120.1 { + SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY b DESC LIMIT 5; +} {5 9999 | 1 1999 | 1 1998 | 1 1997 | 1 1996 |} +set fast_count $sqlite_search_count +set sqlite_search_count 0 +do_execsql_test limit2-120.2 { + SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY +b DESC LIMIT 5; +} {5 9999 | 1 1999 | 1 1998 | 1 1997 | 1 1996 |} +do_test limit2-120.3 { + set slow_count $sqlite_search_count + expr {$fast_count < 0.02*$slow_count} +} {1} + + + +finish_test