/ Check-in [20672012]
Login

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

Overview
Comment:Fix multiple issues with the ORDER BY LIMIT optimization. This is the proposed resolution to ticket [9936b2fa443fec03ff25].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:206720129ed2fa8875a286266d05b99fb2caf8671e4b74b26a6286a2073fcd8b
User & Date: drh 2018-09-08 20:09:46
References
2018-09-17
15:25
Disable the ORDER BY LIMIT optimization in queries using window functions. This fixes a problem that was introduced by check-in [206720129ed2fa8875a286] which attempted to fix ticket [9936b2fa443fec03ff25f9]. This changes is a fix for the follow-in tocket [510cde277783b5fb5de628]. check-in: 36c75fd5 user: drh tags: branch-3.25
15:19
Disable the ORDER BY LIMIT optimization in queries using window functions. This fixes a problem that was introduced by check-in [206720129ed2fa8875a286] which attempted to fix ticket [9936b2fa443fec03ff25f9]. This changes is a fix for the follow-in tocket [510cde277783b5fb5de628]. check-in: c6c9585f user: drh tags: trunk
14:28 New ticket [510cde27] Endless loop on a query with window functions, ORDER BY, and LIMIT. artifact: 614870a8 user: drh
Context
2018-09-08
20:29
Fix an unreachable branch in the new sqlite3WhereOrderByLimitOptLabel() function of the query planner. check-in: 5a954533 user: drh tags: trunk
20:09
Fix multiple issues with the ORDER BY LIMIT optimization. This is the proposed resolution to ticket [9936b2fa443fec03ff25]. check-in: 20672012 user: drh tags: trunk
16:55
Add a missing call to free() in Lemon. check-in: 8b4cf33a user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

64
65
66
67
68
69
70

71
72
73
74
75
76
77
78
79
...
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
...
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
....
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
  ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
  int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
  int iECursor;         /* Cursor number for the sorter */
  int regReturn;        /* Register holding block-output return address */
  int labelBkOut;       /* Start label for the block-output subroutine */
  int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
  int labelDone;        /* Jump here when done, ex: LIMIT reached */

  u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
  u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
#ifdef SQLITE_ENABLE_SORTER_REFERENCES
  u8 nDefer;            /* Number of valid entries in aDefer[] */
  struct DeferredCsr {
    Table *pTab;        /* Table definition */
    int iCsr;           /* Cursor number for table */
    int nKey;           /* Number of PK columns for table pTab (>=1) */
  } aDefer[4];
................................................................................
    ** less than LIMIT+OFFSET items or (b) the new record is smaller than 
    ** the largest record currently in the sorter. If (b) is true and there
    ** are already LIMIT+OFFSET items in the sorter, delete the largest
    ** entry before inserting the new one. This way there are never more 
    ** than LIMIT+OFFSET items in the sorter.
    **
    ** If the new record does not need to be inserted into the sorter,
    ** jump to the next iteration of the loop. Or, if the
    ** pSort->bOrderedInnerLoop flag is set to indicate that the inner
    ** loop delivers items in sorted order, jump to the next iteration
    ** of the outer loop.
    */
    int iCsr = pSort->iECursor;
    sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);
    VdbeCoverage(v);
    sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);
    iSkip = sqlite3VdbeAddOp4Int(v, OP_IdxLE,
                                 iCsr, 0, regBase+nOBSat, nExpr-nOBSat);
................................................................................
    op = OP_SorterInsert;
  }else{
    op = OP_IdxInsert;
  }
  sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
                       regBase+nOBSat, nBase-nOBSat);
  if( iSkip ){
    assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 );
    sqlite3VdbeChangeP2(v, iSkip,
         sqlite3VdbeCurrentAddr(v) + pSort->bOrderedInnerLoop);
  }
}

