SQLite

Check-in [997ce6c90b]
Login

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

Overview
Comment:Improvements and simplifications to the equality seek logic. Tests are adjusted so that they all pass now.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | seekeq-experiment
Files: files | file ages | folders
SHA1: 997ce6c90b454c03cc2ef6934752ee8dd2e520e3
User & Date: drh 2015-11-05 22:30:54.990
Context
2015-11-06
20:22
Avoid an unnecessary key comparison when doing an indexed lookup against an equality constraint. (check-in: d741e1ccdc user: drh tags: trunk)
2015-11-05
22:30
Improvements and simplifications to the equality seek logic. Tests are adjusted so that they all pass now. (Closed-Leaf check-in: 997ce6c90b user: drh tags: seekeq-experiment)
20:25
The top of an index equality loop normally starts with OP_SeekGE and OP_IdxGT. This check-in adds a flag to OP_SeekGE such that it fails immediately if the key is not equal, then jumps over the OP_IdxGT, saving a call to the key comparison functions. Consider this check-in a proof-of-concept. It needs improvement before going on trunk. Some tests fail, but only because they new use fewer key comparisons than expected (which is a good thing!). (check-in: 32e31b9bc8 user: drh tags: seekeq-experiment)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
5037
5038
5039
5040
5041
5042
5043


5044
5045
5046
5047
5048
5049
5050
**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches intKey/pIdxKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than intKey/pIdxKey.
**


*/
int sqlite3BtreeMovetoUnpacked(
  BtCursor *pCur,          /* The cursor to be moved */
  UnpackedRecord *pIdxKey, /* Unpacked index key */
  i64 intKey,              /* The table key */
  int biasRight,           /* If true, bias the search to the high end */
  int *pRes                /* Write search results here */







>
>







5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches intKey/pIdxKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than intKey/pIdxKey.
**
** For index tables, the pIdxKey->eqSeen field is set to 1 if there
** exists an entry in the table that exactly matches pIdxKey.  
*/
int sqlite3BtreeMovetoUnpacked(
  BtCursor *pCur,          /* The cursor to be moved */
  UnpackedRecord *pIdxKey, /* Unpacked index key */
  i64 intKey,              /* The table key */
  int biasRight,           /* If true, bias the search to the high end */
  int *pRes                /* Write search results here */
9640
9641
9642
9643
9644
9645
9646
9647
9648
9649
9650
9651
9652
9653
9654
9655
9656
9657
9658
9659
9660
9661
9662
9663
9664
9665
9666
9667
    }
  }

  pBt->btsFlags &= ~BTS_NO_WAL;
  return rc;
}

#ifdef SQLITE_DEBUG
/*
** Return true if the cursor has a hint specified.  This routine is
** only used from within assert() statements
*/
int sqlite3BtreeCursorHasHint(BtCursor *pCsr, unsigned int mask){
  return (pCsr->hints & mask)!=0;
}
#endif

/*
** Return true if the given Btree is read-only.
*/
int sqlite3BtreeIsReadonly(Btree *p){
  return (p->pBt->btsFlags & BTS_READ_ONLY)!=0;
}

/*
** Return the size of the header added to each page by this module.
*/
int sqlite3HeaderSizeBtree(void){ return ROUND8(sizeof(MemPage)); }







<







<












9642
9643
9644
9645
9646
9647
9648

9649
9650
9651
9652
9653
9654
9655

9656
9657
9658
9659
9660
9661
9662
9663
9664
9665
9666
9667
    }
  }

  pBt->btsFlags &= ~BTS_NO_WAL;
  return rc;
}


/*
** Return true if the cursor has a hint specified.  This routine is
** only used from within assert() statements
*/
int sqlite3BtreeCursorHasHint(BtCursor *pCsr, unsigned int mask){
  return (pCsr->hints & mask)!=0;
}


/*
** Return true if the given Btree is read-only.
*/
int sqlite3BtreeIsReadonly(Btree *p){
  return (p->pBt->btsFlags & BTS_READ_ONLY)!=0;
}

/*
** Return the size of the header added to each page by this module.
*/
int sqlite3HeaderSizeBtree(void){ return ROUND8(sizeof(MemPage)); }
Changes to src/btree.h.
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot, int, int*);
struct Pager *sqlite3BtreePager(Btree*);

