/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

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

Changes to src/where.c.

  5835   5835   static int wherePathSatisfiesOrderBy(
  5836   5836     WhereInfo *pWInfo,    /* The WHERE clause */
  5837   5837     WherePath *pPath,     /* The WherePath to check */
  5838   5838     int nLoop,            /* Number of entries in pPath->aLoop[] */
  5839   5839     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  5840   5840     Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
  5841   5841   ){
  5842         -  u8 revSet;
  5843         -  u8 rev;
         5842  +  u8 revSet;            /* True if rev is known */
         5843  +  u8 rev;               /* Composite sort order */
         5844  +  u8 revIdx;            /* Index sort order */
  5844   5845     u8 isUnique;
  5845   5846     u8 requireUnique = 0;
  5846   5847     u16 nColumn;
  5847   5848     u16 nOrderBy;
  5848   5849     int i, j;
  5849   5850     int nUsed = 0;
  5850   5851     int iCur;
................................................................................
  5886   5887       return pLast->u.vtab.isOrdered;
  5887   5888     }
  5888   5889   
  5889   5890     /* Sorting is always required if any term of the ORDER BY is not a 
  5890   5891     ** column reference */
  5891   5892     nOrderBy = pOrderBy->nExpr;
  5892   5893     for(i=0; i<nOrderBy; i++){
  5893         -    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
         5894  +    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  5894   5895       if( pOBExpr->op!=TK_COLUMN ) return 0;
  5895   5896     }
  5896   5897       
  5897   5898     for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
  5898   5899       pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
  5899   5900       assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
  5900   5901       isUnique = 1;
  5901   5902       if( pLoop->wsFlags & WHERE_IPK ){
  5902   5903         if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
  5903   5904         if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
  5904   5905         pIndex = 0;
  5905         -      nColumn = 1;
         5906  +      nColumn = 0;
  5906   5907       }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
  5907   5908         return 0;
  5908   5909       }else{
  5909   5910         nColumn = pIndex->nColumn;
  5910   5911         if( pIndex->onError==OE_None ){
  5911   5912           isUnique = 0;
  5912   5913         }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
................................................................................
  5917   5918         }
  5918   5919       }
  5919   5920       if( !isUnique && requireUnique ) return 0;
  5920   5921       requireUnique = !isUnique;
  5921   5922       iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  5922   5923       j = 0;
  5923   5924       revSet = rev = 0;
  5924         -    for(j=0; j<nColumn && nUsed<nOrderBy; j++, nUsed++){
         5925  +    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
  5925   5926         pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
  5926   5927         assert( pOBExpr->op==TK_COLUMN );
  5927   5928         if( pOBExpr->iTable!=iCur ) break;
  5928         -      if( pIndex==0 ){
  5929         -        if( pOBExpr->iColumn<0 && j==0 ){
  5930         -          isUnique = 1;
  5931         -          rev = pOrderBy->a[nUsed].sortOrder;
  5932         -        }else if( isUnique ){
  5933         -          continue;
  5934         -        }else{
  5935         -          return 0;
  5936         -        }
  5937         -      }
  5938   5929         if( isUnique ) continue;
  5939         -      iColumn = pIndex->aiColumn[j];
  5940         -      if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
         5930  +      if( j<nColumn ){
         5931  +        /* Normal index columns */
         5932  +        iColumn = pIndex->aiColumn[j];
         5933  +        revIdx = pIndex->aSortOrder[j];
         5934  +        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
         5935  +      }else{
         5936  +        /* The ROWID column at the end */
         5937  +        iColumn = -1;
         5938  +        revIdx = 0;
         5939  +      }
  5941   5940         if( pOBExpr->iColumn!=iColumn ) return 0;
  5942         -      pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
  5943         -      if( !pColl ) pColl = db->pDfltColl;
  5944         -      if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;
         5941  +      if( iColumn>=0 ){
         5942  +        pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
         5943  +        if( !pColl ) pColl = db->pDfltColl;
         5944  +        if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;
         5945  +      }
  5945   5946         if( revSet ){
  5946         -        if( pIndex->aSortOrder[j]!=rev ) return 0;
         5947  +        if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
  5947   5948         }else{
  5948         -        rev = pIndex->aSortOrder[j];
         5949  +        rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
  5949   5950           revSet = 1;
  5950   5951         }
  5951   5952       }
  5952   5953       if( rev ) revMask |= ((Bitmask)1)<<i;
  5953   5954     }
  5954   5955     if( nUsed==nOrderBy ){
  5955   5956       *pRevMask = revMask;
................................................................................
  5996   5997     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  5997   5998     WhereLoop **pX;           /* Used to divy up the pSpace memory */
  5998   5999     char *pSpace;             /* Temporary memory used by this routine */
  5999   6000   
  6000   6001     db = pWInfo->pParse->db;
  6001   6002     nLoop = pWInfo->nLevel;
  6002   6003     assert( nLoop<=pWInfo->pTabList->nSrc );
         6004  +#ifdef WHERETRACE_ENABLED
         6005  +  if( sqlite3WhereTrace>=2 ) sqlite3DebugPrintf("---- begin solver\n");
         6006  +#endif
  6003   6007   
  6004   6008     /* Allocate and initialize space for aTo and aFrom */
  6005   6009     ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  6006   6010     pSpace = sqlite3DbMallocRaw(db, ii);
  6007   6011     if( pSpace==0 ) return SQLITE_NOMEM;
  6008   6012     aTo = (WherePath*)pSpace;
  6009   6013     aFrom = aTo+mxChoice;
................................................................................
  6016   6020     /* Seed the search with a single WherePath containing zero WhereLoops */
  6017   6021     aFrom[0].nRow = (double)1;
  6018   6022     nFrom = 1;
  6019   6023   
  6020   6024     /* Precompute the cost of sorting the final result set, if the caller
  6021   6025     ** to sqlite3WhereBegin() was concerned about sorting */
  6022   6026     rSortCost = (double)0;
  6023         -  if( pWInfo->pOrderBy==0 || nRowEst<0.0 ){
         6027  +  if( pWInfo->pOrderBy==0 || nRowEst<=0.0 ){
  6024   6028       aFrom[0].isOrderedValid = 1;
  6025   6029     }else{
  6026   6030       /* Compute an estimate on the cost to sort the entire result set */
  6027         -#if 0
  6028         -    rSortCost = (double)1;
  6029         -    for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
  6030         -      pNext = pWLoop->pNextLoop;
  6031         -      rCost = pWLoop->nOut;
  6032         -      while( pNext && pNext->iTab==pWLoop->iTab ){
  6033         -        if( pNext->nOut<rCost ) rCost = pNext->nOut;
  6034         -        pNext = pNext->pNextLoop;
  6035         -      }
  6036         -      rSortCost *= rCost;
  6037         -    }
  6038         -    rSortCost *= estLog(rSortCost);
  6039         -#else
  6040   6031       rSortCost = nRowEst*estLog(nRowEst);
  6041         -#endif
  6042   6032   #ifdef WHERETRACE_ENABLED
  6043   6033       if( sqlite3WhereTrace>=2 ){
  6044         -      sqlite3DebugPrintf("--solver sort cost=%-7.2g\n", rSortCost);
         6034  +      sqlite3DebugPrintf("---- sort cost=%-7.2g\n", rSortCost);
  6045   6035       }
  6046   6036   #endif
  6047   6037     }
  6048   6038   
  6049   6039     /* Compute successively longer WherePaths using the previous generation
  6050   6040     ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  6051   6041     ** best paths at each generation */
................................................................................
  6158   6148         }
  6159   6149       }
  6160   6150   
  6161   6151   #ifdef WHERETRACE_ENABLED
  6162   6152       if( sqlite3WhereTrace>=2 ){
  6163   6153         sqlite3DebugPrintf("---- after round %d ----\n", iLoop);
  6164   6154         for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
  6165         -        sqlite3DebugPrintf(" %s cost=%-7.2g nrow=%-7.2g order=%c\n",
         6155  +        sqlite3DebugPrintf(" %s cost=%-7.2g nrow=%-7.2g order=%c",
  6166   6156              wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  6167   6157              pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
         6158  +        if( pTo->isOrderedValid && pTo->isOrdered ){
         6159  +          sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop);
         6160  +        }else{
         6161  +          sqlite3DebugPrintf("\n");
         6162  +        }
  6168   6163         }
  6169   6164       }
  6170   6165   #endif
  6171   6166   
  6172   6167       /* Swap the roles of aFrom and aTo for the next generation */
  6173   6168       pFrom = aTo;
  6174   6169       aTo = aFrom;