/*
** Add code to implement the OFFSET
*/
static void codeOffset(
................................................................................
      p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
    }
    if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
      sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
    }
    if( sSort.pOrderBy ){
      sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
      sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
      if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
        sSort.pOrderBy = 0;
      }
    }

    /* If sorting index that was created by a prior OP_OpenEphemeral 
    ** instruction ended up not being needed, then change the OP_OpenEphemeral







>

<







 







|
|
|
|







 







<

|







 







|







64
65
66
67
68
69
70
71
72

73
74
75
76
77
78
79
...
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
...
714
715
716
717
718
719
720

721
722
723
724
725
726
727
728
729
....
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
  ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
  int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
  int iECursor;         /* Cursor number for the sorter */
  int regReturn;        /* Register holding block-output return address */
  int labelBkOut;       /* Start label for the block-output subroutine */
  int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
  int labelDone;        /* Jump here when done, ex: LIMIT reached */
  int labelOBLopt;      /* Jump here when sorter is full */
  u8 sortFlags;         /* Zero or more SORTFLAG_* bits */

#ifdef SQLITE_ENABLE_SORTER_REFERENCES
  u8 nDefer;            /* Number of valid entries in aDefer[] */
  struct DeferredCsr {
    Table *pTab;        /* Table definition */
    int iCsr;           /* Cursor number for table */
    int nKey;           /* Number of PK columns for table pTab (>=1) */
  } aDefer[4];
................................................................................
    ** less than LIMIT+OFFSET items or (b) the new record is smaller than 
    ** the largest record currently in the sorter. If (b) is true and there
    ** are already LIMIT+OFFSET items in the sorter, delete the largest
    ** entry before inserting the new one. This way there are never more 
    ** than LIMIT+OFFSET items in the sorter.
    **
    ** If the new record does not need to be inserted into the sorter,
    ** jump to the next iteration of the loop. If the pSort->labelOBLopt
    ** value is not zero, then it is a label of where to jump.  Otherwise,
    ** just bypass the row insert logic.  See the header comment on the
    ** sqlite3WhereOrderByLimitOptLabel() function for additional info.
    */
    int iCsr = pSort->iECursor;
    sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);
    VdbeCoverage(v);
    sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);
    iSkip = sqlite3VdbeAddOp4Int(v, OP_IdxLE,
                                 iCsr, 0, regBase+nOBSat, nExpr-nOBSat);
................................................................................
    op = OP_SorterInsert;
  }else{
    op = OP_IdxInsert;
  }
  sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
                       regBase+nOBSat, nBase-nOBSat);
  if( iSkip ){

    sqlite3VdbeChangeP2(v, iSkip,
         pSort->labelOBLopt ? pSort->labelOBLopt : sqlite3VdbeCurrentAddr(v));
  }
}

/*
** Add code to implement the OFFSET
*/
static void codeOffset(
................................................................................
      p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
    }
    if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
      sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
    }
    if( sSort.pOrderBy ){
      sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
      sSort.labelOBLopt = sqlite3WhereOrderByLimitOptLabel(pWInfo);
      if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
        sSort.pOrderBy = 0;
      }
    }

    /* If sorting index that was created by a prior OP_OpenEphemeral 
    ** instruction ended up not being needed, then change the OP_OpenEphemeral

Changes to src/sqliteInt.h.

3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
void sqlite3Update(Parse*, SrcList*, ExprList*,Expr*,int,ExprList*,Expr*,
                   Upsert*);
WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
void sqlite3WhereEnd(WhereInfo*);
LogEst sqlite3WhereOutputRowCount(WhereInfo*);
int sqlite3WhereIsDistinct(WhereInfo*);
int sqlite3WhereIsOrdered(WhereInfo*);
int sqlite3WhereOrderedInnerLoop(WhereInfo*);
int sqlite3WhereIsSorted(WhereInfo*);
int sqlite3WhereContinueLabel(WhereInfo*);
int sqlite3WhereBreakLabel(WhereInfo*);
int sqlite3WhereOkOnePass(WhereInfo*, int*);
#define ONEPASS_OFF      0        /* Use of ONEPASS not allowed */
#define ONEPASS_SINGLE   1        /* ONEPASS valid for a single row update */
#define ONEPASS_MULTI    2        /* ONEPASS is valid for multiple rows */







