/ Check-in [81069d71]
Login

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

Overview
Comment:Add support for using indexes for some ORDER BY clauses that use non-default NULL handling. Still some problems on this branch.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nulls-last
Files: files | file ages | folders
SHA3-256: 81069d7196857e909c94195d67388f71bc9f832eafd9156d8c5cdddb63513b4a
User & Date: dan 2019-08-16 21:07:19
Context
2019-08-17
15:47
Merge trunk changes into this branch. check-in: db1e6080 user: dan tags: nulls-last
2019-08-16
21:07
Add support for using indexes for some ORDER BY clauses that use non-default NULL handling. Still some problems on this branch. check-in: 81069d71 user: dan tags: nulls-last
2019-08-12
16:36
Experimental implementation of NULLS FIRST/LAST. This branch still has problems - the most significant of which is that ORDER BY clauses with a non-default NULLS FIRST/LAST qualifier can never use an index. check-in: 07babb0f user: dan tags: nulls-last
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
....
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855


3856
3857
3858
3859
3860







3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
....
5057
5058
5059
5060
5061
5062
5063

5064
5065
5066
5067
5068
5069
5070
....
5198
5199
5200
5201
5202
5203
5204











5205
5206
5207
5208
5209
5210
5211
        }

        /* Get the column number in the table (iColumn) and sort order
        ** (revIdx) for the j-th column of the index.
        */
        if( pIndex ){
          iColumn = pIndex->aiColumn[j];
          revIdx = pIndex->aSortOrder[j];
          if( iColumn==pIndex->pTable->iPKey ) iColumn = XN_ROWID;
        }else{
          iColumn = XN_ROWID;
          revIdx = 0;
        }

        /* An unconstrained column that might be NULL means that this
................................................................................
            if( pOBExpr->iColumn!=iColumn ) continue;
          }else{
            Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr;
            if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){
              continue;
            }
          }
          if( pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL ) continue;
          if( iColumn!=XN_ROWID ){
            pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
          }
          if( wctrlFlags & WHERE_DISTINCTBY ){
            pLoop->u.btree.nDistinctCol = j+1;
          }
          isMatch = 1;
          break;
        }
        if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){
          /* Make sure the sort order is compatible in an ORDER BY clause.
          ** Sort order is irrelevant for a GROUP BY clause. */
          assert( (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL)==0 );
          if( revSet ){
            if( (rev ^ revIdx)!=pOrderBy->a[i].sortFlags ) isMatch = 0;


          }else{
            rev = revIdx ^ pOrderBy->a[i].sortFlags;
            if( rev ) *pRevMask |= MASKBIT(iLoop);
            revSet = 1;
          }







        }
        if( isMatch ){
          if( iColumn==XN_ROWID ){
            testcase( distinctColumns==0 );
            distinctColumns = 1;
          }
          obSat |= MASKBIT(i);
          if( (wctrlFlags & WHERE_ORDERBY_MIN) && j==pLoop->u.btree.nEq ){
            pLoop->wsFlags |= WHERE_MIN_ORDERED;
          }
        }else{
          /* No match found */
          if( j==0 || j<nKeyCol ){
            testcase( isOrderDistinct!=0 );
            isOrderDistinct = 0;
          }
          break;
................................................................................
      assert( pIx->pSchema==pTab->pSchema );
      assert( iIndexCur>=0 );
      if( op ){
        sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb);
        sqlite3VdbeSetP4KeyInfo(pParse, pIx);
        if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0
         && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0

         && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0
         && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED
        ){
          sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */
        }
        VdbeComment((v, "%s", pIx->zName));
#ifdef SQLITE_ENABLE_COLUMN_USED_MASK
................................................................................
      sqlite3VdbeResolveLabel(v, pLevel->addrCont);
      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
      sqlite3VdbeChangeP5(v, pLevel->p5);
      VdbeCoverage(v);
      VdbeCoverageIf(v, pLevel->op==OP_Next);
      VdbeCoverageIf(v, pLevel->op==OP_Prev);
      VdbeCoverageIf(v, pLevel->op==OP_VNext);











