/ Check-in [c448f15a]
Login

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

Overview
Comment:Allow OP_MoveGt and similar to use an array of registers instead of a serialized record. Modify one type of index range scan to use this. (CVS 5028)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:c448f15aa5ed3dec511426775e893efea324faa1
User & Date: danielk1977 2008-04-18 09:01:16
Context
2008-04-18
10:25
Combine cases 3 and 4 in where.c, since case 4 is now a special case of case 3. (CVS 5029) check-in: 9a976819 user: danielk1977 tags: trunk
09:01
Allow OP_MoveGt and similar to use an array of registers instead of a serialized record. Modify one type of index range scan to use this. (CVS 5028) check-in: c448f15a user: danielk1977 tags: trunk
2008-04-17
20:59
Continuing progress on the journal_mode pragma. It still does not work. (CVS 5027) check-in: 4a72a7bb user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
2128
2129
2130
2131
2132
2133
2134




















2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
....
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816




2817
2818
2819
2820
2821
2822
2823
....
2844
2845
2846
2847
2848
2849
2850

2851

2852
2853









2854
2855
2856
2857
2858
2859
2860
....
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
....
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839











3840

3841
3842
3843
3844
3845
3846
3847
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.730 2008/04/15 12:14:22 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  rc = sqlite3VdbeMemMakeWriteable(pDest);

op_column_out:
  UPDATE_MAX_BLOBSIZE(pDest);
  REGISTER_TRACE(pOp->p3, pDest);
  break;
}





















/* Opcode: MakeRecord P1 P2 P3 P4 *
**
** Convert P2 registers beginning with P1 into a single entry
** suitable for use as a data record in a database table or as a key
** in an index.  The details of the format are irrelavant as long as
** the OP_Column opcode can decode the record later.
** Refer to source code comments for the details of the record
** format.
**
** P4 may be a string that is P1 characters long.  The nth character of the
** string indicates the column affinity that should be used for the nth
** field of the index key.
**
** The mapping from character to affinity is given by the SQLITE_AFF_
** macros defined in sqliteInt.h.
**
** If P4 is NULL then all index fields have the affinity NONE.
................................................................................
** cursor P1 so that it points to the largest entry that is less
** than the key in register P3.
** If there are no records less than the key
** then jump to P2.
**
** See also: Found, NotFound, Distinct, MoveGt, MoveGe, MoveLe
*/
/* Opcode: MoveLe P1 P2 P3 * *
**
** Use the value in register P3 as a key.  Reposition
** cursor P1 so that it points to the largest entry that is less than
** or equal to the key.
** If there are no records less than or eqal to the key
** then jump to P2.




**
** See also: Found, NotFound, Distinct, MoveGt, MoveGe, MoveLt
*/
case OP_MoveLt:         /* jump, in3 */
case OP_MoveLe:         /* jump, in3 */
case OP_MoveGe:         /* jump, in3 */
case OP_MoveGt: {       /* jump, in3 */
................................................................................
      rc = sqlite3BtreeMoveto(pC->pCursor, 0, 0, (u64)iKey, 0, &res);
      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->lastRowid = iKey;
      pC->rowidIsValid = res==0;
    }else{

      assert( pIn3->flags & MEM_Blob );

      ExpandBlob(pIn3);
      rc = sqlite3BtreeMoveto(pC->pCursor, pIn3->z, 0, pIn3->n, 0, &res);









      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->rowidIsValid = 0;
    }
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
................................................................................
    if( res<0 ){
      rc = sqlite3BtreeNext(pCrsr, &res);
      if( res ){
        pc = pOp->p2 - 1;
        break;
      }
    }
    rc = sqlite3VdbeIdxKeyCompare(pCx, len, (u8*)zKey, &res); 
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
    if( res>0 ){
      pc = pOp->p2 - 1;
      break;
    }

    /* At this point, pCrsr is pointing to an entry in P1 where all but
................................................................................
** The value in register P3 is an index entry that omits the ROWID.  Compare
** the this value against the index that P1 is currently pointing to.
** Ignore the ROWID on the P1 index.
**
** If the P1 index entry is less than the register P3 value
** then jump to P2.  Otherwise fall through to the next instruction.
**
** If P5 is non-zero then the
** index taken from register P3 is temporarily increased by
** an epsilon prior to the comparison.  This makes the opcode work
** like IdxLE.
*/
case OP_IdxLT:          /* jump, in3 */
case OP_IdxGE: {        /* jump, in3 */
  int i= pOp->p1;
  Cursor *pC;

  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
 
    assert( pIn3->flags & MEM_Blob );  /* Created using OP_MakeRecord */
    assert( pC->deferredMoveto==0 );
    ExpandBlob(pIn3);
    assert( pOp->p5==0 || pOp->p5==1 );
    *pC->pIncrKey = pOp->p5;











    rc = sqlite3VdbeIdxKeyCompare(pC, pIn3->n, (u8*)pIn3->z, &res);

    *pC->pIncrKey = 0;
    if( rc!=SQLITE_OK ){
      break;
    }
    if( pOp->opcode==OP_IdxLT ){
      res = -res;
    }else{







|







 







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










|







 







|

|
|
|
|
|
>
>
>
>







 







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







 







|







 







<
|
|
|











<

<


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







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
....
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
....
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
....
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
....
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
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.731 2008/04/18 09:01:16 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  rc = sqlite3VdbeMemMakeWriteable(pDest);

op_column_out:
  UPDATE_MAX_BLOBSIZE(pDest);
  REGISTER_TRACE(pOp->p3, pDest);
  break;
}

/* Opcode: Affinity P1 P2 * P4 *
**
** Apply affinities to a range of P2 registers starting with P1.
**
** P4 is a string that is P2 characters long. The nth character of the
** string indicates the column affinity that should be used for the nth
** memory cell in the range.
*/
case OP_Affinity: {
  char *zAffinity = pOp->p4.z;
  Mem *pData0 = &p->aMem[pOp->p1];
  Mem *pLast = &pData0[pOp->p2-1];
  Mem *pRec;

  for(pRec=pData0; pRec<=pLast; pRec++){
    applyAffinity(pRec, zAffinity[pRec-pData0], encoding);
  }
  break;
}

/* Opcode: MakeRecord P1 P2 P3 P4 *
**
** Convert P2 registers beginning with P1 into a single entry
** suitable for use as a data record in a database table or as a key
** in an index.  The details of the format are irrelavant as long as
** the OP_Column opcode can decode the record later.
** Refer to source code comments for the details of the record
** format.
**
** P4 may be a string that is P2 characters long.  The nth character of the
** string indicates the column affinity that should be used for the nth
** field of the index key.
**
** The mapping from character to affinity is given by the SQLITE_AFF_
** macros defined in sqliteInt.h.
**
** If P4 is NULL then all index fields have the affinity NONE.
................................................................................
** cursor P1 so that it points to the largest entry that is less
** than the key in register P3.
** If there are no records less than the key
** then jump to P2.
**
** See also: Found, NotFound, Distinct, MoveGt, MoveGe, MoveLe
*/
/* Opcode: MoveLe P1 P2 P3 P4 *
**
** P4 is always an integer value. If it is zero, then use the value in
** register P3 as a key. Reposition cursor P1 so that it points to the
** largest entry that is less than or equal to the key. If there are no 
** records less than or eqal to the key then jump to P2.
**
** If the integer value in operand P4 is non-zero, then P3 is the first
** of a contiguous array of P4 memory cells that form an unpacked index
** key. In this case the unpacked key is used instead of the value of
** register P3 in the procedure described above.
**
** See also: Found, NotFound, Distinct, MoveGt, MoveGe, MoveLt
*/
case OP_MoveLt:         /* jump, in3 */
case OP_MoveLe:         /* jump, in3 */
case OP_MoveGe:         /* jump, in3 */
case OP_MoveGt: {       /* jump, in3 */
................................................................................
      rc = sqlite3BtreeMoveto(pC->pCursor, 0, 0, (u64)iKey, 0, &res);
      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->lastRowid = iKey;
      pC->rowidIsValid = res==0;
    }else{
      int nField = ((pOp->p4type==P4_INT32)?pOp->p4.i:0);
      assert( pIn3->flags&MEM_Blob || nField>0 );
      if( nField==0 ){
        ExpandBlob(pIn3);
        rc = sqlite3BtreeMoveto(pC->pCursor, pIn3->z, 0, pIn3->n, 0, &res);
      }else{
        UnpackedRecord r;
        r.pKeyInfo = pC->pKeyInfo;
        r.nField = nField;
        r.needFree = 0;
        r.needDestroy = 0;
        r.aMem = &p->aMem[pOp->p3];
        rc = sqlite3BtreeMoveto(pC->pCursor, 0, &r, 0, 0, &res);
      }
      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->rowidIsValid = 0;
    }
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
................................................................................
    if( res<0 ){
      rc = sqlite3BtreeNext(pCrsr, &res);
      if( res ){
        pc = pOp->p2 - 1;
        break;
      }
    }
    rc = sqlite3VdbeIdxKeyCompare(pCx, 0, len, (u8*)zKey, &res); 
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
    if( res>0 ){
      pc = pOp->p2 - 1;
      break;
    }

    /* At this point, pCrsr is pointing to an entry in P1 where all but
................................................................................
** The value in register P3 is an index entry that omits the ROWID.  Compare
** the this value against the index that P1 is currently pointing to.
** Ignore the ROWID on the P1 index.
**
** If the P1 index entry is less than the register P3 value
** then jump to P2.  Otherwise fall through to the next instruction.
**

** If P5 is non-zero then the index taken from register P3 is temporarily 
** increased by an epsilon prior to the comparison.  This makes the opcode 
** work like IdxLE.
*/
case OP_IdxLT:          /* jump, in3 */
case OP_IdxGE: {        /* jump, in3 */
  int i= pOp->p1;
  Cursor *pC;

  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
 

    assert( pC->deferredMoveto==0 );

    assert( pOp->p5==0 || pOp->p5==1 );
    *pC->pIncrKey = pOp->p5;
    if( pOp->p4type!=P4_INT32 || pOp->p4.i==0 ){
      assert( pIn3->flags & MEM_Blob );  /* Created using OP_MakeRecord */
      ExpandBlob(pIn3);
      rc = sqlite3VdbeIdxKeyCompare(pC, 0, pIn3->n, (u8*)pIn3->z, &res);
    }else{
      UnpackedRecord r;
      r.pKeyInfo = pC->pKeyInfo;
      r.nField = pOp->p4.i;
      r.needFree = 0;
      r.needDestroy = 0;
      r.aMem = &p->aMem[pOp->p3];
      rc = sqlite3VdbeIdxKeyCompare(pC, &r, 0, 0, &res);
    }
    *pC->pIncrKey = 0;
    if( rc!=SQLITE_OK ){
      break;
    }
    if( pOp->opcode==OP_IdxLT ){
      res = -res;
    }else{

Changes to src/vdbeInt.h.

383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
int sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
int sqlite3VdbeSerialPut(unsigned char*, int, Mem*, int);
int sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
void sqlite3VdbeDeleteAuxData(VdbeFunc*, int);

int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
int sqlite3VdbeIdxKeyCompare(Cursor*,int,const unsigned char*,int*);
int sqlite3VdbeIdxRowid(BtCursor *, i64 *);
int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
int sqlite3VdbeIdxRowidLen(const u8*);
int sqlite3VdbeExec(Vdbe*);
int sqlite3VdbeList(Vdbe*);
int sqlite3VdbeHalt(Vdbe*);
int sqlite3VdbeChangeEncoding(Mem *, int);







|







383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
int sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
int sqlite3VdbeSerialPut(unsigned char*, int, Mem*, int);
int sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
void sqlite3VdbeDeleteAuxData(VdbeFunc*, int);

int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
int sqlite3VdbeIdxKeyCompare(Cursor*,UnpackedRecord *,int,const unsigned char*,int*);
int sqlite3VdbeIdxRowid(BtCursor *, i64 *);
int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
int sqlite3VdbeIdxRowidLen(const u8*);
int sqlite3VdbeExec(Vdbe*);
int sqlite3VdbeList(Vdbe*);
int sqlite3VdbeHalt(Vdbe*);
int sqlite3VdbeChangeEncoding(Mem *, int);

Changes to src/vdbeaux.c.

2397
2398
2399
2400
2401
2402
2403

2404
2405
2406
2407
2408
2409
2410
....
2421
2422
2423
2424
2425
2426
2427

2428
2429



2430
2431
2432
2433

2434

2435
2436
2437
2438
2439
2440
2441
**
** pKey is either created without a rowid or is truncated so that it
** omits the rowid at the end.  The rowid at the end of the index entry
** is ignored as well.
*/
int sqlite3VdbeIdxKeyCompare(
  Cursor *pC,                 /* The cursor to compare against */

  int nKey, const u8 *pKey,   /* The key to compare */
  int *res                    /* Write the comparison result here */
){
  i64 nCellKey = 0;
  int rc;
  BtCursor *pCur = pC->pCursor;
  int lenRowid;
................................................................................
  m.flags = 0;
  m.zMalloc = 0;
  rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, nCellKey, 1, &m);
  if( rc ){
    return rc;
  }
  lenRowid = sqlite3VdbeIdxRowidLen((u8*)m.z);

  pRec = sqlite3VdbeRecordUnpack(pC->pKeyInfo, nKey, pKey,
                                zSpace, sizeof(zSpace));



  if( pRec==0 ){
    return SQLITE_NOMEM;
  }
  *res = sqlite3VdbeRecordCompare(m.n-lenRowid, m.z, pRec);

  sqlite3VdbeDeleteUnpackedRecord(pRec);

  sqlite3VdbeMemRelease(&m);
  return SQLITE_OK;
}

/*
** This routine sets the value to be returned by subsequent calls to
** sqlite3_changes() on the database handle 'db'. 







>







 







>
|

>
>
>




>
|
>







2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
....
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
**
** pKey is either created without a rowid or is truncated so that it
** omits the rowid at the end.  The rowid at the end of the index entry
** is ignored as well.
*/
int sqlite3VdbeIdxKeyCompare(
  Cursor *pC,                 /* The cursor to compare against */
  UnpackedRecord *pUnpacked,
  int nKey, const u8 *pKey,   /* The key to compare */
  int *res                    /* Write the comparison result here */
){
  i64 nCellKey = 0;
  int rc;
  BtCursor *pCur = pC->pCursor;
  int lenRowid;
................................................................................
  m.flags = 0;
  m.zMalloc = 0;
  rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, nCellKey, 1, &m);
  if( rc ){
    return rc;
  }
  lenRowid = sqlite3VdbeIdxRowidLen((u8*)m.z);
  if( !pUnpacked ){
    pRec = sqlite3VdbeRecordUnpack(pC->pKeyInfo, nKey, pKey,
                                zSpace, sizeof(zSpace));
  }else{
    pRec = pUnpacked;
  }
  if( pRec==0 ){
    return SQLITE_NOMEM;
  }
  *res = sqlite3VdbeRecordCompare(m.n-lenRowid, m.z, pRec);
  if( !pUnpacked ){
    sqlite3VdbeDeleteUnpackedRecord(pRec);
  }
  sqlite3VdbeMemRelease(&m);
  return SQLITE_OK;
}

/*
** This routine sets the value to be returned by subsequent calls to
** sqlite3_changes() on the database handle 'db'. 

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507




2508
2509
2510
2511
2512
2513
2514
....
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628


2629
2630
2631
2632
2633
2634
2635

2636
2637
2638
2639

2640
2641
2642
2643
2644
2645
2646
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.299 2008/04/17 19:14:02 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
      **         right-most column can be an inequality - the rest must
      **         use the "==" and "IN" operators.
      **
      **         This case is also used when there are no WHERE clause
      **         constraints but an index is selected anyway, in order
      **         to force the output order to conform to an ORDER BY.
      */
      int start;
      int nEq = pLevel->nEq;
      int topEq=0;        /* True if top limit uses ==. False is strictly < */
      int btmEq=0;        /* True if btm limit uses ==. False if strictly > */
      int topOp, btmOp;   /* Operators for the top and bottom search bounds */
      int testOp;
      int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
      int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;
      int isMinQuery = 0;      /* If this is an optimized SELECT min(x) ... */
      int regBase;        /* Base register holding constraint values */
      int r1;             /* Temp register */

      /* Generate code to evaluate all constraint terms using == or IN
      ** and level the values of those terms on the stack.
      */
      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 2);

      /* Figure out what comparison operators to use for top and bottom 
      ** search bounds. For an ascending index, the bottom bound is a > or >=
      ** operator and the top bound is a < or <= operator.  For a descending
      ** index the operators are reversed.
      */
      if( pIdx->aSortOrder[nEq]==SQLITE_SO_ASC ){
        topOp = WO_LT|WO_LE;
        btmOp = WO_GT|WO_GE;
      }else{
        topOp = WO_GT|WO_GE;
        btmOp = WO_LT|WO_LE;
        SWAP(int, topLimit, btmLimit);
      }





      /* 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,
................................................................................
       && (pLevel->flags&WHERE_ORDERBY)
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
      }

      /* Generate the termination key.  This is the key value that
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
      ** key computed here really ends up being the start key.
      */
      nxt = pLevel->nxt;
      if( topLimit ){
        Expr *pX;
        int k = pIdx->aiColumn[nEq];
        pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight, regBase+nEq);
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
        topEq = pTerm->eOperator & (WO_LE|WO_GE);
        disableTerm(pLevel, pTerm);
        testOp = OP_IdxGE;
      }else{
        testOp = nEq>0 ? OP_IdxGE : OP_Noop;
        topEq = 1;
      }
      if( testOp!=OP_Noop || (isMinQuery&&bRev) ){
        int nCol = nEq + topLimit;
        if( isMinQuery && bRev && !topLimit ){
          sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nCol);
          nCol++;
          topEq = 0;
        }
        buildIndexProbe(pParse, nCol, pIdx, regBase, pLevel->iMem);
        if( bRev ){
          int op = topEq ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp3(v, op, iIdxCur, nxt, pLevel->iMem);
        }
      }else if( bRev ){
        sqlite3VdbeAddOp2(v, OP_Last, iIdxCur, brk);
      }
   
      /* Generate the start key.  This is the key that defines the lower
      ** bound on the search.  There is no start key if there are no
      ** equality terms and if there is no "X>..." term.  In
      ** that case, generate a "Rewind" instruction in place of the
      ** start key search.
      **
      ** 2002-Dec-04: In the case of a reverse-order search, the so-called
      ** "start" key really ends up being used as the termination key.
      */
      if( btmLimit ){
        Expr *pX;
        int k = pIdx->aiColumn[nEq];
        pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight, regBase+nEq);
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
        btmEq = pTerm->eOperator & (WO_LE|WO_GE);
        disableTerm(pLevel, pTerm);
      }else{
        btmEq = 1;
      }
      if( nEq>0 || btmLimit || (isMinQuery&&!bRev) ){
        int nCol = nEq + btmLimit;
        if( isMinQuery && !bRev && !btmLimit ){
          sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nCol);
          nCol++;
          btmEq = 0;
        }
        if( bRev ){
          r1 = pLevel->iMem;
          testOp = OP_IdxLT;
        }else{
          r1 = sqlite3GetTempReg(pParse);
        }
        buildIndexProbe(pParse, nCol, pIdx, regBase, r1);
        if( !bRev ){
          int op = btmEq ? OP_MoveGe : OP_MoveGt;
          sqlite3VdbeAddOp3(v, op, iIdxCur, nxt, r1);
          sqlite3ReleaseTempReg(pParse, r1);
        }
      }else if( bRev ){
        testOp = OP_Noop;
      }else{
        sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, brk);
      }

      /* Generate the the top of the loop.  If there is a termination
      ** key we have to test for that key and abort at the top of the
      ** loop.
      */
      start = sqlite3VdbeCurrentAddr(v);
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp3(v, testOp, iIdxCur, nxt, pLevel->iMem);
        if( (topEq && !bRev) || (!btmEq && bRev) ){
          sqlite3VdbeChangeP5(v, 1);
        }
      }
      r1 = sqlite3GetTempReg(pParse);
      if( topLimit | btmLimit ){
        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
        sqlite3VdbeAddOp2(v, OP_IsNull, r1, cont);
      }


      if( !omitTable ){
        sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
        sqlite3VdbeAddOp3(v, OP_MoveGe, iCur, 0, r1);  /* Deferred seek */
      }
      sqlite3ReleaseTempReg(pParse, r1);

      /* Record the instruction used to terminate the loop.

      */
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;

    }else if( pLevel->flags & WHERE_COLUMN_EQ ){
      /* Case 4:  There is an index and all terms of the WHERE clause that
      **          refer to the index using the "==" or "IN" operators.
      */
      int start;
      int nEq = pLevel->nEq;
      int isMinQuery = 0;      /* If this is an optimized SELECT min(x) ... */







|







 







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







 







|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<



>
>






|
>



|
>







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
....
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599






























2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.300 2008/04/18 09:01:16 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
      **         right-most column can be an inequality - the rest must
      **         use the "==" and "IN" operators.
      **
      **         This case is also used when there are no WHERE clause
      **         constraints but an index is selected anyway, in order
      **         to force the output order to conform to an ORDER BY.
      */
      int aStartOp[] = {
        0,
        0,
        OP_Rewind,           /* 2: (!start_constraints && startEq && !bRev) */
        OP_Last,             /* 3: (!start_constraints && startEq && bRev)  */
        OP_MoveGt,           /* 4: (start_constraints  && !startEq && !bRev) */
        OP_MoveLt,           /* 5: (start_constraints  && !startEq && bRev) */
        OP_MoveGe,           /* 6: (start_constraints  &&  startEq && !bRev) */
        OP_MoveLe            /* 7: (start_constraints  &&  startEq && bRev) */
      };
      int aEndOp[] = {
        OP_Noop,             /* 0: () */
        OP_IdxGE,            /* 1: (end_constraints && !bRev) */
        OP_IdxLT             /* 2: (end_constraints && bRev) */
      };
      int nEq = pLevel->nEq;
      int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
      int regBase;                 /* Base register holding constraint values */
      int r1;                      /* Temp register */
      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 k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */
      char *ptr;
      int op;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and store the values of those terms in an array of registers
      ** starting at regBase.
      */
      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 2);
      nxt = pLevel->nxt;

      /* 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,
................................................................................
       && (pLevel->flags&WHERE_ORDERBY)
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
      }

      /* Find the inequality constraint terms for the start and end 
      ** of the range. 
      */
      if( pLevel->flags & WHERE_TOP_LIMIT ){
        pRangeEnd = findTerm(&wc, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
      }
      if( pLevel->flags & WHERE_BTM_LIMIT ){
        pRangeStart = findTerm(&wc, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
      }

      /* 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( bRev==((pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)?1:0) ){
        SWAP(WhereTerm *, pRangeEnd, pRangeStart);
      }

      startEq = ((!pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE))?1:0);
      endEq = ((!pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE))?1:0);
      start_constraints = ((pRangeStart || nEq>0)?1:0);

      /* Seek the index cursor to the start of the range. */
      ptr = (char *)(sqlite3_intptr_t)nEq;
      if( pRangeStart ){
        int dcc = pParse->disableColCache;
        if( pRangeEnd ){
          pParse->disableColCache = 1;
        }
        sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
        pParse->disableColCache = dcc;
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
        ptr++;
      }else if( isMinQuery ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
        ptr++;
        startEq = 0;
        start_constraints = 1;
      }
      sqlite3VdbeAddOp2(v, OP_Affinity, regBase, (int)ptr);
      sqlite3IndexAffinityStr(v, pIdx);
      op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
      sqlite3VdbeAddOp4(v, op, iIdxCur, nxt, regBase, ptr, P4_INT32);

      /* Load the value for the inequality constraint at the end of the
      ** range (if any).
      */
      ptr = (char *)(sqlite3_intptr_t)nEq;
      if( pRangeEnd ){
        sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
        ptr++;
      }
      sqlite3VdbeAddOp2(v, OP_Affinity, regBase, (int)ptr);
      sqlite3IndexAffinityStr(v, pIdx);

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

      /* Check if the index cursor is past the end of the range. */
      op = aEndOp[((pRangeEnd || nEq)?1:0) * (1 + bRev)];
      sqlite3VdbeAddOp4(v, op, iIdxCur, nxt, regBase, ptr, P4_INT32);
      sqlite3VdbeChangeP5(v, endEq!=bRev);

      /* If there are inequality constraints (there may not be if the
      ** index is only being used to optimize ORDER BY), check that the
      ** value of the table column the inequality contrains is not NULL.
      ** If it is, jump to the next iteration of the loop.
      */
      r1 = sqlite3GetTempReg(pParse);
      if( pLevel->flags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){






























        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
        sqlite3VdbeAddOp2(v, OP_IsNull, r1, cont);
      }

      /* Seek the table cursor, if required */
      if( !omitTable ){
        sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
        sqlite3VdbeAddOp3(v, OP_MoveGe, iCur, 0, r1);  /* Deferred seek */
      }
      sqlite3ReleaseTempReg(pParse, r1);

      /* Record the instruction used to terminate the loop. Disable 
      ** WHERE clause terms made redundant by the index range scan.
      */
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      disableTerm(pLevel, pRangeStart);
      disableTerm(pLevel, pRangeEnd);
    }else if( pLevel->flags & WHERE_COLUMN_EQ ){
      /* Case 4:  There is an index and all terms of the WHERE clause that
      **          refer to the index using the "==" or "IN" operators.
      */
      int start;
      int nEq = pLevel->nEq;
      int isMinQuery = 0;      /* If this is an optimized SELECT min(x) ... */