/ Check-in [2c2577e6]
Login

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

Overview
Comment:Modify the query planner interface so that it always passes in the result set. This is the first step toward adding an optimization that will omit tables from a join that do not contribute to the result.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | omit-join-table-opt
Files: files | file ages | folders
SHA1: 2c2577e69ccb47f1af674a755e71221e2ca0b322
User & Date: drh 2013-06-21 00:35:37
Context
2013-06-21
02:05
Attempt to disable inner loops of a join that do not generate output. This does not work, since the inner loops might run zero times and thus inhibit all output. Needs to be enhanced to work only for LEFT JOINs or when we know that the inner loop will always run at least once. check-in: ca839723 user: drh tags: omit-join-table-opt
00:35
Modify the query planner interface so that it always passes in the result set. This is the first step toward adding an optimization that will omit tables from a join that do not contribute to the result. check-in: 2c2577e6 user: drh tags: omit-join-table-opt
2013-06-20
17:32
Add a NEVER() macro and an explanation comment around an unreachable branch in the STAT3 logic. check-in: 604c3c5d user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  4257   4257       sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  4258   4258     }else{
  4259   4259       sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  4260   4260     }
  4261   4261   
  4262   4262     if( !isAgg && pGroupBy==0 ){
  4263   4263       /* No aggregate functions and no GROUP BY clause */
  4264         -    ExprList *pDist = (sDistinct.isTnct ? p->pEList : 0);
         4264  +    u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
  4265   4265   
  4266   4266       /* Begin the database scan. */
  4267         -    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, pDist, 0,0);
         4267  +    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList,
         4268  +                               wctrlFlags, 0);
  4268   4269       if( pWInfo==0 ) goto select_end;
  4269   4270       if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
  4270   4271         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  4271   4272       }
  4272         -    if( sqlite3WhereIsDistinct(pWInfo) ){
         4273  +    if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  4273   4274         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  4274   4275       }
  4275   4276       if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0;
  4276   4277   
  4277   4278       /* If sorting index that was created by a prior OP_OpenEphemeral 
  4278   4279       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  4279   4280       ** into an OP_Noop.

Changes to src/sqliteInt.h.

  1970   1970   #define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
  1971   1971   #define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
  1972   1972   #define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
  1973   1973   #define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
  1974   1974   #define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
  1975   1975   #define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
  1976   1976   #define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */
         1977  +#define WHERE_WANT_DISTINCT    0x0400 /* All output needs to be distinct */
  1977   1978   
  1978   1979   /* Allowed return values from sqlite3WhereIsDistinct()
  1979   1980   */
  1980   1981   #define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
  1981   1982   #define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
  1982   1983   #define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
  1983   1984   #define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */

Changes to src/where.c.

   379    379   ** An instance of this object holds the complete state of the query
   380    380   ** planner.
   381    381   */
   382    382   struct WhereInfo {
   383    383     Parse *pParse;            /* Parsing and code generating context */
   384    384     SrcList *pTabList;        /* List of tables in the join */
   385    385     ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
   386         -  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */
          386  +  ExprList *pResultSet;     /* Result set. DISTINCT operates on these */
   387    387     WhereLoop *pLoops;        /* List of all WhereLoop objects */
   388    388     Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
   389    389     WhereCost nRowOut;        /* Estimated number of output rows */
   390    390     u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
   391    391     u8 bOBSat;                /* ORDER BY satisfied by indices */
   392    392     u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
   393    393     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
................................................................................
  3924   3924   /*
  3925   3925   ** Print a WhereLoop object for debugging purposes
  3926   3926   */
  3927   3927   static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  3928   3928     int nb = 1+(pTabList->nSrc+7)/8;
  3929   3929     struct SrcList_item *pItem = pTabList->a + p->iTab;
  3930   3930     Table *pTab = pItem->pTab;
  3931         -  sqlite3DebugPrintf("%c %2d.%0*llx.%0*llx", p->cId,
         3931  +  sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p->cId,
  3932   3932                        p->iTab, nb, p->maskSelf, nb, p->prereq);
  3933         -  sqlite3DebugPrintf(" %8s",
         3933  +  sqlite3DebugPrintf(" %12s",
  3934   3934                        pItem->zAlias ? pItem->zAlias : pTab->zName);
  3935   3935     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  3936   3936       if( p->u.btree.pIndex ){
  3937   3937         const char *zName = p->u.btree.pIndex->zName;
  3938   3938         if( zName==0 ) zName = "ipk";
  3939   3939         if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
  3940   3940           int i = sqlite3Strlen30(zName) - 1;
  3941   3941           while( zName[i]!='_' ) i--;
  3942   3942           zName += i;
  3943   3943         }
  3944         -      sqlite3DebugPrintf(".%-12s %2d", zName, p->u.btree.nEq);
         3944  +      sqlite3DebugPrintf(".%-16s %2d", zName, p->u.btree.nEq);
  3945   3945       }else{
  3946         -      sqlite3DebugPrintf("%16s","");
         3946  +      sqlite3DebugPrintf("%20s","");
  3947   3947       }
  3948   3948     }else{
  3949   3949       char *z;
  3950   3950       if( p->u.vtab.idxStr ){
  3951   3951         z = sqlite3_mprintf("(%d,\"%s\",%x)",
  3952   3952                   p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask);
  3953   3953       }else{
  3954   3954         z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask);
  3955   3955       }
  3956         -    sqlite3DebugPrintf(" %-15s", z);
         3956  +    sqlite3DebugPrintf(" %-19s", z);
  3957   3957       sqlite3_free(z);
  3958   3958     }
  3959         -  sqlite3DebugPrintf(" fg %05x N %d", p->wsFlags, p->nLTerm);
         3959  +  sqlite3DebugPrintf(" f %04x N %d", p->wsFlags, p->nLTerm);
  3960   3960     sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut);
  3961   3961   }
  3962   3962   #endif
  3963   3963   
  3964   3964   /*
  3965   3965   ** Convert bulk memory into a valid WhereLoop that can be passed
  3966   3966   ** to whereLoopClear harmlessly.
................................................................................
  5366   5366     /* Load the lowest cost path into pWInfo */
  5367   5367     for(iLoop=0; iLoop<nLoop; iLoop++){
  5368   5368       WhereLevel *pLevel = pWInfo->a + iLoop;
  5369   5369       pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
  5370   5370       pLevel->iFrom = pWLoop->iTab;
  5371   5371       pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  5372   5372     }
  5373         -  if( (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 
  5374         -   && pWInfo->pDistinct
         5373  +  if( (pWInfo->wctrlFlags & (WHERE_DISTINCTBY|WHERE_WANT_DISTINCT))
         5374  +                ==WHERE_WANT_DISTINCT
  5375   5375      && nRowEst
  5376   5376     ){
  5377   5377       Bitmask notUsed;
  5378         -    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinct, pFrom,
         5378  +    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
  5379   5379                    WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
  5380   5380       if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5381   5381     }
  5382   5382     if( pFrom->isOrdered ){
  5383   5383       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  5384   5384         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5385   5385       }else{
................................................................................
  5460   5460     if( pLoop->wsFlags ){
  5461   5461       pLoop->nOut = (WhereCost)1;
  5462   5462       pWInfo->a[0].pWLoop = pLoop;
  5463   5463       pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
  5464   5464       pWInfo->a[0].iTabCur = iCur;
  5465   5465       pWInfo->nRowOut = 1;
  5466   5466       if( pWInfo->pOrderBy ) pWInfo->bOBSat =  1;
  5467         -    if( pWInfo->pDistinct ) pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
         5467  +    if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
         5468  +      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
         5469  +    }
  5468   5470   #ifdef SQLITE_DEBUG
  5469   5471       pLoop->cId = '0';
  5470   5472   #endif
  5471   5473       return 1;
  5472   5474     }
  5473   5475     return 0;
  5474   5476   }
................................................................................
  5550   5552   **
  5551   5553   ** pOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
  5552   5554   ** if there is one.  If there is no ORDER BY clause or if this routine
  5553   5555   ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
  5554   5556   */
  5555   5557   WhereInfo *sqlite3WhereBegin(
  5556   5558     Parse *pParse,        /* The parser context */
  5557         -  SrcList *pTabList,    /* A list of all tables to be scanned */
         5559  +  SrcList *pTabList,    /* FROM clause: A list of all tables to be scanned */
  5558   5560     Expr *pWhere,         /* The WHERE clause */
  5559   5561     ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
  5560         -  ExprList *pDistinct,  /* The select-list for DISTINCT queries - or NULL */
         5562  +  ExprList *pResultSet, /* Result set of the query */
  5561   5563     u16 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
  5562   5564     int iIdxCur           /* If WHERE_ONETABLE_ONLY is set, index cursor number */
  5563   5565   ){
  5564   5566     int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
  5565   5567     int nTabList;              /* Number of elements in pTabList */
  5566   5568     WhereInfo *pWInfo;         /* Will become the return value of this function */
  5567   5569     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
................................................................................
  5609   5611       pWInfo = 0;
  5610   5612       goto whereBeginError;
  5611   5613     }
  5612   5614     pWInfo->nLevel = nTabList;
  5613   5615     pWInfo->pParse = pParse;
  5614   5616     pWInfo->pTabList = pTabList;
  5615   5617     pWInfo->pOrderBy = pOrderBy;
  5616         -  pWInfo->pDistinct = pDistinct;
         5618  +  pWInfo->pResultSet = pResultSet;
  5617   5619     pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  5618   5620     pWInfo->wctrlFlags = wctrlFlags;
  5619   5621     pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  5620   5622     pMaskSet = &pWInfo->sMaskSet;
  5621   5623     sWLB.pWInfo = pWInfo;
  5622   5624     sWLB.pWC = &pWInfo->sWC;
  5623   5625     sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList];
