/ Changes On Branch skip-scan
Login

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

Changes In Branch skip-scan Excluding Merge-Ins

This is equivalent to a diff from e7d34ec6 to f668616a

2013-11-13
20:46
Merge the skip-scan enhancement into trunk. (check-in: b0bb975c user: drh tags: trunk)
19:01
Import the "PRAGMA vdbe_eqp" enhancement and the enhanced EXPLAIN formatting the shell from trunk. Fix a bug in skip-scan and add a test case to prevent a regression. (Closed-Leaf check-in: f668616a user: drh tags: skip-scan)
18:35
In the shell tool, if an "EXPLAIN" command is executed in ".explain on" mode, attempt to automatically indent the bodies of loops in the output VDBE program. (check-in: e7d34ec6 user: dan tags: trunk)
17:58
Add the "PRAGMA vdbe_eqp" command, only available with SQLITE_DEBUG. Simplify some of the other debugging logic. (check-in: 8ce33f4c user: drh tags: trunk)
17:24
Add VDBE comments to the beginning and end of skip-scan loops. (check-in: 0c85d93b user: drh tags: skip-scan)

Changes to src/analyze.c.

  1424   1424     if( argv==0 || argv[0]==0 || argv[2]==0 ){
  1425   1425       return 0;
  1426   1426     }
  1427   1427     pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
  1428   1428     if( pTable==0 ){
  1429   1429       return 0;
  1430   1430     }
  1431         -  if( argv[1] ){
  1432         -    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
         1431  +  if( argv[1]==0 ){
         1432  +    pIndex = 0;
         1433  +  }else if( sqlite3_stricmp(argv[0],argv[1])==0 ){
         1434  +    pIndex = sqlite3PrimaryKeyIndex(pTable);
  1433   1435     }else{
  1434         -    pIndex = 0;
         1436  +    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  1435   1437     }
  1436   1438     z = argv[2];
  1437   1439   
  1438   1440     if( pIndex ){
  1439   1441       decodeIntArray((char*)z, pIndex->nKeyCol+1, pIndex->aiRowEst, pIndex);
  1440   1442       if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
  1441   1443     }else{

Changes to src/shell.c.

  1169   1169   **
  1170   1170   ** The indenting rules are:
  1171   1171   **
  1172   1172   **     * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent
  1173   1173   **       all opcodes that occur between the p2 jump destination and the opcode
  1174   1174   **       itself by 2 spaces.
  1175   1175   **
  1176         -**     * For each "Goto", if the jump destination is a "Yield" instruction
  1177         -**       that occurs earlier in the program than the Goto itself, indent
  1178         -**       all opcodes between the "Yield" and "Goto" by 2 spaces.
         1176  +**     * For each "Goto", if the jump destination is a "Yield", "SeekGt",
         1177  +**       or "SeekLt" instruction that occurs earlier in the program than
         1178  +**       the Goto itself, indent all opcodes between the earlier instruction
         1179  +**       and "Goto" by 2 spaces.
  1179   1180   */
  1180   1181   static void explain_data_prepare(struct callback_data *p, sqlite3_stmt *pSql){
  1181   1182     const char *zSql;               /* The text of the SQL statement */
  1182   1183     const char *z;                  /* Used to check if this is an EXPLAIN */
  1183   1184     int *abYield = 0;               /* True if op is an OP_Yield */
  1184   1185     int nAlloc = 0;                 /* Allocated size of p->aiIndent[], abYield */
  1185   1186     int iOp;
  1186   1187   
  1187   1188     const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", 0 };
  1188         -  const char *azYield[] = { "Yield", 0 };
         1189  +  const char *azYield[] = { "Yield", "SeekLt", "SeekGt", 0 };
  1189   1190     const char *azGoto[] = { "Goto", 0 };
  1190   1191   
  1191   1192     /* Try to figure out if this is really an EXPLAIN statement. If this
  1192   1193     ** cannot be verified, return early.  */
  1193   1194     zSql = sqlite3_sql(pSql);
  1194   1195     if( zSql==0 ) return;
  1195   1196     for(z=zSql; *z==' ' || *z=='\t' || *z=='\n' || *z=='\f' || *z=='\r'; z++);

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  +    sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
         2508  +    VdbeComment((v, "begin skip-scan on %s", pIdx->zName));
         2509  +    j = sqlite3VdbeAddOp0(v, OP_Goto);
         2510  +    pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLt:OP_SeekGt),
         2511  +                            iIdxCur, 0, regBase, nSkip);
         2512  +    sqlite3VdbeJumpHere(v, j);
         2513  +    for(j=0; j<nSkip; j++){
         2514  +      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
         2515  +      assert( pIdx->aiColumn[j]>=0 );
         2516  +      VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName));
         2517  +    }
         2518  +  }    
  2496   2519   
  2497   2520     /* Evaluate the equality constraints
  2498   2521     */
  2499   2522     assert( zAff==0 || (int)strlen(zAff)>=nEq );
  2500         -  for(j=0; j<nEq; j++){
         2523  +  for(j=nSkip; j<nEq; j++){
  2501   2524       int r1;
  2502   2525       pTerm = pLoop->aLTerm[j];
  2503   2526       assert( pTerm!=0 );
  2504         -    /* The following true for indices with redundant columns. 
         2527  +    /* The following testcase is true for indices with redundant columns. 
  2505   2528       ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
  2506   2529       testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
  2507   2530       testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2508   2531       r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
  2509   2532       if( r1!=regBase+j ){
  2510   2533         if( nReg==1 ){
  2511   2534           sqlite3ReleaseTempReg(pParse, regBase);
................................................................................
  2571   2594   **
  2572   2595   ** The returned pointer points to memory obtained from sqlite3DbMalloc().
  2573   2596   ** It is the responsibility of the caller to free the buffer when it is
  2574   2597   ** no longer required.
  2575   2598   */
  2576   2599   static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){
  2577   2600     Index *pIndex = pLoop->u.btree.pIndex;
  2578         -  int nEq = pLoop->u.btree.nEq;
         2601  +  u16 nEq = pLoop->u.btree.nEq;
         2602  +  u16 nSkip = pLoop->u.btree.nSkip;
  2579   2603     int i, j;
  2580   2604     Column *aCol = pTab->aCol;
  2581   2605     i16 *aiColumn = pIndex->aiColumn;
  2582   2606     StrAccum txt;
  2583   2607   
  2584   2608     if( nEq==0 && (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
  2585   2609       return 0;
  2586   2610     }
  2587   2611     sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
  2588   2612     txt.db = db;
  2589   2613     sqlite3StrAccumAppend(&txt, " (", 2);
  2590   2614     for(i=0; i<nEq; i++){
  2591   2615       char *z = (i==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[i]].zName;
  2592         -    explainAppendTerm(&txt, i, z, "=");
         2616  +    if( i>=nSkip ){
         2617  +      explainAppendTerm(&txt, i, z, "=");
         2618  +    }else{
         2619  +      if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5);
         2620  +      sqlite3StrAccumAppend(&txt, "ANY(", 4);
         2621  +      sqlite3StrAccumAppend(&txt, z, -1);
         2622  +      sqlite3StrAccumAppend(&txt, ")", 1);
         2623  +    }
  2593   2624     }
  2594   2625   
  2595   2626     j = i;
  2596   2627     if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
  2597   2628       char *z = (j==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[j]].zName;
  2598   2629       explainAppendTerm(&txt, i++, z, ">");
  2599   2630     }
................................................................................
  2951   2982         OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
  2952   2983       };
  2953   2984       static const u8 aEndOp[] = {
  2954   2985         OP_Noop,             /* 0: (!end_constraints) */
  2955   2986         OP_IdxGE,            /* 1: (end_constraints && !bRev) */
  2956   2987         OP_IdxLT             /* 2: (end_constraints && bRev) */
  2957   2988       };
  2958         -    int nEq = pLoop->u.btree.nEq;  /* Number of == or IN terms */
  2959         -    int isMinQuery = 0;            /* If this is an optimized SELECT min(x).. */
         2989  +    u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
         2990  +    u16 nSkip = pLoop->u.btree.nSkip; /* Number of left index terms to skip */
         2991  +    int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
  2960   2992       int regBase;                 /* Base register holding constraint values */
  2961   2993       int r1;                      /* Temp register */
  2962   2994       WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  2963   2995       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  2964   2996       int startEq;                 /* True if range start uses ==, >= or <= */
  2965   2997       int endEq;                   /* True if range end uses ==, >= or <= */
  2966   2998       int start_constraints;       /* Start of range is constrained */
