/ Check-in [27dd5993]
Login

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

Overview
Comment:Add the ability to use an index even if the left-most columns of the index are unconstrainted, provided that the left-most columns have few distinct values.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | skip-scan
Files: files | file ages | folders
SHA1: 27dd5993d1ae5625eb94bf406421eb390d001be9
User & Date: drh 2013-11-13 12:27:25
Context
2013-11-13
15:32
Add test cases for skip-scan. Enhance "do_test" so that if the expected result is of the form "/*..*/" or "~/*..*/" it treats the expected result as a glob pattern rather than as a regular expression. Fix a bug in ANALYZE result loading associated with WITHOUT ROWID tables. check-in: d3e6e9b2 user: drh tags: skip-scan
12:27
Add the ability to use an index even if the left-most columns of the index are unconstrainted, provided that the left-most columns have few distinct values. check-in: 27dd5993 user: drh tags: skip-scan
08:55
Avoid an unnecessary OP_IfNull while doing an indexed search. check-in: 51960009 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  2418   2418     }
  2419   2419     disableTerm(pLevel, pTerm);
  2420   2420     return iReg;
  2421   2421   }
  2422   2422   
  2423   2423   /*
  2424   2424   ** Generate code that will evaluate all == and IN constraints for an
  2425         -** index.
         2425  +** index scan.
  2426   2426   **
  2427   2427   ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
  2428   2428   ** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
  2429   2429   ** The index has as many as three equality constraints, but in this
  2430   2430   ** example, the third "c" value is an inequality.  So only two 
  2431   2431   ** constraints are coded.  This routine will generate code to evaluate
  2432   2432   ** a==5 and b IN (1,2,3).  The current values for a and b will be stored
................................................................................
  2433   2433   ** in consecutive registers and the index of the first register is returned.
  2434   2434   **
  2435   2435   ** In the example above nEq==2.  But this subroutine works for any value
  2436   2436   ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
  2437   2437   ** The only thing it does is allocate the pLevel->iMem memory cell and
  2438   2438   ** compute the affinity string.
  2439   2439   **
  2440         -** This routine always allocates at least one memory cell and returns
  2441         -** the index of that memory cell. The code that
  2442         -** calls this routine will use that memory cell to store the termination
         2440  +** The nExtraReg parameter is 0 or 1.  It is 0 if all WHERE clause constraints
         2441  +** are == or IN and are covered by the nEq.  nExtraReg is 1 if there is
         2442  +** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
         2443  +** occurs after the nEq quality constraints.
         2444  +**
         2445  +** This routine allocates a range of nEq+nExtraReg memory cells and returns
         2446  +** the index of the first memory cell in that range. The code that
         2447  +** calls this routine will use that memory range to store keys for
         2448  +** start and termination conditions of the loop.
  2443   2449   ** key value of the loop.  If one or more IN operators appear, then
  2444   2450   ** this routine allocates an additional nEq memory cells for internal
  2445   2451   ** use.
  2446   2452   **
  2447   2453   ** Before returning, *pzAff is set to point to a buffer containing a
  2448   2454   ** copy of the column affinity string of the index allocated using
  2449   2455   ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
................................................................................
  2462   2468   static int codeAllEqualityTerms(
  2463   2469     Parse *pParse,        /* Parsing context */
  2464   2470     WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  2465   2471     int bRev,             /* Reverse the order of IN operators */
  2466   2472     int nExtraReg,        /* Number of extra registers to allocate */
  2467   2473     char **pzAff          /* OUT: Set to point to affinity string */
  2468   2474   ){
  2469         -  int nEq;                      /* The number of == or IN constraints to code */
         2475  +  u16 nEq;                      /* The number of == or IN constraints to code */
         2476  +  u16 nSkip;                    /* Number of left-most columns to skip */
  2470   2477     Vdbe *v = pParse->pVdbe;      /* The vm under construction */
  2471   2478     Index *pIdx;                  /* The index being used for this loop */
  2472   2479     WhereTerm *pTerm;             /* A single constraint term */
  2473   2480     WhereLoop *pLoop;             /* The WhereLoop object */
  2474   2481     int j;                        /* Loop counter */
  2475   2482     int regBase;                  /* Base register */
  2476   2483     int nReg;                     /* Number of registers to allocate */
  2477   2484     char *zAff;                   /* Affinity string to return */
  2478   2485   
  2479   2486     /* This module is only called on query plans that use an index. */
  2480   2487     pLoop = pLevel->pWLoop;
  2481   2488     assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
  2482   2489     nEq = pLoop->u.btree.nEq;
         2490  +  nSkip = pLoop->u.btree.nSkip;
  2483   2491     pIdx = pLoop->u.btree.pIndex;
  2484   2492     assert( pIdx!=0 );
  2485   2493   
  2486   2494     /* Figure out how many memory cells we will need then allocate them.
  2487   2495     */
  2488   2496     regBase = pParse->nMem + 1;
  2489   2497     nReg = pLoop->u.btree.nEq + nExtraReg;
  2490   2498     pParse->nMem += nReg;
  2491   2499   
  2492   2500     zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  2493   2501     if( !zAff ){
  2494   2502       pParse->db->mallocFailed = 1;
  2495   2503     }
         2504  +
         2505  +  if( nSkip ){
         2506  +    int iIdxCur = pLevel->iIdxCur;
         2507  +    sqlite3VdbeAddOp2(v, (bRev?OP_Last:OP_Rewind), iIdxCur, pLevel->addrNxt);
         2508  +    pLevel->addrSkip = sqlite3VdbeCurrentAddr(v);
         2509  +    pLevel->opSkip = bRev ? OP_SeekLt : OP_SeekGt;
         2510  +    pLevel->p3Skip = regBase;
         2511  +    pLevel->p4Skip = nSkip;
         2512  +    for(j=0; j<nSkip; j++){
         2513  +      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
         2514  +      assert( pIdx->aiColumn[j]>=0 );
         2515  +      VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName));
         2516  +    }
         2517  +  }    
  2496   2518   
  2497   2519     /* Evaluate the equality constraints
  2498   2520     */
  2499   2521     assert( zAff==0 || (int)strlen(zAff)>=nEq );
  2500         -  for(j=0; j<nEq; j++){
         2522  +  for(j=nSkip; j<nEq; j++){
  2501   2523       int r1;
  2502   2524       pTerm = pLoop->aLTerm[j];
  2503   2525       assert( pTerm!=0 );
  2504         -    /* The following true for indices with redundant columns. 
         2526  +    /* The following testcase is true for indices with redundant columns. 
  2505   2527       ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
  2506   2528       testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
  2507   2529       testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2508   2530       r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
  2509   2531       if( r1!=regBase+j ){
  2510   2532         if( nReg==1 ){
  2511   2533           sqlite3ReleaseTempReg(pParse, regBase);
................................................................................
  2571   2593   **
  2572   2594   ** The returned pointer points to memory obtained from sqlite3DbMalloc().
  2573   2595   ** It is the responsibility of the caller to free the buffer when it is
  2574   2596   ** no longer required.
  2575   2597   */
  2576   2598   static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){
  2577   2599     Index *pIndex = pLoop->u.btree.pIndex;
  2578         -  int nEq = pLoop->u.btree.nEq;
         2600  +  u16 nEq = pLoop->u.btree.nEq;
         2601  +  u16 nSkip = pLoop->u.btree.nSkip;
  2579   2602     int i, j;
  2580   2603     Column *aCol = pTab->aCol;
  2581   2604     i16 *aiColumn = pIndex->aiColumn;
  2582   2605     StrAccum txt;
  2583   2606   
  2584   2607     if( nEq==0 && (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
  2585   2608       return 0;
  2586   2609     }
  2587   2610     sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
  2588   2611     txt.db = db;
  2589   2612     sqlite3StrAccumAppend(&txt, " (", 2);
  2590   2613     for(i=0; i<nEq; i++){
  2591   2614       char *z = (i==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[i]].zName;
  2592         -    explainAppendTerm(&txt, i, z, "=");
         2615  +    if( i>=nSkip ){
         2616  +      explainAppendTerm(&txt, i, z, "=");
         2617  +    }else{
         2618  +      if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5);
         2619  +      sqlite3StrAccumAppend(&txt, "ANY(", 4);
         2620  +      sqlite3StrAccumAppend(&txt, z, -1);
         2621  +      sqlite3StrAccumAppend(&txt, ")", 1);
         2622  +    }
  2593   2623     }
  2594   2624   
  2595   2625     j = i;
  2596   2626     if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
  2597   2627       char *z = (j==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[j]].zName;
  2598   2628       explainAppendTerm(&txt, i++, z, ">");
  2599   2629     }
................................................................................
  2948   2978         OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
  2949   2979       };
  2950   2980       static const u8 aEndOp[] = {
  2951   2981         OP_Noop,             /* 0: (!end_constraints) */
  2952   2982         OP_IdxGE,            /* 1: (end_constraints && !bRev) */
  2953   2983         OP_IdxLT             /* 2: (end_constraints && bRev) */
  2954   2984       };
  2955         -    int nEq = pLoop->u.btree.nEq;  /* Number of == or IN terms */
  2956         -    int isMinQuery = 0;            /* If this is an optimized SELECT min(x).. */
         2985  +    u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
         2986  +    u16 nSkip = pLoop->u.btree.nSkip; /* Number of left index terms to skip */
         2987  +    int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
  2957   2988       int regBase;                 /* Base register holding constraint values */
  2958   2989       int r1;                      /* Temp register */
  2959   2990       WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  2960   2991       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  2961   2992       int startEq;                 /* True if range start uses ==, >= or <= */
  2962   2993       int endEq;                   /* True if range end uses ==, >= or <= */
  2963   2994       int start_constraints;       /* Start of range is constrained */
