/ Check-in [e258df23]
Login

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

Overview
Comment: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.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: e258df236b7de70087c8227cb209080e55b9bf9c
User & Date: drh 2014-03-18 20:33:42
Context
2014-03-19
14:10
First attempt at getting block-sort to work. This is an incremental check-in. There are many problems still to be worked out. check-in: 59742dd4 user: drh tags: orderby-planning
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: e258df23 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: 59d49b7f user: drh tags: orderby-planning
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

   558    558   */
   559    559   static void selectInnerLoop(
   560    560     Parse *pParse,          /* The parser context */
   561    561     Select *p,              /* The complete select statement being coded */
   562    562     ExprList *pEList,       /* List of values being extracted */
   563    563     int srcTab,             /* Pull data from this table */
   564    564     ExprList *pOrderBy,     /* If not NULL, sort results using this key */
          565  +  int nOBSat,             /* Terms of ORDER BY already satisfied */
   565    566     DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
   566    567     SelectDest *pDest,      /* How to dispose of the results */
   567    568     int iContinue,          /* Jump here to continue with next row */
   568    569     int iBreak              /* Jump here to break out of the inner loop */
   569    570   ){
   570    571     Vdbe *v = pParse->pVdbe;
   571    572     int i;
................................................................................
  1050   1051   ** then the results were placed in a sorter.  After the loop is terminated
  1051   1052   ** we need to run the sorter and output the results.  The following
  1052   1053   ** routine generates the code needed to do that.
  1053   1054   */
  1054   1055   static void generateSortTail(
  1055   1056     Parse *pParse,    /* Parsing context */
  1056   1057     Select *p,        /* The SELECT statement */
  1057         -  Vdbe *v,          /* Generate code into this VDBE */
  1058   1058     int nColumn,      /* Number of columns of data */
  1059   1059     SelectDest *pDest /* Write the sorted results here */
  1060   1060   ){
         1061  +  Vdbe *v = pParse->pVdbe;                     /* The prepared statement */
  1061   1062     int addrBreak = sqlite3VdbeMakeLabel(v);     /* Jump here to exit loop */
  1062   1063     int addrContinue = sqlite3VdbeMakeLabel(v);  /* Jump here for next cycle */
  1063   1064     int addr;
  1064   1065     int iTab;
  1065   1066     int pseudoTab = 0;
  1066   1067     ExprList *pOrderBy = p->pOrderBy;
  1067   1068   
................................................................................
  1914   1915     }
  1915   1916     sqlite3VdbeAddOp1(v, OP_Delete, iQueue);
  1916   1917   
  1917   1918     /* Output the single row in Current */
  1918   1919     addrCont = sqlite3VdbeMakeLabel(v);
  1919   1920     codeOffset(v, regOffset, addrCont);
  1920   1921     selectInnerLoop(pParse, p, p->pEList, iCurrent,
  1921         -      0, 0, pDest, addrCont, addrBreak);
         1922  +      0, 0, 0, pDest, addrCont, addrBreak);
  1922   1923     if( regLimit ){
  1923   1924       sqlite3VdbeAddOp3(v, OP_IfZero, regLimit, addrBreak, -1);
  1924   1925       VdbeCoverage(v);
  1925   1926     }
  1926   1927     sqlite3VdbeResolveLabel(v, addrCont);
  1927   1928   
  1928   1929     /* Execute the recursive SELECT taking the single row in Current as
................................................................................
  2188   2189           }
  2189   2190           iBreak = sqlite3VdbeMakeLabel(v);
  2190   2191           iCont = sqlite3VdbeMakeLabel(v);
  2191   2192           computeLimitRegisters(pParse, p, iBreak);
  2192   2193           sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);
  2193   2194           iStart = sqlite3VdbeCurrentAddr(v);
  2194   2195           selectInnerLoop(pParse, p, p->pEList, unionTab,
  2195         -                        0, 0, &dest, iCont, iBreak);
         2196  +                        0, 0, 0, &dest, iCont, iBreak);
  2196   2197           sqlite3VdbeResolveLabel(v, iCont);
  2197   2198           sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);
  2198   2199           sqlite3VdbeResolveLabel(v, iBreak);
  2199   2200           sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
  2200   2201         }
  2201   2202         break;
  2202   2203       }
................................................................................
  2266   2267         computeLimitRegisters(pParse, p, iBreak);
  2267   2268         sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);
  2268   2269         r1 = sqlite3GetTempReg(pParse);
  2269   2270         iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);
  2270   2271         sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);
  2271   2272         sqlite3ReleaseTempReg(pParse, r1);
  2272   2273         selectInnerLoop(pParse, p, p->pEList, tab1,
  2273         -                      0, 0, &dest, iCont, iBreak);
         2274  +                      0, 0, 0, &dest, iCont, iBreak);
  2274   2275         sqlite3VdbeResolveLabel(v, iCont);
  2275   2276         sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);
  2276   2277         sqlite3VdbeResolveLabel(v, iBreak);
  2277   2278         sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
  2278   2279         sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
  2279   2280         break;
  2280   2281       }
................................................................................
  4726   4727     }else{
  4727   4728       sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  4728   4729     }
  4729   4730   
  4730   4731     if( !isAgg && pGroupBy==0 ){
  4731   4732       /* No aggregate functions and no GROUP BY clause */
  4732   4733       u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
         4734  +    int nOBSat;
  4733   4735   
  4734   4736       /* Begin the database scan. */
  4735   4737       pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList,
  4736   4738                                  wctrlFlags, 0);
  4737   4739       if( pWInfo==0 ) goto select_end;
  4738   4740       if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
  4739   4741         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  4740   4742       }
  4741   4743       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  4742   4744         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  4743   4745       }
  4744         -    if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0;
         4746  +    nOBSat = sqlite3WhereIsOrdered(pWInfo);
         4747  +    if( pOrderBy && nOBSat==pOrderBy->nExpr ){ pOrderBy = 0;  nOBSat = 0; }
  4745   4748   
  4746   4749       /* If sorting index that was created by a prior OP_OpenEphemeral 
  4747   4750       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  4748   4751       ** into an OP_Noop.
  4749   4752       */
  4750   4753       if( addrSortIndex>=0 && pOrderBy==0 ){
  4751   4754         sqlite3VdbeChangeToNoop(v, addrSortIndex);
  4752   4755         p->addrOpenEphm[2] = -1;
  4753   4756       }
  4754   4757   
  4755   4758       /* Use the standard inner loop. */
  4756         -    selectInnerLoop(pParse, p, pEList, -1, pOrderBy, &sDistinct, pDest,
         4759  +    selectInnerLoop(pParse, p, pEList, -1, pOrderBy, nOBSat, &sDistinct, pDest,
  4757   4760                       sqlite3WhereContinueLabel(pWInfo),
  4758   4761                       sqlite3WhereBreakLabel(pWInfo));
  4759   4762   
  4760   4763       /* End the database scan loop.
  4761   4764       */
  4762   4765       sqlite3WhereEnd(pWInfo);
  4763   4766     }else{
................................................................................
  4871   4874         ** it might be a single loop that uses an index to extract information
  4872   4875         ** in the right order to begin with.
  4873   4876         */
  4874   4877         sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
  4875   4878         pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 
  4876   4879                                    WHERE_GROUPBY, 0);
  4877   4880         if( pWInfo==0 ) goto select_end;
  4878         -      if( sqlite3WhereIsOrdered(pWInfo) ){
         4881  +      if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
  4879   4882           /* The optimizer is able to deliver rows in group by order so
  4880   4883           ** we do not have to sort.  The OP_OpenEphemeral table will be
  4881   4884           ** cancelled later because we still need to use the pKeyInfo
  4882   4885           */
  4883   4886           groupBySort = 0;
  4884   4887         }else{
  4885   4888           /* Rows are coming out in undetermined order.  We have to push
................................................................................
  5022   5025         sqlite3VdbeResolveLabel(v, addrOutputRow);
  5023   5026         addrOutputRow = sqlite3VdbeCurrentAddr(v);
  5024   5027         sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeCoverage(v);
  5025   5028         VdbeComment((v, "Groupby result generator entry point"));
  5026   5029         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5027   5030         finalizeAggFunctions(pParse, &sAggInfo);
  5028   5031         sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
  5029         -      selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy,
         5032  +      selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy, 0,
  5030   5033                         &sDistinct, pDest,
  5031   5034                         addrOutputRow+1, addrSetAbort);
  5032   5035         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5033   5036         VdbeComment((v, "end groupby result generator"));
  5034   5037   
  5035   5038         /* Generate a subroutine that will reset the group-by accumulator
  5036   5039         */
................................................................................
  5154   5157           pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);
  5155   5158           if( pWInfo==0 ){
  5156   5159             sqlite3ExprListDelete(db, pDel);
  5157   5160             goto select_end;
  5158   5161           }
  5159   5162           updateAccumulator(pParse, &sAggInfo);
  5160   5163           assert( pMinMax==0 || pMinMax->nExpr==1 );
  5161         -        if( sqlite3WhereIsOrdered(pWInfo) ){
         5164  +        if( sqlite3WhereIsOrdered(pWInfo)>0 ){
  5162   5165             sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3WhereBreakLabel(pWInfo));
  5163   5166             VdbeComment((v, "%s() by index",
  5164   5167                   (flag==WHERE_ORDERBY_MIN?"min":"max")));
  5165   5168           }
  5166   5169           sqlite3WhereEnd(pWInfo);
  5167   5170           finalizeAggFunctions(pParse, &sAggInfo);
  5168   5171         }
  5169   5172   
  5170   5173         pOrderBy = 0;
  5171   5174         sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
  5172         -      selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 
         5175  +      selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 0, 
  5173   5176                         pDest, addrEnd, addrEnd);
  5174   5177         sqlite3ExprListDelete(db, pDel);
  5175   5178       }
  5176   5179       sqlite3VdbeResolveLabel(v, addrEnd);
  5177   5180       
  5178   5181     } /* endif aggregate query */
  5179   5182   
