SQLite
Diff
Not logged in

Differences From Artifact [aafcb21a]:

To Artifact [a6d127dd]:


   123    123   #else
   124    124   #  define TERM_VNULL    0x00   /* Disabled if not using stat3 */
   125    125   #endif
   126    126   
   127    127   /*
   128    128   ** An instance of the following structure holds all information about a
   129    129   ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
          130  +**
          131  +** Explanation of pOuter:  For a WHERE clause of the form
          132  +**
          133  +**           a AND ((b AND c) OR (d AND e)) AND f
          134  +**
          135  +** There are separate WhereClause objects for the whole clause and for
          136  +** the subclauses "(b AND c)" and "(d AND e)".  The pOuter field of the
          137  +** subclauses points to the WhereClause object for the whole clause.
   130    138   */
   131    139   struct WhereClause {
   132    140     Parse *pParse;           /* The parser context */
   133    141     WhereMaskSet *pMaskSet;  /* Mapping of table cursor numbers to bitmasks */
   134    142     Bitmask vmask;           /* Bitmask identifying virtual table cursors */
          143  +  WhereClause *pOuter;     /* Outer conjunction */
   135    144     u8 op;                   /* Split operator.  TK_AND or TK_OR */
          145  +  u16 wctrlFlags;          /* Might include WHERE_AND_ONLY */
   136    146     int nTerm;               /* Number of terms */
   137    147     int nSlot;               /* Number of entries in a[] */
   138    148     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   139    149   #if defined(SQLITE_SMALL_STACK)
   140    150     WhereTerm aStatic[1];    /* Initial static space for a[] */
   141    151   #else
   142    152     WhereTerm aStatic[8];    /* Initial static space for a[] */
................................................................................
   257    267   
   258    268   /*
   259    269   ** Initialize a preallocated WhereClause structure.
   260    270   */
   261    271   static void whereClauseInit(
   262    272     WhereClause *pWC,        /* The WhereClause to be initialized */
   263    273     Parse *pParse,           /* The parsing context */
   264         -  WhereMaskSet *pMaskSet   /* Mapping from table cursor numbers to bitmasks */
          274  +  WhereMaskSet *pMaskSet,  /* Mapping from table cursor numbers to bitmasks */
          275  +  u16 wctrlFlags           /* Might include WHERE_AND_ONLY */
   265    276   ){
   266    277     pWC->pParse = pParse;
   267    278     pWC->pMaskSet = pMaskSet;
          279  +  pWC->pOuter = 0;
   268    280     pWC->nTerm = 0;
   269    281     pWC->nSlot = ArraySize(pWC->aStatic);
   270    282     pWC->a = pWC->aStatic;
   271    283     pWC->vmask = 0;
          284  +  pWC->wctrlFlags = wctrlFlags;
   272    285   }
   273    286   
   274    287   /* Forward reference */
   275    288   static void whereClauseClear(WhereClause*);
   276    289   
   277    290   /*
   278    291   ** Deallocate all memory associated with a WhereOrInfo object.
................................................................................
   580    593     u32 op,               /* Mask of WO_xx values describing operator */
   581    594     Index *pIdx           /* Must be compatible with this index, if not NULL */
   582    595   ){
   583    596     WhereTerm *pTerm;
   584    597     int k;
   585    598     assert( iCur>=0 );
   586    599     op &= WO_ALL;
   587         -  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   588         -    if( pTerm->leftCursor==iCur
   589         -       && (pTerm->prereqRight & notReady)==0
   590         -       && pTerm->u.leftColumn==iColumn
   591         -       && (pTerm->eOperator & op)!=0
   592         -    ){
   593         -      if( pIdx && pTerm->eOperator!=WO_ISNULL ){
   594         -        Expr *pX = pTerm->pExpr;
   595         -        CollSeq *pColl;
   596         -        char idxaff;
   597         -        int j;
   598         -        Parse *pParse = pWC->pParse;
   599         -
   600         -        idxaff = pIdx->pTable->aCol[iColumn].affinity;
   601         -        if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
   602         -
   603         -        /* Figure out the collation sequence required from an index for
   604         -        ** it to be useful for optimising expression pX. Store this
   605         -        ** value in variable pColl.
   606         -        */
   607         -        assert(pX->pLeft);
   608         -        pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
   609         -        assert(pColl || pParse->nErr);
   610         -
   611         -        for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
   612         -          if( NEVER(j>=pIdx->nColumn) ) return 0;
   613         -        }
   614         -        if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
   615         -      }
   616         -      return pTerm;
          600  +  for(; pWC; pWC=pWC->pOuter){
          601  +    for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
          602  +      if( pTerm->leftCursor==iCur
          603  +         && (pTerm->prereqRight & notReady)==0
          604  +         && pTerm->u.leftColumn==iColumn
          605  +         && (pTerm->eOperator & op)!=0
          606  +      ){
          607  +        if( pIdx && pTerm->eOperator!=WO_ISNULL ){
          608  +          Expr *pX = pTerm->pExpr;
          609  +          CollSeq *pColl;
          610  +          char idxaff;
          611  +          int j;
          612  +          Parse *pParse = pWC->pParse;
          613  +  
          614  +          idxaff = pIdx->pTable->aCol[iColumn].affinity;
          615  +          if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
          616  +  
          617  +          /* Figure out the collation sequence required from an index for
          618  +          ** it to be useful for optimising expression pX. Store this
          619  +          ** value in variable pColl.
          620  +          */
          621  +          assert(pX->pLeft);
          622  +          pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
          623  +          assert(pColl || pParse->nErr);
          624  +  
          625  +          for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
          626  +            if( NEVER(j>=pIdx->nColumn) ) return 0;
          627  +          }
          628  +          if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
          629  +        }
          630  +        return pTerm;
          631  +      }
   617    632       }
   618    633     }
   619    634     return 0;
   620    635   }
   621    636   
   622    637   /* Forward reference */
   623    638   static void exprAnalyze(SrcList*, WhereClause*, int);
