/ Check-in [e17003fc]
Login

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

Overview
Comment:Now generating OR-clause plans.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: e17003fcfec0c0b524b1b9ff8e15e7ee83efa571
User & Date: drh 2013-05-10 20:26:22
Context
2013-05-11
00:06
Minor fixes to the OR-clause processing in the NGQP. check-in: d6946f33 user: drh tags: nextgen-query-plan-exp
2013-05-10
20:26
Now generating OR-clause plans. check-in: e17003fc user: drh tags: nextgen-query-plan-exp
15:16
Update the NGQP so that it can produce plans that include automatic indices. check-in: 586b55d8 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   285    285     WhereInfo *pWInfo;        /* Information about this WHERE */
   286    286     sqlite3 *db;              /* Database connection */
   287    287     Parse *pParse;            /* Parsing context */
   288    288     WhereClause *pWC;         /* WHERE clause terms */
   289    289     SrcList *pTabList;        /* FROM clause */
   290    290     ExprList *pOrderBy;       /* ORDER BY clause */
   291    291     WhereLoop *pNew;          /* Template WhereLoop */
          292  +  WhereLoop *pBest;         /* If non-NULL, store single best loop here */
   292    293     int mxTerm;               /* Maximum number of aTerm[] entries on pNew */
   293    294   };
   294    295   
   295    296   /*
   296    297   ** Bitmasks for the operators that indices are able to exploit.  An
   297    298   ** OR-ed combination of these values can be used when searching for
   298    299   ** terms in the where clause.
................................................................................
  5158   5159   **
  5159   5160   ** An existing WhereLoop entry might be overwritten if the new template
  5160   5161   ** is better and has fewer dependencies.  Or the template will be ignored
  5161   5162   ** and no insert will occur if an existing WhereLoop is faster and has
  5162   5163   ** fewer dependencies than the template.  Otherwise a new WhereLoop is
  5163   5164   ** added based no the template.
  5164   5165   */
  5165         -static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){
         5166  +static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  5166   5167     WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  5167   5168     WhereTerm **paTerm = 0;
  5168         -  sqlite3 *db = pWInfo->pParse->db;
         5169  +  sqlite3 *db = pBuilder->db;
         5170  +  WhereInfo *pWInfo = pBuilder->pWInfo;
         5171  +
         5172  +  if( (p = pBuilder->pBest)!=0 ){
         5173  +    if( p->maskSelf!=0 ){
         5174  +      if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
         5175  +        return SQLITE_OK;
         5176  +      }
         5177  +      if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
         5178  +       && p->prereq <= pTemplate->prereq ){
         5179  +        return SQLITE_OK;
         5180  +      }
         5181  +    }
         5182  +    *p = *pTemplate;
         5183  +    p->aTerm = 0;
         5184  +    p->u.vtab.needFree = 0;
         5185  +    return SQLITE_OK;
         5186  +  }
  5169   5187   
  5170   5188     /* Search for an existing WhereLoop to overwrite, or which takes
  5171   5189     ** priority over pTemplate.
  5172   5190     */
  5173   5191     for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
  5174   5192       if( p->iTab!=pTemplate->iTab ) continue;
  5175   5193       if( (p->prereq & pTemplate->prereq)==p->prereq
................................................................................
  5206   5224         return SQLITE_NOMEM;
  5207   5225       }
  5208   5226     }
  5209   5227     *p = *pTemplate;
  5210   5228     p->pNextLoop = pNext;
  5211   5229     *ppPrev = p;
  5212   5230     p->aTerm = paTerm;
  5213         -  if( pTemplate->nTerm ){
  5214         -    memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
         5231  +  if( p->nTerm ){
         5232  +    memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  5215   5233     }
  5216   5234     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  5217         -    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ) p->u.btree.pIndex = 0;
         5235  +    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
         5236  +      p->u.btree.pIndex = 0;
         5237  +    }
  5218   5238     }else{
  5219   5239       pTemplate->u.vtab.needFree = 0;
  5220   5240     }
  5221   5241     return SQLITE_OK;
  5222   5242   }
  5223   5243   
  5224   5244   /*
................................................................................
  5301   5321       }else{
  5302   5322         /* Each row involves a step of the index, then a binary search of
  5303   5323         ** the main table */
  5304   5324         pNew->rRun += pNew->nOut*(1 + rLogSize);
  5305   5325       }
  5306   5326       /* TBD: Adjust nOut and rRun for STAT3 range values */
  5307   5327       /* TBD: Adjust nOut for additional constraints */
  5308         -    rc = whereLoopInsert(pBuilder->pWInfo, pNew);
         5328  +    rc = whereLoopInsert(pBuilder, pNew);
  5309   5329       if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
  5310   5330        && pNew->u.btree.nEq<pProbe->nColumn
  5311   5331       ){
  5312   5332         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
  5313   5333       }
  5314   5334     }
  5315   5335     *pNew = savedLoop;
