/ Check-in [586b55d8]
Login

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

Overview
Comment:Update the NGQP so that it can produce plans that include automatic indices.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:586b55d8d7722de1c0530b3b832bae0511e6d05c
User & Date: drh 2013-05-10 15:16:30
Context
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
03:30
Factor out common operations into whereLoopAddAll(). Add stubs for missing features. check-in: 0278e420 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  +  int mxTerm;               /* Maximum number of aTerm[] entries on pNew */
   292    293   };
   293    294   
   294    295   /*
   295    296   ** Bitmasks for the operators that indices are able to exploit.  An
   296    297   ** OR-ed combination of these values can be used when searching for
   297    298   ** terms in the where clause.
   298    299   */
................................................................................
  5237   5238     WhereLoop *pNew;                /* Template WhereLoop under construction */
  5238   5239     WhereTerm *pTerm;               /* A WhereTerm under consideration */
  5239   5240     int opMask;                     /* Valid operators for constraints */
  5240   5241     WhereScan scan;                 /* Iterator for WHERE terms */
  5241   5242     WhereLoop savedLoop;            /* Saved original content of pNew[] */
  5242   5243     int iCol;                       /* Index of the column in the table */
  5243   5244     int rc = SQLITE_OK;             /* Return code */
         5245  +  double rLogSize;                /* Logarithm of table size */
  5244   5246   
  5245   5247     db = pBuilder->db;
  5246   5248     pNew = pBuilder->pNew;
  5247   5249     if( db->mallocFailed ) return SQLITE_NOMEM;
  5248   5250   
  5249   5251     assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  5250   5252     assert( pNew->u.btree.nEq<pProbe->nColumn );
................................................................................
  5258   5260     }
  5259   5261   
  5260   5262     iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  5261   5263     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  5262   5264                           opMask, iCol>=0 ? pProbe : 0);
  5263   5265     savedLoop = *pNew;
  5264   5266     pNew->rSetup = (double)0;
         5267  +  rLogSize = estLog(pProbe->aiRowEst[0]);
  5265   5268     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  5266   5269       int nIn = 1;
  5267   5270       pNew->u.btree.nEq = savedLoop.u.btree.nEq;
  5268   5271       pNew->nTerm = savedLoop.nTerm;
         5272  +    if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */
  5269   5273       pNew->aTerm[pNew->nTerm++] = pTerm;
  5270   5274       pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
  5271   5275       if( pTerm->eOperator & WO_IN ){
  5272   5276         Expr *pExpr = pTerm->pExpr;
  5273   5277         pNew->wsFlags |= WHERE_COLUMN_IN;
  5274   5278         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  5275   5279           /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
................................................................................
  5287   5291       }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
  5288   5292         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
  5289   5293         pNew->nOut = savedLoop.nOut/3;
  5290   5294       }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
  5291   5295         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
  5292   5296         pNew->nOut = savedLoop.nOut/3;
  5293   5297       }
  5294         -    pNew->rRun = pNew->nOut + estLog(pProbe->aiRowEst[0])*nIn;
         5298  +    pNew->rRun = rLogSize*nIn;  /* Cost for nIn binary searches */
         5299  +    if( pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK) ){
         5300  +      pNew->rRun += pNew->nOut;  /* Unit step cost to reach each row */
         5301  +    }else{
         5302  +      /* Each row involves a step of the index, then a binary search of
         5303  +      ** the main table */
         5304  +      pNew->rRun += pNew->nOut*(1 + rLogSize);
         5305  +    }
         5306  +    /* TBD: Adjust nOut and rRun for STAT3 range values */
         5307  +    /* TBD: Adjust nOut for additional constraints */
  5295   5308       rc = whereLoopInsert(pBuilder->pWInfo, pNew);
  5296   5309       if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
  5297   5310        && pNew->u.btree.nEq<pProbe->nColumn
  5298   5311       ){
  5299   5312         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
  5300   5313       }
  5301   5314     }
