/ Check-in [559733b0]
Login

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

Overview
Comment:For queries with both ORDER BY and LIMIT, if the rows of the inner loop are emitted in ORDER BY order and the LIMIT has been reached, then optimize by exiting the inner loop and continuing with the next cycle of the first outer loop.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 559733b09e9630fac9d9318a7ecbaba9134e9160
User & Date: drh 2016-05-20 14:11:37
References
2018-09-08
03:22 New ticket [9936b2fa] Infinite loop due to the ORDER BY LIMIT optimization. artifact: 9b89fdd3 user: drh
2017-12-13
16:33 New ticket [123c9ba3] Incorrect result when an index is used for an ordered join. artifact: da421d67 user: drh
2016-10-12
14:00 New ticket [96c1454c] Incorrect result with ORDER BY DESC and LIMIT (again). artifact: e3b3158e user: drh
2016-09-07
00:42 New ticket [0c4df461] Incorrect result with ORDER BY DESC and LIMIT. artifact: 51389ac4 user: drh
Context
2016-05-20
14:54
Optimizations to link list merge sort code in vdbesort.c, pcache.c, and rowset.c. Resulting binaries are 10 bytes smaller and use 0.03% fewer CPU cycles. check-in: 9033afbb user: drh tags: trunk
14:11
For queries with both ORDER BY and LIMIT, if the rows of the inner loop are emitted in ORDER BY order and the LIMIT has been reached, then optimize by exiting the inner loop and continuing with the next cycle of the first outer loop. check-in: 559733b0 user: drh tags: trunk
13:44
Set the NULLEQ flag on the sequence counter comparison in the ORDER BY LIMIT optimization, to avoid coverage complaints about not testing the NULL case. Closed-Leaf check-in: ed1b30dc user: drh tags: orderby-limit
12:22
Autoconf configure.ac adjustment to try to get it to look for both editline and readline automatically. check-in: 645bd696 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  +      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
          615  +      VdbeCoverage(v);
          616  +    }
   595    617       sqlite3VdbeJumpHere(v, addr);
   596    618     }
   597    619   }
   598    620   
   599    621   /*
   600    622   ** Add code to implement the OFFSET
   601    623   */
................................................................................
  5172   5194         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  5173   5195       }
  5174   5196       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  5175   5197         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  5176   5198       }
  5177   5199       if( sSort.pOrderBy ){
  5178   5200         sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
         5201  +      sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
  5179   5202         if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
  5180   5203           sSort.pOrderBy = 0;
  5181   5204         }
  5182   5205       }
  5183   5206   
  5184   5207       /* If sorting index that was created by a prior OP_OpenEphemeral 
  5185   5208       ** instruction ended up not being needed, then change the OP_OpenEphemeral

Changes to src/sqliteInt.h.

  2536   2536   #define WHERE_OR_SUBCLAUSE     0x0020 /* Processing a sub-WHERE as part of
  2537   2537                                         ** the OR optimization  */
  2538   2538   #define WHERE_GROUPBY          0x0040 /* pOrderBy is really a GROUP BY */
  2539   2539   #define WHERE_DISTINCTBY       0x0080 /* pOrderby is really a DISTINCT clause */
  2540   2540   #define WHERE_WANT_DISTINCT    0x0100 /* All output needs to be distinct */
  2541   2541   #define WHERE_SORTBYGROUP      0x0200 /* Support sqlite3WhereIsSorted() */
  2542   2542   #define WHERE_SEEK_TABLE       0x0400 /* Do not defer seeks on main table */
  2543         -                        /*     0x0800    not currently used */
         2543  +#define WHERE_ORDERBY_LIMIT    0x0800 /* ORDERBY+LIMIT on the inner loop */
  2544   2544                           /*     0x1000    not currently used */
  2545   2545                           /*     0x2000    not currently used */
  2546   2546   #define WHERE_USE_LIMIT        0x4000 /* Use the LIMIT in cost estimates */
  2547   2547                           /*     0x8000    not currently used */
  2548   2548   
  2549   2549   /* Allowed return values from sqlite3WhereIsDistinct()
  2550   2550   */
................................................................................
  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 );
