/ Check-in [876bd21a]
Login

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

Overview
Comment:Begin an effort to enhance the query planner to do a better job with OR terms in the WHERE clause. This change allows ANDs outside of the OR to be factored into the OR terms if that is helpful in finding better indices.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | or-opt
Files: files | file ages | folders
SHA1: 876bd21aaac444c7e056730e35696a74e9a1af0a
User & Date: drh 2011-10-07 13:33:10
Context
2011-10-07
14:40
Prevent infinite recursion of in the query planner for some pathological test cases by disabling OR-clause processing upon first recursion. check-in: 9fca05ea user: drh tags: or-opt
13:33
Begin an effort to enhance the query planner to do a better job with OR terms in the WHERE clause. This change allows ANDs outside of the OR to be factored into the OR terms if that is helpful in finding better indices. check-in: 876bd21a user: drh tags: or-opt
12:59
Enhance the sqlite3_data_count() routine so that it can be used to determine if SQLITE_DONE has been seen on the prepared statement. check-in: 9913996e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   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 */
   136    145     int nTerm;               /* Number of terms */
   137    146     int nSlot;               /* Number of entries in a[] */
   138    147     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   139    148   #if defined(SQLITE_SMALL_STACK)
   140    149     WhereTerm aStatic[1];    /* Initial static space for a[] */
   141    150   #else
................................................................................
   261    270   static void whereClauseInit(
   262    271     WhereClause *pWC,        /* The WhereClause to be initialized */
   263    272     Parse *pParse,           /* The parsing context */
   264    273     WhereMaskSet *pMaskSet   /* Mapping from table cursor numbers to bitmasks */
   265    274   ){
   266    275     pWC->pParse = pParse;
   267    276     pWC->pMaskSet = pMaskSet;
          277  +  pWC->pOuter = 0;
   268    278     pWC->nTerm = 0;
   269    279     pWC->nSlot = ArraySize(pWC->aStatic);
   270    280     pWC->a = pWC->aStatic;
   271    281     pWC->vmask = 0;
   272    282   }
   273    283   
   274    284   /* Forward reference */
................................................................................
   580    590     u32 op,               /* Mask of WO_xx values describing operator */
   581    591     Index *pIdx           /* Must be compatible with this index, if not NULL */
   582    592   ){
   583    593     WhereTerm *pTerm;
   584    594     int k;
   585    595     assert( iCur>=0 );
   586    596     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;
          597  +  for(; pWC; pWC=pWC->pOuter){
          598  +    for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
          599  +      if( pTerm->leftCursor==iCur
          600  +         && (pTerm->prereqRight & notReady)==0
          601  +         && pTerm->u.leftColumn==iColumn
          602  +         && (pTerm->eOperator & op)!=0
          603  +      ){
          604  +        if( pIdx && pTerm->eOperator!=WO_ISNULL ){
          605  +          Expr *pX = pTerm->pExpr;
          606  +          CollSeq *pColl;
          607  +          char idxaff;
          608  +          int j;
          609  +          Parse *pParse = pWC->pParse;
          610  +  
          611  +          idxaff = pIdx->pTable->aCol[iColumn].affinity;
          612  +          if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
          613  +  
          614  +          /* Figure out the collation sequence required from an index for
          615  +          ** it to be useful for optimising expression pX. Store this
          616  +          ** value in variable pColl.
          617  +          */
          618  +          assert(pX->pLeft);
          619  +          pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
          620  +          assert(pColl || pParse->nErr);
          621  +  
          622  +          for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
          623  +            if( NEVER(j>=pIdx->nColumn) ) return 0;
          624  +          }
          625  +          if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
          626  +        }
          627  +        return pTerm;
          628  +      }
   617    629       }
   618    630     }
   619    631     return 0;
   620    632   }
   621    633   
   622    634   /* Forward reference */
   623    635   static void exprAnalyze(SrcList*, WhereClause*, int);
................................................................................
   903    915           pOrTerm->u.pAndInfo = pAndInfo;
   904    916           pOrTerm->wtFlags |= TERM_ANDINFO;
   905    917           pOrTerm->eOperator = WO_AND;
   906    918           pAndWC = &pAndInfo->wc;
   907    919           whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
   908    920           whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
   909    921           exprAnalyzeAll(pSrc, pAndWC);
          922  +        pAndWC->pOuter = pWC;
   910    923           testcase( db->mallocFailed );
   911    924           if( !db->mallocFailed ){
   912    925             for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
   913    926               assert( pAndTerm->pExpr );
   914    927               if( allowedOp(pAndTerm->pExpr->op) ){
   915    928                 b |= getMask(pMaskSet, pAndTerm->leftCursor);
   916    929               }
................................................................................
  1829   1842           if( pOrTerm->eOperator==WO_AND ){
  1830   1843             WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
  1831   1844             bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost);
  1832   1845           }else if( pOrTerm->leftCursor==iCur ){
  1833   1846             WhereClause tempWC;
  1834   1847             tempWC.pParse = pWC->pParse;
  1835   1848             tempWC.pMaskSet = pWC->pMaskSet;
         1849  +          tempWC.pOuter = pWC;
  1836   1850             tempWC.op = TK_AND;
  1837   1851             tempWC.a = pOrTerm;
  1838   1852             tempWC.nTerm = 1;
  1839   1853             bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost);
  1840   1854           }else{
  1841   1855             continue;
  1842   1856           }