................................................................................
   873    888     */
   874    889     assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
   875    890     assert( pExpr->op==TK_OR );
   876    891     pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
   877    892     if( pOrInfo==0 ) return;
   878    893     pTerm->wtFlags |= TERM_ORINFO;
   879    894     pOrWc = &pOrInfo->wc;
   880         -  whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
          895  +  whereClauseInit(pOrWc, pWC->pParse, pMaskSet, pWC->wctrlFlags);
   881    896     whereSplit(pOrWc, pExpr, TK_OR);
   882    897     exprAnalyzeAll(pSrc, pOrWc);
   883    898     if( db->mallocFailed ) return;
   884    899     assert( pOrWc->nTerm>=2 );
   885    900   
   886    901     /*
   887    902     ** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
   900    915           WhereTerm *pAndTerm;
   901    916           int j;
   902    917           Bitmask b = 0;
   903    918           pOrTerm->u.pAndInfo = pAndInfo;
   904    919           pOrTerm->wtFlags |= TERM_ANDINFO;
   905    920           pOrTerm->eOperator = WO_AND;
   906    921           pAndWC = &pAndInfo->wc;
   907         -        whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
          922  +        whereClauseInit(pAndWC, pWC->pParse, pMaskSet, pWC->wctrlFlags);
   908    923           whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
   909    924           exprAnalyzeAll(pSrc, pAndWC);
          925  +        pAndWC->pOuter = pWC;
   910    926           testcase( db->mallocFailed );
   911    927           if( !db->mallocFailed ){
   912    928             for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
   913    929               assert( pAndTerm->pExpr );
   914    930               if( allowedOp(pAndTerm->pExpr->op) ){
   915    931                 b |= getMask(pMaskSet, pAndTerm->leftCursor);
   916    932               }
................................................................................
  1797   1813   ){
  1798   1814   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  1799   1815     const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  1800   1816     const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
  1801   1817     WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
  1802   1818     WhereTerm *pTerm;                 /* A single term of the WHERE clause */
  1803   1819   
  1804         -  /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
  1805         -  ** are used */
         1820  +  /* The OR-clause optimization is disallowed if the INDEXED BY or
         1821  +  ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
  1806   1822     if( pSrc->notIndexed || pSrc->pIndex!=0 ){
  1807   1823       return;
         1824  +  }
         1825  +  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
         1826  +    return;
  1808   1827     }
  1809   1828   
  1810   1829     /* Search the WHERE clause terms for a usable WO_OR term. */
  1811   1830     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1812   1831       if( pTerm->eOperator==WO_OR 
  1813   1832        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
  1814   1833        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
................................................................................
  1829   1848           if( pOrTerm->eOperator==WO_AND ){
  1830   1849             WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
  1831   1850             bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost);
  1832   1851           }else if( pOrTerm->leftCursor==iCur ){
  1833   1852             WhereClause tempWC;
  1834   1853             tempWC.pParse = pWC->pParse;
  1835   1854             tempWC.pMaskSet = pWC->pMaskSet;
         1855  +          tempWC.pOuter = pWC;
  1836   1856             tempWC.op = TK_AND;
  1837   1857             tempWC.a = pOrTerm;
  1838   1858             tempWC.nTerm = 1;
  1839   1859             bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost);
  1840   1860           }else{
  1841   1861             continue;
  1842   1862           }
