/ Check-in [67367f1e]
Login

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

Overview
Comment:Work toward improving the NGQP's ability to optimize out ORDER BY clauses.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:67367f1e1f0c3eb6be65eea9873910aa62b49884
User & Date: drh 2013-05-21 15:52:07
Context
2013-05-21
19:23
Enhanced "wheretrace" output in the NGQP solver routine. check-in: 04dfb85a user: drh tags: nextgen-query-plan-exp
15:52
Work toward improving the NGQP's ability to optimize out ORDER BY clauses. check-in: 67367f1e user: drh tags: nextgen-query-plan-exp
2013-05-20
15:14
Merge in all trunk changes up through the 3.7.17 release. check-in: 14ab6675 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  1915   1915   ** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each
  1916   1916   ** jointype expresses the join between the table and the previous table.
  1917   1917   **
  1918   1918   ** In the colUsed field, the high-order bit (bit 63) is set if the table
  1919   1919   ** contains more than 63 columns and the 64-th or later column is used.
  1920   1920   */
  1921   1921   struct SrcList {
  1922         -  i16 nSrc;        /* Number of tables or subqueries in the FROM clause */
  1923         -  i16 nAlloc;      /* Number of entries allocated in a[] below */
         1922  +  u8 nSrc;        /* Number of tables or subqueries in the FROM clause */
         1923  +  u8 nAlloc;      /* Number of entries allocated in a[] below */
  1924   1924     struct SrcList_item {
  1925   1925       Schema *pSchema;  /* Schema to which this item is fixed */
  1926   1926       char *zDatabase;  /* Name of database holding this table */
  1927   1927       char *zName;      /* Name of the table */
  1928   1928       char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
  1929   1929       Table *pTab;      /* An SQL table corresponding to zName */
  1930   1930       Select *pSelect;  /* A SELECT statement used in place of a table name */

Changes to src/where.c.

    52     52   ** term of a join.  The WhereClause object holds a table of these
    53     53   ** objects using (maskSelf,prereq,) as the primary key.  Note that the
    54     54   ** same join term might have multiple associated WhereLoop objects.
    55     55   */
    56     56   struct WhereLoop {
    57     57     Bitmask prereq;       /* Bitmask of other loops that must run first */
    58     58     Bitmask maskSelf;     /* Bitmask identifying table iTab */
    59         -  u16 iTab;             /* Index of the table coded by this loop */
           59  +  u8 iTab;              /* Position in FROM clause of table coded by this loop */
           60  +  u8 iSortIdx;          /* Sorting index number.  0==None */
    60     61     u16 nTerm;            /* Number of entries in aTerm[] */
    61     62     u32 wsFlags;          /* WHERE_* flags describing the plan */
    62     63     double rSetup;        /* One-time setup cost (ex: create transient index) */
    63     64     double rRun;          /* Cost of running each loop */
    64     65     double nOut;          /* Estimated number of output rows */
    65     66     union {
    66     67       struct {               /* Information for internal btree tables */
................................................................................
  1983   1984     struct SrcList_item *pSrc,     /* Table we are trying to access */
  1984   1985     Bitmask notReady               /* Tables in outer loops of the join */
  1985   1986   ){
  1986   1987     char aff;
  1987   1988     if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  1988   1989     if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  1989   1990     if( (pTerm->prereqRight & notReady)!=0 ) return 0;
         1991  +  if( pTerm->u.leftColumn<0 ) return 0;
  1990   1992     aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  1991   1993     if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  1992   1994     return 1;
  1993   1995   }
  1994   1996   #endif
  1995   1997   
  1996   1998   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
................................................................................
  5164   5166   ** Insert or replace a WhereLoop entry using the template supplied.
  5165   5167   **
  5166   5168   ** An existing WhereLoop entry might be overwritten if the new template
  5167   5169   ** is better and has fewer dependencies.  Or the template will be ignored
  5168   5170   ** and no insert will occur if an existing WhereLoop is faster and has
  5169   5171   ** fewer dependencies than the template.  Otherwise a new WhereLoop is
  5170   5172   ** added based no the template.
         5173  +**
         5174  +** If pBuilder->pBest is not NULL then we only care about the very
         5175  +** best template and that template should be stored in pBuilder->pBest.
         5176  +** If pBuilder->pBest is NULL then a list of the best templates are stored
         5177  +** in pBuilder->pWInfo->pLoops.
         5178  +**
         5179  +** When accumulating multiple loops (when pBuilder->pBest is NULL) we
         5180  +** still might overwrite similar loops with the new template if the
         5181  +** template is better.  Loops may be overwritten if the following 
         5182  +** conditions are met:
         5183  +**
         5184  +**    (1)  They have the same iTab.
         5185  +**    (2)  They have the same iSortIdx.
         5186  +**    (3)  The template has same or fewer dependencies than the current loop
         5187  +**    (4)  The template has the same or lower cost than the current loop
  5171   5188   */
  5172   5189   static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  5173   5190     WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  5174   5191     WhereTerm **paTerm = 0;
  5175   5192     sqlite3 *db = pBuilder->db;
  5176   5193     WhereInfo *pWInfo = pBuilder->pWInfo;
  5177   5194   
         5195  +  /* If pBuilder->pBest is defined, then only keep track of the single
         5196  +  ** best WhereLoop.  pBuilder->pBest->maskSelf==0 indicates that no
         5197  +  ** prior WhereLoops have been evaluated and that the current pTemplate
         5198  +  ** is therefore the first and hence the best and should be retained.
         5199  +  */
  5178   5200     if( (p = pBuilder->pBest)!=0 ){
  5179   5201       if( p->maskSelf!=0 ){
  5180   5202         if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
  5181   5203           return SQLITE_OK;
  5182   5204         }
  5183   5205         if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
  5184   5206          && p->prereq <= pTemplate->prereq ){
................................................................................
  5191   5213       return SQLITE_OK;
  5192   5214     }
  5193   5215   
  5194   5216     /* Search for an existing WhereLoop to overwrite, or which takes
  5195   5217     ** priority over pTemplate.
  5196   5218     */
  5197   5219     for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
  5198         -    if( p->iTab!=pTemplate->iTab ) continue;
         5220  +    if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ) continue;
  5199   5221       if( (p->prereq & pTemplate->prereq)==p->prereq
  5200   5222        && p->rSetup<=pTemplate->rSetup
  5201   5223        && p->rRun<=pTemplate->rRun
  5202   5224       ){
  5203   5225         /* Already holding an equal or better WhereLoop.
  5204   5226         ** Return without changing or adding anything */
  5205   5227         return SQLITE_OK;
................................................................................
  5234   5256     p->pNextLoop = pNext;
  5235   5257     *ppPrev = p;
  5236   5258     p->aTerm = paTerm;
  5237   5259     if( p->nTerm ){
  5238   5260       memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  5239   5261     }
  5240   5262     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  5241         -    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
         5263  +    if( p->u.btree.pIndex && p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
  5242   5264         p->u.btree.pIndex = 0;
  5243   5265       }
  5244   5266     }else{
  5245   5267       pTemplate->u.vtab.needFree = 0;
  5246   5268     }
  5247   5269     return SQLITE_OK;
  5248   5270   }
................................................................................
  5337   5359       ){
  5338   5360         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
  5339   5361       }
  5340   5362     }
  5341   5363     *pNew = savedLoop;
  5342   5364     return rc;
  5343   5365   }
         5366  +
         5367  +/*
         5368  +** Return True if it is possible that pIndex might be useful in
         5369  +** implementing the ORDER BY clause in pBuilder.
         5370  +**
         5371  +** Return False if pBuilder does not contain an ORDER BY clause or
         5372  +** if there is no way for pIndex to be useful in implementing that
         5373  +** ORDER BY clause.
         5374  +*/
         5375  +static int indexMightHelpWithOrderBy(
         5376  +  WhereLoopBuilder *pBuilder,
         5377  +  Index *pIndex,
         5378  +  int iCursor
         5379  +){
         5380  +  ExprList *pOB;
         5381  +  int iCol;
         5382  +  int ii;
         5383  +
         5384  +  if( (pOB = pBuilder->pOrderBy)==0 ) return 0;
         5385  +  iCol = pIndex->aiColumn[0];
         5386  +  for(ii=0; ii<pOB->nExpr; ii++){
         5387  +    Expr *pExpr = pOB->a[ii].pExpr;
         5388  +    if( pExpr->op!=TK_COLUMN ) return 0;
         5389  +    if( pExpr->iTable==iCursor ){
         5390  +      if( pExpr->iColumn==iCol ) return 1;
         5391  +      return 0;
         5392  +    }
         5393  +  }
         5394  +  return 0;
         5395  +}
  5344   5396   
  5345   5397   /*
  5346   5398   ** Add all WhereLoop objects a single table of the join were the table
  5347   5399   ** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
  5348   5400   ** a b-tree table, not a virtual table.
  5349   5401   */
  5350   5402   static int whereLoopAddBtree(
................................................................................
  5354   5406     Index *pProbe;              /* An index we are evaluating */
  5355   5407     Index sPk;                  /* A fake index object for the primary key */
  5356   5408     tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  5357   5409     int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  5358   5410     struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  5359   5411     WhereLoop *pNew;            /* Template WhereLoop object */
  5360   5412     int rc = SQLITE_OK;         /* Return code */
         5413  +  int iSortIdx = 0;           /* Index number */
         5414  +  int b;                      /* A boolean value */
  5361   5415     double rSize;               /* number of rows in the table */
  5362   5416     double rLogSize;            /* Logarithm of the number of rows in the table */
  5363         -
         5417  +  
  5364   5418     pNew = pBuilder->pNew;
  5365   5419     pSrc = pBuilder->pTabList->a + pNew->iTab;
  5366   5420     assert( !IsVirtual(pSrc->pTab) );
  5367   5421   
  5368   5422     if( pSrc->pIndex ){
  5369   5423       /* An INDEXED BY clause specifies a particular index to use */
  5370   5424       pProbe = pSrc->pIndex;
................................................................................
  5415   5469           pNew->wsFlags = WHERE_TEMP_INDEX;
  5416   5470           pNew->prereq = mExtra | pTerm->prereqRight;
  5417   5471           rc = whereLoopInsert(pBuilder, pNew);
  5418   5472         }
  5419   5473       }
  5420   5474     }
  5421   5475   
  5422         -  /* Insert a full table scan */
  5423         -  pNew->u.btree.nEq = 0;
  5424         -  pNew->nTerm = 0;
  5425         -  pNew->rSetup = (double)0;
  5426         -  pNew->prereq = mExtra;
  5427         -  pNew->u.btree.pIndex = 0;
  5428         -  pNew->wsFlags = 0;
  5429         -  pNew->nOut = rSize;
  5430         -  pNew->rRun = rSize + rLogSize;
  5431         -  /* TBD: Reduce nOut using constraints */
  5432         -  rc = whereLoopInsert(pBuilder, pNew);
  5433         -
  5434   5476     /* Loop over all indices
  5435   5477     */
  5436         -  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
         5478  +  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  5437   5479       pNew->u.btree.nEq = 0;
  5438   5480       pNew->nTerm = 0;
         5481  +    pNew->iSortIdx = 0;
         5482  +    pNew->rSetup = (double)0;
         5483  +    pNew->prereq = mExtra;
         5484  +    pNew->u.btree.pIndex = pProbe;
         5485  +    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
  5439   5486       if( pProbe->tnum<=0 ){
  5440   5487         /* Integer primary key index */
  5441   5488         pNew->wsFlags = WHERE_IPK;
         5489  +
         5490  +      /* Full table scan */
         5491  +      pNew->nOut = rSize;
         5492  +      pNew->rRun = (rSize + rLogSize)*(3+b); /* 4x penalty for a full-scan */
         5493  +      rc = whereLoopInsert(pBuilder, pNew);
         5494  +      if( rc ) break;
  5442   5495       }else{
  5443   5496         Bitmask m = pSrc->colUsed;
  5444   5497         int j;
  5445   5498         for(j=pProbe->nColumn-1; j>=0; j--){
  5446   5499           int x = pProbe->aiColumn[j];
  5447   5500           if( x<BMS-1 ){
  5448   5501             m &= ~(((Bitmask)1)<<x);
  5449   5502           }
  5450   5503         }
  5451         -      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
         5504  +      pNew->wsFlags = (m==0) ? WHERE_IDX_ONLY : 0;
         5505  +
         5506  +      /* Full scan via index */
         5507  +      if( m==0 || b ){
         5508  +        pNew->iSortIdx = b ? iSortIdx : 0;
         5509  +        pNew->nOut = rSize;
         5510  +        pNew->rRun = (m==0) ? (rSize + rLogSize)*(1+b) : (rSize*rLogSize);
         5511  +        rc = whereLoopInsert(pBuilder, pNew);
         5512  +        if( rc ) break;
         5513  +      }
  5452   5514       }
  5453         -    pNew->u.btree.pIndex = pProbe;
  5454         -
  5455   5515       rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);
  5456   5516   
  5457   5517       /* If there was an INDEXED BY clause, then only that one index is
  5458   5518       ** considered. */
  5459   5519       if( pSrc->pIndex ) break;
  5460   5520     }
  5461   5521     return rc;
................................................................................
  5677   5737         pNew->nTerm = 1;
  5678   5738         pNew->aTerm[0] = pTerm;
  5679   5739         pNew->wsFlags = WHERE_MULTI_OR;
  5680   5740         pNew->rSetup = (double)0;
  5681   5741         pNew->rRun = rTotal;
  5682   5742         pNew->nOut = nRow;
  5683   5743         pNew->prereq = prereq;
         5744  +      memset(&pNew->u, 0, sizeof(pNew->u));
  5684   5745         rc = whereLoopInsert(pBuilder, pNew);
  5685   5746       }
  5686   5747     }
  5687   5748     return rc;
  5688   5749   }
  5689   5750   
  5690   5751   /*