|







3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
void sqlite3Update(Parse*, SrcList*, ExprList*,Expr*,int,ExprList*,Expr*,
                   Upsert*);
WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
void sqlite3WhereEnd(WhereInfo*);
LogEst sqlite3WhereOutputRowCount(WhereInfo*);
int sqlite3WhereIsDistinct(WhereInfo*);
int sqlite3WhereIsOrdered(WhereInfo*);
int sqlite3WhereOrderByLimitOptLabel(WhereInfo*);
int sqlite3WhereIsSorted(WhereInfo*);
int sqlite3WhereContinueLabel(WhereInfo*);
int sqlite3WhereBreakLabel(WhereInfo*);
int sqlite3WhereOkOnePass(WhereInfo*, int*);
#define ONEPASS_OFF      0        /* Use of ONEPASS not allowed */
#define ONEPASS_SINGLE   1        /* ONEPASS valid for a single row update */
#define ONEPASS_MULTI    2        /* ONEPASS is valid for multiple rows */

Changes to src/where.c.

63
64
65
66
67
68
69
70
71




72
73
74
75














76
77

78







79
80
81
82
83
84
85
....
4244
4245
4246
4247
4248
4249
4250

4251
4252
4253
4254
4255
4256
4257
** Return FALSE if the output needs to be sorted.
*/
int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
  return pWInfo->nOBSat;
}

/*
** Return TRUE if the innermost loop of the WHERE clause implementation
** returns rows in ORDER BY order for complete run of the inner loop.




**
** Across multiple iterations of outer loops, the output rows need not be
** sorted.  As long as rows are sorted for just the innermost loop, this
** routine can return TRUE.














*/
int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){

  return pWInfo->bOrderedInnerLoop;







}

/*
** Return the VDBE address or label to jump to in order to continue
** immediately with the next row of a WHERE clause.
*/
int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
    Bitmask notUsed;
    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
                 WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
    if( rc==pWInfo->pResultSet->nExpr ){
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }
  }

  if( pWInfo->pOrderBy ){
    if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
      if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
      }
    }else{
      pWInfo->nOBSat = pFrom->isOrdered;







|
|
>
>
>
>

<
<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|
>
|
>
>
>
>
>
>
>







 







>







63
64
65
66
67
68
69
70
71
72
73
74
75
76



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
....
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
** Return FALSE if the output needs to be sorted.
*/
int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
  return pWInfo->nOBSat;
}

/*
** In the ORDER BY LIMIT optimization, if the inner-most loop is known
** to emit rows in increasing order, and if the last row emitted by the
** inner-most loop did not fit within the sorter, then we can skip all
** subsequent rows for the current iteration of the inner loop (because they
** will not fit in the sorter either) and continue with the second inner
** loop - the loop immediately outside the inner-most.
**



** When a row does not fit in the sorter (because the sorter already
** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
** label returned by this function.
**
** If the ORDER BY LIMIT optimization applies, the jump destination should
** be the continuation for the second-inner-most loop.  If the ORDER BY
** LIMIT optimization does not apply, then the jump destination should
** be the continuation for the inner-most loop.
**
** It is always safe for this routine to return the continuation of the
** inner-most loop, in the sense that a correct answer will result.  
** Returning the continuation the second inner loop is an optimization
** that might make the code run a little faster, but should not change
** the final answer.
*/
int sqlite3WhereOrderByLimitOptLabel(WhereInfo *pWInfo){
  WhereLevel *pInner;
  if( !pWInfo->bOrderedInnerLoop ){
    /* The ORDER BY LIMIT optimization does not apply.  Jump to the 
    ** continuation of the inner-most loop. */
    return pWInfo->iContinue;
  }
  pInner = &pWInfo->a[pWInfo->nLevel-1];
  if( pInner->addrNxt ) return pInner->addrNxt;
  return pInner->addrBrk;
}