#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
      if( addrSeek ) sqlite3VdbeJumpHere(v, addrSeek);
#endif
    }else{
      sqlite3VdbeResolveLabel(v, pLevel->addrCont);
    }
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){







|







 







<













<

|
>
>

|



>
>
>
>
>
>
>







<
<
<







 







>







 







>
>
>
>
>
>
>
>
>
>
>







3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
....
3832
3833
3834
3835
3836
3837
3838

3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851

3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874



3875
3876
3877
3878
3879
3880
3881
....
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
....
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
        }

        /* Get the column number in the table (iColumn) and sort order
        ** (revIdx) for the j-th column of the index.
        */
        if( pIndex ){
          iColumn = pIndex->aiColumn[j];
          revIdx = pIndex->aSortOrder[j] & KEYINFO_ORDER_DESC;
          if( iColumn==pIndex->pTable->iPKey ) iColumn = XN_ROWID;
        }else{
          iColumn = XN_ROWID;
          revIdx = 0;
        }

        /* An unconstrained column that might be NULL means that this
................................................................................
            if( pOBExpr->iColumn!=iColumn ) continue;
          }else{
            Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr;
            if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){
              continue;
            }
          }

          if( iColumn!=XN_ROWID ){
            pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
          }
          if( wctrlFlags & WHERE_DISTINCTBY ){
            pLoop->u.btree.nDistinctCol = j+1;
          }
          isMatch = 1;
          break;
        }
        if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){
          /* Make sure the sort order is compatible in an ORDER BY clause.
          ** Sort order is irrelevant for a GROUP BY clause. */

          if( revSet ){
            if( (rev ^ revIdx)!=(pOrderBy->a[i].sortFlags&KEYINFO_ORDER_DESC) ){
              isMatch = 0;
            }
          }else{
            rev = revIdx ^ (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC);
            if( rev ) *pRevMask |= MASKBIT(iLoop);
            revSet = 1;
          }
        }
        if( isMatch && (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL) ){
          if( j==pLoop->u.btree.nEq ){
            pLoop->wsFlags |= WHERE_BIGNULL_SORT;
          }else{
            isMatch = 0;
          }
        }
        if( isMatch ){
          if( iColumn==XN_ROWID ){
            testcase( distinctColumns==0 );
            distinctColumns = 1;
          }
          obSat |= MASKBIT(i);



        }else{
          /* No match found */
          if( j==0 || j<nKeyCol ){
            testcase( isOrderDistinct!=0 );
            isOrderDistinct = 0;
          }
          break;
................................................................................
      assert( pIx->pSchema==pTab->pSchema );
      assert( iIndexCur>=0 );
      if( op ){
        sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb);
        sqlite3VdbeSetP4KeyInfo(pParse, pIx);
        if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0
         && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0
         && (pLoop->wsFlags & WHERE_BIGNULL_SORT)==0
         && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0
         && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED
        ){
          sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */
        }
        VdbeComment((v, "%s", pIx->zName));
#ifdef SQLITE_ENABLE_COLUMN_USED_MASK
................................................................................
      sqlite3VdbeResolveLabel(v, pLevel->addrCont);
      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
      sqlite3VdbeChangeP5(v, pLevel->p5);
      VdbeCoverage(v);
      VdbeCoverageIf(v, pLevel->op==OP_Next);
      VdbeCoverageIf(v, pLevel->op==OP_Prev);
      VdbeCoverageIf(v, pLevel->op==OP_VNext);
      if( pLevel->regBignull ){
        sqlite3VdbeResolveLabel(v, pLevel->addrBignull);
        addr = sqlite3VdbeAddOp1(v, OP_If, pLevel->regBignull);
        sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->regBignull);
        sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->p2-1);
        sqlite3VdbeChangeP5(v, pLevel->p5);
        VdbeCoverage(v);
        VdbeCoverageIf(v, pLevel->op==OP_Next);
        VdbeCoverageIf(v, pLevel->op==OP_Prev);
        sqlite3VdbeJumpHere(v, addr);
      }