................................................................................
  5182   5185     }
  5183   5186   
  5184   5187     /* If there is an ORDER BY clause, then we need to sort the results
  5185   5188     ** and send them to the callback one by one.
  5186   5189     */
  5187   5190     if( pOrderBy ){
  5188   5191       explainTempTable(pParse, "ORDER BY");
  5189         -    generateSortTail(pParse, p, v, pEList->nExpr, pDest);
         5192  +    generateSortTail(pParse, p, pEList->nExpr, pDest);
  5190   5193     }
  5191   5194   
  5192   5195     /* Jump here to skip this query
  5193   5196     */
  5194   5197     sqlite3VdbeResolveLabel(v, iEnd);
  5195   5198   
  5196   5199     /* The SELECT was successfully coded.   Set the return code to 0

Changes to src/where.c.

    35     35   }
    36     36   
    37     37   /*
    38     38   ** Return TRUE if the WHERE clause returns rows in ORDER BY order.
    39     39   ** Return FALSE if the output needs to be sorted.
    40     40   */
    41     41   int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
    42         -  return pWInfo->bOBSat!=0;
           42  +  return pWInfo->nOBSat;
    43     43   }
    44     44   
    45     45   /*
    46     46   ** Return the VDBE address or label to jump to in order to continue
    47     47   ** immediately with the next row of a WHERE clause.
    48     48   */
    49     49   int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
  3032   3032       ** was passed to this function to implement a "SELECT min(x) ..." 
  3033   3033       ** query, then the caller will only allow the loop to run for
  3034   3034       ** a single iteration. This means that the first row returned
  3035   3035       ** should not have a NULL value stored in 'x'. If column 'x' is
  3036   3036       ** the first one after the nEq equality constraints in the index,
  3037   3037       ** this requires some special handling.
  3038   3038       */
         3039  +    assert( pWInfo->pOrderBy==0
         3040  +         || pWInfo->pOrderBy->nExpr==1
         3041  +         || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 );
  3039   3042       if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
  3040         -     && (pWInfo->bOBSat!=0)
         3043  +     && pWInfo->nOBSat>0
  3041   3044        && (pIdx->nKeyCol>nEq)
  3042   3045       ){
  3043   3046         assert( pLoop->u.btree.nSkip==0 );
  3044   3047         bSeekPastNull = 1;
  3045   3048         nExtraReg = 1;
  3046   3049       }
  3047   3050   
