SQLite

Check-in [12c709b436]
Login

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

Overview
Comment:Improvements to ORDER BY handling in the NGQP. Fix an "exit" mistakenly left in a test script during the previous check-in.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 12c709b4369c7d94d7fb743d0d0da7a9350a3d16
User & Date: drh 2013-05-22 02:06:59.780
Context
2013-05-22
17:01
Allow the rowid at the end of an index to be used in a constraint on that index. (check-in: 9bf0524df7 user: drh tags: nextgen-query-plan-exp)
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: 12c709b436 user: drh tags: nextgen-query-plan-exp)
2013-05-21
19:23
Enhanced "wheretrace" output in the NGQP solver routine. (check-in: 04dfb85a2a user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
5982
5983
5984
5985
5986
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
** error occurs.
*/
static int wherePathSolver(WhereInfo *pWInfo){
  const int mxChoice = 10;  /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  double rCost;             /* Cost of a path */
  double mxCost;            /* Maximum cost of a set of paths */
  double 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 *pNext;         /* Next loop */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
  char *pSpace;             /* Temporary memory used by this routine */

  db = pWInfo->pParse->db;
  nLoop = pWInfo->nLevel;
  assert( nLoop<=pWInfo->pTabList->nSrc );








|














<







5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978

5979
5980
5981
5982
5983
5984
5985
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
** error occurs.
*/
static int wherePathSolver(WhereInfo *pWInfo, double nRowEst){
  const int mxChoice = 10;  /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  double rCost;             /* Cost of a path */
  double mxCost;            /* Maximum cost of a set of paths */
  double 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 */
  char *pSpace;             /* Temporary memory used by this routine */

  db = pWInfo->pParse->db;
  nLoop = pWInfo->nLevel;
  assert( nLoop<=pWInfo->pTabList->nSrc );

5999
6000
6001
6002
6003
6004
6005
6006
6007
6008
6009

6010
6011
6012
6013
6014
6015
6016
6017
6018
6019
6020








6021
6022
6023
6024
6025
6026
6027
  /* Seed the search with a single WherePath containing zero WhereLoops */
  aFrom[0].nRow = (double)1;
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = (double)0;
  if( pWInfo->pOrderBy==0 ){
    aFrom[0].isOrderedValid = 1;
  }else{
    /* Compute an estimate on the cost to sort the entire result set */

    rSortCost = (double)1;
    for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
      pNext = pWLoop->pNextLoop;
      rCost = pWLoop->nOut;
      while( pNext && pNext->iTab==pWLoop->iTab ){
        if( pNext->nOut<rCost ) rCost = pNext->nOut;
        pNext = pNext->pNextLoop;
      }
      rSortCost *= rCost;
    }
    rSortCost *= estLog(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;







|



>











>
>
>
>
>
>
>
>







5998
5999
6000
6001
6002
6003
6004
6005
6006
6007
6008
6009
6010
6011
6012
6013
6014
6015
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
  /* Seed the search with a single WherePath containing zero WhereLoops */
  aFrom[0].nRow = (double)1;
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = (double)0;
  if( pWInfo->pOrderBy==0 || nRowEst<0.0 ){
    aFrom[0].isOrderedValid = 1;
  }else{
    /* Compute an estimate on the cost to sort the entire result set */
#if 0
    rSortCost = (double)1;
    for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
      pNext = pWLoop->pNextLoop;
      rCost = pWLoop->nOut;
      while( pNext && pNext->iTab==pWLoop->iTab ){
        if( pNext->nOut<rCost ) rCost = pNext->nOut;
        pNext = pNext->pNextLoop;
      }
      rSortCost *= rCost;
    }
    rSortCost *= estLog(rSortCost);
#else
    rSortCost = nRowEst*estLog(nRowEst);
#endif
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){
      sqlite3DebugPrintf("--solver sort cost=%-7.2g\n", rSortCost);
    }
#endif
  }

  /* 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;
6130
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
6144
6145
6146
6147
          }
        }
      }
    }

#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){
      sqlite3DebugPrintf("---- round %d ----\n", iLoop);
      for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
        sqlite3DebugPrintf("%2d: %s cost=%-7.2g nrow=%-7.2g order=%c\n",
           ii, wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */
    pFrom = aTo;







|

|
|







6138
6139
6140
6141
6142
6143
6144
6145
6146
6147
6148
6149
6150
6151
6152
6153
6154
6155
          }
        }
      }
    }

#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){
      sqlite3DebugPrintf("---- after round %d ----\n", iLoop);
      for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
        sqlite3DebugPrintf(" %s cost=%-7.2g nrow=%-7.2g order=%c\n",
           wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */
    pFrom = aTo;
6163
6164
6165
6166
6167
6168
6169

6170
6171
6172
6173
6174
6175
6176
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }
  if( pFrom->isOrdered ){
    pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
  }


  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*







>







6171
6172
6173
6174
6175
6176
6177
6178
6179
6180
6181
6182
6183
6184
6185
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }
  if( pFrom->isOrdered ){
    pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*
6428
6429
6430
6431
6432
6433
6434



6435
6436

6437
6438
6439
6440
6441
6442
6443
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      p->cId = zLabel[(i++)%sizeof(zLabel)];
      whereLoopPrint(p, pTabList);
    }
  }
#endif




  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;

#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
    }else{







>
>
>
|
|
>







6437
6438
6439
6440
6441
6442
6443
6444
6445
6446
6447
6448
6449
6450
6451
6452
6453
6454
6455
6456
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      p->cId = zLabel[(i++)%sizeof(zLabel)];
      whereLoopPrint(p, pTabList);
    }
  }
#endif

  wherePathSolver(pWInfo, -1);
  if( db->mallocFailed ) goto whereBeginError;
  if( pWInfo->pOrderBy ){
     wherePathSolver(pWInfo, pWInfo->nRowOut);
     if( db->mallocFailed ) goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
    }else{
Changes to test/boundary3.test.
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
  }
} {72057594037927935 17}
do_test boundary3-2.1.3 {
  db eval {
    SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
  }
} {72057594037927935 00ffffffffffffff}
exit
do_test boundary3-2.1.gt.1 {
  db eval {
    SELECT t2.a FROM t1 JOIN t2 USING(a)
     WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
  }
} {3 28}
do_test boundary3-2.1.gt.2 {







<







119
120
121
122
123
124
125

126
127
128
129
130
131
132
  }
} {72057594037927935 17}
do_test boundary3-2.1.3 {
  db eval {
    SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
  }
} {72057594037927935 00ffffffffffffff}

do_test boundary3-2.1.gt.1 {
  db eval {
    SELECT t2.a FROM t1 JOIN t2 USING(a)
     WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
  }
} {3 28}
do_test boundary3-2.1.gt.2 {