/ Check-in [fa95f843]
Login

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

Overview
Comment:Simplify the VM code that implements WHERE claues. (CVS 6067)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fa95f843e179a38f663978d675607c4c3037928d
User & Date: drh 2008-12-28 16:55:25
Context
2008-12-28
18:35
Optimize WHERE clauses that constain AND, BETWEEN, and LIKE terms as operands of an OR. (CVS 6068) check-in: 67cf24b3 user: drh tags: trunk
16:55
Simplify the VM code that implements WHERE claues. (CVS 6067) check-in: fa95f843 user: drh tags: trunk
2008-12-27
15:23
Fix a problem with savepoint and incremental-vacuum. (CVS 6066) check-in: 08352f9e user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.815 2008/12/23 23:56:22 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.816 2008/12/28 16:55:25 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Include the configuration header output by 'configure' if we're using the
    21     21   ** autoconf-based build
................................................................................
  1591   1591     */
  1592   1592     sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
  1593   1593   };
  1594   1594   
  1595   1595   /*
  1596   1596   ** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin().
  1597   1597   */
  1598         -#define WHERE_ORDERBY_NORMAL    0x000  /* No-op */
  1599         -#define WHERE_ORDERBY_MIN       0x001  /* ORDER BY processing for min() func */
  1600         -#define WHERE_ORDERBY_MAX       0x002  /* ORDER BY processing for max() func */
  1601         -#define WHERE_ONEPASS_DESIRED   0x004  /* Want to do one-pass UPDATE/DELETE */
  1602         -#define WHERE_FILL_ROWSET       0x008  /* Save results in a RowSet object */
         1598  +#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
         1599  +#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
         1600  +#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
         1601  +#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
         1602  +#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
         1603  +#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
         1604  +#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
  1603   1605   
  1604   1606   /*
  1605   1607   ** The WHERE clause processing routine has two halves.  The
  1606   1608   ** first part does the start of the WHERE loop and the second
  1607   1609   ** half does the tail of the WHERE loop.  An instance of
  1608   1610   ** this structure is returned by the first half and passed
  1609   1611   ** into the second half to give some continuity.
  1610   1612   */
  1611   1613   struct WhereInfo {
  1612   1614     Parse *pParse;       /* Parsing and code generating context */
         1615  +  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  1613   1616     u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  1614   1617     int regRowSet;                 /* Store rowids in this rowset if >=0 */
  1615   1618     SrcList *pTabList;             /* List of tables in the join */
  1616   1619     int iTop;                      /* The very beginning of the WHERE loop */
  1617   1620     int iContinue;                 /* Jump here to continue with next record */
  1618   1621     int iBreak;                    /* Jump here to break out of the loop */
  1619   1622     int nLevel;                    /* Number of nested loop */

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is responsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.344 2008/12/24 11:25:40 danielk1977 Exp $
           19  +** $Id: where.c,v 1.345 2008/12/28 16:55:25 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** Trace output macros
    25     25   */
    26     26   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
    27     27   int sqlite3WhereTrace = 0;
    28     28   #endif
    29         -#if 1
           29  +#if 0
    30     30   # define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
    31     31   #else
    32     32   # define WHERETRACE(X)
    33     33   #endif
    34     34   
    35     35   /* Forward reference
    36     36   */
................................................................................
  2107   2107   ** index.  The values for all constraints are left on the stack.
  2108   2108   **
  2109   2109   ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
  2110   2110   ** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
  2111   2111   ** The index has as many as three equality constraints, but in this
  2112   2112   ** example, the third "c" value is an inequality.  So only two 
  2113   2113   ** constraints are coded.  This routine will generate code to evaluate
  2114         -** a==5 and b IN (1,2,3).  The current values for a and b will be left
  2115         -** on the stack - a is the deepest and b the shallowest.
         2114  +** a==5 and b IN (1,2,3).  The current values for a and b will be stored
         2115  +** in consecutive registers and the index of the first register is returned.
  2116   2116   **
  2117   2117   ** In the example above nEq==2.  But this subroutine works for any value
  2118   2118   ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
  2119   2119   ** The only thing it does is allocate the pLevel->iMem memory cell.
  2120   2120   **
  2121   2121   ** This routine always allocates at least one memory cell and returns
  2122   2122   ** the index of that memory cell. The code that
................................................................................
  2135   2135     int nEq = pLevel->plan.nEq;   /* The number of == or IN constraints to code */
  2136   2136     Vdbe *v = pParse->pVdbe;      /* The vm under construction */
  2137   2137     Index *pIdx;                  /* The index being used for this loop */
  2138   2138     int iCur = pLevel->iTabCur;   /* The cursor of the table */
  2139   2139     WhereTerm *pTerm;             /* A single constraint term */
  2140   2140     int j;                        /* Loop counter */
  2141   2141     int regBase;                  /* Base register */
         2142  +  int nReg;                     /* Number of registers to allocate */
  2142   2143   
  2143   2144     /* This module is only called on query plans that use an index. */
  2144   2145     assert( pLevel->plan.wsFlags & WHERE_INDEXED );
  2145   2146     pIdx = pLevel->plan.u.pIdx;
  2146   2147   
  2147   2148     /* Figure out how many memory cells we will need then allocate them.
  2148         -  ** We always need at least one used to store the loop terminator
  2149         -  ** value.  If there are IN operators we'll need one for each == or
  2150         -  ** IN constraint.
  2151   2149     */
  2152   2150     regBase = pParse->nMem + 1;
  2153         -  pParse->nMem += pLevel->plan.nEq + 1 + nExtraReg;
         2151  +  nReg = pLevel->plan.nEq + nExtraReg;
         2152  +  pParse->nMem += nReg;
  2154   2153   
  2155   2154     /* Evaluate the equality constraints
  2156   2155     */
  2157   2156     assert( pIdx->nColumn>=nEq );
  2158   2157     for(j=0; j<nEq; j++){
  2159   2158       int r1;
  2160   2159       int k = pIdx->aiColumn[j];
  2161   2160       pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
  2162   2161       if( NEVER(pTerm==0) ) break;
  2163   2162       assert( (pTerm->wtFlags & TERM_CODED)==0 );
  2164   2163       r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
  2165   2164       if( r1!=regBase+j ){
  2166         -      sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
         2165  +      if( nReg==1 ){
         2166  +        sqlite3ReleaseTempReg(pParse, regBase);
         2167  +        regBase = r1;
         2168  +      }else{
         2169  +        sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
         2170  +      }
  2167   2171       }
  2168   2172       testcase( pTerm->eOperator & WO_ISNULL );
  2169   2173       testcase( pTerm->eOperator & WO_IN );
  2170   2174       if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
  2171   2175         sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
  2172   2176       }
  2173   2177     }
