SQLite
Check-in [3047a25f1c]
Not logged in
Overview
SHA1 Hash:3047a25f1c41e83f0b4772f7c36fbfec0f12dc7e
Date: 2014-03-28 18:35:39
User: drh
Comment:Merge the latest changes from trunk.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c

4584
4585
4586
4587
4588
4589
4590

4591
4592
4593
4594
4595
4596
4597
....
4707
4708
4709
4710
4711
4712
4713

4714
4715
4716
4717
4718
4719
4720
4721
4722

4723
4724
4725
4726
4727
4728
4729
      *pRes = -1;
      return SQLITE_OK;
    }
  }

  if( pIdxKey ){
    xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);

    assert( pIdxKey->default_rc==1 
         || pIdxKey->default_rc==0 
         || pIdxKey->default_rc==-1
    );
  }else{
    xRecordCompare = 0; /* All keys are integers */
  }
................................................................................
          if( rc ){
            sqlite3_free(pCellKey);
            goto moveto_finish;
          }
          c = xRecordCompare(nCell, pCellKey, pIdxKey, 0);
          sqlite3_free(pCellKey);
        }

        if( c<0 ){
          lwr = idx+1;
        }else if( c>0 ){
          upr = idx-1;
        }else{
          assert( c==0 );
          *pRes = 0;
          rc = SQLITE_OK;
          pCur->aiIdx[pCur->iPage] = (u16)idx;

          goto moveto_finish;
        }
        if( lwr>upr ) break;
        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
      }
    }







>







 







>









>







4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
....
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
      *pRes = -1;
      return SQLITE_OK;
    }
  }

  if( pIdxKey ){
    xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);
    pIdxKey->isCorrupt = 0;
    assert( pIdxKey->default_rc==1 
         || pIdxKey->default_rc==0 
         || pIdxKey->default_rc==-1
    );
  }else{
    xRecordCompare = 0; /* All keys are integers */
  }
................................................................................
          if( rc ){
            sqlite3_free(pCellKey);
            goto moveto_finish;
          }
          c = xRecordCompare(nCell, pCellKey, pIdxKey, 0);
          sqlite3_free(pCellKey);
        }
        assert( pIdxKey->isCorrupt==0 || c==0 );
        if( c<0 ){
          lwr = idx+1;
        }else if( c>0 ){
          upr = idx-1;
        }else{
          assert( c==0 );
          *pRes = 0;
          rc = SQLITE_OK;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          if( pIdxKey->isCorrupt ) rc = SQLITE_CORRUPT;
          goto moveto_finish;
        }
        if( lwr>upr ) break;
        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
      }
    }

Changes to src/sqliteInt.h

1623
1624
1625
1626
1627
1628
1629

1630
1631
1632
1633
1634
1635
1636
** 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 */
  u16 nField;         /* Number of entries in apMem[] */
  i8 default_rc;      /* Comparison result if keys are equal */

  Mem *aMem;          /* Values */
  int r1;             /* Value to return if (lhs > rhs) */
  int r2;             /* Value to return if (rhs < lhs) */
};


/*







>







1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
** 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 */
  u16 nField;         /* Number of entries in apMem[] */
  i8 default_rc;      /* Comparison result if keys are equal */
  u8 isCorrupt;       /* Corruption detected by xRecordCompare() */
  Mem *aMem;          /* Values */
  int r1;             /* Value to return if (lhs > rhs) */
  int r2;             /* Value to return if (rhs < lhs) */
};


/*

Changes to src/vdbe.h

207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8);
void sqlite3VdbeSetVarmask(Vdbe*, int);
#ifndef SQLITE_OMIT_TRACE
  char *sqlite3VdbeExpandSql(Vdbe*, const char*);
#endif

void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*);
int sqlite3VdbeRecordCompare(int,const void*,const UnpackedRecord*,int);
UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **);

typedef int (*RecordCompare)(int,const void*,const UnpackedRecord*,int);
RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*);

#ifndef SQLITE_OMIT_TRIGGER
void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *);
#endif

/* Use SQLITE_ENABLE_COMMENTS to enable generation of extra comments on







|


|







207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8);
void sqlite3VdbeSetVarmask(Vdbe*, int);
#ifndef SQLITE_OMIT_TRACE
  char *sqlite3VdbeExpandSql(Vdbe*, const char*);
#endif

void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*);
int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*,int);
UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **);

typedef int (*RecordCompare)(int,const void*,UnpackedRecord*,int);
RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*);

#ifndef SQLITE_OMIT_TRIGGER
void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *);
#endif

/* Use SQLITE_ENABLE_COMMENTS to enable generation of extra comments on

Changes to src/vdbeInt.h

388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
u32 sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32);
u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
void sqlite3VdbeDeleteAuxData(Vdbe*, int, int);

int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
int sqlite3VdbeIdxKeyCompare(VdbeCursor*,const UnpackedRecord*,int*);
int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *);
int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
int sqlite3VdbeExec(Vdbe*);
int sqlite3VdbeList(Vdbe*);
int sqlite3VdbeHalt(Vdbe*);
int sqlite3VdbeChangeEncoding(Mem *, int);
int sqlite3VdbeMemTooBig(Mem*);







|







388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
u32 sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32);
u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
void sqlite3VdbeDeleteAuxData(Vdbe*, int, int);

int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*);
int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *);
int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
int sqlite3VdbeExec(Vdbe*);
int sqlite3VdbeList(Vdbe*);
int sqlite3VdbeHalt(Vdbe*);
int sqlite3VdbeChangeEncoding(Mem *, int);
int sqlite3VdbeMemTooBig(Mem*);

Changes to src/vdbeaux.c

3401
3402
3403
3404
3405
3406
3407



3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
....
3430
3431
3432
3433
3434
3435
3436
3437



3438
3439
3440
3441
3442
3443
3444
....
3507
3508
3509
3510
3511
3512
3513

3514
3515
3516
3517
3518
3519
3520
3521
....
3533
3534
3535
3536
3537
3538
3539

3540
3541
3542
3543
3544
3545
3546
3547
....
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
....
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
....
3711
3712
3713
3714
3715
3716
3717


3718

3719
3720
3721
3722
3723
3724
3725
....
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
**
** If argument bSkip is non-zero, it is assumed that the caller has already
** determined that the first fields of the keys are equal.
**
** Key1 and Key2 do not have to contain the same number of fields. If all 
** fields that appear in both keys are equal, then pPKey2->default_rc is 
** returned.



*/
int sqlite3VdbeRecordCompare(
  int nKey1, const void *pKey1,   /* Left key */
  const UnpackedRecord *pPKey2,   /* Right key */
  int bSkip                       /* If true, skip the first field */
){
  u32 d1;                         /* Offset into aKey[] of next data element */
  int i;                          /* Index of next field to compare */
  u32 szHdr1;                     /* Size of record header in bytes */
  u32 idx1;                       /* Offset of first type in header */
  int rc = 0;                     /* Return value */
................................................................................
    szHdr1 = aKey1[0];
    d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1);
    i = 1;
    pRhs++;
  }else{
    idx1 = getVarint32(aKey1, szHdr1);
    d1 = szHdr1;
    if( d1>(unsigned)nKey1 ) return 1;  /* Corruption */



    i = 0;
  }

  VVA_ONLY( mem1.zMalloc = 0; ) /* Only needed by assert() statements */
  assert( pPKey2->pKeyInfo->nField+pPKey2->pKeyInfo->nXField>=pPKey2->nField 
       || CORRUPT_DB );
  assert( pPKey2->pKeyInfo->aSortOrder!=0 );
................................................................................
      }else if( !(serial_type & 0x01) ){
        rc = +1;
      }else{
        mem1.n = (serial_type - 12) / 2;
        testcase( (d1+mem1.n)==(unsigned)nKey1 );
        testcase( (d1+mem1.n+1)==(unsigned)nKey1 );
        if( (d1+mem1.n) > (unsigned)nKey1 ){

          rc = 1;                /* Corruption */
        }else if( pKeyInfo->aColl[i] ){
          mem1.enc = pKeyInfo->enc;
          mem1.db = pKeyInfo->db;
          mem1.flags = MEM_Str;
          mem1.z = (char*)&aKey1[d1];
          rc = vdbeCompareMemString(&mem1, pRhs, pKeyInfo->aColl[i]);
        }else{
................................................................................
      if( serial_type<12 || (serial_type & 0x01) ){
        rc = -1;
      }else{
        int nStr = (serial_type - 12) / 2;
        testcase( (d1+nStr)==(unsigned)nKey1 );
        testcase( (d1+nStr+1)==(unsigned)nKey1 );
        if( (d1+nStr) > (unsigned)nKey1 ){

          rc = 1;                /* Corruption */
        }else{
          int nCmp = MIN(nStr, pRhs->n);
          rc = memcmp(&aKey1[d1], pRhs->z, nCmp);
          if( rc==0 ) rc = nStr - pRhs->n;
        }
      }
    }
................................................................................
** byte (i.e. is less than 128).
**
** To avoid concerns about buffer overreads, this routine is only used
** on schemas where the maximum valid header size is 63 bytes or less.
*/
static int vdbeRecordCompareInt(
  int nKey1, const void *pKey1, /* Left key */
  const UnpackedRecord *pPKey2, /* Right key */
  int bSkip                     /* Ignored */
){
  const u8 *aKey = &((const u8*)pKey1)[*(const u8*)pKey1 & 0x3F];
  int serial_type = ((const u8*)pKey1)[1];
  int res;
  u32 y;
  u64 x;
................................................................................
** This function is an optimized version of sqlite3VdbeRecordCompare() 
** that (a) the first field of pPKey2 is a string, that (b) the first field
** uses the collation sequence BINARY and (c) that the size-of-header varint 
** at the start of (pKey1/nKey1) fits in a single byte.
*/
static int vdbeRecordCompareString(
  int nKey1, const void *pKey1, /* Left key */
  const UnpackedRecord *pPKey2, /* Right key */
  int bSkip
){
  const u8 *aKey1 = (const u8*)pKey1;
  int serial_type;
  int res;
  UNUSED_PARAMETER(bSkip);

................................................................................
    res = pPKey2->r2;      /* (pKey1/nKey1) is a blob */
  }else{
    int nCmp;
    int nStr;
    int szHdr = aKey1[0];

    nStr = (serial_type-12) / 2;


    if( (szHdr + nStr) > nKey1 ) return 0;    /* Corruption */

    nCmp = MIN( pPKey2->aMem[0].n, nStr );
    res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp);

    if( res==0 ){
      res = nStr - pPKey2->aMem[0].n;
      if( res==0 ){
        if( pPKey2->nField>1 ){
................................................................................
** pUnpacked 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.  Hence, this routine only compares the prefixes 
** of the keys prior to the final rowid, not the entire key.
*/
int sqlite3VdbeIdxKeyCompare(
  VdbeCursor *pC,                  /* The cursor to compare against */
  const UnpackedRecord *pUnpacked, /* Unpacked version of key */
  int *res                         /* Write the comparison result here */
){
  i64 nCellKey = 0;
  int rc;
  BtCursor *pCur = pC->pCursor;
  Mem m;








>
>
>



|







 







|
>
>
>







 







>
|







 







>
|







 







|







 







|







 







>
>
|
>







 







|







3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
....
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
....
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
....
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
....
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
....
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
....
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
....
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
**
** If argument bSkip is non-zero, it is assumed that the caller has already
** determined that the first fields of the keys are equal.
**
** Key1 and Key2 do not have to contain the same number of fields. If all 
** fields that appear in both keys are equal, then pPKey2->default_rc is 
** returned.
**
** If database corruption is discovered, set pPKey2->isCorrupt to non-zero
** and return 0.
*/
int sqlite3VdbeRecordCompare(
  int nKey1, const void *pKey1,   /* Left key */
  UnpackedRecord *pPKey2,         /* Right key */
  int bSkip                       /* If true, skip the first field */
){
  u32 d1;                         /* Offset into aKey[] of next data element */
  int i;                          /* Index of next field to compare */
  u32 szHdr1;                     /* Size of record header in bytes */
  u32 idx1;                       /* Offset of first type in header */
  int rc = 0;                     /* Return value */
................................................................................
    szHdr1 = aKey1[0];
    d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1);
    i = 1;
    pRhs++;
  }else{
    idx1 = getVarint32(aKey1, szHdr1);
    d1 = szHdr1;
    if( d1>(unsigned)nKey1 ){ 
      pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
      return 0;  /* Corruption */
    }
    i = 0;
  }

  VVA_ONLY( mem1.zMalloc = 0; ) /* Only needed by assert() statements */
  assert( pPKey2->pKeyInfo->nField+pPKey2->pKeyInfo->nXField>=pPKey2->nField 
       || CORRUPT_DB );
  assert( pPKey2->pKeyInfo->aSortOrder!=0 );
................................................................................
      }else if( !(serial_type & 0x01) ){
        rc = +1;
      }else{
        mem1.n = (serial_type - 12) / 2;
        testcase( (d1+mem1.n)==(unsigned)nKey1 );
        testcase( (d1+mem1.n+1)==(unsigned)nKey1 );
        if( (d1+mem1.n) > (unsigned)nKey1 ){
          pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
          return 0;                /* Corruption */
        }else if( pKeyInfo->aColl[i] ){
          mem1.enc = pKeyInfo->enc;
          mem1.db = pKeyInfo->db;
          mem1.flags = MEM_Str;
          mem1.z = (char*)&aKey1[d1];
          rc = vdbeCompareMemString(&mem1, pRhs, pKeyInfo->aColl[i]);
        }else{
................................................................................
      if( serial_type<12 || (serial_type & 0x01) ){
        rc = -1;
      }else{
        int nStr = (serial_type - 12) / 2;
        testcase( (d1+nStr)==(unsigned)nKey1 );
        testcase( (d1+nStr+1)==(unsigned)nKey1 );
        if( (d1+nStr) > (unsigned)nKey1 ){
          pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
          return 0;                /* Corruption */
        }else{
          int nCmp = MIN(nStr, pRhs->n);
          rc = memcmp(&aKey1[d1], pRhs->z, nCmp);
          if( rc==0 ) rc = nStr - pRhs->n;
        }
      }
    }
................................................................................
** byte (i.e. is less than 128).
**
** To avoid concerns about buffer overreads, this routine is only used
** on schemas where the maximum valid header size is 63 bytes or less.
*/
static int vdbeRecordCompareInt(
  int nKey1, const void *pKey1, /* Left key */
  UnpackedRecord *pPKey2,       /* Right key */
  int bSkip                     /* Ignored */
){
  const u8 *aKey = &((const u8*)pKey1)[*(const u8*)pKey1 & 0x3F];
  int serial_type = ((const u8*)pKey1)[1];
  int res;
  u32 y;
  u64 x;
................................................................................
** This function is an optimized version of sqlite3VdbeRecordCompare() 
** that (a) the first field of pPKey2 is a string, that (b) the first field
** uses the collation sequence BINARY and (c) that the size-of-header varint 
** at the start of (pKey1/nKey1) fits in a single byte.
*/
static int vdbeRecordCompareString(
  int nKey1, const void *pKey1, /* Left key */
  UnpackedRecord *pPKey2,       /* Right key */
  int bSkip
){
  const u8 *aKey1 = (const u8*)pKey1;
  int serial_type;
  int res;
  UNUSED_PARAMETER(bSkip);

................................................................................
    res = pPKey2->r2;      /* (pKey1/nKey1) is a blob */
  }else{
    int nCmp;
    int nStr;
    int szHdr = aKey1[0];

    nStr = (serial_type-12) / 2;
    if( (szHdr + nStr) > nKey1 ){
      pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
      return 0;    /* Corruption */
    }
    nCmp = MIN( pPKey2->aMem[0].n, nStr );
    res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp);

    if( res==0 ){
      res = nStr - pPKey2->aMem[0].n;
      if( res==0 ){
        if( pPKey2->nField>1 ){
................................................................................
** pUnpacked 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.  Hence, this routine only compares the prefixes 
** of the keys prior to the final rowid, not the entire key.
*/
int sqlite3VdbeIdxKeyCompare(
  VdbeCursor *pC,                  /* The cursor to compare against */
  UnpackedRecord *pUnpacked,       /* Unpacked version of key */
  int *res                         /* Write the comparison result here */
){
  i64 nCellKey = 0;
  int rc;
  BtCursor *pCur = pC->pCursor;
  Mem m;

Changes to src/where.c

4324
4325
4326
4327
4328
4329
4330




4331
4332
4333
4334
4335



4336
4337
4338
4339
4340
4341











4342
4343
4344
4345
4346
4347
4348
4349
....
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
....
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046








5047
5048
5049
5050
5051
5052
5053
5054
5055
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;




        if( m==0 ){
          /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
          **  +  The extra factor K of between 1.1 and 3.0 that depends
          **     on the relative sizes of the table and the index.  K
          **     is smaller for smaller indices, thus favoring them.



          */
          pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 +
                        (15*pProbe->szIdxRow)/pTab->szTabRow;
        }else{
          /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
          ** which we will simplify to just N*log2(N) */











          pNew->rRun = rSize + rLogSize;
        }
        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }
................................................................................
        if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;
        if( (mTerm&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  } /* End the loop over all WhereLoops from outer-most down to inner-most */
  if( obSat==obDone ) return nOrderBy;
  if( !isOrderDistinct ){
    for(i=nOrderBy-1; i>0; i--){
      Bitmask m = MASKBIT(i) - 1;
      if( (obSat&m)==m ) return i;
    }
    return 0;
  }
................................................................................
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).
            ** If some but not all of the columns are in sorted order, then
            ** scale down the log(N) term. */








            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;
            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,







>
>
>
>





>
>
>

<
|

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







 







|







 







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







4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343

4344
4345
4346

4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
....
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
....
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        /* TUNING:  The base cost of an index scan is N + log2(N).
        ** The log2(N) is for the initial seek to the beginning and the N
        ** is for the scan itself. */
        pNew->rRun = sqlite3LogEstAdd(rSize, rLogSize);
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
          **  +  The extra factor K of between 1.1 and 3.0 that depends
          **     on the relative sizes of the table and the index.  K
          **     is smaller for smaller indices, thus favoring them.
          **     The upper bound on K (3.0) matches the penalty factor
          **     on a full table scan that tries to encourage the use of
          **     indexed lookups over full scans.
          */

          pNew->rRun +=  1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
        }else{
          /* TUNING: The cost of scanning a non-covering index is multiplied

          ** by log2(N) to account for the binary search of the main table
          ** that must happen for each row of the index.
          ** TODO: Should there be a multiplier here, analogous to the 3x
          ** multiplier for a fulltable scan or covering index scan, to
          ** further discourage the use of an index scan?  Or is the log2(N)
          ** term sufficient discouragement?
          ** TODO: What if some or all of the WHERE clause terms can be
          ** computed without reference to the original table.  Then the
          ** penality should reduce to logK where K is the number of output
          ** rows.
          */
          pNew->rRun += rLogSize;
        }
        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }
................................................................................
        if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;
        if( (mTerm&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  } /* End the loop over all WhereLoops from outer-most down to inner-most */
  if( obSat==obDone ) return (i8)nOrderBy;
  if( !isOrderDistinct ){
    for(i=nOrderBy-1; i>0; i--){
      Bitmask m = MASKBIT(i) - 1;
      if( (obSat&m)==m ) return i;
    }
    return 0;
  }
................................................................................
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting is N*log(N).
            ** If the order-by clause has X terms but only the last Y terms
            ** are out of order, then block-sorting will reduce the sorting
            ** cost to N*log(N)*log(Y/X).  The log(Y/X) term is computed
            ** by rScale.
            ** TODO: Should the sorting cost get a small multiplier to help
            ** discourage the use of sorting and encourage the use of index
            ** scans instead?
            */
            LogEst rScale, rSortCost;
            assert( nOrderBy>0 );
            rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66;
            rSortCost = nRowEst + estLog(nRowEst) + rScale;
            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,

Changes to test/corruptG.test

43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
..
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
sqlite3 db test.db

# Try to use the file.
do_test 1.2 {
  catchsql {
    SELECT c FROM t1 WHERE a>'abc';
  }
} {0 {}}
do_test 1.3 {
  catchsql {
     PRAGMA integrity_check
  }
} {0 ok}
do_test 1.4 {
  catchsql {
    SELECT c FROM t1 ORDER BY a;
  }
} {1 {database disk image is malformed}}

# Corrupt the same file in a slightly different way.  Make the record header
................................................................................
hexio_write test.db [expr {$idxroot*512-15}] 0513ff7f01
sqlite3 db test.db

do_test 2.1 {
  catchsql {
    SELECT rowid FROM t1 WHERE a='abc' and b='xyz123456789XYZ';
  }
  # The following test result is brittle.  The point above is to try to
  # force a buffer overread by a corrupt database file.  If we get an
  # incorrect answer from a corrupt database file, that is OK.  If the
  # result below changes, that just means that "undefined behavior" has
  # changed.
} {/0 .*/}

finish_test







|




|







 







|
<
<
<
<
<


43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
..
67
68
69
70
71
72
73
74





75
76
sqlite3 db test.db

# Try to use the file.
do_test 1.2 {
  catchsql {
    SELECT c FROM t1 WHERE a>'abc';
  }
} {1 {database disk image is malformed}}
do_test 1.3 {
  catchsql {
     PRAGMA integrity_check
  }
} {1 {database disk image is malformed}}
do_test 1.4 {
  catchsql {
    SELECT c FROM t1 ORDER BY a;
  }
} {1 {database disk image is malformed}}

# Corrupt the same file in a slightly different way.  Make the record header
................................................................................
hexio_write test.db [expr {$idxroot*512-15}] 0513ff7f01
sqlite3 db test.db

do_test 2.1 {
  catchsql {
    SELECT rowid FROM t1 WHERE a='abc' and b='xyz123456789XYZ';
  }
} {1 {database disk image is malformed}}






finish_test

Changes to test/corruptI.test

47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
do_test 1.3 {
  db close
  set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]]
  set off [expr 2*1024 + $offset + 1]
  hexio_write test.db $off FFFF7f02
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 WHERE a = 10 }
} {0 {}}

do_test 2.0 {
  execsql {
    CREATE TABLE r(x);
    INSERT INTO r VALUES('ABCDEFGHIJK');
    CREATE INDEX r1 ON r(x);
  }







|







47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
do_test 1.3 {
  db close
  set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]]
  set off [expr 2*1024 + $offset + 1]
  hexio_write test.db $off FFFF7f02
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 WHERE a = 10 }
} {1 {database disk image is malformed}}

do_test 2.0 {
  execsql {
    CREATE TABLE r(x);
    INSERT INTO r VALUES('ABCDEFGHIJK');
    CREATE INDEX r1 ON r(x);
  }

Changes to test/wal64k.test

14
15
16
17
18
19
20





21
22
23
24
25
26
27
..
40
41
42
43
44
45
46
47
#

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

ifcapable !wal {finish_test ; return }






db close
test_syscall pagesize 65536
sqlite3 db test.db

do_execsql_test 1.0 { 
  PRAGMA journal_mode = WAL;
................................................................................
} {131072}

integrity_check 1.3

db close
test_syscall pagesize -1
finish_test








>
>
>
>
>







 







<
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
..
45
46
47
48
49
50
51

#

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

ifcapable !wal {finish_test ; return }

if {$tcl_platform(platform) != "unix"} {
  finish_test
  return
}

db close
test_syscall pagesize 65536
sqlite3 db test.db

do_execsql_test 1.0 { 
  PRAGMA journal_mode = WAL;
................................................................................
} {131072}

integrity_check 1.3

db close
test_syscall pagesize -1
finish_test

Changes to tool/logest.c

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
92
93
94
95
96
97
98
99
100
101
102
103
104





105















106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123











124
125


126
127
128
129

130
131
132
133
134
135
136
137
138
139
140
141
** integers and LogEst values and back again and for doing simple
** arithmetic operations (multiple and add) on LogEst values.
**
** Usage:
**
**      ./LogEst ARGS
**
** Arguments:
**
**    'x'    Multiple the top two elements of the stack
**    '+'    Add the top two elements of the stack
**    NUM    Convert NUM from integer to LogEst and push onto the stack
**   ^NUM    Interpret NUM as a LogEst and push onto stack.
**
** Examples:
**
** To convert 123 from LogEst to integer:
** 
**         ./LogEst ^123
**
** To convert 123456 from integer to LogEst:
................................................................................
  if( x<1.0 ) return -logEstFromDouble(1/x);
  if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100;
  if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x);
  memcpy(&a, &x, 8);
  e = (a>>52) - 1022;
  return e*10;
}

int isFloat(const char *z){
  while( z[0] ){
    if( z[0]=='.' || z[0]=='E' || z[0]=='e' ) return 1;
    z++;
  }





  return 0;















}

int main(int argc, char **argv){
  int i;
  int n = 0;
  LogEst a[100];
  for(i=1; i<argc; i++){
    const char *z = argv[i];
    if( z[0]=='+' ){
      if( n>=2 ){
        a[n-2] = logEstAdd(a[n-2],a[n-1]);
        n--;
      }
    }else if( z[0]=='x' ){
      if( n>=2 ){
        a[n-2] = logEstMultiply(a[n-2],a[n-1]);
        n--;
      }











    }else if( z[0]=='^' ){
      a[n++] = atoi(z+1);


    }else if( isFloat(z) ){
      a[n++] = logEstFromDouble(atof(z));
    }else{
      a[n++] = logEstFromInteger(atoi(z));

    }
  }
  for(i=n-1; i>=0; i--){
    if( a[i]<0 ){
      printf("%d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
    }else{
      sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024;
      printf("%d (%lld.%02lld)\n", a[i], x/100, x%100);
    }
  }
  return 0;
}







|
<
<
<
<
<
<







 








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








|




|




>
>
>
>
>
>
>
>
>
>
>


>
>
|


<
>




|


|




13
14
15
16
17
18
19
20






21
22
23
24
25
26
27
..
86
87
88
89
90
91
92
93
94
95
96

97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

155
156
157
158
159
160
161
162
163
164
165
166
167
** integers and LogEst values and back again and for doing simple
** arithmetic operations (multiple and add) on LogEst values.
**
** Usage:
**
**      ./LogEst ARGS
**
** See the showHelp() routine for a description of valid arguments.






** Examples:
**
** To convert 123 from LogEst to integer:
** 
**         ./LogEst ^123
**
** To convert 123456 from integer to LogEst:
................................................................................
  if( x<1.0 ) return -logEstFromDouble(1/x);
  if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100;
  if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x);
  memcpy(&a, &x, 8);
  e = (a>>52) - 1022;
  return e*10;
}

int isInteger(const char *z){
  while( z[0]>='0' && z[0]<='9' ) z++;
  return z[0]==0;

}

int isFloat(const char *z){
  char c;
  while( ((c=z[0])>='0' && c<='9') || c=='.' || c=='E' || c=='e'
          || c=='+' || c=='-'  ) z++;
  return z[0]==0;
}

static void showHelp(const char *zArgv0){
  printf("Usage: %s ARGS...\n", zArgv0);
  printf("Arguments:\n"
    "  NUM    Convert NUM from integer to LogEst and push onto the stack\n"
    " ^NUM    Interpret NUM as a LogEst and push onto stack\n"
    "  x      Multiple the top two elements of the stack\n"
    "  +      Add the top two elements of the stack\n"
    "  dup    Dupliate the top element on the stack\n"
    "  inv    Take the reciprocal of the top of stack.  N = 1/N.\n"
    "  log    Find the LogEst of the number on top of stack\n"
    "  nlogn  Compute NlogN where N is the top of stack\n"
  );
  exit(1);
}

int main(int argc, char **argv){
  int i;
  int n = 0;
  LogEst a[100];
  for(i=1; i<argc; i++){
    const char *z = argv[i];
    if( strcmp(z,"+")==0 ){
      if( n>=2 ){
        a[n-2] = logEstAdd(a[n-2],a[n-1]);
        n--;
      }
    }else if( strcmp(z,"x")==0 ){
      if( n>=2 ){
        a[n-2] = logEstMultiply(a[n-2],a[n-1]);
        n--;
      }
    }else if( strcmp(z,"dup")==0 ){
      if( n>0 ){
        a[n] = a[n-1];
        n++;
      }
    }else if( strcmp(z,"log")==0 ){
      if( n>0 ) a[n-1] = logEstFromInteger(a[n-1]) - 33;
    }else if( strcmp(z,"nlogn")==0 ){
      if( n>0 ) a[n-1] += logEstFromInteger(a[n-1]) - 33;
    }else if( strcmp(z,"inv")==0 ){
      if( n>0 ) a[n-1] = -a[n-1];
    }else if( z[0]=='^' ){
      a[n++] = atoi(z+1);
    }else if( isInteger(z) ){
      a[n++] = logEstFromInteger(atoi(z));
    }else if( isFloat(z) && z[0]!='-' ){
      a[n++] = logEstFromDouble(atof(z));
    }else{

      showHelp(argv[0]);
    }
  }
  for(i=n-1; i>=0; i--){
    if( a[i]<0 ){
      printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
    }else{
      sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024;
      printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100);
    }
  }
  return 0;
}