................................................................................
  3008   3028   
  3009   3029       /* Determine the values of nEq and nInMul */
  3010   3030       for(nEq=0; nEq<pProbe->nColumn; nEq++){
  3011   3031         int j = pProbe->aiColumn[nEq];
  3012   3032         pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
  3013   3033         if( pTerm==0 ) break;
  3014   3034         wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
         3035  +      testcase( pTerm->pWC!=pWC );
  3015   3036         if( pTerm->eOperator & WO_IN ){
  3016   3037           Expr *pExpr = pTerm->pExpr;
  3017   3038           wsFlags |= WHERE_COLUMN_IN;
  3018   3039           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  3019   3040             /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  3020   3041             nInMul *= 25;
  3021   3042             bInEst = 1;
................................................................................
  3039   3060           WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
  3040   3061           WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
  3041   3062           whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
  3042   3063           if( pTop ){
  3043   3064             nBound = 1;
  3044   3065             wsFlags |= WHERE_TOP_LIMIT;
  3045   3066             used |= pTop->prereqRight;
         3067  +          testcase( pTop->pWC!=pWC );
  3046   3068           }
  3047   3069           if( pBtm ){
  3048   3070             nBound++;
  3049   3071             wsFlags |= WHERE_BTM_LIMIT;
  3050   3072             used |= pBtm->prereqRight;
         3073  +          testcase( pBtm->pWC!=pWC );
  3051   3074           }
  3052   3075           wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
  3053   3076         }
  3054   3077       }else if( pProbe->onError!=OE_None ){
  3055   3078         testcase( wsFlags & WHERE_COLUMN_IN );
  3056   3079         testcase( wsFlags & WHERE_COLUMN_NULL );
  3057   3080         if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
................................................................................
  3765   3788   ** Generate code for the start of the iLevel-th loop in the WHERE clause
  3766   3789   ** implementation described by pWInfo.
  3767   3790   */
  3768   3791   static Bitmask codeOneLoopStart(
  3769   3792     WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  3770   3793     int iLevel,          /* Which level of pWInfo->a[] should be coded */
  3771   3794     u16 wctrlFlags,      /* One of the WHERE_* flags defined in sqliteInt.h */
  3772         -  Bitmask notReady     /* Which tables are currently available */
         3795  +  Bitmask notReady,    /* Which tables are currently available */
         3796  +  Expr *pWhere         /* Complete WHERE clause */
  3773   3797   ){
  3774   3798     int j, k;            /* Loop counters */
  3775   3799     int iCur;            /* The VDBE cursor for the table */
  3776   3800     int addrNxt;         /* Where to jump to continue with the next IN case */
  3777   3801     int omitTable;       /* True if we use the index only */
  3778   3802     int bRev;            /* True if we need to scan in reverse order */
  3779   3803     WhereLevel *pLevel;  /* The where level to be coded */
................................................................................
  4247   4271   
  4248   4272       int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
  4249   4273       int regRowset = 0;                        /* Register for RowSet object */
  4250   4274       int regRowid = 0;                         /* Register holding rowid */
  4251   4275       int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
  4252   4276       int iRetInit;                             /* Address of regReturn init */
  4253   4277       int untestedTerms = 0;             /* Some terms not completely tested */
  4254         -    int ii;
         4278  +    int ii;                            /* Loop counter */
         4279  +    Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  4255   4280      
  4256   4281       pTerm = pLevel->plan.u.pTerm;
  4257   4282       assert( pTerm!=0 );
  4258   4283       assert( pTerm->eOperator==WO_OR );
  4259   4284       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  4260   4285       pOrWc = &pTerm->u.pOrInfo->wc;
  4261   4286       pLevel->op = OP_Return;
................................................................................
  4296   4321       */
  4297   4322       if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
  4298   4323         regRowset = ++pParse->nMem;
  4299   4324         regRowid = ++pParse->nMem;
  4300   4325         sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
  4301   4326       }
  4302   4327       iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
         4328  +
         4329  +    /* If the original WHERE clause is z of the form:  (x1 OR x2 OR ...) AND y
         4330  +    ** Then for every term xN, evaluate as the subexpression: xN AND z
         4331  +    ** That way, terms in y that are factored into the disjunction will
         4332  +    ** be picked up by the recursive calls to sqlite3WhereBegin() below.
         4333  +    */
         4334  +    if( pWC->nTerm>1 ){
         4335  +      pAndExpr = sqlite3ExprAlloc(pParse->db, TK_AND, 0, 0);
         4336  +      pAndExpr->pRight = pWhere;
         4337  +    }
  4303   4338   
  4304   4339       for(ii=0; ii<pOrWc->nTerm; ii++){
  4305   4340         WhereTerm *pOrTerm = &pOrWc->a[ii];
  4306   4341         if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
  4307   4342           WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
         4343  +        Expr *pOrExpr = pOrTerm->pExpr;
         4344  +        if( pAndExpr ){
         4345  +          pAndExpr->pLeft = pOrExpr;
         4346  +          pOrExpr = pAndExpr;
         4347  +        }
  4308   4348           /* Loop through table entries that match term pOrTerm. */
  4309         -        pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrTerm->pExpr, 0, 0,
  4310         -                        WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
         4349  +        pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
         4350  +                        WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
  4311   4351                           WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
  4312   4352           if( pSubWInfo ){
  4313   4353             explainOneScan(
  4314   4354                 pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
  4315   4355             );
  4316   4356             if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
  4317   4357               int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
................................................................................
  4331   4371             if( pSubWInfo->untestedTerms ) untestedTerms = 1;
  4332   4372   
  4333   4373             /* Finish the loop through table entries that match term pOrTerm. */
  4334   4374             sqlite3WhereEnd(pSubWInfo);
  4335   4375           }
  4336   4376         }
  4337   4377       }
         4378  +    sqlite3DbFree(pParse->db, pAndExpr);
  4338   4379       sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
  4339   4380       sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
  4340   4381       sqlite3VdbeResolveLabel(v, iLoopBody);
  4341   4382   
  4342   4383       if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
  4343   4384       if( !untestedTerms ) disableTerm(pLevel, pTerm);
  4344   4385     }else