................................................................................
  5195   5198         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5196   5199       }
  5197   5200     }
  5198   5201     if( pWInfo->pOrderBy && pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
  5199   5202       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  5200   5203         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5201   5204       }else{
  5202         -      pWInfo->bOBSat = 1;
         5205  +      pWInfo->nOBSat = pFrom->isOrdered;
  5203   5206         pWInfo->revMask = pFrom->revLoop;
  5204   5207       }
  5205   5208     }
  5206   5209     pWInfo->nRowOut = pFrom->nRow;
  5207   5210   
  5208   5211     /* Free temporary memory and return success */
  5209   5212     sqlite3DbFree(db, pSpace);
................................................................................
  5280   5283     }
  5281   5284     if( pLoop->wsFlags ){
  5282   5285       pLoop->nOut = (LogEst)1;
  5283   5286       pWInfo->a[0].pWLoop = pLoop;
  5284   5287       pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
  5285   5288       pWInfo->a[0].iTabCur = iCur;
  5286   5289       pWInfo->nRowOut = 1;
  5287         -    if( pWInfo->pOrderBy ) pWInfo->bOBSat =  1;
         5290  +    if( pWInfo->pOrderBy ) pWInfo->nOBSat =  pWInfo->pOrderBy->nExpr;
  5288   5291       if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
  5289   5292         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5290   5293       }
  5291   5294   #ifdef SQLITE_DEBUG
  5292   5295       pLoop->cId = '0';
  5293   5296   #endif
  5294   5297       return 1;
