/ Check-in [59d49b7fc4]
Login

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

Overview
Comment:Adjust the query planner to keep track of the number of ORDER BY terms satisfied. Still doesn't do anything with this information. Some tests fail after this check-in, but all failures are believed to be benign. The failures will be addressed at a later stage.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 59d49b7fc49fa290e04a02653e7268c85836b27e
User & Date: drh 2014-03-18 18:59:07
Context
2014-03-18
20:33
Make the partial-ORDER-BY information in the query planner available to the SELECT code generator. Still doesn't make a difference in the generated code. check-in: e258df236b user: drh tags: orderby-planning
18:59
Adjust the query planner to keep track of the number of ORDER BY terms satisfied. Still doesn't do anything with this information. Some tests fail after this check-in, but all failures are believed to be benign. The failures will be addressed at a later stage. check-in: 59d49b7fc4 user: drh tags: orderby-planning
15:30
Experiments with the optimization of ORDER BY and GROUP BY clauses. check-in: b150902579 user: drh tags: orderby-planning
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  4912   4912           if( (mTerm&~orderDistinctMask)==0 ){
  4913   4913             obSat |= MASKBIT(i);
  4914   4914           }
  4915   4915         }
  4916   4916       }
  4917   4917     } /* End the loop over all WhereLoops from outer-most down to inner-most */
  4918   4918     if( obSat==obDone ) return nOrderBy;
  4919         -  if( !isOrderDistinct ) return 0;
         4919  +  if( !isOrderDistinct ){
         4920  +    for(i=nOrderBy-1; i>0; i--){
         4921  +      Bitmask m = MASKBIT(i) - 1;
         4922  +      if( (obSat&m)==m ) return i;
         4923  +    }
         4924  +    return 0;
         4925  +  }
  4920   4926     return -1;
  4921   4927   }
  4922   4928   
  4923   4929   #ifdef WHERETRACE_ENABLED
  4924   4930   /* For debugging use only: */
  4925   4931   static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  4926   4932     static char zName[65];
................................................................................
  4949   4955     int mxChoice;             /* Maximum number of simultaneous paths tracked */
  4950   4956     int nLoop;                /* Number of terms in the join */
  4951   4957     Parse *pParse;            /* Parsing context */
  4952   4958     sqlite3 *db;              /* The database connection */
  4953   4959     int iLoop;                /* Loop counter over the terms of the join */
  4954   4960     int ii, jj;               /* Loop counters */
  4955   4961     int mxI = 0;              /* Index of next entry to replace */
         4962  +  int nOrderBy;             /* Number of ORDER BY clause terms */
  4956   4963     LogEst rCost;             /* Cost of a path */
  4957   4964     LogEst nOut;              /* Number of outputs */
  4958   4965     LogEst mxCost = 0;        /* Maximum cost of a set of paths */
  4959   4966     LogEst mxOut = 0;         /* Maximum nOut value on the set of paths */
  4960         -  LogEst rSortCost;         /* Cost to do a sort */
  4961   4967     int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  4962   4968     WherePath *aFrom;         /* All nFrom paths at the previous level */
  4963   4969     WherePath *aTo;           /* The nTo best paths at the current level */
  4964   4970     WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  4965   4971     WherePath *pTo;           /* An element of aTo[] that we are working on */
  4966   4972     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  4967   4973     WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
  4995   5001     ** of computing an automatic index is not paid back within the first 25
  4996   5002     ** rows, then do not use the automatic index. */
  4997   5003     aFrom[0].nRow = MIN(pParse->nQueryLoop, 46);  assert( 46==sqlite3LogEst(25) );
  4998   5004     nFrom = 1;
  4999   5005   
  5000   5006     /* Precompute the cost of sorting the final result set, if the caller
  5001   5007     ** to sqlite3WhereBegin() was concerned about sorting */
  5002         -  rSortCost = 0;
  5003   5008     if( pWInfo->pOrderBy==0 || nRowEst==0 ){
  5004   5009       aFrom[0].isOrdered = 0;
         5010  +    nOrderBy = 0;
  5005   5011     }else{
  5006         -    /* TUNING: Estimated cost of sorting is 48*N*log2(N) where N is the
  5007         -    ** number of output rows. The 48 is the expected size of a row to sort. 
  5008         -    ** FIXME:  compute a better estimate of the 48 multiplier based on the
  5009         -    ** result set expressions. */
  5010   5012       aFrom[0].isOrdered = -1;
  5011         -    rSortCost = nRowEst + estLog(nRowEst);
  5012         -    WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
         5013  +    nOrderBy = pWInfo->pOrderBy->nExpr;
  5013   5014     }
  5014   5015   
  5015   5016     /* Compute successively longer WherePaths using the previous generation
  5016   5017     ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  5017   5018     ** best paths at each generation */
  5018   5019     for(iLoop=0; iLoop<nLoop; iLoop++){
  5019   5020       nTo = 0;
................................................................................
  5030   5031           rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
  5031   5032           nOut = pFrom->nRow + pWLoop->nOut;
  5032   5033           maskNew = pFrom->maskLoop | pWLoop->maskSelf;
  5033   5034           if( isOrdered<0 ){
  5034   5035             isOrdered = wherePathSatisfiesOrderBy(pWInfo,
  5035   5036                          pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
  5036   5037                          iLoop, pWLoop, &revMask);
  5037         -          if( isOrdered==0 ){
         5038  +          if( isOrdered>=0 && isOrdered<nOrderBy ){
         5039  +            /* TUNING: Estimated cost of sorting cost as roughly 4*N*log(N).
         5040  +            ** If some but not all of the columns are in sorted order, then
         5041  +            ** scale down the log(N) term. */
         5042  +            LogEst rSortCost = 20 + nRowEst +
         5043  +                                estLog(nRowEst)*(nOrderBy-isOrdered)/nOrderBy;
         5044  +            WHERETRACE(0x002,
         5045  +               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
         5046  +                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
         5047  +                sqlite3LogEstAdd(rCost,rSortCost)));
  5038   5048               rCost = sqlite3LogEstAdd(rCost, rSortCost);
  5039   5049             }
  5040   5050           }else{
  5041   5051             revMask = pFrom->revLoop;
  5042   5052           }
  5043   5053           /* Check to see if pWLoop should be added to the mxChoice best so far */
  5044   5054           for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){