#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
      if( addrSeek ) sqlite3VdbeJumpHere(v, addrSeek);
#endif
    }else{
      sqlite3VdbeResolveLabel(v, pLevel->addrCont);
    }
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){

Changes to src/whereInt.h.

67
68
69
70
71
72
73


74
75
76
77
78
79
80
81
82
83
84
85
86
87
...
582
583
584
585
586
587
588
589
590
591
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */


#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  u32 iLikeRepCntr;     /* LIKE range processing counter register (times 2) */
  int addrLikeRep;      /* LIKE range processing address */
#endif
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        int iBase;             /* Base register of multi-key index record */
................................................................................
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
#define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
#define WHERE_PARTIALIDX   0x00020000  /* The automatic index is partial */
#define WHERE_IN_EARLYOUT  0x00040000  /* Perhaps quit IN loops early */
#define WHERE_MIN_ORDERED  0x00080000  /* Column nEq of index is min() expr */

#endif /* !defined(SQLITE_WHEREINT_H) */







>
>






|







 







|


67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
...
584
585
586
587
588
589
590
591
592
593
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
  int regBignull;       /* big-null flag register */
  int addrBignull;      /* Jump here for next part of big-null scan */
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  u32 iLikeRepCntr;     /* LIKE range processing counter register (times 2) */
  int addrLikeRep;      /* LIKE range processing address */
#endif
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to end the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        int iBase;             /* Base register of multi-key index record */
................................................................................
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
#define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
#define WHERE_PARTIALIDX   0x00020000  /* The automatic index is partial */
#define WHERE_IN_EARLYOUT  0x00040000  /* Perhaps quit IN loops early */
#define WHERE_BIGNULL_SORT 0x00080000  /* Column nEq of index is BIGNULL */

#endif /* !defined(SQLITE_WHEREINT_H) */

Changes to src/wherecode.c.

1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
....
1609
1610
1611
1612
1613
1614
1615




















1616
1617
1618
1619
1620
1621
1622
....
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
....
1670
1671
1672
1673
1674
1675
1676




1677
1678
1679
1680
1681
1682
1683
1684
1685
1686




1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708


1709
1710



1711
1712
1713
1714

1715
1716
1717
1718
1719
1720
1721
....
1740
1741
1742
1743
1744
1745
1746

1747
1748

1749
1750
1751
1752
1753
1754
1755
1756
1757
1758



1759
1760
1761
1762
1763
1764










1765
1766
1767
1768
1769
1770
1771
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff = 0;           /* Affinity for end of range constraint */
    u8 bSeekPastNull = 0;        /* True to seek past initial nulls */
    u8 bStopAtNull = 0;          /* Add condition to terminate at NULLs */
    int omitTable;               /* True if we use the index only */


    pIdx = pLoop->u.btree.pIndex;
    iIdxCur = pLevel->iIdxCur;
    assert( nEq>=pLoop->nSkip );

    /* If this loop satisfies a sort order (pOrderBy) request that 
    ** was passed to this function to implement a "SELECT min(x) ..." 
    ** query, then the caller will only allow the loop to run for
    ** a single iteration. This means that the first row returned
    ** should not have a NULL value stored in 'x'. If column 'x' is
    ** the first one after the nEq equality constraints in the index,
    ** this requires some special handling.
    */
    assert( (pWInfo->pOrderBy!=0 && pWInfo->pOrderBy->nExpr==1)
         || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 );
    if( pLoop->wsFlags & WHERE_MIN_ORDERED ){
      assert( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN) );
      assert( pWInfo->nOBSat );
      assert( pIdx->nColumn>nEq );
      assert( pLoop->nSkip==0 );
      bSeekPastNull = 1;
      nExtraReg = 1;
    }

    /* Find any inequality constraint terms for the start and end 
    ** of the range. 
    */
    j = nEq;
    if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
      pRangeStart = pLoop->aLTerm[j++];
      nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm);
................................................................................
        j = pIdx->aiColumn[nEq];
        if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){
          bSeekPastNull = 1;
        }
      }
    }
    assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );





















    /* If we are doing a reverse order scan on an ascending index, or
    ** a forward order scan on a descending index, interchange the 
    ** start and end terms (pRangeStart and pRangeEnd).
    */
    if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
     || (bRev && pIdx->nKeyCol==nEq)
................................................................................
    */
    codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
    regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
    assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
    if( zStartAff && nTop ){
      zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]);
    }
    addrNxt = pLevel->addrNxt;

    testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
    testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
    testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
    testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
    startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
    endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
................................................................................
      }
      bSeekPastNull = 0;
    }else if( bSeekPastNull ){
      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
      nConstraint++;
      startEq = 0;
      start_constraints = 1;




    }
    codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
    if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
      /* The skip-scan logic inside the call to codeAllEqualityConstraints()
      ** above has already left the cursor sitting on the correct row,
      ** so no further seeking is needed */
    }else{
      if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
        sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
      }




      op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
      assert( op!=0 );
      sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
      VdbeCoverage(v);
      VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
      VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
      VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
      VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
      VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );
      VdbeCoverageIf(v, op==OP_SeekLT);  testcase( op==OP_SeekLT );

      if( bSeekPastNull && (pLoop->wsFlags & WHERE_TOP_LIMIT)==0 ){
        /* If bSeekPastNull is set only to skip past the NULL values for
        ** a query like "SELECT min(a), b FROM t1", then add code so that
        ** if there are no rows with (a IS NOT NULL), then do the seek 
        ** without jumping past NULLs instead. This allows the code in 
        ** select.c to pick a value for "b" in the above query.  */
        assert( startEq==0 && (op==OP_SeekGT || op==OP_SeekLT) );
        assert( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0 && pWInfo->nOBSat>0 );
        sqlite3VdbeChangeP2(v, -1, sqlite3VdbeCurrentAddr(v)+1);
        sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);



        op = aStartOp[(start_constraints<<2) + (1<<1) + bRev];
        assert( op==OP_SeekGE || op==OP_SeekLE );



        sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
        VdbeCoverage(v);
        VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
        VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );

      }
    }

    /* Load the value for the inequality constraint at the end of the
    ** range (if any).
    */
    nConstraint = nEq;
................................................................................

      if( sqlite3ExprIsVector(pRight)==0 ){
        disableTerm(pLevel, pRangeEnd);
      }else{
        endEq = 1;
      }
    }else if( bStopAtNull ){

      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
      endEq = 0;

      nConstraint++;
    }
    sqlite3DbFree(db, zStartAff);
    sqlite3DbFree(db, zEndAff);

    /* Top of the loop body */
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);

    /* Check if the index cursor is past the end of the range. */
    if( nConstraint ){



      op = aEndOp[bRev*2 + endEq];
      sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
      testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
      testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
      testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
      testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );










    }

    if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
      sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
    }

    /* Seek the table cursor, if required */







|





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







 







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







 







<







 







>
>
>
>










>
>
>
>











|
<
<
<
<
<
<
<
<

<
>
>
|
<
>
>
>
|
<
<
<
>







 







>
|
|
>










>
>
>






>
>
>
>
>
>
>
>
>
>







1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557



















1558
1559
1560
1561
1562
1563
1564
....
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
....
1633
1634
1635
1636
1637
1638
1639

1640
1641
1642
1643
1644
1645
1646
....
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706








1707

1708
1709
1710

1711
1712
1713
1714