................................................................................
  3765   3779   ** Generate code for the start of the iLevel-th loop in the WHERE clause
  3766   3780   ** implementation described by pWInfo.
  3767   3781   */
  3768   3782   static Bitmask codeOneLoopStart(
  3769   3783     WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  3770   3784     int iLevel,          /* Which level of pWInfo->a[] should be coded */
  3771   3785     u16 wctrlFlags,      /* One of the WHERE_* flags defined in sqliteInt.h */
  3772         -  Bitmask notReady     /* Which tables are currently available */
         3786  +  Bitmask notReady,    /* Which tables are currently available */
         3787  +  Expr *pWhere         /* Complete WHERE clause */
  3773   3788   ){
  3774   3789     int j, k;            /* Loop counters */
  3775   3790     int iCur;            /* The VDBE cursor for the table */
  3776   3791     int addrNxt;         /* Where to jump to continue with the next IN case */
  3777   3792     int omitTable;       /* True if we use the index only */
  3778   3793     int bRev;            /* True if we need to scan in reverse order */
  3779   3794     WhereLevel *pLevel;  /* The where level to be coded */
................................................................................
  4247   4262   
  4248   4263       int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
  4249   4264       int regRowset = 0;                        /* Register for RowSet object */
  4250   4265       int regRowid = 0;                         /* Register holding rowid */
  4251   4266       int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
  4252   4267       int iRetInit;                             /* Address of regReturn init */
  4253   4268       int untestedTerms = 0;             /* Some terms not completely tested */
  4254         -    int ii;
         4269  +    int ii;                            /* Loop counter */
         4270  +    Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  4255   4271      
  4256   4272       pTerm = pLevel->plan.u.pTerm;
  4257   4273       assert( pTerm!=0 );
  4258   4274       assert( pTerm->eOperator==WO_OR );
  4259   4275       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  4260   4276       pOrWc = &pTerm->u.pOrInfo->wc;
  4261   4277       pLevel->op = OP_Return;
................................................................................
  4296   4312       */
  4297   4313       if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
  4298   4314         regRowset = ++pParse->nMem;
  4299   4315         regRowid = ++pParse->nMem;
  4300   4316         sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
  4301   4317       }
  4302   4318       iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
         4319  +
         4320  +    /* If the original WHERE clause is z of the form:  (x1 OR x2 OR ...) AND y
         4321  +    ** Then for every term xN, evaluate as the subexpression: xN AND z
         4322  +    ** That way, terms in y that are factored into the disjunction will
         4323  +    ** be picked up by the recursive calls to sqlite3WhereBegin() below.
         4324  +    */
         4325  +    if( pWC->nTerm>1 ){
         4326  +      pAndExpr = sqlite3ExprAlloc(pParse->db, TK_AND, 0, 0);
         4327  +      pAndExpr->pRight = pWhere;
         4328  +    }
  4303   4329   
  4304   4330       for(ii=0; ii<pOrWc->nTerm; ii++){
  4305   4331         WhereTerm *pOrTerm = &pOrWc->a[ii];
  4306   4332         if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
  4307   4333           WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
         4334  +        Expr *pOrExpr = pOrTerm->pExpr;
         4335  +        if( pAndExpr ){
         4336  +          pAndExpr->pLeft = pOrExpr;
         4337  +          pOrExpr = pAndExpr;
         4338  +        }
  4308   4339           /* Loop through table entries that match term pOrTerm. */
  4309         -        pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrTerm->pExpr, 0, 0,
         4340  +        pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
  4310   4341                           WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
  4311   4342                           WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
  4312   4343           if( pSubWInfo ){
  4313   4344             explainOneScan(
  4314   4345                 pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
  4315   4346             );
  4316   4347             if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
................................................................................
  4331   4362             if( pSubWInfo->untestedTerms ) untestedTerms = 1;
  4332   4363   
  4333   4364             /* Finish the loop through table entries that match term pOrTerm. */
  4334   4365             sqlite3WhereEnd(pSubWInfo);
  4335   4366           }
  4336   4367         }
  4337   4368       }
         4369  +    sqlite3DbFree(pParse->db, pAndExpr);
  4338   4370       sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
  4339   4371       sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
  4340   4372       sqlite3VdbeResolveLabel(v, iLoopBody);
  4341   4373   
  4342   4374       if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
  4343   4375       if( !untestedTerms ) disableTerm(pLevel, pTerm);
  4344   4376     }else
................................................................................
  4985   5017     ** loop below generates code for a single nested loop of the VM
  4986   5018     ** program.
  4987   5019     */
  4988   5020     notReady = ~(Bitmask)0;
  4989   5021     for(i=0; i<nTabList; i++){
  4990   5022       pLevel = &pWInfo->a[i];
  4991   5023       explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
  4992         -    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
         5024  +    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady, pWhere);
  4993   5025       pWInfo->iContinue = pLevel->addrCont;
  4994   5026     }
  4995   5027   
  4996   5028   #ifdef SQLITE_TEST  /* For testing and debugging use only */
  4997   5029     /* Record in the query plan information about the current table
  4998   5030     ** and the index used to access it (if any).  If the table itself
  4999   5031     ** is not used, its name is just '{}'.  If no index is used