................................................................................
  2970   3002       int nExtraReg = 0;           /* Number of extra registers needed */
  2971   3003       int op;                      /* Instruction opcode */
  2972   3004       char *zStartAff;             /* Affinity for start of range constraint */
  2973   3005       char *zEndAff;               /* Affinity for end of range constraint */
  2974   3006   
  2975   3007       pIdx = pLoop->u.btree.pIndex;
  2976   3008       iIdxCur = pLevel->iIdxCur;
         3009  +    assert( nEq>=nSkip );
  2977   3010   
  2978   3011       /* If this loop satisfies a sort order (pOrderBy) request that 
  2979   3012       ** was passed to this function to implement a "SELECT min(x) ..." 
  2980   3013       ** query, then the caller will only allow the loop to run for
  2981   3014       ** a single iteration. This means that the first row returned
  2982   3015       ** should not have a NULL value stored in 'x'. If column 'x' is
  2983   3016       ** the first one after the nEq equality constraints in the index,
  2984   3017       ** this requires some special handling.
  2985   3018       */
  2986   3019       if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
  2987   3020        && (pWInfo->bOBSat!=0)
  2988   3021        && (pIdx->nKeyCol>nEq)
  2989   3022       ){
  2990         -      /* assert( pOrderBy->nExpr==1 ); */
  2991         -      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
         3023  +      assert( nSkip==0 );
  2992   3024         isMinQuery = 1;
  2993   3025         nExtraReg = 1;
  2994   3026       }
  2995   3027   
  2996   3028       /* Find any inequality constraint terms for the start and end 
  2997   3029       ** of the range. 
  2998   3030       */
