/ Check-in [db361482]
Login

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

Overview
Comment:Backport the ORDER BY LIMIT optimization to version 3.8.9.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | branch-3.8.9
Files: files | file ages | folders
SHA1: db3614825fa02ddacc76b85d76a37aad9d2a9dc8
User & Date: drh 2016-09-14 01:43:24
Context
2016-09-23
18:06
Fix the ORDER BY LIMIT optimization backport so that it works when the ORDER BY uses the DESC direction. check-in: 0c3cafb7 user: drh tags: branch-3.8.9
2016-09-14
01:43
Backport the ORDER BY LIMIT optimization to version 3.8.9. check-in: db361482 user: drh tags: branch-3.8.9
2015-04-08
12:16
Version 3.8.9 check-in: 8a8ffc86 user: drh tags: trunk, release, version-3.8.9
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

    50     50     ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
    51     51     int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
    52     52     int iECursor;         /* Cursor number for the sorter */
    53     53     int regReturn;        /* Register holding block-output return address */
    54     54     int labelBkOut;       /* Start label for the block-output subroutine */
    55     55     int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
    56     56     u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
           57  +  u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
    57     58   };
    58     59   #define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
    59     60   
    60     61   /*
    61     62   ** Delete all the content of a Select structure.  Deallocate the structure
    62     63   ** itself only if bFree is true.
    63     64   */
................................................................................
   561    562     }else{
   562    563       op = OP_IdxInsert;
   563    564     }
   564    565     sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord);
   565    566     if( pSelect->iLimit ){
   566    567       int addr;
   567    568       int iLimit;
          569  +    int r1 = 0;
   568    570       if( pSelect->iOffset ){
   569    571         iLimit = pSelect->iOffset+1;
   570    572       }else{
   571    573         iLimit = pSelect->iLimit;
   572    574       }
          575  +    /* Fill the sorter until it contains LIMIT+OFFSET entries.  (The iLimit
          576  +    ** register is initialized with value of LIMIT+OFFSET.)  After the sorter
          577  +    ** fills up, delete the least entry in the sorter after each insert.
          578  +    ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
   573    579       addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, -1); VdbeCoverage(v);
   574    580       sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
          581  +    if( pSort->bOrderedInnerLoop ){
          582  +      r1 = ++pParse->nMem;
          583  +      sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1);
          584  +      VdbeComment((v, "seq"));
          585  +    }
   575    586       sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
          587  +    if( pSort->bOrderedInnerLoop ){
          588  +      /* If the inner loop is driven by an index such that values from
          589  +      ** the same iteration of the inner loop are in sorted order, then
          590  +      ** immediately jump to the next iteration of an inner loop if the
          591  +      ** entry from the current iteration does not fit into the top
          592  +      ** LIMIT+OFFSET entries of the sorter. */
          593  +      int iBrk = sqlite3VdbeCurrentAddr(v) + 2;
          594  +      sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1);
          595  +      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
          596  +      VdbeCoverage(v);
          597  +    }
   576    598       sqlite3VdbeJumpHere(v, addr);
   577    599     }
   578    600   }
   579    601   
   580    602   /*
   581    603   ** Add code to implement the OFFSET
   582    604   */
................................................................................
  4997   5019         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  4998   5020       }
  4999   5021       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  5000   5022         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  5001   5023       }
  5002   5024       if( sSort.pOrderBy ){
  5003   5025         sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
         5026  +      sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
  5004   5027         if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
  5005   5028           sSort.pOrderBy = 0;
  5006   5029         }
  5007   5030       }
  5008   5031   
  5009   5032       /* If sorting index that was created by a prior OP_OpenEphemeral 
  5010   5033       ** instruction ended up not being needed, then change the OP_OpenEphemeral

Changes to src/sqliteInt.h.

  2272   2272   #define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
  2273   2273   #define WHERE_NO_AUTOINDEX     0x0080 /* Disallow automatic indexes */
  2274   2274   #define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
  2275   2275   #define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */
  2276   2276   #define WHERE_WANT_DISTINCT    0x0400 /* All output needs to be distinct */
  2277   2277   #define WHERE_SORTBYGROUP      0x0800 /* Support sqlite3WhereIsSorted() */
  2278   2278   #define WHERE_REOPEN_IDX       0x1000 /* Try to use OP_ReopenIdx */
         2279  +#define WHERE_ORDERBY_LIMIT    0x2000 /* ORDERBY+LIMIT on the inner loop */
  2279   2280   
  2280   2281   /* Allowed return values from sqlite3WhereIsDistinct()
  2281   2282   */
  2282   2283   #define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
  2283   2284   #define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
  2284   2285   #define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
  2285   2286   #define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */
................................................................................
  3285   3286   void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
  3286   3287   void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
  3287   3288   WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  3288   3289   void sqlite3WhereEnd(WhereInfo*);
  3289   3290   u64 sqlite3WhereOutputRowCount(WhereInfo*);
  3290   3291   int sqlite3WhereIsDistinct(WhereInfo*);
  3291   3292   int sqlite3WhereIsOrdered(WhereInfo*);
         3293  +int sqlite3WhereOrderedInnerLoop(WhereInfo*);
  3292   3294   int sqlite3WhereIsSorted(WhereInfo*);
  3293   3295   int sqlite3WhereContinueLabel(WhereInfo*);
  3294   3296   int sqlite3WhereBreakLabel(WhereInfo*);
  3295   3297   int sqlite3WhereOkOnePass(WhereInfo*, int*);
  3296   3298   int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
  3297   3299   void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);
  3298   3300   void sqlite3ExprCodeMove(Parse*, int, int, int);

Changes to src/where.c.

    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     42     return pWInfo->nOBSat;
    43     43   }
           44  +
           45  +/*
           46  +** Return TRUE if the innermost loop of the WHERE clause implementation
           47  +** returns rows in ORDER BY order for complete run of the inner loop.
           48  +**
           49  +** Across multiple iterations of outer loops, the output rows need not be
           50  +** sorted.  As long as rows are sorted for just the innermost loop, this
           51  +** routine can return TRUE.
           52  +*/
           53  +int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){
           54  +  return pWInfo->bOrderedInnerLoop;
           55  +}
    44     56   
    45     57   /*
    46     58   ** Return the VDBE address or label to jump to in order to continue
    47     59   ** immediately with the next row of a WHERE clause.
    48     60   */
    49     61   int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
    50     62     assert( pWInfo->iContinue!=0 );
................................................................................
  5598   5610   ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  5599   5611   ** pOrderBy terms must be matched in strict left-to-right order.
  5600   5612   */
  5601   5613   static i8 wherePathSatisfiesOrderBy(
  5602   5614     WhereInfo *pWInfo,    /* The WHERE clause */
  5603   5615     ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
  5604   5616     WherePath *pPath,     /* The WherePath to check */
  5605         -  u16 wctrlFlags,       /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
         5617  +  u16 wctrlFlags,       /* WHERE_GROUPBY, _DISTINCTBY  or _ORDERBY_LIMIT */
  5606   5618     u16 nLoop,            /* Number of entries in pPath->aLoop[] */
  5607   5619     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  5608   5620     Bitmask *pRevMask     /* OUT: Mask of WhereLoops to run in reverse order */
  5609   5621   ){
  5610   5622     u8 revSet;            /* True if rev is known */
  5611   5623     u8 rev;               /* Composite sort order */
  5612   5624     u8 revIdx;            /* Index sort order */
  5613   5625     u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  5614   5626     u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  5615   5627     u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
         5628  +  u16 eqOpMask;         /* Allowed equality operators */
  5616   5629     u16 nKeyCol;          /* Number of key columns in pIndex */
  5617   5630     u16 nColumn;          /* Total number of ordered columns in the index */
  5618   5631     u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  5619   5632     int iLoop;            /* Index of WhereLoop in pPath being processed */
  5620   5633     int i, j;             /* Loop counters */
  5621   5634     int iCur;             /* Cursor number for current WhereLoop */
  5622   5635     int iColumn;          /* A column number within table iCur */
................................................................................
  5659   5672     nOrderBy = pOrderBy->nExpr;
  5660   5673     testcase( nOrderBy==BMS-1 );
  5661   5674     if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  5662   5675     isOrderDistinct = 1;
  5663   5676     obDone = MASKBIT(nOrderBy)-1;
  5664   5677     orderDistinctMask = 0;
  5665   5678     ready = 0;
         5679  +  eqOpMask = WO_EQ | WO_ISNULL;
         5680  +  if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN;
  5666   5681     for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
  5667   5682       if( iLoop>0 ) ready |= pLoop->maskSelf;
         5683  +    if( iLoop<nLoop ){
         5684  +      pLoop = pPath->aLoop[iLoop];
         5685  +      if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
         5686  +    }else{
         5687  +      pLoop = pLast;
         5688  +    }
  5668   5689       pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
  5669   5690       if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
  5670   5691         if( pLoop->u.vtab.isOrdered ) obSat = obDone;
  5671   5692         break;
  5672   5693       }
  5673   5694       iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  5674   5695   