................................................................................
  4612   4653     ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  4613   4654     if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
  4614   4655   
  4615   4656     /* Split the WHERE clause into separate subexpressions where each
  4616   4657     ** subexpression is separated by an AND operator.
  4617   4658     */
  4618   4659     initMaskSet(pMaskSet);
  4619         -  whereClauseInit(pWC, pParse, pMaskSet);
         4660  +  whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags);
  4620   4661     sqlite3ExprCodeConstants(pParse, pWhere);
  4621   4662     whereSplit(pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
  4622   4663       
  4623   4664     /* Special case: a WHERE clause that is constant.  Evaluate the
  4624   4665     ** expression and either jump over all of the code or fall thru.
  4625   4666     */
  4626   4667     if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
................................................................................
  4940   4981       if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  4941   4982         const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
  4942   4983         int iCur = pTabItem->iCursor;
  4943   4984         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
  4944   4985       }else
  4945   4986   #endif
  4946   4987       if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
  4947         -         && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
         4988  +         && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){
  4948   4989         int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
  4949   4990         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
  4950   4991         testcase( pTab->nCol==BMS-1 );
  4951   4992         testcase( pTab->nCol==BMS );
  4952   4993         if( !pWInfo->okOnePass && pTab->nCol<BMS ){
  4953   4994           Bitmask b = pTabItem->colUsed;
  4954   4995           int n = 0;
................................................................................
  4985   5026     ** loop below generates code for a single nested loop of the VM
  4986   5027     ** program.
  4987   5028     */
  4988   5029     notReady = ~(Bitmask)0;
  4989   5030     for(i=0; i<nTabList; i++){
  4990   5031       pLevel = &pWInfo->a[i];
  4991   5032       explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
  4992         -    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
         5033  +    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady, pWhere);
  4993   5034       pWInfo->iContinue = pLevel->addrCont;
  4994   5035     }
  4995   5036   
  4996   5037   #ifdef SQLITE_TEST  /* For testing and debugging use only */
  4997   5038     /* Record in the query plan information about the current table
  4998   5039     ** and the index used to access it (if any).  If the table itself
  4999   5040     ** is not used, its name is just '{}'.  If no index is used
................................................................................
  5120   5161     assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
  5121   5162     for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
  5122   5163       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  5123   5164       Table *pTab = pTabItem->pTab;
  5124   5165       assert( pTab!=0 );
  5125   5166       if( (pTab->tabFlags & TF_Ephemeral)==0
  5126   5167        && pTab->pSelect==0
  5127         -     && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
         5168  +     && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
  5128   5169       ){
  5129   5170         int ws = pLevel->plan.wsFlags;
  5130   5171         if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
  5131   5172           sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  5132   5173         }
  5133   5174         if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
  5134   5175           sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);