................................................................................
  3535   3567     */
  3536   3568     if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){  /* WHERETRACE 0x100 */
  3537   3569       int i;
  3538   3570       Vdbe *v = pWInfo->pParse->pVdbe;
  3539   3571       sqlite3ExplainBegin(v);
  3540   3572       for(i=0; i<p->nLTerm; i++){
  3541   3573         WhereTerm *pTerm = p->aLTerm[i];
         3574  +      if( pTerm==0 ) continue;
  3542   3575         sqlite3ExplainPrintf(v, "  (%d) #%-2d ", i+1, (int)(pTerm-pWC->a));
  3543   3576         sqlite3ExplainPush(v);
  3544   3577         whereExplainTerm(v, pTerm);
  3545   3578         sqlite3ExplainPop(v);
  3546   3579         sqlite3ExplainNL(v);
  3547   3580       }
  3548   3581       sqlite3ExplainFinish(v);
................................................................................
  3818   3851     }
  3819   3852     for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
  3820   3853       if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
  3821   3854       if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
  3822   3855       if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
  3823   3856       for(j=pLoop->nLTerm-1; j>=0; j--){
  3824   3857         pX = pLoop->aLTerm[j];
         3858  +      if( pX==0 ) continue;
  3825   3859         if( pX==pTerm ) break;
  3826   3860         if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
  3827   3861       }
  3828   3862       if( j<0 ) pLoop->nOut += pTerm->truthProb;
  3829   3863     }
  3830   3864   }
  3831   3865   
