SQLite

Check-in [211f7a5374]
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
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.917
Context
2013-05-30
11:48
Merge recent trunk changes into the NGQP branch. (check-in: aebe1f2603 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: 211f7a5374 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: b49fa74561 user: drh tags: nextgen-query-plan-exp)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/sqliteInt.h.
︙
2047
2048
2049
2050
2051
2052
2053

2054
2055
2056
2057
2058
2059
2060

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

5835
5836
5837
5838
5839
5840
5841


5842
5843
5844
5845
5846
5847
5848
5849
5850
5851








-
-
+
+
+








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 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;
︙
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
5913
5914
5915
5916
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

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
5914
5915
5916
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
5956








-
+











-
+


















-
+



-
-
-
-
-
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
-
-
-
-

+
-
-
-
+
+
+
+

-
+

-
+








    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);
    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 = 1;
      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
                                   |WHERE_COLUMN_NULL))!=0 ){
        isUnique = 0;
      }else if( pLoop->u.btree.nEq < pIndex->nColumn ){
        isUnique = 0;
      }
    }
    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++){
    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 ){
      if( isUnique ) continue;
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
          continue;
        }else{
          return 0;
        }
      }else{
        /* The ROWID column at the end */
        iColumn = -1;
        revIdx = 0;
      }
      }
      if( isUnique ) continue;
      iColumn = pIndex->aiColumn[j];
      if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      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;
        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;
        if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
      }else{
        rev = pIndex->aSortOrder[j];
        rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
        revSet = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
︙
5996
5997
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
6036
6037
6038
6039
6040
6041
6042
6043
6044

6045
6046
6047
6048
6049
6050
6051

5997
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
6036
6037
6038
6039
6040
6041








+
+
+




















-
+



-
-
-
-
-
-
-
-
-
-
-
-
-

-


-
+








  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;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }

  /* 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 ){
  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);
      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 */
︙
6158
6159
6160
6161
6162
6163
6164
6165

6166
6167





6168
6169
6170
6171
6172
6173
6174

6148
6149
6150
6151
6152
6153
6154

6155
6156
6157
6158
6159
6160
6161
6162
6163
6164
6165
6166
6167
6168
6169








-
+


+
+
+
+
+








      }
    }

#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",
        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;
︙
6188
6189
6190
6191
6192
6193
6194

6195
6196
6197
6198
6199
6200
6201

6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193
6194
6195
6196
6197








+








  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;
}
︙
6464
6465
6466
6467
6468
6469
6470
6471

6472
6473

6474
6475
6476
6477
6478
6479
6480

6460
6461
6462
6463
6464
6465
6466

6467
6468

6469
6470
6471
6472
6473
6474
6475
6476








-
+

-
+








  if( pWInfo->pOrderBy ){
     wherePathSolver(pWInfo, pWInfo->nRowOut);
     if( db->mallocFailed ) goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    sqlite3DebugPrintf("---- Solution");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
      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);
    }
  }
︙