................................................................................
  6188   6183     assert( pWInfo->nLevel==nLoop );
  6189   6184     /* Load the lowest cost path into pWInfo */
  6190   6185     for(iLoop=0; iLoop<nLoop; iLoop++){
  6191   6186       pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  6192   6187     }
  6193   6188     if( pFrom->isOrdered ){
  6194   6189       pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
         6190  +    pWInfo->revMask = pFrom->revLoop;
  6195   6191     }
  6196   6192     pWInfo->nRowOut = pFrom->nRow;
  6197   6193   
  6198   6194     /* Free temporary memory and return success */
  6199   6195     sqlite3DbFree(db, pSpace);
  6200   6196     return SQLITE_OK;
  6201   6197   }
................................................................................
  6464   6460     if( pWInfo->pOrderBy ){
  6465   6461        wherePathSolver(pWInfo, pWInfo->nRowOut);
  6466   6462        if( db->mallocFailed ) goto whereBeginError;
  6467   6463     }
  6468   6464   #ifdef WHERETRACE_ENABLED
  6469   6465     if( sqlite3WhereTrace ){
  6470   6466       int ii;
  6471         -    sqlite3DebugPrintf("------------ Solution -------------");
         6467  +    sqlite3DebugPrintf("---- Solution");
  6472   6468       if( pWInfo->nOBSat ){
  6473         -      sqlite3DebugPrintf(" ORDER BY omitted\n");
         6469  +      sqlite3DebugPrintf(" ORDER BY omitted rev=0x%llx\n", pWInfo->revMask);
  6474   6470       }else{
  6475   6471         sqlite3DebugPrintf("\n");
  6476   6472       }
  6477   6473       for(ii=0; ii<nTabList; ii++){
  6478   6474         whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
  6479   6475       }
  6480   6476     }