................................................................................
  3847   3881     sqlite3 *db = pParse->db;       /* Database connection malloc context */
  3848   3882     WhereLoop *pNew;                /* Template WhereLoop under construction */
  3849   3883     WhereTerm *pTerm;               /* A WhereTerm under consideration */
  3850   3884     int opMask;                     /* Valid operators for constraints */
  3851   3885     WhereScan scan;                 /* Iterator for WHERE terms */
  3852   3886     Bitmask saved_prereq;           /* Original value of pNew->prereq */
  3853   3887     u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
  3854         -  int saved_nEq;                  /* Original value of pNew->u.btree.nEq */
         3888  +  u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
         3889  +  u16 saved_nSkip;                /* Original value of pNew->u.btree.nSkip */
  3855   3890     u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  3856   3891     LogEst saved_nOut;              /* Original value of pNew->nOut */
  3857   3892     int iCol;                       /* Index of the column in the table */
  3858   3893     int rc = SQLITE_OK;             /* Return code */
  3859   3894     LogEst nRowEst;                 /* Estimated index selectivity */
  3860   3895     LogEst rLogSize;                /* Logarithm of table size */
  3861   3896     WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */
................................................................................
  3882   3917     }else{
  3883   3918       iCol = -1;
  3884   3919       nRowEst = 0;
  3885   3920     }
  3886   3921     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  3887   3922                           opMask, pProbe);
  3888   3923     saved_nEq = pNew->u.btree.nEq;
         3924  +  saved_nSkip = pNew->u.btree.nSkip;
  3889   3925     saved_nLTerm = pNew->nLTerm;
  3890   3926     saved_wsFlags = pNew->wsFlags;
  3891   3927     saved_prereq = pNew->prereq;
  3892   3928     saved_nOut = pNew->nOut;
  3893   3929     pNew->rSetup = 0;
  3894   3930     rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
         3931  +  if( pTerm==0
         3932  +   && saved_nEq==saved_nSkip
         3933  +   && saved_nEq+1<pProbe->nKeyCol
         3934  +   && pProbe->aiRowEst[saved_nEq+1]>50
         3935  +  ){
         3936  +    LogEst nIter;
         3937  +    pNew->u.btree.nEq++;
         3938  +    pNew->u.btree.nSkip++;
         3939  +    pNew->aLTerm[pNew->nLTerm++] = 0;
         3940  +    pNew->wsFlags |= WHERE_SKIPSCAN;
         3941  +    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
         3942  +    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
         3943  +  }
  3895   3944     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  3896   3945       int nIn = 0;
  3897   3946   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  3898   3947       int nRecValid = pBuilder->nRecValid;
  3899   3948   #endif
  3900   3949       if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
  3901   3950        && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