................................................................................
  3246   3258   ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  3247   3259   ** pOrderBy terms must be matched in strict left-to-right order.
  3248   3260   */
  3249   3261   static i8 wherePathSatisfiesOrderBy(
  3250   3262     WhereInfo *pWInfo,    /* The WHERE clause */
  3251   3263     ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
  3252   3264     WherePath *pPath,     /* The WherePath to check */
  3253         -  u16 wctrlFlags,       /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
         3265  +  u16 wctrlFlags,       /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */
  3254   3266     u16 nLoop,            /* Number of entries in pPath->aLoop[] */
  3255   3267     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  3256   3268     Bitmask *pRevMask     /* OUT: Mask of WhereLoops to run in reverse order */
  3257   3269   ){
  3258   3270     u8 revSet;            /* True if rev is known */
  3259   3271     u8 rev;               /* Composite sort order */
  3260   3272     u8 revIdx;            /* Index sort order */
  3261   3273     u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  3262   3274     u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  3263   3275     u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
         3276  +  u16 eqOpMask;         /* Allowed equality operators */
  3264   3277     u16 nKeyCol;          /* Number of key columns in pIndex */
  3265   3278     u16 nColumn;          /* Total number of ordered columns in the index */
  3266   3279     u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  3267   3280     int iLoop;            /* Index of WhereLoop in pPath being processed */
  3268   3281     int i, j;             /* Loop counters */
  3269   3282     int iCur;             /* Cursor number for current WhereLoop */
  3270   3283     int iColumn;          /* A column number within table iCur */
................................................................................
  3307   3320     nOrderBy = pOrderBy->nExpr;
  3308   3321     testcase( nOrderBy==BMS-1 );
  3309   3322     if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  3310   3323     isOrderDistinct = 1;
  3311   3324     obDone = MASKBIT(nOrderBy)-1;
  3312   3325     orderDistinctMask = 0;
  3313   3326     ready = 0;
         3327  +  eqOpMask = WO_EQ | WO_IS | WO_ISNULL;
         3328  +  if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN;
  3314   3329     for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
  3315   3330       if( iLoop>0 ) ready |= pLoop->maskSelf;
  3316         -    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
         3331  +    if( iLoop<nLoop ){
         3332  +      pLoop = pPath->aLoop[iLoop];
         3333  +      if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
         3334  +    }else{
         3335  +      pLoop = pLast;
         3336  +    }
  3317   3337       if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
  3318   3338         if( pLoop->u.vtab.isOrdered ) obSat = obDone;
  3319   3339         break;
  3320   3340       }
  3321   3341       iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  3322   3342   
  3323   3343       /* Mark off any ORDER BY term X that is a column in the table of
................................................................................
  3327   3347       */
  3328   3348       for(i=0; i<nOrderBy; i++){
  3329   3349         if( MASKBIT(i) & obSat ) continue;
  3330   3350         pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  3331   3351         if( pOBExpr->op!=TK_COLUMN ) continue;
  3332   3352         if( pOBExpr->iTable!=iCur ) continue;
  3333   3353         pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
  3334         -                       ~ready, WO_EQ|WO_ISNULL|WO_IS, 0);
         3354  +                       ~ready, eqOpMask, 0);
  3335   3355         if( pTerm==0 ) continue;
  3336   3356         if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){
  3337   3357           const char *z1, *z2;
  3338   3358           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
  3339   3359           if( !pColl ) pColl = db->pDfltColl;
  3340   3360           z1 = pColl->zName;
  3341   3361           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
................................................................................
  3367   3387         ** that are not constrained by == or IN.
  3368   3388         */
  3369   3389         rev = revSet = 0;
  3370   3390         distinctColumns = 0;
  3371   3391         for(j=0; j<nColumn; j++){
  3372   3392           u8 bOnce;   /* True to run the ORDER BY search loop */
  3373   3393   
  3374         -        /* Skip over == and IS NULL terms */
         3394  +        /* Skip over == and IS and ISNULL terms.
         3395  +        ** (Also skip IN terms when doing WHERE_ORDERBY_LIMIT processing)
         3396  +        */
  3375   3397           if( j<pLoop->u.btree.nEq
  3376   3398            && pLoop->nSkip==0
  3377         -         && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL|WO_IS))!=0
         3399  +         && ((i = pLoop->aLTerm[j]->eOperator) & eqOpMask)!=0
  3378   3400           ){
  3379   3401             if( i & WO_ISNULL ){
  3380   3402               testcase( isOrderDistinct );
  3381   3403               isOrderDistinct = 0;
  3382   3404             }
  3383   3405             continue;  
  3384   3406           }
