/ Check-in [04dfb85a]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Enhanced "wheretrace" output in the NGQP solver routine.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 04dfb85a2a7025d4b5056b73fa8477691323919f
User & Date: drh 2013-05-21 19:23:10
Context
2013-05-22
02:06
Improvements to ORDER BY handling in the NGQP. Fix an "exit" mistakenly left in a test script during the previous check-in. check-in: 12c709b4 user: drh tags: nextgen-query-plan-exp
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

    24     24   */
    25     25   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
    26     26   /***/ int sqlite3WhereTrace = 0;
    27     27   #endif
    28     28   #if defined(SQLITE_DEBUG) \
    29     29       && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
    30     30   # define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
           31  +# define WHERETRACE_ENABLED 1
    31     32   #else
    32     33   # define WHERETRACE(X)
    33     34   #endif
    34     35   
    35     36   /* Forward reference
    36     37   */
    37     38   typedef struct WhereClause WhereClause;
................................................................................
    52     53   ** term of a join.  The WhereClause object holds a table of these
    53     54   ** objects using (maskSelf,prereq,) as the primary key.  Note that the
    54     55   ** same join term might have multiple associated WhereLoop objects.
    55     56   */
    56     57   struct WhereLoop {
    57     58     Bitmask prereq;       /* Bitmask of other loops that must run first */
    58     59     Bitmask maskSelf;     /* Bitmask identifying table iTab */
           60  +#ifdef SQLITE_DEBUG
           61  +  char cId;             /* Symbolic ID of this loop for debugging use */
           62  +#endif
    59     63     u8 iTab;              /* Position in FROM clause of table coded by this loop */
    60     64     u8 iSortIdx;          /* Sorting index number.  0==None */
    61     65     u16 nTerm;            /* Number of entries in aTerm[] */
    62     66     u32 wsFlags;          /* WHERE_* flags describing the plan */
    63     67     double rSetup;        /* One-time setup cost (ex: create transient index) */
    64     68     double rRun;          /* Cost of running each loop */
    65     69     double nOut;          /* Estimated number of output rows */
................................................................................
  1831   1835   
  1832   1836   /*
  1833   1837   ** Two routines for printing the content of an sqlite3_index_info
  1834   1838   ** structure.  Used for testing and debugging only.  If neither
  1835   1839   ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
  1836   1840   ** are no-ops.
  1837   1841   */
  1838         -#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
         1842  +#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
  1839   1843   static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
  1840   1844     int i;
  1841   1845     if( !sqlite3WhereTrace ) return;
  1842   1846     for(i=0; i<p->nConstraint; i++){
  1843   1847       sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
  1844   1848          i,
  1845   1849          p->aConstraint[i].iColumn,
................................................................................
  5062   5066   ** analysis only.
  5063   5067   */
  5064   5068   char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
  5065   5069   static int nQPlan = 0;              /* Next free slow in _query_plan[] */
  5066   5070   
  5067   5071   #endif /* SQLITE_TEST */
  5068   5072   
  5069         -#if defined(SQLITE_DEBUG) \
  5070         -    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
         5073  +#ifdef WHERETRACE_ENABLED
  5071   5074   /*
  5072   5075   ** Print a WhereLoop object for debugging purposes
  5073   5076   */
  5074   5077   static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  5075   5078     int nb = 2*((pTabList->nSrc+15)/16);
  5076   5079     struct SrcList_item *pItem = pTabList->a + p->iTab;
  5077   5080     Table *pTab = pItem->pTab;
  5078         -  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
         5081  +  sqlite3DebugPrintf("%c %2d.%0*llx.%0*llx", p->cId,
  5079   5082                        p->iTab, nb, p->maskSelf, nb, p->prereq);
  5080   5083     sqlite3DebugPrintf(" %8s",
  5081   5084                        pItem->zAlias ? pItem->zAlias : pTab->zName);
  5082   5085     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  5083   5086       if( p->u.btree.pIndex ){
  5084   5087         const char *zName = p->u.btree.pIndex->zName;
  5085   5088         if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
................................................................................
  5098   5101       }else{
  5099   5102         z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum);
  5100   5103       }
  5101   5104       sqlite3DebugPrintf(" %-15s", z);
  5102   5105       sqlite3_free(z);
  5103   5106     }
  5104   5107     sqlite3DebugPrintf(" fg %08x N %2d", p->wsFlags, p->nTerm);
  5105         -  sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
         5108  +  sqlite3DebugPrintf(" cost %.2g,%.2g,%.2g\n",
  5106   5109                        p->prereq, p->rSetup, p->rRun, p->nOut);
  5107   5110   }
  5108   5111   #endif
  5109   5112   
  5110   5113   /*
  5111   5114   ** Deallocate internal memory used by a WhereLoop object
  5112   5115   */