................................................................................
  3923   3972           /* "x IN (value, value, ...)" */
  3924   3973           nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
  3925   3974         }
  3926   3975         pNew->rRun += nIn;
  3927   3976         pNew->u.btree.nEq++;
  3928   3977         pNew->nOut = nRowEst + nInMul + nIn;
  3929   3978       }else if( pTerm->eOperator & (WO_EQ) ){
  3930         -      assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
  3931         -                  || nInMul==0 );
         3979  +      assert(
         3980  +        (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0
         3981  +        || nInMul==0
         3982  +      );
  3932   3983         pNew->wsFlags |= WHERE_COLUMN_EQ;
  3933   3984         if( iCol<0  
  3934   3985          || (pProbe->onError!=OE_None && nInMul==0
  3935   3986              && pNew->u.btree.nEq==pProbe->nKeyCol-1)
  3936   3987         ){
  3937   3988           assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
  3938   3989           pNew->wsFlags |= WHERE_ONEROW;
................................................................................
  4005   4056       pNew->nOut = saved_nOut;
  4006   4057   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  4007   4058       pBuilder->nRecValid = nRecValid;
  4008   4059   #endif
  4009   4060     }
  4010   4061     pNew->prereq = saved_prereq;
  4011   4062     pNew->u.btree.nEq = saved_nEq;
         4063  +  pNew->u.btree.nSkip = saved_nSkip;
  4012   4064     pNew->wsFlags = saved_wsFlags;
  4013   4065     pNew->nOut = saved_nOut;
  4014   4066     pNew->nLTerm = saved_nLTerm;
  4015   4067     return rc;
  4016   4068   }
  4017   4069   
  4018   4070   /*
................................................................................
  4151   4203       /* Generate auto-index WhereLoops */
  4152   4204       WhereTerm *pTerm;
  4153   4205       WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
  4154   4206       for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
  4155   4207         if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4156   4208         if( termCanDriveIndex(pTerm, pSrc, 0) ){
  4157   4209           pNew->u.btree.nEq = 1;
         4210  +        pNew->u.btree.nSkip = 0;
  4158   4211           pNew->u.btree.pIndex = 0;
  4159   4212           pNew->nLTerm = 1;
  4160   4213           pNew->aLTerm[0] = pTerm;
  4161   4214           /* TUNING: One-time cost for computing the automatic index is
  4162   4215           ** approximately 7*N*log2(N) where N is the number of rows in
  4163   4216           ** the table being indexed. */
  4164   4217           pNew->rSetup = rLogSize + rSize + 28;  assert( 28==sqlite3LogEst(7) );
................................................................................
  4180   4233     */
  4181   4234     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  4182   4235       if( pProbe->pPartIdxWhere!=0
  4183   4236        && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
  4184   4237         continue;  /* Partial index inappropriate for this query */
  4185   4238       }
  4186   4239       pNew->u.btree.nEq = 0;
         4240  +    pNew->u.btree.nSkip = 0;
  4187   4241       pNew->nLTerm = 0;
  4188   4242       pNew->iSortIdx = 0;
  4189   4243       pNew->rSetup = 0;
  4190   4244       pNew->prereq = mExtra;
  4191   4245       pNew->nOut = rSize;
  4192   4246       pNew->u.btree.pIndex = pProbe;
  4193   4247       b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
................................................................................
  4714   4768         rev = revSet = 0;
  4715   4769         distinctColumns = 0;
  4716   4770         for(j=0; j<nColumn; j++){
  4717   4771           u8 bOnce;   /* True to run the ORDER BY search loop */
  4718   4772   
  4719   4773           /* Skip over == and IS NULL terms */
  4720   4774           if( j<pLoop->u.btree.nEq
         4775  +         && pLoop->u.btree.nSkip==0
  4721   4776            && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
  4722   4777           ){
  4723   4778             if( i & WO_ISNULL ){
  4724   4779               testcase( isOrderDistinct );
  4725   4780               isOrderDistinct = 0;
  4726   4781             }
  4727   4782             continue;  
................................................................................
  5139   5194     pTab = pItem->pTab;
  5140   5195     if( IsVirtual(pTab) ) return 0;
  5141   5196     if( pItem->zIndex ) return 0;
  5142   5197     iCur = pItem->iCursor;
  5143   5198     pWC = &pWInfo->sWC;
  5144   5199     pLoop = pBuilder->pNew;
  5145   5200     pLoop->wsFlags = 0;
         5201  +  pLoop->u.btree.nSkip = 0;
  5146   5202     pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0);
  5147   5203     if( pTerm ){
  5148   5204       pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
  5149   5205       pLoop->aLTerm[0] = pTerm;
  5150   5206       pLoop->nLTerm = 1;
  5151   5207       pLoop->u.btree.nEq = 1;
  5152   5208       /* TUNING: Cost of a rowid lookup is 10 */
................................................................................
  5712   5768     sqlite3 *db = pParse->db;
  5713   5769   
  5714   5770     /* Generate loop termination code.
  5715   5771     */
  5716   5772     VdbeNoopComment((v, "End WHERE-core"));
  5717   5773     sqlite3ExprCacheClear(pParse);
  5718   5774     for(i=pWInfo->nLevel-1; i>=0; i--){
         5775  +    int addr;
  5719   5776       pLevel = &pWInfo->a[i];
  5720   5777       pLoop = pLevel->pWLoop;
  5721   5778       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  5722   5779       if( pLevel->op!=OP_Noop ){
  5723   5780         sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
  5724   5781         sqlite3VdbeChangeP5(v, pLevel->p5);
  5725   5782       }
................................................................................
  5731   5788           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  5732   5789           sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  5733   5790           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
  5734   5791         }
  5735   5792         sqlite3DbFree(db, pLevel->u.in.aInLoop);
  5736   5793       }
  5737   5794       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
         5795  +    if( pLevel->addrSkip ){
         5796  +      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip);
         5797  +      VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));
         5798  +      sqlite3VdbeJumpHere(v, pLevel->addrSkip);
         5799  +      sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
         5800  +    }
  5738   5801       if( pLevel->iLeftJoin ){
  5739         -      int addr;
  5740   5802         addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
  5741   5803         assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
  5742   5804              || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
  5743   5805         if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
  5744   5806           sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
  5745   5807         }
  5746   5808         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 */
    73     74     int p1, p2;           /* Operands of the opcode used to ends the loop */
    74     75     union {               /* Information that depends on pWLoop->wsFlags */
................................................................................
   451    452   #define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
   452    453   #define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
   453    454   #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
   454    455   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   455    456   #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   456    457   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   457    458   #define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
          459  +#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */

Added test/skipscan1.test.

            1  +# 2013-11-13
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# This file implements tests of the "skip-scan" query strategy.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +do_execsql_test skipscan1-1.1 {
           19  +  CREATE TABLE t1(a TEXT, b INT, c INT, d INT);
           20  +  CREATE INDEX t1abc ON t1(a,b,c);
           21  +  INSERT INTO t1 VALUES('abc',123,4,5);
           22  +  INSERT INTO t1 VALUES('abc',234,5,6);
           23  +  INSERT INTO t1 VALUES('abc',234,6,7);
           24  +  INSERT INTO t1 VALUES('abc',345,7,8);
           25  +  INSERT INTO t1 VALUES('def',567,8,9);
           26  +  INSERT INTO t1 VALUES('def',345,9,10);
           27  +  INSERT INTO t1 VALUES('bcd',100,6,11);
           28  +
           29  +  /* Fake the sqlite_stat1 table so that the query planner believes
           30  +  ** the table contains thousands of rows and that the first few
           31  +  ** columns are not selective. */
           32  +  ANALYZE;
           33  +  DELETE FROM sqlite_stat1;
           34  +  INSERT INTO sqlite_stat1 VALUES('t1','t1abc','10000 5000 2000 10');
           35  +  ANALYZE sqlite_master;
           36  +} {}
           37  +
           38  +# Simple queries that leave the first one or two columns of the
           39  +# index unconstrainted.
           40  +#
           41  +do_execsql_test skipscan1-1.2 {
           42  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
           43  +} {abc 345 7 8 | def 345 9 10 |}
           44  +do_execsql_test skipscan1-1.2eqp {
           45  +  EXPLAIN QUERY PLAN
           46  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
           47  +} {/* USING INDEX t1abc (ANY(a) AND b=?)*/}
           48  +do_execsql_test skipscan1-1.2sort {
           49  +  EXPLAIN QUERY PLAN
           50  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
           51  +} {~/*ORDER BY*/}
           52  +
           53  +do_execsql_test skipscan1-1.3 {
           54  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a DESC;
           55  +} {def 345 9 10 | abc 345 7 8 |}
           56  +do_execsql_test skipscan1-1.3eqp {
           57  +  EXPLAIN QUERY PLAN
           58  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
           59  +} {/* USING INDEX t1abc (ANY(a) AND b=?)*/}
           60  +do_execsql_test skipscan1-1.3sort {
           61  +  EXPLAIN QUERY PLAN
           62  +  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
           63  +} {~/*ORDER BY*/}
           64  +
           65  +do_execsql_test skipscan1-1.4 {
           66  +  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
           67  +} {abc 234 6 7 | bcd 100 6 11 |}
           68  +do_execsql_test skipscan1-1.4eqp {
           69  +  EXPLAIN QUERY PLAN
           70  +  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
           71  +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
           72  +do_execsql_test skipscan1-1.4sort {
           73  +  EXPLAIN QUERY PLAN
           74  +  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
           75  +} {~/*ORDER BY*/}
           76  +
           77  +do_execsql_test skipscan1-1.5 {
           78  +  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
           79  +} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
           80  +do_execsql_test skipscan1-1.5eqp {
           81  +  EXPLAIN QUERY PLAN
           82  +  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
           83  +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
           84  +do_execsql_test skipscan1-1.5sort {
           85  +  EXPLAIN QUERY PLAN
           86  +  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
           87  +} {~/*ORDER BY*/}
           88  +
           89  +do_execsql_test skipscan1-1.6 {
           90  +  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
           91  +} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
           92  +do_execsql_test skipscan1-1.6eqp {
           93  +  EXPLAIN QUERY PLAN
           94  +  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
           95  +} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c>? AND c<?)*/}
           96  +do_execsql_test skipscan1-1.6sort {
           97  +  EXPLAIN QUERY PLAN
           98  +  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
           99  +} {~/*ORDER BY*/}
          100  +
          101  +do_execsql_test skipscan1-1.7 {
          102  +  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
          103  +   ORDER BY a, b;
          104  +} {abc 234 6 7 | abc 345 7 8 |}
          105  +do_execsql_test skipscan1-1.7eqp {
          106  +  EXPLAIN QUERY PLAN
          107  +  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
          108  +   ORDER BY a, b;
          109  +} {/* USING INDEX t1abc (ANY(a) AND b=? AND c>? AND c<?)*/}
          110  +do_execsql_test skipscan1-1.7sort {
          111  +  EXPLAIN QUERY PLAN
          112  +  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
          113  +   ORDER BY a, b;
          114  +} {~/*ORDER BY*/}
          115  +
          116  +
          117  +# Joins
          118  +#
          119  +do_execsql_test skipscan1-1.51 {
          120  +  CREATE TABLE t1j(x TEXT, y INTEGER);
          121  +  INSERT INTO t1j VALUES('one',1),('six',6),('ninty-nine',99);
          122  +  INSERT INTO sqlite_stat1 VALUES('t1j',null,'3');
          123  +  ANALYZE sqlite_master;
          124  +  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
          125  +} {six abc 234 6 7 | six bcd 100 6 11 |}
          126  +do_execsql_test skipscan1-1.51eqp {
          127  +  EXPLAIN QUERY PLAN
          128  +  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
          129  +} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
          130  +
          131  +do_execsql_test skipscan1-1.52 {
          132  +  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
          133  +} {one {} {} {} {} | six abc 234 6 7 | six bcd 100 6 11 | ninty-nine {} {} {} {} |}
          134  +do_execsql_test skipscan1-1.52eqp {
          135  +  EXPLAIN QUERY PLAN
          136  +  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
          137  +} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
          138  +
          139  +do_execsql_test skipscan1-2.1 {
          140  +  CREATE TABLE t2(a TEXT, b INT, c INT, d INT,
          141  +                  PRIMARY KEY(a,b,c));
          142  +  INSERT INTO t2 SELECT * FROM t1;
          143  +
          144  +  /* Fake the sqlite_stat1 table so that the query planner believes
          145  +  ** the table contains thousands of rows and that the first few
          146  +  ** columns are not selective. */
          147  +  ANALYZE;
          148  +  UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL;
          149  +  ANALYZE sqlite_master;
          150  +} {}
          151  +
          152  +do_execsql_test skipscan1-2.2 {
          153  +  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
          154  +} {abc 345 7 8 | def 345 9 10 |}
          155  +do_execsql_test skipscan1-2.2eqp {
          156  +  EXPLAIN QUERY PLAN
          157  +  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
          158  +} {/* USING INDEX sqlite_autoindex_t2_1 (ANY(a) AND b=?)*/}
          159  +do_execsql_test skipscan1-2.2sort {
          160  +  EXPLAIN QUERY PLAN
          161  +  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
          162  +} {~/*ORDER BY*/}
          163  +
          164  +
          165  +do_execsql_test skipscan1-3.1 {
          166  +  CREATE TABLE t3(a TEXT, b INT, c INT, d INT,
          167  +                  PRIMARY KEY(a,b,c)) WITHOUT ROWID;
          168  +  INSERT INTO t3 SELECT * FROM t1;
          169  +
          170  +  /* Fake the sqlite_stat1 table so that the query planner believes
          171  +  ** the table contains thousands of rows and that the first few
          172  +  ** columns are not selective. */
          173  +  ANALYZE;
          174  +  UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL;
          175  +  ANALYZE sqlite_master;
          176  +} {}
          177  +
          178  +do_execsql_test skipscan1-3.2 {
          179  +  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
          180  +} {abc 345 7 8 | def 345 9 10 |}
          181  +do_execsql_test skipscan1-3.2eqp {
          182  +  EXPLAIN QUERY PLAN
          183  +  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
          184  +} {/* INDEX sqlite_autoindex_t3_1 (ANY(a) AND b=?)*/}
          185  +do_execsql_test skipscan1-3.2sort {
          186  +  EXPLAIN QUERY PLAN
          187  +  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
          188  +} {~/*ORDER BY*/}
          189  +
          190  +finish_test