................................................................................
  5362   5382       }
  5363   5383       pProbe = &sPk;
  5364   5384     }
  5365   5385     rSize = (double)pSrc->pTab->nRowEst;
  5366   5386     rLogSize = estLog(rSize);
  5367   5387   
  5368   5388     /* Automatic indexes */
  5369         -  if( (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 
         5389  +  if( !pBuilder->pBest
         5390  +   && (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 
  5370   5391      && !pSrc->viaCoroutine
  5371   5392      && !pSrc->notIndexed
  5372   5393      && !pSrc->isCorrelated
  5373   5394     ){
  5374   5395       /* Generate auto-index WhereLoops */
  5375   5396       WhereClause *pWC = pBuilder->pWC;
  5376   5397       WhereTerm *pTerm;
................................................................................
  5381   5402           pNew->nTerm = 1;
  5382   5403           pNew->aTerm[0] = pTerm;
  5383   5404           pNew->rSetup = 2*rLogSize*pSrc->pTab->nRowEst;
  5384   5405           pNew->nOut = (double)10;
  5385   5406           pNew->rRun = rLogSize + pNew->nOut;
  5386   5407           pNew->wsFlags = WHERE_TEMP_INDEX;
  5387   5408           pNew->prereq = mExtra | pTerm->prereqRight;
  5388         -        rc = whereLoopInsert(pBuilder->pWInfo, pNew);
         5409  +        rc = whereLoopInsert(pBuilder, pNew);
  5389   5410         }
  5390   5411       }
  5391   5412     }
  5392   5413   
  5393   5414     /* Insert a full table scan */
  5394   5415     pNew->u.btree.nEq = 0;
  5395   5416     pNew->nTerm = 0;
................................................................................
  5396   5417     pNew->rSetup = (double)0;
  5397   5418     pNew->prereq = mExtra;
  5398   5419     pNew->u.btree.pIndex = 0;
  5399   5420     pNew->wsFlags = 0;
  5400   5421     pNew->nOut = rSize;
  5401   5422     pNew->rRun = rSize + rLogSize;
  5402   5423     /* TBD: Reduce nOut using constraints */
  5403         -  rc = whereLoopInsert(pBuilder->pWInfo, pNew);
         5424  +  rc = whereLoopInsert(pBuilder, pNew);
  5404   5425   
  5405   5426     /* Loop over all indices
  5406   5427     */
  5407   5428     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
  5408   5429       pNew->u.btree.nEq = 0;
  5409   5430       pNew->nTerm = 0;
  5410   5431       if( pProbe->tnum<=0 ){
................................................................................
  5561   5582         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  5562   5583         pIdxInfo->needToFreeIdxStr = 0;
  5563   5584         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  5564   5585         pNew->u.vtab.isOrdered = (u8)(pIdxInfo->nOrderBy!=0);
  5565   5586         pNew->rSetup = (double)0;
  5566   5587         pNew->rRun = pIdxInfo->estimatedCost;
  5567   5588         pNew->nOut = (double)25;
  5568         -      whereLoopInsert(pBuilder->pWInfo, pNew);
         5589  +      whereLoopInsert(pBuilder, pNew);
  5569   5590         if( pNew->u.vtab.needFree ){
  5570   5591           sqlite3_free(pNew->u.vtab.idxStr);
  5571   5592           pNew->u.vtab.needFree = 0;
  5572   5593         }
  5573   5594       }
  5574   5595     }  
  5575   5596   
  5576   5597   whereLoopAddVtab_exit:
  5577   5598     if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  5578   5599     sqlite3DbFree(db, pIdxInfo);
  5579   5600     return rc;
  5580   5601   }
         5602  +
         5603  +/*
         5604  +** Add WhereLoop entries to handle OR terms.  This works for either
         5605  +** btrees or virtual tables.
         5606  +*/
         5607  +static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
         5608  +  WhereClause *pWC;
         5609  +  WhereLoop *pNew;
         5610  +  WhereTerm *pTerm, *pWCEnd;
         5611  +  int rc = SQLITE_OK;
         5612  +  int iCur;
         5613  +  WhereClause tempWC;
         5614  +  WhereLoopBuilder sSubBuild;
         5615  +  WhereLoop sBest;
         5616  +  struct SrcList_item *pItem;
         5617  +  
         5618  +
         5619  +  pWC = pBuilder->pWC;
         5620  +  if( pWC->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
         5621  +  pWCEnd = pWC->a + pWC->nTerm;
         5622  +  pNew = pBuilder->pNew;
         5623  +  pItem = pBuilder->pTabList->a + pNew->iTab;
         5624  +  iCur = pItem->iCursor;
         5625  +  sSubBuild = *pBuilder;
         5626  +  sSubBuild.pOrderBy = 0;
         5627  +  sSubBuild.pBest = &sBest;
         5628  +  tempWC.pParse = pWC->pParse;
         5629  +  tempWC.pMaskSet = pWC->pMaskSet;
         5630  +  tempWC.pOuter = pWC;
         5631  +  tempWC.op = TK_AND;
         5632  +  tempWC.wctrlFlags = 0;
         5633  +  tempWC.nTerm = 1;
         5634  +
         5635  +  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
         5636  +    if( (pTerm->eOperator & WO_OR)!=0
         5637  +     && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
         5638  +    ){
         5639  +      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
         5640  +      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
         5641  +      WhereTerm *pOrTerm;
         5642  +      double rTotal = 0;
         5643  +      double nRow = 0;
         5644  +      Bitmask prereq = mExtra;
         5645  +
         5646  +
         5647  +      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
         5648  +        if( (pOrTerm->eOperator& WO_AND)!=0 ){
         5649  +          sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
         5650  +        }else if( pOrTerm->leftCursor==iCur ){
         5651  +          tempWC.a = pOrTerm;
         5652  +          sSubBuild.pWC = &tempWC;
         5653  +        }else{
         5654  +          continue;
         5655  +        }
         5656  +        sBest.maskSelf = 0;
         5657  +        if( IsVirtual(pItem->pTab) ){
         5658  +          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
         5659  +        }else{
         5660  +          rc = whereLoopAddBtree(&sSubBuild, mExtra);
         5661  +        }
         5662  +        if( sBest.maskSelf==0 ) break;
         5663  +        assert( sBest.rSetup==(double)0 );
         5664  +        rTotal += sBest.rRun;
         5665  +        nRow += sBest.nOut;
         5666  +        prereq |= sBest.prereq;
         5667  +      }
         5668  +      pNew->nTerm = 1;
         5669  +      pNew->aTerm[0] = pTerm;
         5670  +      pNew->wsFlags = WHERE_MULTI_OR;
         5671  +      pNew->rSetup = (double)0;
         5672  +      pNew->rRun = rTotal;
         5673  +      pNew->nOut = nRow;
         5674  +      pNew->prereq = prereq;
         5675  +      rc = whereLoopInsert(pBuilder, pNew);
         5676  +    }
         5677  +  }
         5678  +  return rc;
         5679  +}
  5581   5680   
  5582   5681   /*
  5583   5682   ** Add all WhereLoop objects for all tables 
  5584   5683   */
  5585   5684   static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  5586   5685     Bitmask mExtra = 0;
  5587   5686     Bitmask mPrior = 0;
................................................................................
  5615   5714         mExtra = mPrior;
  5616   5715       }
  5617   5716       if( IsVirtual(pItem->pTab) ){
  5618   5717         rc = whereLoopAddVirtual(pBuilder, mExtra);
  5619   5718       }else{
  5620   5719         rc = whereLoopAddBtree(pBuilder, mExtra);
  5621   5720       }
  5622         -#if 0
  5623   5721       if( rc==SQLITE_OK ){
  5624   5722         rc = whereLoopAddOr(pBuilder, mExtra);
  5625   5723       }
  5626         -#endif
  5627   5724       mPrior |= pNew->maskSelf;
  5628   5725       if( rc || db->mallocFailed ) break;
  5629   5726     }
  5630   5727   whereLoopAddAll_end:
  5631   5728     whereLoopDelete(db, pBuilder->pNew);
  5632   5729     pBuilder->pNew = 0;
  5633   5730     return rc;