................................................................................
  5624   5626     whereLoopInit(sWLB.pNew);
  5625   5627   #ifdef SQLITE_DEBUG
  5626   5628     sWLB.pNew->cId = '*';
  5627   5629   #endif
  5628   5630   
  5629   5631     /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  5630   5632     ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  5631         -  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;
         5633  +  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){
         5634  +    wctrlFlags &= ~WHERE_WANT_DISTINCT;
         5635  +  }
  5632   5636   
  5633   5637     /* Split the WHERE clause into separate subexpressions where each
  5634   5638     ** subexpression is separated by an AND operator.
  5635   5639     */
  5636   5640     initMaskSet(pMaskSet);
  5637   5641     whereClauseInit(&pWInfo->sWC, pWInfo);
  5638   5642     sqlite3ExprCodeConstants(pParse, pWhere);
................................................................................
  5646   5650       pWhere = 0;
  5647   5651     }
  5648   5652   
  5649   5653     /* Special case: No FROM clause
  5650   5654     */
  5651   5655     if( nTabList==0 ){
  5652   5656       if( pOrderBy ) pWInfo->bOBSat = 1;
  5653         -    if( pDistinct ) pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
         5657  +    if( wctrlFlags & WHERE_WANT_DISTINCT ){
         5658  +      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
         5659  +    }
  5654   5660     }
  5655   5661   
  5656   5662     /* Assign a bit from the bitmask to every term in the FROM clause.
  5657   5663     **
  5658   5664     ** When assigning bitmask values to FROM clause cursors, it must be
  5659   5665     ** the case that if X is the bitmask for the N-th FROM clause term then
  5660   5666     ** the bitmask for all FROM clause terms to the left of the N-th term
................................................................................
  5693   5699       goto whereBeginError;
  5694   5700     }
  5695   5701   
  5696   5702     /* If the ORDER BY (or GROUP BY) clause contains references to general
  5697   5703     ** expressions, then we won't be able to satisfy it using indices, so
  5698   5704     ** go ahead and disable it now.
  5699   5705     */
  5700         -  if( pOrderBy && pDistinct ){
         5706  +  if( pOrderBy && (wctrlFlags & WHERE_WANT_DISTINCT)!=0 ){
  5701   5707       for(ii=0; ii<pOrderBy->nExpr; ii++){
  5702   5708         Expr *pExpr = sqlite3ExprSkipCollate(pOrderBy->a[ii].pExpr);
  5703   5709         if( pExpr->op!=TK_COLUMN ){
  5704   5710           pWInfo->pOrderBy = pOrderBy = 0;
  5705   5711           break;
  5706   5712         }else if( pExpr->iColumn<0 ){
  5707   5713           break;
  5708   5714         }
  5709   5715       }
  5710   5716     }
  5711   5717   
  5712         -  /* Check if the DISTINCT qualifier, if there is one, is redundant. 
  5713         -  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  5714         -  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  5715         -  */
  5716         -  if( pDistinct ){
  5717         -    if( isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){
  5718         -      pDistinct = 0;
         5718  +  if( wctrlFlags & WHERE_WANT_DISTINCT ){
         5719  +    if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){
         5720  +      /* The DISTINCT marking is pointless.  Ignore it. */
         5721  +      wctrlFlags &= ~WHERE_WANT_DISTINCT;
  5719   5722         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5720   5723       }else if( pOrderBy==0 ){
         5724  +      /* Try to ORDER BY the result set to make distinct processing easier */
  5721   5725         pWInfo->wctrlFlags |= WHERE_DISTINCTBY;
  5722         -      pWInfo->pOrderBy = pDistinct;
         5726  +      pWInfo->pOrderBy = pResultSet;
  5723   5727       }
  5724   5728     }
  5725   5729   
  5726   5730     /* Construct the WhereLoop objects */
  5727   5731     WHERETRACE(0xffff,("*** Optimizer Start ***\n"));
  5728   5732     if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
  5729   5733       rc = whereLoopAddAll(&sWLB);

Changes to test/alter2.test.

   116    116   } {1 2 10 3 4 {} 5 6 {}}
   117    117   do_test alter2-1.5 {
   118    118     execsql {
   119    119       CREATE INDEX abc_i ON abc(c);
   120    120     }
   121    121   } {}
   122    122   do_test alter2-1.6 {
          123  +breakpoint
   123    124     execsql {
   124    125       SELECT c FROM abc ORDER BY c;
   125    126     }
   126    127   } {{} {} 10}
   127    128   do_test alter2-1.7 {
   128    129     execsql {
   129    130       SELECT * FROM abc WHERE c = 10;