................................................................................
  5314   5327     Index *pProbe;              /* An index we are evaluating */
  5315   5328     Index sPk;                  /* A fake index object for the primary key */
  5316   5329     tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  5317   5330     int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  5318   5331     struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  5319   5332     WhereLoop *pNew;            /* Template WhereLoop object */
  5320   5333     int rc = SQLITE_OK;         /* Return code */
         5334  +  double rSize;               /* number of rows in the table */
         5335  +  double rLogSize;            /* Logarithm of the number of rows in the table */
  5321   5336   
  5322   5337     pNew = pBuilder->pNew;
  5323   5338     pSrc = pBuilder->pTabList->a + pNew->iTab;
  5324   5339   
  5325   5340     if( pSrc->pIndex ){
  5326   5341       /* An INDEXED BY clause specifies a particular index to use */
  5327   5342       pProbe = pSrc->pIndex;
................................................................................
  5343   5358       if( pSrc->notIndexed==0 ){
  5344   5359         /* The real indices of the table are only considered if the
  5345   5360         ** NOT INDEXED qualifier is omitted from the FROM clause */
  5346   5361         sPk.pNext = pFirst;
  5347   5362       }
  5348   5363       pProbe = &sPk;
  5349   5364     }
         5365  +  rSize = (double)pSrc->pTab->nRowEst;
         5366  +  rLogSize = estLog(rSize);
         5367  +
         5368  +  /* Automatic indexes */
         5369  +  if( (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 
         5370  +   && !pSrc->viaCoroutine
         5371  +   && !pSrc->notIndexed
         5372  +   && !pSrc->isCorrelated
         5373  +  ){
         5374  +    /* Generate auto-index WhereLoops */
         5375  +    WhereClause *pWC = pBuilder->pWC;
         5376  +    WhereTerm *pTerm;
         5377  +    WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
         5378  +    for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
         5379  +      if( termCanDriveIndex(pTerm, pSrc, 0) ){
         5380  +        pNew->u.btree.nEq = 1;
         5381  +        pNew->nTerm = 1;
         5382  +        pNew->aTerm[0] = pTerm;
         5383  +        pNew->rSetup = 2*rLogSize*pSrc->pTab->nRowEst;
         5384  +        pNew->nOut = (double)10;
         5385  +        pNew->rRun = rLogSize + pNew->nOut;
         5386  +        pNew->wsFlags = WHERE_TEMP_INDEX;
         5387  +        pNew->prereq = mExtra | pTerm->prereqRight;
         5388  +        rc = whereLoopInsert(pBuilder->pWInfo, pNew);
         5389  +      }
         5390  +    }
         5391  +  }
  5350   5392   
  5351   5393     /* Insert a full table scan */
  5352   5394     pNew->u.btree.nEq = 0;
  5353   5395     pNew->nTerm = 0;
  5354   5396     pNew->rSetup = (double)0;
  5355   5397     pNew->prereq = mExtra;
  5356   5398     pNew->u.btree.pIndex = 0;
  5357   5399     pNew->wsFlags = 0;
  5358         -  pNew->rRun = (double)pSrc->pTab->nRowEst;
  5359         -  pNew->nOut = (double)pSrc->pTab->nRowEst;
         5400  +  pNew->nOut = rSize;
         5401  +  pNew->rRun = rSize + rLogSize;
         5402  +  /* TBD: Reduce nOut using constraints */
  5360   5403     rc = whereLoopInsert(pBuilder->pWInfo, pNew);
  5361   5404   
  5362         -  /* TBD: Insert automatic index opportunities */
  5363         -
  5364   5405     /* Loop over all indices
  5365   5406     */
  5366   5407     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
  5367   5408       pNew->u.btree.nEq = 0;
  5368   5409       pNew->nTerm = 0;
  5369   5410       if( pProbe->tnum<=0 ){
  5370   5411         /* Integer primary key index */
................................................................................
  5474   5515       pIdxInfo->orderByConsumed = 0;
  5475   5516       /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  5476   5517       pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  5477   5518       rc = vtabBestIndex(pParse, pTab, pIdxInfo);
  5478   5519       if( rc ) goto whereLoopAddVtab_exit;
  5479   5520       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  5480   5521       pNew->prereq = 0;
         5522  +    assert( pIdxInfo->nConstraint<=pBuilder->mxTerm );
  5481   5523       for(i=0; i<pIdxInfo->nConstraint; i++) pNew->aTerm[i] = 0;
  5482   5524       mxTerm = -1;
  5483   5525       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  5484   5526         if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
  5485   5527           j = pIdxCons->iTermOffset;
  5486   5528           if( iTerm>=pIdxInfo->nConstraint
  5487   5529            || j<0
................................................................................
  5551   5593     int nTabList = pBuilder->pWInfo->nLevel;
  5552   5594     int rc = SQLITE_OK;
  5553   5595     WhereLoop *pNew;
  5554   5596   
  5555   5597     /* Loop over the tables in the join, from left to right */
  5556   5598     pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  5557   5599     if( pNew==0 ) return SQLITE_NOMEM;
  5558         -  pNew->aTerm = sqlite3DbMallocZero(db, (pWC->nTerm+1)*sizeof(pNew->aTerm[0]));
         5600  +  pBuilder->mxTerm = pWC->nTerm+1;
         5601  +  while( pWC->pOuter ){
         5602  +    pWC = pWC->pOuter;
         5603  +    pBuilder->mxTerm += pWC->nTerm;
         5604  +  }
         5605  +  pWC = pBuilder->pWC;
         5606  +  pNew->aTerm = sqlite3DbMallocZero(db,pBuilder->mxTerm*sizeof(pNew->aTerm[0]));
  5559   5607     if( pNew->aTerm==0 ){
  5560   5608       rc = SQLITE_NOMEM;
  5561   5609       goto whereLoopAddAll_end;
  5562   5610     }
  5563   5611     for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
  5564   5612       pNew->iTab = iTab;
  5565   5613       pNew->maskSelf = getMask(pWC->pMaskSet, pItem->iCursor);
................................................................................
  6327   6375     */
  6328   6376     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  6329   6377     if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
  6330   6378       pWInfo->okOnePass = 1;
  6331   6379       pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  6332   6380     }
  6333   6381   
         6382  +#if 0
         6383  +  /* Scaffolding:  Check the new query plan against the old.  Report any
         6384  +  ** discrepencies */
         6385  +  for(ii=0; ii<nTabList; ii++){
         6386  +    if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){
         6387  +      sqlite3DebugPrintf("(QP-Mismatch)");
         6388  +      break;
         6389  +    }
         6390  +  }
         6391  +#endif
         6392  +
  6334   6393     /* Open all tables in the pTabList and any indices selected for
  6335   6394     ** searching those tables.
  6336   6395     */
  6337   6396     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  6338   6397     notReady = ~(Bitmask)0;
  6339   6398     pWInfo->nRowOut = (double)1;
  6340   6399     for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){