SQLite

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
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 59d49b7fc49fa290e04a02653e7268c85836b27e
User & Date: drh 2014-03-18 18:59:07.798
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
Unified Diff Show Whitespace Changes Patch
Changes to src/where.c.
4912
4913
4914
4915
4916
4917
4918
4919






4920
4921
4922
4923
4924
4925
4926
        if( (mTerm&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  } /* End the loop over all WhereLoops from outer-most down to inner-most */
  if( obSat==obDone ) return nOrderBy;
  if( !isOrderDistinct ) return 0;






  return -1;
}

#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  static char zName[65];







|
>
>
>
>
>
>







4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
        if( (mTerm&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  } /* End the loop over all WhereLoops from outer-most down to inner-most */
  if( obSat==obDone ) return nOrderBy;
  if( !isOrderDistinct ){
    for(i=nOrderBy-1; i>0; i--){
      Bitmask m = MASKBIT(i) - 1;
      if( (obSat&m)==m ) return i;
    }
    return 0;
  }
  return -1;
}

#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  static char zName[65];
4949
4950
4951
4952
4953
4954
4955

4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
  int mxChoice;             /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  Parse *pParse;            /* Parsing context */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  int mxI = 0;              /* Index of next entry to replace */

  LogEst rCost;             /* Cost of a path */
  LogEst nOut;              /* Number of outputs */
  LogEst mxCost = 0;        /* Maximum cost of a set of paths */
  LogEst mxOut = 0;         /* Maximum nOut value on the set of paths */
  LogEst rSortCost;         /* Cost to do a sort */
  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */







>




<







4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966

4967
4968
4969
4970
4971
4972
4973
  int mxChoice;             /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  Parse *pParse;            /* Parsing context */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  int mxI = 0;              /* Index of next entry to replace */
  int nOrderBy;             /* Number of ORDER BY clause terms */
  LogEst rCost;             /* Cost of a path */
  LogEst nOut;              /* Number of outputs */
  LogEst mxCost = 0;        /* Maximum cost of a set of paths */
  LogEst mxOut = 0;         /* Maximum nOut value on the set of paths */

  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
4995
4996
4997
4998
4999
5000
5001
5002
5003
5004

5005
5006
5007
5008
5009
5010
5011
5012

5013
5014
5015
5016
5017
5018
5019
  ** of computing an automatic index is not paid back within the first 25
  ** rows, then do not use the automatic index. */
  aFrom[0].nRow = MIN(pParse->nQueryLoop, 46);  assert( 46==sqlite3LogEst(25) );
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = 0;
  if( pWInfo->pOrderBy==0 || nRowEst==0 ){
    aFrom[0].isOrdered = 0;

  }else{
    /* TUNING: Estimated cost of sorting is 48*N*log2(N) where N is the
    ** number of output rows. The 48 is the expected size of a row to sort. 
    ** FIXME:  compute a better estimate of the 48 multiplier based on the
    ** result set expressions. */
    aFrom[0].isOrdered = -1;
    rSortCost = nRowEst + estLog(nRowEst);
    WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));

  }

  /* Compute successively longer WherePaths using the previous generation
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;







<


>

<
<
<
<

<
<
>







5001
5002
5003
5004
5005
5006
5007

5008
5009
5010
5011




5012


5013
5014
5015
5016
5017
5018
5019
5020
  ** of computing an automatic index is not paid back within the first 25
  ** rows, then do not use the automatic index. */
  aFrom[0].nRow = MIN(pParse->nQueryLoop, 46);  assert( 46==sqlite3LogEst(25) );
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */

  if( pWInfo->pOrderBy==0 || nRowEst==0 ){
    aFrom[0].isOrdered = 0;
    nOrderBy = 0;
  }else{




    aFrom[0].isOrdered = -1;


    nOrderBy = pWInfo->pOrderBy->nExpr;
  }

  /* Compute successively longer WherePaths using the previous generation
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
5030
5031
5032
5033
5034
5035
5036
5037









5038
5039
5040
5041
5042
5043
5044
        rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered==0 ){









            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{
          revMask = pFrom->revLoop;
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){







|
>
>
>
>
>
>
>
>
>







5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
        rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly 4*N*log(N).
            ** If some but not all of the columns are in sorted order, then
            ** scale down the log(N) term. */
            LogEst rSortCost = 20 + nRowEst +
                                estLog(nRowEst)*(nOrderBy-isOrdered)/nOrderBy;
            WHERETRACE(0x002,
               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{
          revMask = pFrom->revLoop;
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){