................................................................................
  5488   5491         sWLB.pWC->a[ii].wtFlags |= TERM_CODED;
  5489   5492       }
  5490   5493     }
  5491   5494   
  5492   5495     /* Special case: No FROM clause
  5493   5496     */
  5494   5497     if( nTabList==0 ){
  5495         -    if( pOrderBy ) pWInfo->bOBSat = 1;
         5498  +    if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr;
  5496   5499       if( wctrlFlags & WHERE_WANT_DISTINCT ){
  5497   5500         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5498   5501       }
  5499   5502     }
  5500   5503   
  5501   5504     /* Assign a bit from the bitmask to every term in the FROM clause.
  5502   5505     **
................................................................................
  5599   5602     if( pParse->nErr || NEVER(db->mallocFailed) ){
  5600   5603       goto whereBeginError;
  5601   5604     }
  5602   5605   #ifdef WHERETRACE_ENABLED /* !=0 */
  5603   5606     if( sqlite3WhereTrace ){
  5604   5607       int ii;
  5605   5608       sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);
  5606         -    if( pWInfo->bOBSat ){
  5607         -      sqlite3DebugPrintf(" ORDERBY=0x%llx", pWInfo->revMask);
         5609  +    if( pWInfo->nOBSat>0 ){
         5610  +      sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask);
  5608   5611       }
  5609   5612       switch( pWInfo->eDistinct ){
  5610   5613         case WHERE_DISTINCT_UNIQUE: {
  5611   5614           sqlite3DebugPrintf("  DISTINCT=unique");
  5612   5615           break;
  5613   5616         }
  5614   5617         case WHERE_DISTINCT_ORDERED: {

Changes to src/whereInt.h.

   393    393     SrcList *pTabList;        /* List of tables in the join */
   394    394     ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
   395    395     ExprList *pResultSet;     /* Result set. DISTINCT operates on these */
   396    396     WhereLoop *pLoops;        /* List of all WhereLoop objects */
   397    397     Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
   398    398     LogEst nRowOut;           /* Estimated number of output rows */
   399    399     u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
   400         -  u8 bOBSat;                /* ORDER BY satisfied by indices */
          400  +  i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
   401    401     u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
   402    402     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
   403    403     u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
   404    404     u8 nLevel;                /* Number of nested loop */
   405    405     int iTop;                 /* The very beginning of the WHERE loop */
   406    406     int iContinue;            /* Jump here to continue with next record */
   407    407     int iBreak;               /* Jump here to break out of the loop */