/*
** Return the VDBE address or label to jump to in order to continue
** immediately with the next row of a WHERE clause.
*/
int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
    Bitmask notUsed;
    int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
                 WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
    if( rc==pWInfo->pResultSet->nExpr ){
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }
  }
  pWInfo->bOrderedInnerLoop = 0;
  if( pWInfo->pOrderBy ){
    if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
      if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
      }
    }else{
      pWInfo->nOBSat = pFrom->isOrdered;

Changes to test/limit2.test.

162
163
164
165
166
167
168
169















































170
  DROP TABLE IF EXISTS t1;
  CREATE TABLE t1(a, b);  INSERT INTO t1 VALUES(1,2);
  DROP TABLE IF EXISTS t2;
  CREATE TABLE t2(x, y);  INSERT INTO t2 VALUES(1,3);
  CREATE INDEX t1ab ON t1(a,b);
  SELECT y FROM t1, t2 WHERE a=x AND b<=y ORDER BY b DESC;
} {3}
















































finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
  DROP TABLE IF EXISTS t1;
  CREATE TABLE t1(a, b);  INSERT INTO t1 VALUES(1,2);
  DROP TABLE IF EXISTS t2;
  CREATE TABLE t2(x, y);  INSERT INTO t2 VALUES(1,3);
  CREATE INDEX t1ab ON t1(a,b);
  SELECT y FROM t1, t2 WHERE a=x AND b<=y ORDER BY b DESC;
} {3}

# Ticket https://www.sqlite.org/src/info/9936b2fa443fec03 2018-09-08
# Infinite loop due to the ORDER BY LIMIT optimization.
#
do_execsql_test 700 {
  DROP TABLE IF EXISTS t1;
  DROP TABLE IF EXISTS t2;
  CREATE TABLE t1(aa VARCHAR PRIMARY KEY NOT NULL,bb,cc,x VARCHAR(400));
  INSERT INTO t1(aa,bb,cc) VALUES('maroon','meal','lecture');
  INSERT INTO t1(aa,bb,cc) VALUES('reality','meal','catsear');
  CREATE TABLE t2(aa VARCHAR PRIMARY KEY, dd INT DEFAULT 1, ee, x VARCHAR(100));
  INSERT INTO t2(aa,dd,ee) VALUES('maroon',0,'travel'),('reality',0,'hour');
  CREATE INDEX t2x1 ON t2(dd,ee);
  ANALYZE;
  DROP TABLE IF EXISTS sqlite_stat4;
  DELETE FROM sqlite_stat1;
  INSERT INTO sqlite_stat1 VALUES
    ('t2','t2x1','3 3 3'),
    ('t2','sqlite_autoindex_t2_1','3 1'),
    ('t1','sqlite_autoindex_t1_1','2 1');
  ANALYZE sqlite_master;
  SELECT *
    FROM t1 LEFT JOIN t2 ON t1.aa=t2.aa
   WHERE t1.bb='meal'
   ORDER BY t2.dd DESC
   LIMIT 1;
} {maroon meal lecture {} maroon 0 travel {}}
do_execsql_test 710 {
  DROP TABLE t1;
  DROP TABLE t2;
  CREATE TABLE t1(aa, bb);
  INSERT INTO t1 VALUES('maroon','meal');
  CREATE TABLE t2(cc, dd, ee, x VARCHAR(100));
  INSERT INTO t2(cc,dd,ee) VALUES('maroon',1,'one');
  INSERT INTO t2(cc,dd,ee) VALUES('maroon',2,'two');
  INSERT INTO t2(cc,dd,ee) VALUES('maroon',0,'zero');
  CREATE INDEX t2ddee ON t2(dd,ee);
  CREATE INDEX t2cc ON t2(cc);
   ANALYZE;
  SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
  ORDER BY t2.dd LIMIT 1;
} {maroon 0 zero}
do_execsql_test 720 {
  SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
  WHERE t1.bb='meal'
  ORDER BY t2.dd LIMIT 1;
} {maroon 0 zero}

finish_test