/ Check-in [211f7a53]
Login

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

Overview
Comment:Update the NGQP to record which loops need be run in reverse order to satisfy ORDER BY clauses.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 211f7a5374fe20a02535edc8b799a8a7136ff6b3
User & Date: drh 2013-05-27 17:59:37
Context
2013-05-30
11:48
Merge recent trunk changes into the NGQP branch. check-in: aebe1f26 user: drh tags: nextgen-query-plan-exp
2013-05-27
17:59
Update the NGQP to record which loops need be run in reverse order to satisfy ORDER BY clauses. check-in: 211f7a53 user: drh tags: nextgen-query-plan-exp
2013-05-24
14:52
Record in the WhereLoop object the set of virtual table constraints that need not be separately checked. check-in: b49fa745 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to src/sqliteInt.h.

2047
2048
2049
2050
2051
2052
2053

2054
2055
2056
2057
2058
2059
2060
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */

  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */







>







2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */
  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */

Changes to src/where.c.

5835
5836
5837
5838
5839
5840
5841
5842
5843

5844
5845
5846
5847
5848
5849
5850
....
5886
5887
5888
5889
5890
5891
5892
5893
5894
5895
5896
5897
5898
5899
5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
....
5917
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927
5928
5929
5930
5931
5932
5933
5934
5935
5936
5937
5938


5939

5940





5941

5942
5943
5944

5945
5946

5947
5948

5949
5950
5951
5952
5953
5954
5955
....
5996
5997
5998
5999
6000
6001
6002



6003
6004
6005
6006
6007
6008
6009
....
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
....
6158
6159
6160
6161
6162
6163
6164
6165
6166
6167





6168
6169
6170
6171
6172
6173
6174
....
6188
6189
6190
6191
6192
6193
6194

6195
6196
6197
6198
6199
6200
6201
....
6464
6465
6466
6467
6468
6469
6470
6471
6472
6473
6474
6475
6476
6477
6478
6479
6480
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;
  u8 rev;

  u8 isUnique;
  u8 requireUnique = 0;
  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
................................................................................
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;
  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isUnique = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
      if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
      pIndex = 0;
      nColumn = 1;
    }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
      return 0;
    }else{
      nColumn = pIndex->nColumn;
      if( pIndex->onError==OE_None ){
        isUnique = 0;
      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
................................................................................
      }
    }
    if( !isUnique && requireUnique ) return 0;
    requireUnique = !isUnique;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<nColumn && nUsed<nOrderBy; j++, nUsed++){
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( pIndex==0 ){
        if( pOBExpr->iColumn<0 && j==0 ){
          isUnique = 1;
          rev = pOrderBy->a[nUsed].sortOrder;
        }else if( isUnique ){
          continue;
        }else{
          return 0;
        }
      }
      if( isUnique ) continue;


      iColumn = pIndex->aiColumn[j];

      if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;





      if( pOBExpr->iColumn!=iColumn ) return 0;

      pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;

      if( revSet ){
        if( pIndex->aSortOrder[j]!=rev ) return 0;

      }else{
        rev = pIndex->aSortOrder[j];

        revSet = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
................................................................................
  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 );




  /* Allocate and initialize space for aTo and aFrom */
  ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  pSpace = sqlite3DbMallocRaw(db, ii);
  if( pSpace==0 ) return SQLITE_NOMEM;
  aTo = (WherePath*)pSpace;
  aFrom = aTo+mxChoice;
................................................................................
  /* 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 */
................................................................................
      }
    }

#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;
    aTo = aFrom;
................................................................................
  assert( pWInfo->nLevel==nLoop );
  /* 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;
}
................................................................................
  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{
      sqlite3DebugPrintf("\n");
    }
    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }







|
|
>







 







|











|







 







|



<
<
<
<
<
<
<
<
<
<

>
>
|
>
|
>
>
>
>
>

>



>

<
>

<
>







 







>
>
>







 







|



<
<
<
<
<
<
<
<
<
<
<
<
<

<


|







 







|


>
>
>
>
>







 







>







 







|

|







5835
5836
5837
5838
5839
5840
5841
5842
5843
5844
5845
5846
5847
5848
5849
5850
5851
....
5887
5888
5889
5890
5891
5892
5893
5894
5895
5896
5897
5898
5899
5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
....
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927
5928










5929
5930
5931
5932
5933
5934
5935
5936
5937
5938
5939
5940
5941
5942
5943
5944
5945
5946

5947
5948

5949
5950
5951
5952
5953
5954
5955
5956
....
5997
5998
5999
6000
6001
6002
6003
6004
6005
6006
6007
6008
6009
6010
6011
6012
6013
....
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030













6031

6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
....
6148
6149
6150
6151
6152
6153
6154
6155
6156
6157
6158
6159
6160
6161
6162
6163
6164
6165
6166
6167
6168
6169
....
6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193
6194
6195
6196
6197
....
6460
6461
6462
6463
6464
6465
6466
6467
6468
6469
6470
6471
6472
6473
6474
6475
6476
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isUnique;
  u8 requireUnique = 0;
  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
................................................................................
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;
  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isUnique = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
      if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
      pIndex = 0;
      nColumn = 0;
    }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
      return 0;
    }else{
      nColumn = pIndex->nColumn;
      if( pIndex->onError==OE_None ){
        isUnique = 0;
      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
................................................................................
      }
    }
    if( !isUnique && requireUnique ) return 0;
    requireUnique = !isUnique;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;










      if( isUnique ) continue;
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      }else{
        /* The ROWID column at the end */
        iColumn = -1;
        revIdx = 0;
      }
      if( pOBExpr->iColumn!=iColumn ) return 0;
      if( iColumn>=0 ){
        pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
        if( !pColl ) pColl = db->pDfltColl;
        if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;
      }
      if( revSet ){

        if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
      }else{

        rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
        revSet = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
................................................................................
  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 );
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace>=2 ) sqlite3DebugPrintf("---- begin solver\n");
#endif

  /* Allocate and initialize space for aTo and aFrom */
  ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  pSpace = sqlite3DbMallocRaw(db, ii);
  if( pSpace==0 ) return SQLITE_NOMEM;
  aTo = (WherePath*)pSpace;
  aFrom = aTo+mxChoice;
................................................................................
  /* 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 */













    rSortCost = nRowEst*estLog(nRowEst);

#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){
      sqlite3DebugPrintf("---- 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 */
................................................................................
      }
    }

#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",
           wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
        if( pTo->isOrderedValid && pTo->isOrdered ){
          sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop);
        }else{
          sqlite3DebugPrintf("\n");
        }
      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */
    pFrom = aTo;
    aTo = aFrom;
................................................................................
  assert( pWInfo->nLevel==nLoop );
  /* 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->revMask = pFrom->revLoop;
  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}
................................................................................
  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 rev=0x%llx\n", pWInfo->revMask);
    }else{
      sqlite3DebugPrintf("\n");
    }
    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }