/ Check-in [71bf91c2]
Login

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

Overview
Comment:When processing an "ORDER BY ... LIMIT" that does not use an index, check whether or not a record may appear in the final result set before adding it to the sorter.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sorter-limit-opt
Files: files | file ages | folders
SHA3-256:71bf91c218334381b1b4bdba6a093e623b62e17f3e8550e154a11f0cb0b404f3
User & Date: dan 2018-04-26 16:13:47
Context
2018-04-26
17:43
When processing an "ORDER BY ... LIMIT" that does not use an index, check whether or not a record may appear in the final result set before adding it to the temp b-tree used for sorting. check-in: 0fcfc36c user: dan tags: trunk
16:13
When processing an "ORDER BY ... LIMIT" that does not use an index, check whether or not a record may appear in the final result set before adding it to the sorter. Closed-Leaf check-in: 71bf91c2 user: dan tags: sorter-limit-opt
15:04
Clarification of the behavior of a BEFORE UPDATE trigger when the trigger changes the values of some of the columns used to compute new columns in the UPDATE. check-in: 7bb23c2a user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590

591
592
593
594
595
596
597
...
617
618
619
620
621
622
623





























624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
                          SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
  if( bSeq ){
    sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
  }
  if( nPrefixReg==0 && nData>0 ){
    sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
  }
  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
  if( nOBSat>0 ){
    int regPrevKey;   /* The first nOBSat columns of the previous row */
    int addrFirst;    /* Address of the OP_IfNot opcode */
    int addrJmp;      /* Address of the OP_Jump opcode */
    VdbeOp *pOp;      /* Opcode that opens the sorter */
    int nKey;         /* Number of sorting key columns, including OP_Sequence */
    KeyInfo *pKI;     /* Original KeyInfo on the sorter table */


    regPrevKey = pParse->nMem+1;
    pParse->nMem += pSort->nOBSat;
    nKey = nExpr - pSort->nOBSat + bSeq;
    if( bSeq ){
      addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); 
    }else{
      addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);
................................................................................
      sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);
      VdbeCoverage(v);
    }
    sqlite3VdbeJumpHere(v, addrFirst);
    sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);
    sqlite3VdbeJumpHere(v, addrJmp);
  }





























  if( pSort->sortFlags & SORTFLAG_UseSorter ){
    op = OP_SorterInsert;
  }else{
    op = OP_IdxInsert;
  }
  sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
                       regBase+nOBSat, nBase-nOBSat);
  if( iLimit ){
    int addr;
    int r1 = 0;
    /* Fill the sorter until it contains LIMIT+OFFSET entries.  (The iLimit
    ** register is initialized with value of LIMIT+OFFSET.)  After the sorter
    ** fills up, delete the least entry in the sorter after each insert.
    ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
    addr = sqlite3VdbeAddOp1(v, OP_IfNotZero, iLimit); VdbeCoverage(v);
    sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
    if( pSort->bOrderedInnerLoop ){
      r1 = ++pParse->nMem;
      sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1);
      VdbeComment((v, "seq"));
    }
    sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
    if( pSort->bOrderedInnerLoop ){
      /* If the inner loop is driven by an index such that values from
      ** the same iteration of the inner loop are in sorted order, then
      ** immediately jump to the next iteration of an inner loop if the
      ** entry from the current iteration does not fit into the top
      ** LIMIT+OFFSET entries of the sorter. */
      int iBrk = sqlite3VdbeCurrentAddr(v) + 2;
      sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1);
      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
      VdbeCoverage(v);
    }
    sqlite3VdbeJumpHere(v, addr);
  }
}

/*
** Add code to implement the OFFSET
*/
static void codeOffset(
  Vdbe *v,          /* Generate code into this VM */







<








>







 







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







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







575
576
577
578
579
580
581

582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
...
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659




























660
661
662
663
664
665
666
                          SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
  if( bSeq ){
    sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
  }
  if( nPrefixReg==0 && nData>0 ){
    sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
  }

  if( nOBSat>0 ){
    int regPrevKey;   /* The first nOBSat columns of the previous row */
    int addrFirst;    /* Address of the OP_IfNot opcode */
    int addrJmp;      /* Address of the OP_Jump opcode */
    VdbeOp *pOp;      /* Opcode that opens the sorter */
    int nKey;         /* Number of sorting key columns, including OP_Sequence */
    KeyInfo *pKI;     /* Original KeyInfo on the sorter table */

    sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat,regRecord);
    regPrevKey = pParse->nMem+1;
    pParse->nMem += pSort->nOBSat;
    nKey = nExpr - pSort->nOBSat + bSeq;
    if( bSeq ){
      addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); 
    }else{
      addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);
................................................................................
      sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);
      VdbeCoverage(v);
    }
    sqlite3VdbeJumpHere(v, addrFirst);
    sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);
    sqlite3VdbeJumpHere(v, addrJmp);
  }
  if( iLimit ){
    /* At this point the values for the new sorter entry are stored
    ** in an array of registers. They need to be composed into a record
    ** and inserted into the sorter if either (a) there are currently
    ** 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;
    int iJmp = sqlite3VdbeCurrentAddr(v)+5+(nOBSat<=0)+pSort->bOrderedInnerLoop;
    assert( pSort->bOrderedInnerLoop==0 || pSort->bOrderedInnerLoop==1 );
    sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);
    VdbeCoverage(v);
    sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);
    sqlite3VdbeAddOp4Int(v, OP_IdxLE, iCsr, iJmp, regBase+nOBSat, nExpr-nOBSat);
    VdbeCoverage(v);
    sqlite3VdbeAddOp1(v, OP_Delete, iCsr);
  }
  if( nOBSat<=0 ){
    sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat,regRecord);
  }
  if( pSort->sortFlags & SORTFLAG_UseSorter ){
    op = OP_SorterInsert;
  }else{
    op = OP_IdxInsert;
  }
  sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
                       regBase+nOBSat, nBase-nOBSat);




























}

/*
** Add code to implement the OFFSET
*/
static void codeOffset(
  Vdbe *v,          /* Generate code into this VM */