................................................................................
  2967   2998       int nExtraReg = 0;           /* Number of extra registers needed */
  2968   2999       int op;                      /* Instruction opcode */
  2969   3000       char *zStartAff;             /* Affinity for start of range constraint */
  2970   3001       char *zEndAff;               /* Affinity for end of range constraint */
  2971   3002   
  2972   3003       pIdx = pLoop->u.btree.pIndex;
  2973   3004       iIdxCur = pLevel->iIdxCur;
         3005  +    assert( nEq>=nSkip );
  2974   3006   
  2975   3007       /* If this loop satisfies a sort order (pOrderBy) request that 
  2976   3008       ** was passed to this function to implement a "SELECT min(x) ..." 
  2977   3009       ** query, then the caller will only allow the loop to run for
  2978   3010       ** a single iteration. This means that the first row returned
  2979   3011       ** should not have a NULL value stored in 'x'. If column 'x' is
  2980   3012       ** the first one after the nEq equality constraints in the index,
  2981   3013       ** this requires some special handling.
  2982   3014       */
  2983   3015       if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
  2984   3016        && (pWInfo->bOBSat!=0)
  2985   3017        && (pIdx->nKeyCol>nEq)
  2986   3018       ){
  2987         -      /* assert( pOrderBy->nExpr==1 ); */
  2988         -      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
         3019  +      assert( nSkip==0 );
  2989   3020         isMinQuery = 1;
  2990   3021         nExtraReg = 1;
  2991   3022       }
  2992   3023   
  2993   3024       /* Find any inequality constraint terms for the start and end 
  2994   3025       ** of the range. 
  2995   3026       */