Changes to test/tester.tcl.

   612    612         fail_test $name
   613    613       } else {
   614    614         if {[regexp {^~?/.*/$} $expected]} {
   615    615           # "expected" is of the form "/PATTERN/" then the result if correct if
   616    616           # regular expression PATTERN matches the result.  "~/PATTERN/" means
   617    617           # the regular expression must not match.
   618    618           if {[string index $expected 0]=="~"} {
   619         -          set re [string map {# {[-0-9.]+}} [string range $expected 2 end-1]]
   620         -          set ok [expr {![regexp $re $result]}]
          619  +          set re [string range $expected 2 end-1]
          620  +          if {[string index $re 0]=="*"} {
          621  +            # If the regular expression begins with * then treat it as a glob instead
          622  +            set ok [string match $re $result]
          623  +          } else {
          624  +            set re [string map {# {[-0-9.]+}} $re]
          625  +            set ok [regexp $re $result]
          626  +          }
          627  +          set ok [expr {!$ok}]
   621    628           } else {
   622         -          set re [string map {# {[-0-9.]+}} [string range $expected 1 end-1]]
   623         -          set ok [regexp $re $result]
          629  +          set re [string range $expected 1 end-1]
          630  +          if {[string index $re 0]=="*"} {
          631  +            # If the regular expression begins with * then treat it as a glob instead
          632  +            set ok [string match $re $result]
          633  +          } else {
          634  +            set re [string map {# {[-0-9.]+}} $re]
          635  +            set ok [regexp $re $result]
          636  +          }
   624    637           }
   625    638         } elseif {[regexp {^~?\*.*\*$} $expected]} {
   626    639           # "expected" is of the form "*GLOB*" then the result if correct if
   627    640           # glob pattern GLOB matches the result.  "~/GLOB/" means
   628    641           # the glob must not match.
   629    642           if {[string index $expected 0]=="~"} {
   630    643             set e [string range $expected 1 end]