................................................................................
  5679   5700       */
  5680   5701       for(i=0; i<nOrderBy; i++){
  5681   5702         if( MASKBIT(i) & obSat ) continue;
  5682   5703         pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  5683   5704         if( pOBExpr->op!=TK_COLUMN ) continue;
  5684   5705         if( pOBExpr->iTable!=iCur ) continue;
  5685   5706         pTerm = findTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
  5686         -                       ~ready, WO_EQ|WO_ISNULL, 0);
         5707  +                       ~ready, eqOpMask, 0);
  5687   5708         if( pTerm==0 ) continue;
         5709  +      if( pTerm->eOperator==WO_IN ){
         5710  +        /* IN terms are only valid for sorting in the ORDER BY LIMIT 
         5711  +        ** optimization, and then only if they are actually used
         5712  +        ** by the query plan */
         5713  +        assert( wctrlFlags & WHERE_ORDERBY_LIMIT );
         5714  +        for(j=0; j<pLoop->nLTerm && pTerm!=pLoop->aLTerm[j]; j++){}
         5715  +        if( j>=pLoop->nLTerm ) continue;
         5716  +      }
  5688   5717         if( (pTerm->eOperator&WO_EQ)!=0 && pOBExpr->iColumn>=0 ){
  5689   5718           const char *z1, *z2;
  5690   5719           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
  5691   5720           if( !pColl ) pColl = db->pDfltColl;
  5692   5721           z1 = pColl->zName;
  5693   5722           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
  5694   5723           if( !pColl ) pColl = db->pDfltColl;
................................................................................
  5717   5746         ** that are not constrained by == or IN.
  5718   5747         */
  5719   5748         rev = revSet = 0;
  5720   5749         distinctColumns = 0;
  5721   5750         for(j=0; j<nColumn; j++){
  5722   5751           u8 bOnce;   /* True to run the ORDER BY search loop */
  5723   5752   
  5724         -        /* Skip over == and IS NULL terms */
         5753  +        /* Skip over == and IS NULL terms
         5754  +        ** (Also skip IN terms when doing WHERE_ORDERBY_LIMIT processing)
         5755  +        */
  5725   5756           if( j<pLoop->u.btree.nEq
  5726   5757            && pLoop->nSkip==0
  5727         -         && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
         5758  +         && ((i = pLoop->aLTerm[j]->eOperator) & eqOpMask)!=0
  5728   5759           ){
  5729   5760             if( i & WO_ISNULL ){
  5730   5761               testcase( isOrderDistinct );
  5731   5762               isOrderDistinct = 0;
  5732   5763             }
  5733   5764             continue;  
  5734   5765           }
................................................................................
  6233   6264     if( pWInfo->pOrderBy ){
  6234   6265       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  6235   6266         if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
  6236   6267           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  6237   6268         }
  6238   6269       }else{
  6239   6270         pWInfo->nOBSat = pFrom->isOrdered;
  6240         -      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
         6271  +      pWInfo->revMask = pFrom->revLoop;
         6272  +      if( pWInfo->nOBSat<=0 ){
         6273  +        pWInfo->nOBSat = 0;
         6274  +        if( nLoop>0 && (pFrom->aLoop[nLoop-1]->wsFlags & WHERE_ONEROW)==0 ){
         6275  +          Bitmask m;
         6276  +          int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom,
         6277  +                      WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m);
         6278  +          if( rc==pWInfo->pOrderBy->nExpr ){
         6279  +            pWInfo->bOrderedInnerLoop = 1;
         6280  +            pWInfo->revMask = m;
         6281  +          }
         6282  +        }
         6283  +      }
  6241   6284         pWInfo->revMask = pFrom->revLoop;
  6242   6285       }
  6243   6286       if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
  6244   6287           && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr
  6245   6288       ){
  6246   6289         Bitmask revMask = 0;
  6247   6290         int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 

Changes to src/whereInt.h.

   408    408     u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
   409    409     i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
   410    410     u8 sorted;                /* True if really sorted (not just grouped) */
   411    411     u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
   412    412     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
   413    413     u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
   414    414     u8 nLevel;                /* Number of nested loop */
          415  +  u8 bOrderedInnerLoop;     /* True if only the inner-most loop is ordered */
   415    416     int iTop;                 /* The very beginning of the WHERE loop */
   416    417     int iContinue;            /* Jump here to continue with next record */
   417    418     int iBreak;               /* Jump here to break out of the loop */
   418    419     int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
   419    420     int aiCurOnePass[2];      /* OP_OpenWrite cursors for the ONEPASS opt */
   420    421     WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
   421    422     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  +# Bug report against the new ORDER BY LIMIT optimization just prior to
           81  +# release.  (Unreleased so there is no ticket).
           82  +#
           83  +# Make sure the optimization is not applied if the inner loop can only
           84  +# provide a single row of output.
           85  +#
           86  +do_execsql_test limit2-200 {
           87  +  CREATE TABLE t200(a, b);
           88  +  WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<1000)
           89  +    INSERT INTO t200(a,b) SELECT x, x FROM c;
           90  +  CREATE TABLE t201(x INTEGER PRIMARY KEY, y);
           91  +  INSERT INTO t201(x,y) VALUES(2,12345);
           92  +
           93  +  SELECT *, '|' FROM t200, t201 WHERE x=b ORDER BY y LIMIT 3;
           94  +} {2 2 2 12345 |}
           95  +do_execsql_test limit2-210 {
           96  +  SELECT *, '|' FROM t200 LEFT JOIN t201 ON x=b ORDER BY y LIMIT 3;
           97  +} {1 1 {} {} | 3 3 {} {} | 4 4 {} {} |}
           98  +
           99  +# Bug in the ORDER BY LIMIT optimization reported on 2016-09-06.
          100  +# Ticket https://www.sqlite.org/src/info/559733b09e96
          101  +#
          102  +do_execsql_test limit2-300 {
          103  +  CREATE TABLE t300(a,b,c);
          104  +  CREATE INDEX t300x ON t300(a,b,c);
          105  +  INSERT INTO t300 VALUES(0,1,99),(0,1,0),(0,0,0);
          106  +  SELECT *,'.' FROM t300 WHERE a=0 AND (c=0 OR c=99) ORDER BY c DESC;
          107  +} {0 1 99 . 0 0 0 . 0 1 0 .}
          108  +do_execsql_test limit2-310 {
          109  +  SELECT *,'.' FROM t300 WHERE a=0 AND (c=0 OR c=99) ORDER BY c DESC LIMIT 1;
          110  +} {0 1 99 .}
          111  +
          112  +
          113  +
          114  +
          115  +finish_test