/ Check-in [852d1eda]
Login

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

Overview
Comment:In a query with both ORDER BY and LIMIT, if the inner loop satisfies the ORDER BY then try to cut short each invocation of the inner loop once the LIMIT has been satisfied. This check-in is a partial implementation only.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-limit
Files: files | file ages | folders
SHA1: 852d1eda6ecca1171f6ed800b06f5b4854672002
User & Date: drh 2016-05-19 22:13:37
Context
2016-05-19
22:40
Appears to work now. Needs test cases, more comments, and code optimization. check-in: 990fe50c user: drh tags: orderby-limit
22:13
In a query with both ORDER BY and LIMIT, if the inner loop satisfies the ORDER BY then try to cut short each invocation of the inner loop once the LIMIT has been satisfied. This check-in is a partial implementation only. check-in: 852d1eda user: drh tags: orderby-limit
19:31
Fixup comments on wctrlFlags value definitions. check-in: 58b516e8 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

    52     52     int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
    53     53     int iECursor;         /* Cursor number for the sorter */
    54     54     int regReturn;        /* Register holding block-output return address */
    55     55     int labelBkOut;       /* Start label for the block-output subroutine */
    56     56     int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
    57     57     int labelDone;        /* Jump here when done, ex: LIMIT reached */
    58     58     u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
           59  +  u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
    59     60   };
    60     61   #define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
    61     62   
    62     63   /*
    63     64   ** Delete all the content of a Select structure.  Deallocate the structure
    64     65   ** itself only if bFree is true.
    65     66   */
................................................................................
   585    586       op = OP_SorterInsert;
   586    587     }else{
   587    588       op = OP_IdxInsert;
   588    589     }
   589    590     sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord);
   590    591     if( iLimit ){
   591    592       int addr;
          593  +    int r1 = 0;
          594  +    /* Fill the sorter until it contains LIMIT+OFFSET entries.  (The iLimit
          595  +    ** register is initialized with value of LIMIT+OFFSET.)  After the sorter
          596  +    ** fills up, delete the least entry in the sorter after each insert.
          597  +    ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
   592    598       addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, 1); VdbeCoverage(v);
   593    599       sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
          600  +    if( pSort->bOrderedInnerLoop ){
          601  +      r1 = ++pParse->nMem;
          602  +      sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1);
          603  +      VdbeComment((v, "seq"));
          604  +    }
   594    605       sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
          606  +    if( pSort->bOrderedInnerLoop ){
          607  +      /* If the inner loop is driven by an index such that values from
          608  +      ** the same iteration of the inner loop are in sorted order, then
          609  +      ** immediately jump to the next iteration of an inner loop if the
          610  +      ** entry from the current iteration does not fit into the top
          611  +      ** LIMIT+OFFSET entries of the sorter. */
          612  +      int iBrk = sqlite3VdbeCurrentAddr(v) + 2;
          613  +      sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1);
          614  +      VdbeCoverage(v);
          615  +    }
   595    616       sqlite3VdbeJumpHere(v, addr);
   596    617     }
   597    618   }
   598    619   
   599    620   /*
   600    621   ** Add code to implement the OFFSET
   601    622   */
................................................................................
  5172   5193         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  5173   5194       }
  5174   5195       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  5175   5196         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  5176   5197       }
  5177   5198       if( sSort.pOrderBy ){
  5178   5199         sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
         5200  +      sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
  5179   5201         if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
  5180   5202           sSort.pOrderBy = 0;
  5181   5203         }
  5182   5204       }
  5183   5205   
  5184   5206       /* If sorting index that was created by a prior OP_OpenEphemeral 
  5185   5207       ** instruction ended up not being needed, then change the OP_OpenEphemeral

Changes to src/sqliteInt.h.

  3633   3633   void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
  3634   3634   void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
  3635   3635   WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  3636   3636   void sqlite3WhereEnd(WhereInfo*);
  3637   3637   LogEst sqlite3WhereOutputRowCount(WhereInfo*);
  3638   3638   int sqlite3WhereIsDistinct(WhereInfo*);
  3639   3639   int sqlite3WhereIsOrdered(WhereInfo*);
         3640  +int sqlite3WhereOrderedInnerLoop(WhereInfo*);
  3640   3641   int sqlite3WhereIsSorted(WhereInfo*);
  3641   3642   int sqlite3WhereContinueLabel(WhereInfo*);
  3642   3643   int sqlite3WhereBreakLabel(WhereInfo*);
  3643   3644   int sqlite3WhereOkOnePass(WhereInfo*, int*);
  3644   3645   #define ONEPASS_OFF      0        /* Use of ONEPASS not allowed */
  3645   3646   #define ONEPASS_SINGLE   1        /* ONEPASS valid for a single row update */
  3646   3647   #define ONEPASS_MULTI    2        /* ONEPASS is valid for multiple rows */

Changes to src/where.c.

    46     46   /*
    47     47   ** Return TRUE if the WHERE clause returns rows in ORDER BY order.
    48     48   ** Return FALSE if the output needs to be sorted.
    49     49   */
    50     50   int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
    51     51     return pWInfo->nOBSat;
    52     52   }
           53  +
           54  +/*
           55  +** Return TRUE if the innermost loop of the WHERE clause implementation
           56  +** returns rows in ORDER BY order for complete run of the inner loop.
           57  +**
           58  +** Across multiple iterations of outer loops, the output rows need not be
           59  +** sorted.  As long as rows are sorted for just the innermost loop, this
           60  +** routine can return TRUE.
           61  +*/
           62  +int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){
           63  +  return pWInfo->bOrderedInnerLoop;
           64  +}
    53     65   
    54     66   /*
    55     67   ** Return the VDBE address or label to jump to in order to continue
    56     68   ** immediately with the next row of a WHERE clause.
    57     69   */
    58     70   int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
    59     71     assert( pWInfo->iContinue!=0 );
................................................................................
  3894   3906     if( pWInfo->pOrderBy ){
  3895   3907       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  3896   3908         if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
  3897   3909           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  3898   3910         }
  3899   3911       }else{
  3900   3912         pWInfo->nOBSat = pFrom->isOrdered;
  3901         -      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
  3902   3913         pWInfo->revMask = pFrom->revLoop;
         3914  +      if( pWInfo->nOBSat<=0 ){
         3915  +        pWInfo->nOBSat = 0;
         3916  +      }
  3903   3917       }
  3904   3918       if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
  3905   3919           && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
  3906   3920       ){
  3907   3921         Bitmask revMask = 0;
  3908   3922         int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 
  3909   3923             pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask

Changes to src/whereInt.h.

   414    414     LogEst nRowOut;           /* Estimated number of output rows */
   415    415     LogEst iLimit;            /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */
   416    416     u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
   417    417     i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
   418    418     u8 sorted;                /* True if really sorted (not just grouped) */
   419    419     u8 eOnePass;              /* ONEPASS_OFF, or _SINGLE, or _MULTI */
   420    420     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
   421         -  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
          421  +  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values */
   422    422     u8 nLevel;                /* Number of nested loop */
          423  +  u8 bOrderedInnerLoop;     /* True if only the inner-most loop is ordered */
   423    424     int iTop;                 /* The very beginning of the WHERE loop */
   424    425     int iContinue;            /* Jump here to continue with next record */
   425    426     int iBreak;               /* Jump here to break out of the loop */
   426    427     int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
   427    428     int aiCurOnePass[2];      /* OP_OpenWrite cursors for the ONEPASS opt */
   428    429     WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
   429    430     WhereClause sWC;          /* Decomposition of the WHERE clause */