................................................................................
  3532   3563     */
  3533   3564     if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){  /* WHERETRACE 0x100 */
  3534   3565       int i;
  3535   3566       Vdbe *v = pWInfo->pParse->pVdbe;
  3536   3567       sqlite3ExplainBegin(v);
  3537   3568       for(i=0; i<p->nLTerm; i++){
  3538   3569         WhereTerm *pTerm = p->aLTerm[i];
         3570  +      if( pTerm==0 ) continue;
  3539   3571         sqlite3ExplainPrintf(v, "  (%d) #%-2d ", i+1, (int)(pTerm-pWC->a));
  3540   3572         sqlite3ExplainPush(v);
  3541   3573         whereExplainTerm(v, pTerm);
  3542   3574         sqlite3ExplainPop(v);
  3543   3575         sqlite3ExplainNL(v);
  3544   3576       }
  3545   3577       sqlite3ExplainFinish(v);
................................................................................
  3844   3876     sqlite3 *db = pParse->db;       /* Database connection malloc context */
  3845   3877     WhereLoop *pNew;                /* Template WhereLoop under construction */
  3846   3878     WhereTerm *pTerm;               /* A WhereTerm under consideration */
  3847   3879     int opMask;                     /* Valid operators for constraints */
  3848   3880     WhereScan scan;                 /* Iterator for WHERE terms */
  3849   3881     Bitmask saved_prereq;           /* Original value of pNew->prereq */
  3850   3882     u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
  3851         -  int saved_nEq;                  /* Original value of pNew->u.btree.nEq */
         3883  +  u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
         3884  +  u16 saved_nSkip;                /* Original value of pNew->u.btree.nSkip */
  3852   3885     u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  3853   3886     LogEst saved_nOut;              /* Original value of pNew->nOut */
  3854   3887     int iCol;                       /* Index of the column in the table */
  3855   3888     int rc = SQLITE_OK;             /* Return code */
  3856   3889     LogEst nRowEst;                 /* Estimated index selectivity */
  3857   3890     LogEst rLogSize;                /* Logarithm of table size */
  3858   3891     WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */
................................................................................
  3879   3912     }else{
  3880   3913       iCol = -1;
  3881   3914       nRowEst = 0;
  3882   3915     }
  3883   3916     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  3884   3917                           opMask, pProbe);
  3885   3918     saved_nEq = pNew->u.btree.nEq;
         3919  +  saved_nSkip = pNew->u.btree.nSkip;
  3886   3920     saved_nLTerm = pNew->nLTerm;
  3887   3921     saved_wsFlags = pNew->wsFlags;
  3888   3922     saved_prereq = pNew->prereq;
  3889   3923     saved_nOut = pNew->nOut;
  3890   3924     pNew->rSetup = 0;
  3891   3925     rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
         3926  +  if( pTerm==0
         3927  +   && saved_nEq==saved_nSkip
         3928  +   && saved_nEq+1<pProbe->nKeyCol
         3929  +   && pProbe->aiRowEst[saved_nEq+1]>50
         3930  +  ){
         3931  +    pNew->u.btree.nEq++;
         3932  +    pNew->u.btree.nSkip++;
         3933  +    pNew->aLTerm[pNew->nLTerm++] = 0;
         3934  +    pNew->wsFlags |= WHERE_SKIP_SCAN;
         3935  +    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul);
         3936  +  }
  3892   3937     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  3893   3938       int nIn = 0;
  3894   3939   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  3895   3940       int nRecValid = pBuilder->nRecValid;
  3896   3941   #endif
  3897   3942       if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
  3898   3943        && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
