Index: src/analyze.c ================================================================== --- src/analyze.c +++ src/analyze.c @@ -1426,14 +1426,16 @@ } pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase); if( pTable==0 ){ return 0; } - if( argv[1] ){ - pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); + if( argv[1]==0 ){ + pIndex = 0; + }else if( sqlite3_stricmp(argv[0],argv[1])==0 ){ + pIndex = sqlite3PrimaryKeyIndex(pTable); }else{ - pIndex = 0; + pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); } z = argv[2]; if( pIndex ){ decodeIntArray((char*)z, pIndex->nKeyCol+1, pIndex->aiRowEst, pIndex); Index: src/shell.c ================================================================== --- src/shell.c +++ src/shell.c @@ -1171,23 +1171,24 @@ ** ** * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent ** all opcodes that occur between the p2 jump destination and the opcode ** itself by 2 spaces. ** -** * For each "Goto", if the jump destination is a "Yield" instruction -** that occurs earlier in the program than the Goto itself, indent -** all opcodes between the "Yield" and "Goto" by 2 spaces. +** * For each "Goto", if the jump destination is a "Yield", "SeekGt", +** or "SeekLt" instruction that occurs earlier in the program than +** the Goto itself, indent all opcodes between the earlier instruction +** and "Goto" by 2 spaces. */ static void explain_data_prepare(struct callback_data *p, sqlite3_stmt *pSql){ const char *zSql; /* The text of the SQL statement */ const char *z; /* Used to check if this is an EXPLAIN */ int *abYield = 0; /* True if op is an OP_Yield */ int nAlloc = 0; /* Allocated size of p->aiIndent[], abYield */ int iOp; const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", 0 }; - const char *azYield[] = { "Yield", 0 }; + const char *azYield[] = { "Yield", "SeekLt", "SeekGt", 0 }; const char *azGoto[] = { "Goto", 0 }; /* Try to figure out if this is really an EXPLAIN statement. If this ** cannot be verified, return early. */ zSql = sqlite3_sql(pSql); Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -2420,11 +2420,11 @@ return iReg; } /* ** Generate code that will evaluate all == and IN constraints for an -** index. +** index scan. ** ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c). ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10 ** The index has as many as three equality constraints, but in this ** example, the third "c" value is an inequality. So only two @@ -2435,13 +2435,19 @@ ** In the example above nEq==2. But this subroutine works for any value ** of nEq including 0. If nEq==0, this routine is nearly a no-op. ** The only thing it does is allocate the pLevel->iMem memory cell and ** compute the affinity string. ** -** This routine always allocates at least one memory cell and returns -** the index of that memory cell. The code that -** calls this routine will use that memory cell to store the termination +** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints +** are == or IN and are covered by the nEq. nExtraReg is 1 if there is +** an inequality constraint (such as the "c>=5 AND c<10" in the example) that +** occurs after the nEq quality constraints. +** +** This routine allocates a range of nEq+nExtraReg memory cells and returns +** the index of the first memory cell in that range. The code that +** calls this routine will use that memory range to store keys for +** start and termination conditions of the loop. ** key value of the loop. If one or more IN operators appear, then ** this routine allocates an additional nEq memory cells for internal ** use. ** ** Before returning, *pzAff is set to point to a buffer containing a @@ -2464,11 +2470,12 @@ WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ int bRev, /* Reverse the order of IN operators */ int nExtraReg, /* Number of extra registers to allocate */ char **pzAff /* OUT: Set to point to affinity string */ ){ - int nEq; /* The number of == or IN constraints to code */ + u16 nEq; /* The number of == or IN constraints to code */ + u16 nSkip; /* Number of left-most columns to skip */ Vdbe *v = pParse->pVdbe; /* The vm under construction */ Index *pIdx; /* The index being used for this loop */ WhereTerm *pTerm; /* A single constraint term */ WhereLoop *pLoop; /* The WhereLoop object */ int j; /* Loop counter */ @@ -2478,10 +2485,11 @@ /* This module is only called on query plans that use an index. */ pLoop = pLevel->pWLoop; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); nEq = pLoop->u.btree.nEq; + nSkip = pLoop->u.btree.nSkip; pIdx = pLoop->u.btree.pIndex; assert( pIdx!=0 ); /* Figure out how many memory cells we will need then allocate them. */ @@ -2491,19 +2499,34 @@ zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx)); if( !zAff ){ pParse->db->mallocFailed = 1; } + + if( nSkip ){ + int iIdxCur = pLevel->iIdxCur; + sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur); + VdbeComment((v, "begin skip-scan on %s", pIdx->zName)); + j = sqlite3VdbeAddOp0(v, OP_Goto); + pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLt:OP_SeekGt), + iIdxCur, 0, regBase, nSkip); + sqlite3VdbeJumpHere(v, j); + for(j=0; jaiColumn[j]>=0 ); + VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName)); + } + } /* Evaluate the equality constraints */ assert( zAff==0 || (int)strlen(zAff)>=nEq ); - for(j=0; jaLTerm[j]; assert( pTerm!=0 ); - /* The following true for indices with redundant columns. + /* The following testcase is true for indices with redundant columns. ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j); if( r1!=regBase+j ){ @@ -2573,11 +2596,12 @@ ** It is the responsibility of the caller to free the buffer when it is ** no longer required. */ static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){ Index *pIndex = pLoop->u.btree.pIndex; - int nEq = pLoop->u.btree.nEq; + u16 nEq = pLoop->u.btree.nEq; + u16 nSkip = pLoop->u.btree.nSkip; int i, j; Column *aCol = pTab->aCol; i16 *aiColumn = pIndex->aiColumn; StrAccum txt; @@ -2587,11 +2611,18 @@ sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH); txt.db = db; sqlite3StrAccumAppend(&txt, " (", 2); for(i=0; inKeyCol ) ? "rowid" : aCol[aiColumn[i]].zName; - explainAppendTerm(&txt, i, z, "="); + if( i>=nSkip ){ + explainAppendTerm(&txt, i, z, "="); + }else{ + if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5); + sqlite3StrAccumAppend(&txt, "ANY(", 4); + sqlite3StrAccumAppend(&txt, z, -1); + sqlite3StrAccumAppend(&txt, ")", 1); + } } j = i; if( pLoop->wsFlags&WHERE_BTM_LIMIT ){ char *z = (j==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[j]].zName; @@ -2953,12 +2984,13 @@ static const u8 aEndOp[] = { OP_Noop, /* 0: (!end_constraints) */ OP_IdxGE, /* 1: (end_constraints && !bRev) */ OP_IdxLT /* 2: (end_constraints && bRev) */ }; - int nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ - int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */ + u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ + u16 nSkip = pLoop->u.btree.nSkip; /* Number of left index terms to skip */ + int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */ int regBase; /* Base register holding constraint values */ int r1; /* Temp register */ WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ int startEq; /* True if range start uses ==, >= or <= */ @@ -2972,10 +3004,11 @@ char *zStartAff; /* Affinity for start of range constraint */ char *zEndAff; /* Affinity for end of range constraint */ pIdx = pLoop->u.btree.pIndex; iIdxCur = pLevel->iIdxCur; + assert( nEq>=nSkip ); /* If this loop satisfies a sort order (pOrderBy) request that ** was passed to this function to implement a "SELECT min(x) ..." ** query, then the caller will only allow the loop to run for ** a single iteration. This means that the first row returned @@ -2985,12 +3018,11 @@ */ if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0 && (pWInfo->bOBSat!=0) && (pIdx->nKeyCol>nEq) ){ - /* assert( pOrderBy->nExpr==1 ); */ - /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */ + assert( nSkip==0 ); isMinQuery = 1; nExtraReg = 1; } /* Find any inequality constraint terms for the start and end @@ -3537,10 +3569,11 @@ int i; Vdbe *v = pWInfo->pParse->pVdbe; sqlite3ExplainBegin(v); for(i=0; inLTerm; i++){ WhereTerm *pTerm = p->aLTerm[i]; + if( pTerm==0 ) continue; sqlite3ExplainPrintf(v, " (%d) #%-2d ", i+1, (int)(pTerm-pWC->a)); sqlite3ExplainPush(v); whereExplainTerm(v, pTerm); sqlite3ExplainPop(v); sqlite3ExplainNL(v); @@ -3820,10 +3853,11 @@ if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break; if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue; if( (pTerm->prereqAll & notAllowed)!=0 ) continue; for(j=pLoop->nLTerm-1; j>=0; j--){ pX = pLoop->aLTerm[j]; + if( pX==0 ) continue; if( pX==pTerm ) break; if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } if( j<0 ) pLoop->nOut += pTerm->truthProb; } @@ -3849,11 +3883,12 @@ WhereTerm *pTerm; /* A WhereTerm under consideration */ int opMask; /* Valid operators for constraints */ WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ - int saved_nEq; /* Original value of pNew->u.btree.nEq */ + u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ + u16 saved_nSkip; /* Original value of pNew->u.btree.nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ int iCol; /* Index of the column in the table */ int rc = SQLITE_OK; /* Return code */ LogEst nRowEst; /* Estimated index selectivity */ @@ -3884,16 +3919,30 @@ nRowEst = 0; } pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; + saved_nSkip = pNew->u.btree.nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0])); + if( pTerm==0 + && saved_nEq==saved_nSkip + && saved_nEq+1nKeyCol + && pProbe->aiRowEst[saved_nEq+1]>50 + ){ + LogEst nIter; + pNew->u.btree.nEq++; + pNew->u.btree.nSkip++; + pNew->aLTerm[pNew->nLTerm++] = 0; + pNew->wsFlags |= WHERE_SKIPSCAN; + nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]); + whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter); + } for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nRecValid = pBuilder->nRecValid; #endif @@ -3925,12 +3974,14 @@ } pNew->rRun += nIn; pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ - assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0 - || nInMul==0 ); + assert( + (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0 + || nInMul==0 + ); pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (pProbe->onError!=OE_None && nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1) ){ @@ -4007,10 +4058,11 @@ pBuilder->nRecValid = nRecValid; #endif } pNew->prereq = saved_prereq; pNew->u.btree.nEq = saved_nEq; + pNew->u.btree.nSkip = saved_nSkip; pNew->wsFlags = saved_wsFlags; pNew->nOut = saved_nOut; pNew->nLTerm = saved_nLTerm; return rc; } @@ -4153,10 +4205,11 @@ WhereTerm *pWCEnd = pWC->a + pWC->nTerm; for(pTerm=pWC->a; rc==SQLITE_OK && pTermprereqRight & pNew->maskSelf ) continue; if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; + pNew->u.btree.nSkip = 0; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; /* TUNING: One-time cost for computing the automatic index is ** approximately 7*N*log2(N) where N is the number of rows in @@ -4182,10 +4235,11 @@ if( pProbe->pPartIdxWhere!=0 && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){ continue; /* Partial index inappropriate for this query */ } pNew->u.btree.nEq = 0; + pNew->u.btree.nSkip = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = 0; pNew->prereq = mExtra; pNew->nOut = rSize; @@ -4716,10 +4770,11 @@ for(j=0; ju.btree.nEq + && pLoop->u.btree.nSkip==0 && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0 ){ if( i & WO_ISNULL ){ testcase( isOrderDistinct ); isOrderDistinct = 0; @@ -5141,10 +5196,11 @@ if( pItem->zIndex ) return 0; iCur = pItem->iCursor; pWC = &pWInfo->sWC; pLoop = pBuilder->pNew; pLoop->wsFlags = 0; + pLoop->u.btree.nSkip = 0; pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; @@ -5714,10 +5770,11 @@ /* Generate loop termination code. */ VdbeNoopComment((v, "End WHERE-core")); sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ + int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2); @@ -5733,12 +5790,17 @@ sqlite3VdbeJumpHere(v, pIn->addrInTop-1); } sqlite3DbFree(db, pLevel->u.in.aInLoop); } sqlite3VdbeResolveLabel(v, pLevel->addrBrk); + if( pLevel->addrSkip ){ + sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip); + VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); + sqlite3VdbeJumpHere(v, pLevel->addrSkip); + sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); + } if( pLevel->iLeftJoin ){ - int addr; addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || (pLoop->wsFlags & WHERE_INDEXED)!=0 ); if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){ sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor); Index: src/whereInt.h ================================================================== --- src/whereInt.h +++ src/whereInt.h @@ -63,10 +63,11 @@ int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to access pIdx */ int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ + int addrSkip; /* Jump here for next iteration of skip-scan */ int addrCont; /* Jump here to continue with the next loop cycle */ int addrFirst; /* First instruction of interior of the loop */ int addrBody; /* Beginning of the body of this loop */ u8 iFrom; /* Which entry in the FROM clause */ u8 op, p5; /* Opcode and P5 of the opcode that ends the loop */ @@ -453,5 +454,6 @@ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ +#define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ ADDED test/skipscan1.test Index: test/skipscan1.test ================================================================== --- /dev/null +++ test/skipscan1.test @@ -0,0 +1,190 @@ +# 2013-11-13 +# +# 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 tests of the "skip-scan" query strategy. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +do_execsql_test skipscan1-1.1 { + CREATE TABLE t1(a TEXT, b INT, c INT, d INT); + CREATE INDEX t1abc ON t1(a,b,c); + INSERT INTO t1 VALUES('abc',123,4,5); + INSERT INTO t1 VALUES('abc',234,5,6); + INSERT INTO t1 VALUES('abc',234,6,7); + INSERT INTO t1 VALUES('abc',345,7,8); + INSERT INTO t1 VALUES('def',567,8,9); + INSERT INTO t1 VALUES('def',345,9,10); + INSERT INTO t1 VALUES('bcd',100,6,11); + + /* Fake the sqlite_stat1 table so that the query planner believes + ** the table contains thousands of rows and that the first few + ** columns are not selective. */ + ANALYZE; + DELETE FROM sqlite_stat1; + INSERT INTO sqlite_stat1 VALUES('t1','t1abc','10000 5000 2000 10'); + ANALYZE sqlite_master; +} {} + +# Simple queries that leave the first one or two columns of the +# index unconstrainted. +# +do_execsql_test skipscan1-1.2 { + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; +} {abc 345 7 8 | def 345 9 10 |} +do_execsql_test skipscan1-1.2eqp { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; +} {/* USING INDEX t1abc (ANY(a) AND b=?)*/} +do_execsql_test skipscan1-1.2sort { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; +} {~/*ORDER BY*/} + +do_execsql_test skipscan1-1.3 { + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a DESC; +} {def 345 9 10 | abc 345 7 8 |} +do_execsql_test skipscan1-1.3eqp { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; +} {/* USING INDEX t1abc (ANY(a) AND b=?)*/} +do_execsql_test skipscan1-1.3sort { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; +} {~/*ORDER BY*/} + +do_execsql_test skipscan1-1.4 { + SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; +} {abc 234 6 7 | bcd 100 6 11 |} +do_execsql_test skipscan1-1.4eqp { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} +do_execsql_test skipscan1-1.4sort { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; +} {~/*ORDER BY*/} + +do_execsql_test skipscan1-1.5 { + SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; +} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |} +do_execsql_test skipscan1-1.5eqp { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} +do_execsql_test skipscan1-1.5sort { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; +} {~/*ORDER BY*/} + +do_execsql_test skipscan1-1.6 { + SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c; +} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |} +do_execsql_test skipscan1-1.6eqp { + EXPLAIN QUERY PLAN + SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c; +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c>? AND c? AND c