................................................................................
  3894   3916     if( pWInfo->pOrderBy ){
  3895   3917       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  3896   3918         if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
  3897   3919           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  3898   3920         }
  3899   3921       }else{
  3900   3922         pWInfo->nOBSat = pFrom->isOrdered;
  3901         -      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
  3902   3923         pWInfo->revMask = pFrom->revLoop;
         3924  +      if( pWInfo->nOBSat<=0 ){
         3925  +        pWInfo->nOBSat = 0;
         3926  +        if( nLoop>0 ){
         3927  +          Bitmask m;
         3928  +          int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom,
         3929  +                      WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m);
         3930  +          if( rc==pWInfo->pOrderBy->nExpr ){
         3931  +            pWInfo->bOrderedInnerLoop = 1;
         3932  +            pWInfo->revMask = m;
         3933  +          }
         3934  +        }
         3935  +      }
  3903   3936       }
  3904   3937       if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
  3905   3938           && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
  3906   3939       ){
  3907   3940         Bitmask revMask = 0;
  3908   3941         int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 
  3909   3942             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 */

Added test/limit2.test.

            1  +# 2016-05-20
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this file is testing the LIMIT in combination with ORDER BY
           13  +# and in particular, the optimizations in the inner loop that cause an
           14  +# early exit of the inner loop when the LIMIT is reached and the inner
           15  +# loop is emitting rows in ORDER BY order.
           16  +
           17  +
           18  +set testdir [file dirname $argv0]
           19  +source $testdir/tester.tcl
           20  +
           21  +do_execsql_test limit2-100 {
           22  +  CREATE TABLE t1(a,b);
           23  +  WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<1000)
           24  +    INSERT INTO t1(a,b) SELECT 1, (x*17)%1000 + 1000 FROM c;
           25  +  INSERT INTO t1(a,b) VALUES(2,2),(3,1006),(4,4),(5,9999);
           26  +  CREATE INDEX t1ab ON t1(a,b);
           27  +}
           28  +set sqlite_search_count 0
           29  +do_execsql_test limit2-100.1 {
           30  +  SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY b LIMIT 5;
           31  +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |}
           32  +set fast_count $sqlite_search_count
           33  +set sqlite_search_count 0
           34  +do_execsql_test limit2-100.2 {
           35  +  SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY +b LIMIT 5;
           36  +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |}
           37  +do_test limit2-100.3 {
           38  +  set slow_count $sqlite_search_count
           39  +  expr {$fast_count < 0.02*$slow_count}
           40  +} {1}
           41  +
           42  +do_execsql_test limit2-110 {
           43  +  CREATE TABLE t2(x,y);
           44  +  INSERT INTO t2(x,y) VALUES('a',1),('a',2),('a',3),('a',4);
           45  +  INSERT INTO t2(x,y) VALUES('b',1),('c',2),('d',3),('e',4);
           46  +  CREATE INDEX t2xy ON t2(x,y);
           47  +}
           48  +set sqlite_search_count 0
           49  +do_execsql_test limit2-110.1 {
           50  +  SELECT a, b, '|' FROM t2, t1 WHERE t2.x='a' AND t1.a=t2.y ORDER BY t1.b LIMIT 5;
           51  +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |}
           52  +set fast_count $sqlite_search_count
           53  +set sqlite_search_count 0
           54  +do_execsql_test limit2-110.2 {
           55  +  SELECT a, b, '|' FROM t2, t1 WHERE t2.x='a' AND t1.a=t2.y ORDER BY +t1.b LIMIT 5;
           56  +} {2 2 | 4 4 | 1 1000 | 1 1001 | 1 1002 |}
           57  +set slow_count $sqlite_search_count
           58  +do_test limit2-110.3 {
           59  +  expr {$fast_count < 0.02*$slow_count}
           60  +} {1}
           61  +
           62  +do_execsql_test limit2-120 {
           63  +  DROP INDEX t1ab;
           64  +  CREATE INDEX t1ab ON t1(a,b DESC);
           65  +}
           66  +set sqlite_search_count 0
           67  +do_execsql_test limit2-120.1 {
           68  +  SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY b DESC LIMIT 5;
           69  +} {5 9999 | 1 1999 | 1 1998 | 1 1997 | 1 1996 |}
           70  +set fast_count $sqlite_search_count
           71  +set sqlite_search_count 0
           72  +do_execsql_test limit2-120.2 {
           73  +  SELECT a, b, '|' FROM t1 WHERE a IN (2,4,5,3,1) ORDER BY +b DESC LIMIT 5;
           74  +} {5 9999 | 1 1999 | 1 1998 | 1 1997 | 1 1996 |}
           75  +do_test limit2-120.3 {
           76  +  set slow_count $sqlite_search_count
           77  +  expr {$fast_count < 0.02*$slow_count}
           78  +} {1}
           79  +
           80  +
           81  +
           82  +finish_test