int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
void sqlite3BtreeIncrblobCursor(BtCursor *);
void sqlite3BtreeClearCursor(BtCursor *);
int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);
#ifdef SQLITE_DEBUG
int sqlite3BtreeCursorHasHint(BtCursor*, unsigned int mask);
#endif
int sqlite3BtreeIsReadonly(Btree *pBt);
int sqlite3HeaderSizeBtree(void);

#ifndef NDEBUG
int sqlite3BtreeCursorIsValid(BtCursor*);
#endif








<

<







253
254
255
256
257
258
259

260

261
262
263
264
265
266
267
char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot, int, int*);
struct Pager *sqlite3BtreePager(Btree*);

int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
void sqlite3BtreeIncrblobCursor(BtCursor *);
void sqlite3BtreeClearCursor(BtCursor *);
int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);

int sqlite3BtreeCursorHasHint(BtCursor*, unsigned int mask);

int sqlite3BtreeIsReadonly(Btree *pBt);
int sqlite3HeaderSizeBtree(void);

#ifndef NDEBUG
int sqlite3BtreeCursorIsValid(BtCursor*);
#endif

Changes to src/sqliteInt.h.
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825



1826
1827
1828











1829





1830
1831
1832
1833
1834
1835
1836
  u16 nXField;        /* Number of columns beyond the key columns */
  sqlite3 *db;        /* The database connection */
  u8 *aSortOrder;     /* Sort order for each column. */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** An instance of the following structure holds information about a
** single index record that has already been parsed out into individual
** values.
**
** A record is an object that contains one or more fields of data.
** Records are used to store the content of a table row and to store
** the key of an index.  A blob encoding of a record is created by
** the OP_MakeRecord opcode of the VDBE and is disassembled by the
** OP_Column opcode.
**
** This structure holds a record that has already been disassembled



** into its constituent fields.
**
** The r1 and r2 member variables are only used by the optimized comparison











** functions vdbeRecordCompareInt() and vdbeRecordCompareString().





*/
struct UnpackedRecord {
  KeyInfo *pKeyInfo;  /* Collation and sort-order information */
  Mem *aMem;          /* Values */
  u16 nField;         /* Number of entries in apMem[] */
  i8 default_rc;      /* Comparison result if keys are equal */
  u8 errCode;         /* Error detected by xRecordCompare (CORRUPT or NOMEM) */







<
|
|







|
>
>
>
|

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







1808
1809
1810
1811
1812
1813
1814

1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
  u16 nXField;        /* Number of columns beyond the key columns */
  sqlite3 *db;        /* The database connection */
  u8 *aSortOrder;     /* Sort order for each column. */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*

** This object holds a record which has been parsed out into individual
** fields, for the purposes of doing a comparison.
**
** A record is an object that contains one or more fields of data.
** Records are used to store the content of a table row and to store
** the key of an index.  A blob encoding of a record is created by
** the OP_MakeRecord opcode of the VDBE and is disassembled by the
** OP_Column opcode.
**
** An instance of this object serves as a "key" for doing a search on
** an index b+tree. The goal of the search is to find the entry that
** is closed to the key described by this object.  This object might hold
** just a prefix of the key.  The number of fields is given by
** pKeyInfo->nField.
**
** The r1 and r2 fields are the values to return if this key is less than
** or greater than a key in the btree, respectively.  These are normally
** -1 and +1 respectively, but might be inverted to +1 and -1 if the b-tree
** is in DESC order.
**
** The key comparison functions actually return default_rc when they find
** an equals comparison.  default_rc can be -1, 0, or +1.  If there are
** multiple entries in the b-tree with the same key (when only looking
** at the first pKeyInfo->nFields,) then default_rc can be set to -1 to 
** cause the search to find the last match, or +1 to cause the search to
** find the first match.
**
** The key comparison functions will set eqSeen to true if they ever
** get and equal results when comparing this structure to a b-tree record.
** When default_rc!=0, the search might end up on the record immediately
** before the first match or immediately after the last match.  The
** eqSeen field will indicate whether or not an exact match exists in the
** b-tree.
*/
struct UnpackedRecord {
  KeyInfo *pKeyInfo;  /* Collation and sort-order information */
  Mem *aMem;          /* Values */
  u16 nField;         /* Number of entries in apMem[] */
  i8 default_rc;      /* Comparison result if keys are equal */
  u8 errCode;         /* Error detected by xRecordCompare (CORRUPT or NOMEM) */
Changes to src/vdbe.c.
3592
3593
3594
3595
3596
3597
3598







3599
3600
3601
3602
3603
3604
3605
** use the value in register P3 as the key.  If cursor P1 refers 
** to an SQL index, then P3 is the first in an array of P4 registers 
** that are used as an unpacked index key. 
**
** Reposition cursor P1 so that  it points to the smallest entry that 
** is greater than or equal to the key value. If there are no records 
** greater than or equal to the key and P2 is not zero, then jump to P2.







**
** This opcode leaves the cursor configured to move in forward order,
** from the beginning toward the end.  In other words, the cursor is
** configured to use Next, not Prev.
**
** See also: Found, NotFound, SeekLt, SeekGt, SeekLe
*/







>
>
>
>
>
>
>







3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
** use the value in register P3 as the key.  If cursor P1 refers 
** to an SQL index, then P3 is the first in an array of P4 registers 
** that are used as an unpacked index key. 
**
** Reposition cursor P1 so that  it points to the smallest entry that 
** is greater than or equal to the key value. If there are no records 
** greater than or equal to the key and P2 is not zero, then jump to P2.
**
** If the cursor P1 was opened using the OPFLAG_SEEKEQ flag, then this
** opcode will always land on a record that equally equals the key, or
** else jump immediately to P2.  When the cursor is OPFLAG_SEEKEQ, this
** opcode must be followed by an IdxLE opcode with the same arguments.
** The IdxLE opcode will be skipped if this opcode succeeds, but the
** IdxLE opcode will be used on subsequent loop iterations.
**
** This opcode leaves the cursor configured to move in forward order,
** from the beginning toward the end.  In other words, the cursor is
** configured to use Next, not Prev.
**
** See also: Found, NotFound, SeekLt, SeekGt, SeekLe
*/
3651
3652
3653
3654
3655
3656
3657







3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669

3670
3671
3672
3673
3674
3675
3676
** is less than or equal to the key value. If there are no records 
** less than or equal to the key and P2 is not zero, then jump to P2.
**
** This opcode leaves the cursor configured to move in reverse order,
** from the end toward the beginning.  In other words, the cursor is
** configured to use Prev, not Next.
**







** See also: Found, NotFound, SeekGt, SeekGe, SeekLt
*/
case OP_SeekLT:         /* jump, in3 */
case OP_SeekLE:         /* jump, in3 */
case OP_SeekGE:         /* jump, in3 */
case OP_SeekGT: {       /* jump, in3 */
  int res;
  int oc;
  VdbeCursor *pC;
  UnpackedRecord r;
  int nField;
  i64 iKey;      /* The rowid we are to seek to */


  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  assert( pOp->p2!=0 );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->pseudoTableReg==0 );
  assert( OP_SeekLE == OP_SeekLT+1 );







>
>
>
>
>
>
>






|
|
|
|
|
|
>







3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
** is less than or equal to the key value. If there are no records 
** less than or equal to the key and P2 is not zero, then jump to P2.
**
** This opcode leaves the cursor configured to move in reverse order,
** from the end toward the beginning.  In other words, the cursor is
** configured to use Prev, not Next.
**
** If the cursor P1 was opened using the OPFLAG_SEEKEQ flag, then this
** opcode will always land on a record that equally equals the key, or
** else jump immediately to P2.  When the cursor is OPFLAG_SEEKEQ, this
** opcode must be followed by an IdxGE opcode with the same arguments.
** The IdxGE opcode will be skipped if this opcode succeeds, but the
** IdxGE opcode will be used on subsequent loop iterations.
**
** See also: Found, NotFound, SeekGt, SeekGe, SeekLt
*/
case OP_SeekLT:         /* jump, in3 */
case OP_SeekLE:         /* jump, in3 */
case OP_SeekGE:         /* jump, in3 */
case OP_SeekGT: {       /* jump, in3 */
  int res;           /* Comparison result */
  int oc;            /* Opcode */
  VdbeCursor *pC;    /* The cursor to seek */
  UnpackedRecord r;  /* The key to seek for */
  int nField;        /* Number of columns or fields in the key */
  i64 iKey;          /* The rowid we are to seek to */
  int eqOnly = 0;    /* Only interested in == results */

  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  assert( pOp->p2!=0 );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->pseudoTableReg==0 );
  assert( OP_SeekLE == OP_SeekLT+1 );
3684
3685
3686
3687
3688
3689
3690
3691
3692

3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
  pC->seekOp = pOp->opcode;
#endif

  /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and
  ** OP_SeekLE opcodes are allowed, and these must be immediately followed
  ** by an OP_IdxGT or OP_IdxLT opcode, respectively, with the same key.
  */
#ifdef SQLITE_DEBUG
  if( sqlite3BtreeCursorHasHint(pC->pCursor, BTREE_SEEK_EQ) ){

    assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE );
#if 0
    assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
    assert( pOp[1].p1==pOp[0].p1 );
    assert( pOp[1].p2==pOp[0].p2 );
    assert( pOp[1].p3==pOp[0].p3 );
    assert( pOp[1].p4.i==pOp[0].p4.i );
#endif
  }
#endif
 
  if( pC->isTable ){
    /* The input value in P3 might be of any type: integer, real, string,
    ** blob, or NULL.  But it needs to be an integer before we can do
    ** the seek, so convert it. */
    pIn3 = &aMem[pOp->p3];
    if( (pIn3->flags & (MEM_Int|MEM_Real|MEM_Str))==MEM_Str ){







<

>

<





<

<







3699
3700
3701
3702
3703
3704
3705

3706
3707
3708

3709
3710
3711
3712
3713

3714

3715
3716
3717
3718
3719
3720
3721
  pC->seekOp = pOp->opcode;
#endif

  /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and
  ** OP_SeekLE opcodes are allowed, and these must be immediately followed
  ** by an OP_IdxGT or OP_IdxLT opcode, respectively, with the same key.
  */

  if( sqlite3BtreeCursorHasHint(pC->pCursor, BTREE_SEEK_EQ) ){
    eqOnly = 1;
    assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE );

    assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
    assert( pOp[1].p1==pOp[0].p1 );
    assert( pOp[1].p2==pOp[0].p2 );
    assert( pOp[1].p3==pOp[0].p3 );
    assert( pOp[1].p4.i==pOp[0].p4.i );

  }

 
  if( pC->isTable ){
    /* The input value in P3 might be of any type: integer, real, string,
    ** blob, or NULL.  But it needs to be an integer before we can do
    ** the seek, so convert it. */
    pIn3 = &aMem[pOp->p3];
    if( (pIn3->flags & (MEM_Int|MEM_Real|MEM_Str))==MEM_Str ){
3745
3746
3747
3748
3749
3750
3751

3752
3753
3754
3755
3756
3757
3758
      }
    } 
    rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, 0, (u64)iKey, 0, &res);
    pC->movetoTarget = iKey;  /* Used by OP_Delete */
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }

  }else{
    nField = pOp->p4.i;
    assert( pOp->p4type==P4_INT32 );
    assert( nField>0 );
    r.pKeyInfo = pC->pKeyInfo;
    r.nField = (u16)nField;








>







3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
      }
    } 
    rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, 0, (u64)iKey, 0, &res);
    pC->movetoTarget = iKey;  /* Used by OP_Delete */
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    if( eqOnly && res ) goto seek_not_found;
  }else{
    nField = pOp->p4.i;
    assert( pOp->p4type==P4_INT32 );
    assert( nField>0 );
    r.pKeyInfo = pC->pKeyInfo;
    r.nField = (u16)nField;

3775
3776
3777
3778
3779
3780
3781
3782

3783
3784
3785
3786
3787
3788
3789
3790
#endif
    ExpandBlob(r.aMem);
    r.eqSeen = 0;
    rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    if( (pOp->p5 & OPFLAG_SEEKEQ)!=0 && r.eqSeen==0 ){

      goto take_the_jump;
    }
  }
  pC->deferredMoveto = 0;
  pC->cacheStatus = CACHE_STALE;
#ifdef SQLITE_TEST
  sqlite3_search_count++;
#endif







|
>
|







3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
#endif
    ExpandBlob(r.aMem);
    r.eqSeen = 0;
    rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    if( eqOnly && r.eqSeen==0 ){
      assert( res!=0 );
      goto seek_not_found;
    }
  }
  pC->deferredMoveto = 0;
  pC->cacheStatus = CACHE_STALE;
#ifdef SQLITE_TEST
  sqlite3_search_count++;
#endif
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816



3817
3818
3819
3820
3821
3822
3823
    }else{
      /* res might be negative because the table is empty.  Check to
      ** see if this is the case.
      */
      res = sqlite3BtreeEof(pC->pCursor);
    }
  }
take_the_jump:
  assert( pOp->p2>0 );
  VdbeBranchTaken(res!=0,2);
  if( res ){
    goto jump_to_p2;



  }
  break;
}

/* Opcode: Seek P1 P2 * * *
** Synopsis:  intkey=r[P2]
**







|




>
>
>







3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
    }else{
      /* res might be negative because the table is empty.  Check to
      ** see if this is the case.
      */
      res = sqlite3BtreeEof(pC->pCursor);
    }
  }
seek_not_found:
  assert( pOp->p2>0 );
  VdbeBranchTaken(res!=0,2);
  if( res ){
    goto jump_to_p2;
  }else if( eqOnly ){
    assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
    pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */
  }
  break;
}

/* Opcode: Seek P1 P2 * * *
** Synopsis:  intkey=r[P2]
**
Changes to src/wherecode.c.
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
    };
    u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
    int regBase;                 /* Base register holding constraint values */
    WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
    WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
    int startEq;                 /* True if range start uses ==, >= or <= */
    int endEq;                   /* True if range end uses ==, >= or <= */
    int eqOnly;                  /* True if uses only == */
    int start_constraints;       /* Start of range is constrained */
    int nConstraint;             /* Number of constraint terms */
    Index *pIdx;                 /* The index we will be using */
    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */







<







1022
1023
1024
1025
1026
1027
1028

1029
1030
1031
1032
1033
1034
1035
    };
    u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
    int regBase;                 /* Base register holding constraint values */
    WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
    WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
    int startEq;                 /* True if range start uses ==, >= or <= */
    int endEq;                   /* True if range end uses ==, >= or <= */

    int start_constraints;       /* Start of range is constrained */
    int nConstraint;             /* Number of constraint terms */
    Index *pIdx;                 /* The index we will be using */
    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
       && (j = pIdx->aiColumn[nEq])>=0 
       && pIdx->pTable->aCol[j].notNull==0
      ){
        bSeekPastNull = 1;
      }
    }
    assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );
    eqOnly = nEq>0 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)==0
                   && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==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)







<
<







1091
1092
1093
1094
1095
1096
1097


1098
1099
1100
1101
1102
1103
1104
       && (j = pIdx->aiColumn[nEq])>=0 
       && pIdx->pTable->aCol[j].notNull==0
      ){
        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)
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
    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( eqOnly ) sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ);

    /* Load the value for the inequality constraint at the end of the
    ** range (if any).
    */
    nConstraint = nEq;
    if( pRangeEnd ){
      Expr *pRight = pRangeEnd->pExpr->pRight;







<







1163
1164
1165
1166
1167
1168
1169

1170
1171
1172
1173
1174
1175
1176
    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 );


    /* Load the value for the inequality constraint at the end of the
    ** range (if any).
    */
    nConstraint = nEq;
    if( pRangeEnd ){
      Expr *pRight = pRangeEnd->pExpr->pRight;
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
    sqlite3DbFree(db, zStartAff);

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

    /* Check if the index cursor is past the end of the range. */
    if( nConstraint ){
      if( eqOnly ){
        int bx = sqlite3VdbeCurrentAddr(v);
        sqlite3VdbeAddOp2(v, OP_Goto, 0, bx+2);
        pLevel->p2 = bx+1;
      }
      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 );
    }







<
<
<
<
<







1198
1199
1200
1201
1202
1203
1204





