/ Check-in [9fca05ea]
Login

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

Overview
Comment:Prevent infinite recursion of in the query planner for some pathological test cases by disabling OR-clause processing upon first recursion.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | or-opt
Files: files | file ages | folders
SHA1: 9fca05eac503d712886a05d03794f76c61fb39ed
User & Date: drh 2011-10-07 14:40:59
Context
2011-10-07
16:08
More test cases for the OR optimization. check-in: 4997d8b8 user: drh tags: or-opt
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  1975   1975   ** and the WhereInfo.wctrlFlags member.
  1976   1976   */
  1977   1977   #define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
  1978   1978   #define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
  1979   1979   #define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
  1980   1980   #define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
  1981   1981   #define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
  1982         -#define WHERE_OMIT_OPEN        0x0010 /* Table cursors are already open */
  1983         -#define WHERE_OMIT_CLOSE       0x0020 /* Omit close of table & index cursors */
  1984         -#define WHERE_FORCE_TABLE      0x0040 /* Do not use an index-only search */
  1985         -#define WHERE_ONETABLE_ONLY    0x0080 /* Only code the 1st table in pTabList */
         1982  +#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
         1983  +#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
         1984  +#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
         1985  +#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
  1986   1986   
  1987   1987   /*
  1988   1988   ** The WHERE clause processing routine has two halves.  The
  1989   1989   ** first part does the start of the WHERE loop and the second
  1990   1990   ** half does the tail of the WHERE loop.  An instance of
  1991   1991   ** this structure is returned by the first half and passed
  1992   1992   ** into the second half to give some continuity.

Changes to src/where.c.

   138    138   */
   139    139   struct WhereClause {
   140    140     Parse *pParse;           /* The parser context */
   141    141     WhereMaskSet *pMaskSet;  /* Mapping of table cursor numbers to bitmasks */
   142    142     Bitmask vmask;           /* Bitmask identifying virtual table cursors */
   143    143     WhereClause *pOuter;     /* Outer conjunction */
   144    144     u8 op;                   /* Split operator.  TK_AND or TK_OR */
          145  +  u16 wctrlFlags;          /* Might include WHERE_AND_ONLY */
   145    146     int nTerm;               /* Number of terms */
   146    147     int nSlot;               /* Number of entries in a[] */
   147    148     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   148    149   #if defined(SQLITE_SMALL_STACK)
   149    150     WhereTerm aStatic[1];    /* Initial static space for a[] */
   150    151   #else
   151    152     WhereTerm aStatic[8];    /* Initial static space for a[] */
................................................................................
   266    267   
   267    268   /*
   268    269   ** Initialize a preallocated WhereClause structure.
   269    270   */
   270    271   static void whereClauseInit(
   271    272     WhereClause *pWC,        /* The WhereClause to be initialized */
   272    273     Parse *pParse,           /* The parsing context */
   273         -  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 */
   274    276   ){
   275    277     pWC->pParse = pParse;
   276    278     pWC->pMaskSet = pMaskSet;
   277    279     pWC->pOuter = 0;
   278    280     pWC->nTerm = 0;
   279    281     pWC->nSlot = ArraySize(pWC->aStatic);
   280    282     pWC->a = pWC->aStatic;
   281    283     pWC->vmask = 0;
          284  +  pWC->wctrlFlags = wctrlFlags;
   282    285   }
   283    286   
   284    287   /* Forward reference */
   285    288   static void whereClauseClear(WhereClause*);
   286    289   
   287    290   /*
   288    291   ** Deallocate all memory associated with a WhereOrInfo object.
................................................................................
   885    888     */
   886    889     assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
   887    890     assert( pExpr->op==TK_OR );
   888    891     pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
   889    892     if( pOrInfo==0 ) return;
   890    893     pTerm->wtFlags |= TERM_ORINFO;
   891    894     pOrWc = &pOrInfo->wc;
   892         -  whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
          895  +  whereClauseInit(pOrWc, pWC->pParse, pMaskSet, pWC->wctrlFlags);
   893    896     whereSplit(pOrWc, pExpr, TK_OR);
   894    897     exprAnalyzeAll(pSrc, pOrWc);
   895    898     if( db->mallocFailed ) return;
   896    899     assert( pOrWc->nTerm>=2 );
   897    900   
   898    901     /*
   899    902     ** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
   912    915           WhereTerm *pAndTerm;
   913    916           int j;
   914    917           Bitmask b = 0;
   915    918           pOrTerm->u.pAndInfo = pAndInfo;
   916    919           pOrTerm->wtFlags |= TERM_ANDINFO;
   917    920           pOrTerm->eOperator = WO_AND;
   918    921           pAndWC = &pAndInfo->wc;
   919         -        whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
          922  +        whereClauseInit(pAndWC, pWC->pParse, pMaskSet, pWC->wctrlFlags);
   920    923           whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
   921    924           exprAnalyzeAll(pSrc, pAndWC);
   922    925           pAndWC->pOuter = pWC;
   923    926           testcase( db->mallocFailed );
   924    927           if( !db->mallocFailed ){
   925    928             for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
   926    929               assert( pAndTerm->pExpr );
................................................................................
  1810   1813   ){
  1811   1814   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  1812   1815     const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  1813   1816     const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
  1814   1817     WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
  1815   1818     WhereTerm *pTerm;                 /* A single term of the WHERE clause */
  1816   1819   
  1817         -  /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
  1818         -  ** 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. */
  1819   1822     if( pSrc->notIndexed || pSrc->pIndex!=0 ){
  1820   1823       return;
         1824  +  }
         1825  +  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
         1826  +    return;
  1821   1827     }
  1822   1828   
  1823   1829     /* Search the WHERE clause terms for a usable WO_OR term. */
  1824   1830     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1825   1831       if( pTerm->eOperator==WO_OR 
  1826   1832        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
  1827   1833        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
................................................................................
  4334   4340           Expr *pOrExpr = pOrTerm->pExpr;
  4335   4341           if( pAndExpr ){
  4336   4342             pAndExpr->pLeft = pOrExpr;
  4337   4343             pOrExpr = pAndExpr;
  4338   4344           }
  4339   4345           /* Loop through table entries that match term pOrTerm. */
  4340   4346           pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
  4341         -                        WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
         4347  +                        WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
  4342   4348                           WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
  4343   4349           if( pSubWInfo ){
  4344   4350             explainOneScan(
  4345   4351                 pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
  4346   4352             );
  4347   4353             if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
  4348   4354               int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
................................................................................
  4644   4650     ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  4645   4651     if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
  4646   4652   
  4647   4653     /* Split the WHERE clause into separate subexpressions where each
  4648   4654     ** subexpression is separated by an AND operator.
  4649   4655     */
  4650   4656     initMaskSet(pMaskSet);
  4651         -  whereClauseInit(pWC, pParse, pMaskSet);
         4657  +  whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags);
  4652   4658     sqlite3ExprCodeConstants(pParse, pWhere);
  4653   4659     whereSplit(pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
  4654   4660       
  4655   4661     /* Special case: a WHERE clause that is constant.  Evaluate the
  4656   4662     ** expression and either jump over all of the code or fall thru.
  4657   4663     */
  4658   4664     if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
................................................................................
  4972   4978       if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  4973   4979         const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
  4974   4980         int iCur = pTabItem->iCursor;
  4975   4981         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
  4976   4982       }else
  4977   4983   #endif
  4978   4984       if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
  4979         -         && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
         4985  +         && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){
  4980   4986         int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
  4981   4987         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
  4982   4988         testcase( pTab->nCol==BMS-1 );
  4983   4989         testcase( pTab->nCol==BMS );
  4984   4990         if( !pWInfo->okOnePass && pTab->nCol<BMS ){
  4985   4991           Bitmask b = pTabItem->colUsed;
  4986   4992           int n = 0;
................................................................................
  5152   5158     assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
  5153   5159     for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
  5154   5160       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  5155   5161       Table *pTab = pTabItem->pTab;
  5156   5162       assert( pTab!=0 );
  5157   5163       if( (pTab->tabFlags & TF_Ephemeral)==0
  5158   5164        && pTab->pSelect==0
  5159         -     && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
         5165  +     && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
  5160   5166       ){
  5161   5167         int ws = pLevel->plan.wsFlags;
  5162   5168         if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
  5163   5169           sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  5164   5170         }
  5165   5171         if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
  5166   5172           sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);