................................................................................
  2460   2464       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  2461   2465       int startEq;                 /* True if range start uses ==, >= or <= */
  2462   2466       int endEq;                   /* True if range end uses ==, >= or <= */
  2463   2467       int start_constraints;       /* Start of range is constrained */
  2464   2468       int nConstraint;             /* Number of constraint terms */
  2465   2469       Index *pIdx;         /* The index we will be using */
  2466   2470       int iIdxCur;         /* The VDBE cursor for the index */
  2467         -    int op;
         2471  +    int nExtraReg = 0;   /* Number of extra registers needed */
         2472  +    int op;              /* Instruction opcode */
  2468   2473   
  2469   2474       pIdx = pLevel->plan.u.pIdx;
  2470   2475       iIdxCur = pLevel->iIdxCur;
  2471   2476       k = pIdx->aiColumn[nEq];     /* Column for inequality constraints */
  2472   2477   
  2473         -    /* Generate code to evaluate all constraint terms using == or IN
  2474         -    ** and store the values of those terms in an array of registers
  2475         -    ** starting at regBase.
  2476         -    */
  2477         -    regBase = codeAllEqualityTerms(pParse, pLevel, pWC, notReady, 2);
  2478         -    addrNxt = pLevel->addrNxt;
  2479         -
  2480   2478       /* If this loop satisfies a sort order (pOrderBy) request that 
  2481   2479       ** was passed to this function to implement a "SELECT min(x) ..." 
  2482   2480       ** query, then the caller will only allow the loop to run for
  2483   2481       ** a single iteration. This means that the first row returned
  2484   2482       ** should not have a NULL value stored in 'x'. If column 'x' is
  2485   2483       ** the first one after the nEq equality constraints in the index,
  2486   2484       ** this requires some special handling.
................................................................................
  2488   2486       if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
  2489   2487        && (pLevel->plan.wsFlags&WHERE_ORDERBY)
  2490   2488        && (pIdx->nColumn>nEq)
  2491   2489       ){
  2492   2490         /* assert( pOrderBy->nExpr==1 ); */
  2493   2491         /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
  2494   2492         isMinQuery = 1;
         2493  +      nExtraReg = 1;
  2495   2494       }
  2496   2495   
  2497   2496       /* Find any inequality constraint terms for the start and end 
  2498   2497       ** of the range. 
  2499   2498       */
  2500   2499       if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
  2501   2500         pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
         2501  +      nExtraReg = 1;
  2502   2502       }
  2503   2503       if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
  2504   2504         pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
         2505  +      nExtraReg = 1;
  2505   2506       }
         2507  +
         2508  +    /* Generate code to evaluate all constraint terms using == or IN
         2509  +    ** and store the values of those terms in an array of registers
         2510  +    ** starting at regBase.
         2511  +    */
         2512  +    regBase = codeAllEqualityTerms(pParse, pLevel, pWC, notReady, nExtraReg);
         2513  +    addrNxt = pLevel->addrNxt;
         2514  +
  2506   2515   
  2507   2516       /* If we are doing a reverse order scan on an ascending index, or
  2508   2517       ** a forward order scan on a descending index, interchange the 
  2509   2518       ** start and end terms (pRangeStart and pRangeEnd).
  2510   2519       */
  2511   2520       if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
  2512   2521         SWAP(WhereTerm *, pRangeEnd, pRangeStart);