................................................................................
  5873   5876     }
  5874   5877       
  5875   5878     for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
  5876   5879       pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
  5877   5880       assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
  5878   5881       isUnique = 1;
  5879   5882       if( pLoop->wsFlags & WHERE_IPK ){
  5880         -      if( (pLoop->wsFlags & WHERE_COLUMN_EQ)!=0 ) isUnique = 0;
         5883  +      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
         5884  +      if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
  5881   5885         pIndex = 0;
  5882   5886         nColumn = 1;
  5883   5887       }else if( pLoop->u.btree.pIndex==0 ){
  5884   5888         return 0;
  5885   5889       }else{
  5886   5890         pIndex = pLoop->u.btree.pIndex;
  5887   5891         nColumn = pIndex->nColumn;
................................................................................
  5931   5935     }
  5932   5936     if( nUsed==nOrderBy ){
  5933   5937       *pRevMask = revMask;
  5934   5938       return 1;
  5935   5939     }
  5936   5940     return -1;
  5937   5941   }
         5942  +
         5943  +#ifdef WHERETRACE_ENABLED
         5944  +/* For debugging use only: */
         5945  +static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
         5946  +  static char zName[65];
         5947  +  int i;
         5948  +  for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
         5949  +  if( pLast ) zName[i++] = pLast->cId;
         5950  +  zName[i] = 0;
         5951  +  return zName;
         5952  +}
         5953  +#endif
  5938   5954   
  5939   5955   
  5940   5956   /*
  5941   5957   ** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
  5942   5958   ** attempts to find the lowest cost path that visits each WhereLoop
  5943   5959   ** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
  5944   5960   **
................................................................................
  6040   6056           /* Check to see if pWLoop should be added to the mxChoice best so far */
  6041   6057           for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
  6042   6058             if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){
  6043   6059               break;
  6044   6060             }
  6045   6061           }
  6046   6062           if( jj>=nTo ){
  6047         -          if( nTo>=mxChoice && rCost>=mxCost ) continue;
         6063  +          if( nTo>=mxChoice && rCost>=mxCost ){
         6064  +#ifdef WHERETRACE_ENABLE
         6065  +            if( sqlite3WhereTrace>=3 ){
         6066  +              sqlite3DebugPrintf("Skip   %s cost=%-7.2g order=%c\n",
         6067  +                  wherePathName(pFrom, iLoop, pWLoop), rCost,
         6068  +                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         6069  +            }
         6070  +#endif
         6071  +            continue;
         6072  +          }
         6073  +          /* Add a new Path to the aTo[] set */
  6048   6074             if( nTo<mxChoice ){
         6075  +            /* Increase the size of the aTo set by one */
  6049   6076               jj = nTo++;
  6050   6077             }else{
         6078  +            /* New path replaces the prior worst to keep count below mxChoice */
  6051   6079               for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); }
  6052   6080             }
  6053   6081             pTo = &aTo[jj];
         6082  +#ifdef WHERETRACE_ENABLED
         6083  +          if( sqlite3WhereTrace>=3 ){
         6084  +            sqlite3DebugPrintf("New    %s cost=%-7.2g order=%c\n",
         6085  +                wherePathName(pFrom, iLoop, pWLoop), rCost,
         6086  +                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         6087  +          }
         6088  +#endif
  6054   6089           }else{
  6055         -          if( pTo->rCost<=rCost ) continue;
         6090  +          if( pTo->rCost<=rCost ){
         6091  +#ifdef WHERETRACE_ENABLED
         6092  +            if( sqlite3WhereTrace>=3 ){
         6093  +              sqlite3DebugPrintf(
         6094  +                  "Skip   %s cost=%-7.2g order=%c",
         6095  +                  wherePathName(pFrom, iLoop, pWLoop), rCost,
         6096  +                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         6097  +              sqlite3DebugPrintf("   vs %s cost=%-7.2g order=%c\n",
         6098  +                  wherePathName(pTo, iLoop+1, 0), pTo->rCost,
         6099  +                  pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
         6100  +            }
         6101  +#endif
         6102  +            continue;
         6103  +          }
         6104  +          /* A new and better score for a previously created equivalent path */
         6105  +#ifdef WHERETRACE_ENABLED
         6106  +          if( sqlite3WhereTrace>=3 ){
         6107  +            sqlite3DebugPrintf(
         6108  +                "Update %s cost=%-7.2g order=%c",
         6109  +                wherePathName(pFrom, iLoop, pWLoop), rCost,
         6110  +                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         6111  +            sqlite3DebugPrintf("  was %s cost=%-7.2g order=%c\n",
         6112  +                wherePathName(pTo, iLoop+1, 0), pTo->rCost,
         6113  +                pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
         6114  +          }
         6115  +#endif
  6056   6116           }
  6057   6117           /* pWLoop is a winner.  Add it to the set of best so far */
  6058   6118           pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
  6059   6119           pTo->revLoop = revMask;
  6060   6120           pTo->nRow = pFrom->nRow * pWLoop->nOut;
  6061   6121           pTo->rCost = rCost;
  6062   6122           pTo->isOrderedValid = isOrderedValid;
................................................................................
  6068   6128             for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
  6069   6129               if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
  6070   6130             }
  6071   6131           }
  6072   6132         }
  6073   6133       }
  6074   6134   
  6075         -#if 0
  6076         -    if( sqlite3WhereTrace ){
  6077         -      sqlite3DebugPrintf("---- round %d ---- nTo=%d\n", iLoop, nTo);
  6078         -      for(ii=0; ii<nTo; ii++){
  6079         -        sqlite3DebugPrintf("%03d:  cost=%g  nrow=%g\n",
  6080         -           ii, aTo[ii].rCost, aTo[ii].nRow);
  6081         -        for(jj=0; jj<=iLoop; jj++){
  6082         -          whereLoopPrint(aTo[ii].aLoop[jj], pWInfo->pTabList);
  6083         -        }
         6135  +#ifdef WHERETRACE_ENABLED
         6136  +    if( sqlite3WhereTrace>=2 ){
         6137  +      sqlite3DebugPrintf("---- round %d ----\n", iLoop);
         6138  +      for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
         6139  +        sqlite3DebugPrintf("%2d: %s cost=%-7.2g nrow=%-7.2g order=%c\n",
         6140  +           ii, wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
         6141  +           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
  6084   6142         }
  6085   6143       }
  6086   6144   #endif
  6087   6145   
  6088   6146       /* Swap the roles of aFrom and aTo for the next generation */
  6089   6147       pFrom = aTo;
  6090   6148       aTo = aFrom;
................................................................................
  6357   6415   
  6358   6416     /* Construct the WhereLoop objects */
  6359   6417     WHERETRACE(("*** Optimizer Start ***\n"));
  6360   6418     rc = whereLoopAddAll(&sWLB);
  6361   6419     if( rc ) goto whereBeginError;
  6362   6420   
  6363   6421     /* Display all of the WhereLoop objects if wheretrace is enabled */
  6364         -#if defined(SQLITE_DEBUG) \
  6365         -    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
         6422  +#ifdef WHERETRACE_ENABLED
  6366   6423     if( sqlite3WhereTrace ){
  6367   6424       WhereLoop *p;
         6425  +    int i = 0;
         6426  +    static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
         6427  +                                     "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
  6368   6428       for(p=pWInfo->pLoops; p; p=p->pNextLoop){
         6429  +      p->cId = zLabel[(i++)%sizeof(zLabel)];
  6369   6430         whereLoopPrint(p, pTabList);
  6370   6431       }
  6371   6432     }
  6372   6433   #endif
  6373   6434   
  6374   6435     wherePathSolver(pWInfo);
  6375   6436     if( db->mallocFailed ) goto whereBeginError;
  6376         -#if defined(SQLITE_DEBUG) \
  6377         -    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
         6437  +#ifdef WHERETRACE_ENABLED
  6378   6438     if( sqlite3WhereTrace ){
  6379   6439       int ii;
  6380   6440       sqlite3DebugPrintf("------------ Solution -------------");
  6381   6441       if( pWInfo->nOBSat ){
  6382   6442         sqlite3DebugPrintf(" ORDER BY omitted\n");
  6383   6443       }else{
  6384   6444         sqlite3DebugPrintf("\n");
................................................................................
  6664   6724     */
  6665   6725     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  6666   6726     if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
  6667   6727       pWInfo->okOnePass = 1;
  6668   6728       pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  6669   6729     }
  6670   6730   
  6671         -#if 0
         6731  +#if 1
  6672   6732     /* Scaffolding:  Check the new query plan against the old.  Report any
  6673   6733     ** discrepencies */
  6674   6734     for(ii=0; ii<nTabList; ii++){
  6675   6735       if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){
  6676   6736         sqlite3DebugPrintf("(QP-Mismatch)");
  6677   6737         break;
  6678   6738       }

Changes to test/boundary3.test.

   119    119     }
   120    120   } {72057594037927935 17}
   121    121   do_test boundary3-2.1.3 {
   122    122     db eval {
   123    123       SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
   124    124     }
   125    125   } {72057594037927935 00ffffffffffffff}
          126  +exit
   126    127   do_test boundary3-2.1.gt.1 {
   127    128     db eval {
   128    129       SELECT t2.a FROM t1 JOIN t2 USING(a)
   129    130        WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
   130    131     }
   131    132   } {3 28}
   132    133   do_test boundary3-2.1.gt.2 {