1715
1716
1717
1718
1719
1720
1721
1722
....
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff = 0;           /* Affinity for end of range constraint */
    u8 bSeekPastNull = 0;        /* True to seek past initial nulls */
    u8 bStopAtNull = 0;          /* Add condition to terminate at NULLs */
    int omitTable;               /* True if we use the index only */
    int regBignull = 0;

    pIdx = pLoop->u.btree.pIndex;
    iIdxCur = pLevel->iIdxCur;
    assert( nEq>=pLoop->nSkip );




















    /* Find any inequality constraint terms for the start and end 
    ** of the range. 
    */
    j = nEq;
    if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
      pRangeStart = pLoop->aLTerm[j++];
      nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm);
................................................................................
        j = pIdx->aiColumn[nEq];
        if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){
          bSeekPastNull = 1;
        }
      }
    }
    assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );

    /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
    ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS 
    ** FIRST). In both cases separate ordered scans are made of those
    ** index entries for which the column is null and for those for which
    ** it is not. For an ASC sort, the non-NULL entries are scanned first.
    ** For DESC, NULL entries are scanned first.
    */
    addrNxt = pLevel->addrNxt;
    if( (pLoop->wsFlags & (WHERE_TOP_LIMIT|WHERE_BTM_LIMIT))==0
     && (pLoop->wsFlags & WHERE_BIGNULL_SORT)!=0
    ){
      assert( bSeekPastNull==0 && nExtraReg==0 && nBtm==0 && nTop==0 );
      assert( pRangeEnd==0 && pRangeStart==0 );
      assert( pLoop->nSkip==0 );
      nExtraReg = 1;
      bSeekPastNull = 1;
      pLevel->regBignull = regBignull = ++pParse->nMem;
      addrNxt = pLevel->addrBignull = sqlite3VdbeMakeLabel(pParse);
    }

    /* If we are doing a reverse order scan on an ascending index, or
    ** a forward order scan on a descending index, interchange the 
    ** start and end terms (pRangeStart and pRangeEnd).
    */
    if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
     || (bRev && pIdx->nKeyCol==nEq)
................................................................................
    */
    codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
    regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
    assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
    if( zStartAff && nTop ){
      zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]);
    }


    testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
    testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
    testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
    testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
    startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
    endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
................................................................................
      }
      bSeekPastNull = 0;
    }else if( bSeekPastNull ){
      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
      nConstraint++;
      startEq = 0;
      start_constraints = 1;
    }else if( regBignull ){
      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
      start_constraints = 1;
      nConstraint++;
    }
    codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
    if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
      /* The skip-scan logic inside the call to codeAllEqualityConstraints()
      ** above has already left the cursor sitting on the correct row,
      ** so no further seeking is needed */
    }else{
      if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
        sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
      }
      if( regBignull ){
        sqlite3VdbeAddOp2(v, OP_Integer, 0, regBignull);
      }

      op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
      assert( op!=0 );
      sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
      VdbeCoverage(v);
      VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
      VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
      VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
      VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
      VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );
      VdbeCoverageIf(v, op==OP_SeekLT);  testcase( op==OP_SeekLT );

      if( regBignull ){








        sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);

        if( bStopAtNull ){
          start_constraints = (nConstraint>1);
          op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];

          sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint-1);
        }else{
          op = aStartOp[(start_constraints<<2) + ((!startEq)<<1) + bRev];
          sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);



        }
      }
    }

    /* Load the value for the inequality constraint at the end of the
    ** range (if any).
    */
    nConstraint = nEq;