................................................................................
  2564   2573       pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  2565   2574   
  2566   2575       /* Check if the index cursor is past the end of the range. */
  2567   2576       op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
  2568   2577       testcase( op==OP_Noop );
  2569   2578       testcase( op==OP_IdxGE );
  2570   2579       testcase( op==OP_IdxLT );
  2571         -    sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
  2572         -                      SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
  2573         -    sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
         2580  +    if( op!=OP_Noop ){
         2581  +      sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
         2582  +                        SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
         2583  +      sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
         2584  +    }
  2574   2585   
  2575   2586       /* If there are inequality constraints, check that the value
  2576   2587       ** of the table column that the inequality contrains is not NULL.
  2577   2588       ** If it is, jump to the next iteration of the loop.
  2578   2589       */
  2579   2590       r1 = sqlite3GetTempReg(pParse);
  2580   2591       testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
................................................................................
  2657   2668       oneTab.nSrc = 1;
  2658   2669       oneTab.nAlloc = 1;
  2659   2670       oneTab.a[0] = *pTabItem;
  2660   2671       for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){
  2661   2672         WhereInfo *pSubWInfo;
  2662   2673         if( pOrTerm->leftCursor!=iCur ) continue;
  2663   2674         pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0,
  2664         -                        WHERE_FILL_ROWSET, regOrRowset);
         2675  +                        WHERE_FILL_ROWSET | WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE,
         2676  +                        regOrRowset);
  2665   2677         if( pSubWInfo ){
  2666         -        pSubWInfo->a[0].plan.wsFlags |= WHERE_IDX_ONLY;
  2667   2678           sqlite3WhereEnd(pSubWInfo);
  2668   2679         }
  2669   2680       }
  2670   2681       sqlite3VdbeResolveLabel(v, addrCont);
  2671   2682       if( !codeRowSetEarly ){
  2672   2683         regNextRowid = sqlite3GetTempReg(pParse);
  2673   2684         addrCont = 
................................................................................
  2931   2942     }
  2932   2943     pWInfo->nLevel = pTabList->nSrc;
  2933   2944     pWInfo->pParse = pParse;
  2934   2945     pWInfo->pTabList = pTabList;
  2935   2946     pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  2936   2947     pWInfo->regRowSet = (wctrlFlags & WHERE_FILL_ROWSET) ? regRowSet : -1;
  2937   2948     pWInfo->pWC = pWC = (WhereClause*)&pWInfo->a[pWInfo->nLevel];
         2949  +  pWInfo->wctrlFlags = wctrlFlags;
  2938   2950     pMaskSet = (WhereMaskSet*)&pWC[1];
  2939   2951   
  2940   2952     /* Split the WHERE clause into separate subexpressions where each
  2941   2953     ** subexpression is separated by an AND operator.
  2942   2954     */
  2943   2955     initMaskSet(pMaskSet);
  2944   2956     whereClauseInit(pWC, pParse, pMaskSet);
................................................................................
  3160   3172   #ifndef SQLITE_OMIT_VIRTUALTABLE
  3161   3173       if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  3162   3174         int iCur = pTabItem->iCursor;
  3163   3175         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
  3164   3176                           (const char*)pTab->pVtab, P4_VTAB);
  3165   3177       }else
  3166   3178   #endif
  3167         -    if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
         3179  +    if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
         3180  +         && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
  3168   3181         int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
  3169   3182         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
  3170   3183         if( !pWInfo->okOnePass && pTab->nCol<BMS ){
  3171   3184           Bitmask b = pTabItem->colUsed;
  3172   3185           int n = 0;
  3173   3186           for(; b; b=b>>1, n++){}
  3174   3187           sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
................................................................................
  3317   3330     /* Close all of the cursors that were opened by sqlite3WhereBegin.
  3318   3331     */
  3319   3332     for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  3320   3333       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  3321   3334       Table *pTab = pTabItem->pTab;
  3322   3335       assert( pTab!=0 );
  3323   3336       if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
  3324         -    if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
  3325         -      sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  3326         -    }
  3327         -    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  3328         -      sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
         3337  +    if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){
         3338  +      if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
         3339  +        sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
         3340  +      }
         3341  +      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         3342  +        sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
         3343  +      }
  3329   3344       }
  3330   3345   
  3331   3346       /* If this scan uses an index, make code substitutions to read data
  3332   3347       ** from the index in preference to the table. Sometimes, this means
  3333   3348       ** the table need never be read from. This is a performance boost,
  3334   3349       ** as the vdbe level waits until the table is read before actually
  3335   3350       ** seeking the table cursor to the record corresponding to the current