................................................................................
  4002   4047       pNew->nOut = saved_nOut;
  4003   4048   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  4004   4049       pBuilder->nRecValid = nRecValid;
  4005   4050   #endif
  4006   4051     }
  4007   4052     pNew->prereq = saved_prereq;
  4008   4053     pNew->u.btree.nEq = saved_nEq;
         4054  +  pNew->u.btree.nSkip = saved_nSkip;
  4009   4055     pNew->wsFlags = saved_wsFlags;
  4010   4056     pNew->nOut = saved_nOut;
  4011   4057     pNew->nLTerm = saved_nLTerm;
  4012   4058     return rc;
  4013   4059   }
  4014   4060   
  4015   4061   /*
................................................................................
  4148   4194       /* Generate auto-index WhereLoops */
  4149   4195       WhereTerm *pTerm;
  4150   4196       WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
  4151   4197       for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
  4152   4198         if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4153   4199         if( termCanDriveIndex(pTerm, pSrc, 0) ){
  4154   4200           pNew->u.btree.nEq = 1;
         4201  +        pNew->u.btree.nSkip = 0;
  4155   4202           pNew->u.btree.pIndex = 0;
  4156   4203           pNew->nLTerm = 1;
  4157   4204           pNew->aLTerm[0] = pTerm;
  4158   4205           /* TUNING: One-time cost for computing the automatic index is
  4159   4206           ** approximately 7*N*log2(N) where N is the number of rows in
  4160   4207           ** the table being indexed. */
  4161   4208           pNew->rSetup = rLogSize + rSize + 28;  assert( 28==sqlite3LogEst(7) );
................................................................................
  4177   4224     */
  4178   4225     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  4179   4226       if( pProbe->pPartIdxWhere!=0
  4180   4227        && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
  4181   4228         continue;  /* Partial index inappropriate for this query */
  4182   4229       }
  4183   4230       pNew->u.btree.nEq = 0;
         4231  +    pNew->u.btree.nSkip = 0;
  4184   4232       pNew->nLTerm = 0;
  4185   4233       pNew->iSortIdx = 0;
  4186   4234       pNew->rSetup = 0;
  4187   4235       pNew->prereq = mExtra;
  4188   4236       pNew->nOut = rSize;
  4189   4237       pNew->u.btree.pIndex = pProbe;
  4190   4238       b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
................................................................................
  4711   4759         rev = revSet = 0;
  4712   4760         distinctColumns = 0;
  4713   4761         for(j=0; j<nColumn; j++){
  4714   4762           u8 bOnce;   /* True to run the ORDER BY search loop */
  4715   4763   
  4716   4764           /* Skip over == and IS NULL terms */
  4717   4765           if( j<pLoop->u.btree.nEq
         4766  +         && pLoop->u.btree.nSkip==0
  4718   4767            && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
  4719   4768           ){
  4720   4769             if( i & WO_ISNULL ){
  4721   4770               testcase( isOrderDistinct );
  4722   4771               isOrderDistinct = 0;
  4723   4772             }
  4724   4773             continue;  
................................................................................
  5136   5185     pTab = pItem->pTab;
  5137   5186     if( IsVirtual(pTab) ) return 0;
  5138   5187     if( pItem->zIndex ) return 0;
  5139   5188     iCur = pItem->iCursor;
  5140   5189     pWC = &pWInfo->sWC;
  5141   5190     pLoop = pBuilder->pNew;
  5142   5191     pLoop->wsFlags = 0;
         5192  +  pLoop->u.btree.nSkip = 0;
  5143   5193     pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0);
  5144   5194     if( pTerm ){
  5145   5195       pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
  5146   5196       pLoop->aLTerm[0] = pTerm;
  5147   5197       pLoop->nLTerm = 1;
  5148   5198       pLoop->u.btree.nEq = 1;
  5149   5199       /* TUNING: Cost of a rowid lookup is 10 */
................................................................................
  5709   5759     sqlite3 *db = pParse->db;
  5710   5760   
  5711   5761     /* Generate loop termination code.
  5712   5762     */
  5713   5763     VdbeNoopComment((v, "End WHERE-core"));
  5714   5764     sqlite3ExprCacheClear(pParse);
  5715   5765     for(i=pWInfo->nLevel-1; i>=0; i--){
         5766  +    int addr;
  5716   5767       pLevel = &pWInfo->a[i];
  5717   5768       pLoop = pLevel->pWLoop;
  5718   5769       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  5719   5770       if( pLevel->op!=OP_Noop ){
  5720   5771         sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
  5721   5772         sqlite3VdbeChangeP5(v, pLevel->p5);
  5722   5773       }
................................................................................
  5728   5779           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  5729   5780           sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  5730   5781           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
  5731   5782         }
  5732   5783         sqlite3DbFree(db, pLevel->u.in.aInLoop);
  5733   5784       }
  5734   5785       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
         5786  +    if( pLevel->addrSkip ){
         5787  +      addr = sqlite3VdbeAddOp4Int(v, pLevel->opSkip, pLevel->iIdxCur, 0,
         5788  +                                  pLevel->p3Skip, pLevel->p4Skip);
         5789  +      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip);
         5790  +      sqlite3VdbeJumpHere(v, pLevel->addrSkip-1);
         5791  +      sqlite3VdbeJumpHere(v, addr);
         5792  +    }
  5735   5793       if( pLevel->iLeftJoin ){
  5736         -      int addr;
  5737   5794         addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
  5738   5795         assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
  5739   5796              || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
  5740   5797         if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
  5741   5798           sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
  5742   5799         }
  5743   5800         if( pLoop->wsFlags & WHERE_INDEXED ){

Changes to src/whereInt.h.

    61     61   */
    62     62   struct WhereLevel {
    63     63     int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
    64     64     int iTabCur;          /* The VDBE cursor used to access the table */
    65     65     int iIdxCur;          /* The VDBE cursor used to access pIdx */
    66     66     int addrBrk;          /* Jump here to break out of the loop */
    67     67     int addrNxt;          /* Jump here to start the next IN combination */
           68  +  int addrSkip;         /* Jump here for next iteration of skip-scan */
    68     69     int addrCont;         /* Jump here to continue with the next loop cycle */
    69     70     int addrFirst;        /* First instruction of interior of the loop */
    70     71     int addrBody;         /* Beginning of the body of this loop */
    71     72     u8 iFrom;             /* Which entry in the FROM clause */
    72     73     u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
           74  +  u8 opSkip;            /* Opcode to terminate the skip-scan */
    73     75     int p1, p2;           /* Operands of the opcode used to ends the loop */
           76  +  int p3Skip;           /* P3 operand for the skip-scan terminator */
           77  +  u16 p4Skip;           /* P4 operand for the skip-scan terminator */
    74     78     union {               /* Information that depends on pWLoop->wsFlags */
    75     79       struct {
    76     80         int nIn;              /* Number of entries in aInLoop[] */
    77     81         struct InLoop {
    78     82           int iCur;              /* The VDBE cursor used by this IN operator */
    79     83           int addrInTop;         /* Top of the IN loop */
    80     84           u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
................................................................................
   451    455   #define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
   452    456   #define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
   453    457   #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
   454    458   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   455    459   #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   456    460   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   457    461   #define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
          462  +#define WHERE_SKIP_SCAN    0x00008000  /* Uses the skip-scan algorithm */