................................................................................

      if( sqlite3ExprIsVector(pRight)==0 ){
        disableTerm(pLevel, pRangeEnd);
      }else{
        endEq = 1;
      }
    }else if( bStopAtNull ){
      if( regBignull==0 ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
        endEq = 0;
      }
      nConstraint++;
    }
    sqlite3DbFree(db, zStartAff);
    sqlite3DbFree(db, zEndAff);

    /* Top of the loop body */
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);

    /* Check if the index cursor is past the end of the range. */
    if( nConstraint ){
      if( regBignull ){
        sqlite3VdbeAddOp2(v, OP_If, regBignull, sqlite3VdbeCurrentAddr(v)+3);
      }
      op = aEndOp[bRev*2 + endEq];
      sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
      testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
      testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
      testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
      testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
    }
    if( regBignull ){
      sqlite3VdbeAddOp2(v, OP_IfNot, regBignull, sqlite3VdbeCurrentAddr(v)+2);
      if( bStopAtNull ){
        op = aEndOp[bRev*2 + 0];
        sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
      }else{
        op = aEndOp[bRev*2 + endEq];
        sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint+1);
      }
    }

    if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
      sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
    }

    /* Seek the table cursor, if required */

Changes to test/nulls1.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20


21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
..
43
44
45
46
47
48
49


50
51


52
































53
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#

####################################################
# DO NOT EDIT! THIS FILE IS AUTOMATICALLY GENERATED!
####################################################

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix nulls1



do_execsql_test 1.0 {
  DROP TABLE IF EXISTS t3;
  CREATE TABLE t3(a INTEGER);
  INSERT INTO t3 VALUES(NULL), (10), (30), (20), (NULL);
} {}

for {set a 0} {$a < 2} {incr a} {
  foreach {tn limit} {
    1 ""
    2 "LIMIT 10"
  } {
    do_execsql_test 1.$a.$tn.1 "
      SELECT a FROM t3 ORDER BY a nULLS FIRST $limit
    " {{}   {}   10   20   30}
................................................................................
    " {{}   {}   30   20   10}
    
    do_execsql_test 1.$a.$tn.4 "
      SELECT a FROM t3 ORDER BY a DESC nULLS LAST $limit
    " {30   20   10   {}   {}}
  }



  catchsql { CREATE INDEX i1 ON t3(a) }
}



































finish_test







<
<
<
<



>
>







|







 







>
>
|
|
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

7
8
9
10
11
12
13




14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#





set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix nulls1

if 1 {

do_execsql_test 1.0 {
  DROP TABLE IF EXISTS t3;
  CREATE TABLE t3(a INTEGER);
  INSERT INTO t3 VALUES(NULL), (10), (30), (20), (NULL);
} {}

for {set a 0} {$a < 3} {incr a} {
  foreach {tn limit} {
    1 ""
    2 "LIMIT 10"
  } {
    do_execsql_test 1.$a.$tn.1 "
      SELECT a FROM t3 ORDER BY a nULLS FIRST $limit
    " {{}   {}   10   20   30}
................................................................................
    " {{}   {}   30   20   10}
    
    do_execsql_test 1.$a.$tn.4 "
      SELECT a FROM t3 ORDER BY a DESC nULLS LAST $limit
    " {30   20   10   {}   {}}
  }

  switch $a {
    0 {
      execsql { CREATE INDEX i1 ON t3(a) }
    }
    1 {
      execsql { DROP INDEX i1 ; CREATE INDEX i1 ON t3(a DESC) }
    }
  }
}

}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 2.0 {
  CREATE TABLE t2(a, b, c);
  CREATE INDEX i2 ON t2(a, b);
  INSERT INTO t2 VALUES(1, 1, 1);
  INSERT INTO t2 VALUES(1, NULL, 2);
  INSERT INTO t2 VALUES(1, NULL, 3);
  INSERT INTO t2 VALUES(1, 4, 4);
}

do_execsql_test 2.1 {
  SELECT * FROM t2 WHERE a=1 ORDER BY b NULLS LAST
} {
  1 1 1    1 4 4   1 {} 2   1 {} 3
}

do_execsql_test 2.2 {
  SELECT * FROM t2 WHERE a=1 ORDER BY b DESC NULLS FIRST
} {
  1 {} 3
  1 {} 2     
  1 4 4     
  1 1 1
}


finish_test