1205
1206
1207
1208
1209
1210
1211
    sqlite3DbFree(db, zStartAff);

    /* 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 );
    }
Changes to test/collate4.test.
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
do_test collate4-2.1.2 {
  execsql {
    CREATE INDEX collate4i1 ON collate4t1(a);
  }
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE a = b;
  }
} {A a A A 5}
do_test collate4-2.1.3 {
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE b = a;
  }
} {A A 19}
do_test collate4-2.1.4 {
  execsql {
    DROP INDEX collate4i1;
    CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT);
  }
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE a = b
     ORDER BY collate4t2.rowid, collate4t1.rowid
  }
} {A a A A 19}
do_test collate4-2.1.5 {
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE b = a;
  }
} {A A 4}
ifcapable subquery {
  do_test collate4-2.1.6 {
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 10}
  do_test collate4-2.1.7 {
    execsql {
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 6}
  do_test collate4-2.1.8 {
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
    }
  } {a A 5}
  do_test collate4-2.1.9 {
    execsql {
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a') ORDER BY rowid;







|



















|
















|




|







348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
do_test collate4-2.1.2 {
  execsql {
    CREATE INDEX collate4i1 ON collate4t1(a);
  }
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE a = b;
  }
} {A a A A 4}
do_test collate4-2.1.3 {
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE b = a;
  }
} {A A 19}
do_test collate4-2.1.4 {
  execsql {
    DROP INDEX collate4i1;
    CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT);
  }
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE a = b
     ORDER BY collate4t2.rowid, collate4t1.rowid
  }
} {A a A A 19}
do_test collate4-2.1.5 {
  count {
    SELECT * FROM collate4t2, collate4t1 WHERE b = a;
  }
} {A A 3}
ifcapable subquery {
  do_test collate4-2.1.6 {
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 10}
  do_test collate4-2.1.7 {
    execsql {
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 5}
  do_test collate4-2.1.8 {
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
    }
  } {a A 4}
  do_test collate4-2.1.9 {
    execsql {
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a') ORDER BY rowid;
Changes to test/where.test.
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
      SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.3a {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 13}
  do_test where-5.3b {
    count {
      SELECT * FROM t1 WHERE w IN (3,-1,1,2) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 13}
  do_test where-5.3c {
    count {
      SELECT * FROM t1 WHERE w IN (3,2,-1,1,2) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 13}
  do_test where-5.3d {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1 DESC;
    }
  } {3 1 16 2 1 9 1 0 4 12}
  do_test where-5.4 {
    count {
      SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.5 {
    count {







|




|




|




|







408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
      SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.3a {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 12}
  do_test where-5.3b {
    count {
      SELECT * FROM t1 WHERE w IN (3,-1,1,2) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 12}
  do_test where-5.3c {
    count {
      SELECT * FROM t1 WHERE w IN (3,2,-1,1,2) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 12}
  do_test where-5.3d {
    count {
      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1 DESC;
    }
  } {3 1 16 2 1 9 1 0 4 11}
  do_test where-5.4 {
    count {
      SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
    }
  } {1 0 4 2 1 9 3 1 16 102}
  do_test where-5.5 {
    count {
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 103}
  do_test where-5.9 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 7}
  do_test where-5.10 {
    count {
      SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 199}
  do_test where-5.11 {
    count {
      SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 199}
  do_test where-5.12 {
    count {
      SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 7}
  do_test where-5.13 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1;
    }
  } {2 1 9 3 1 16 7}
  do_test where-5.14 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
    }
  } {2 1 9 8}
  do_test where-5.15 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
    }
  } {2 1 9 3 1 16 11}
  do_test where-5.100 {
    db eval {
      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
       ORDER BY x, y
    }
  } {2 1 9 54 5 3025 62 5 3969}
  do_test where-5.101 {







|



















|




|




|







461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
      ORDER BY 1;
    }
  } {2 1 9 4 2 25 103}
  do_test where-5.9 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 6}
  do_test where-5.10 {
    count {
      SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
    }
  } {2 1 9 3 1 16 199}
  do_test where-5.11 {
    count {
      SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 199}
  do_test where-5.12 {
    count {
      SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
    }
  } {79 6 6400 89 6 8100 7}
  do_test where-5.13 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1;
    }
  } {2 1 9 3 1 16 6}
  do_test where-5.14 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
    }
  } {2 1 9 5}
  do_test where-5.15 {
    count {
      SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
    }
  } {2 1 9 3 1 16 9}
  do_test where-5.100 {
    db eval {
      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
       ORDER BY x, y
    }
  } {2 1 9 54 5 3025 62 5 3969}
  do_test where-5.101 {
Changes to test/where4.test.
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
  count {SELECT rowid FROM t1 WHERE w='a' AND x IS NULL AND y='c'}
} {4 2}
do_test where4-1.10 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL}
} {6 2}
do_test where4-1.11 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=123}
} {1}
do_test where4-1.12 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=x'7A'}
} {6 2}
do_test where4-1.13 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL}
} {7 2}
do_test where4-1.14 {







|







87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
  count {SELECT rowid FROM t1 WHERE w='a' AND x IS NULL AND y='c'}
} {4 2}
do_test where4-1.10 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL}
} {6 2}
do_test where4-1.11 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=123}
} {0}
do_test where4-1.12 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=x'7A'}
} {6 2}
do_test where4-1.13 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL}
} {7 2}
do_test where4-1.14 {