/ Check-in [aec5473a]
Login

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

Overview
Comment:Refactor the sqlite3VdbeRecordCompare() routine used to compare btree records. Create a couple of fast-track routines to handle the common cases of a string with BINARY collation or integer values as the left-most column. This gives a significant performance boost in common use. Oops: This build does not work on the Beaglebone where "char" defaults to unsigned.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | broken-on-arm
Files: files | file ages | folders
SHA1:aec5473a750e412eb1e11e17bbafd760db086c86
User & Date: drh 2014-03-03 21:59:33
Original Comment: Refactor the sqlite3VdbeRecordCompare() routine used to compare btree records. Create a couple of fast-track routines to handle the common cases of a string with BINARY collation or integer values as the left-most column. This gives a significant performance boost in common use.
Context
2014-03-04
00:15
Do not assume that 'char' is signed. Make it explicit. check-in: 979da752 user: drh tags: broken-on-arm
2014-03-03
21:59
Refactor the sqlite3VdbeRecordCompare() routine used to compare btree records. Create a couple of fast-track routines to handle the common cases of a string with BINARY collation or integer values as the left-most column. This gives a significant performance boost in common use. Oops: This build does not work on the Beaglebone where "char" defaults to unsigned. check-in: aec5473a user: drh tags: broken-on-arm
21:46
Fix a couple of harmless compiler warnings. Closed-Leaf check-in: fcf480cc user: drh tags: experimental
17:36
Change an OP_SCopy into an OP_Copy in a case where the destination might be used after the source has changed. check-in: c0fa0c0e user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  4543   4543     BtCursor *pCur,          /* The cursor to be moved */
  4544   4544     UnpackedRecord *pIdxKey, /* Unpacked index key */
  4545   4545     i64 intKey,              /* The table key */
  4546   4546     int biasRight,           /* If true, bias the search to the high end */
  4547   4547     int *pRes                /* Write search results here */
  4548   4548   ){
  4549   4549     int rc;
         4550  +  RecordCompare xRecordCompare;
  4550   4551   
  4551   4552     assert( cursorHoldsMutex(pCur) );
  4552   4553     assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  4553   4554     assert( pRes );
  4554   4555     assert( (pIdxKey==0)==(pCur->pKeyInfo==0) );
  4555   4556   
  4556   4557     /* If the cursor is already positioned at the point we are trying
................................................................................
  4563   4564         return SQLITE_OK;
  4564   4565       }
  4565   4566       if( pCur->atLast && pCur->info.nKey<intKey ){
  4566   4567         *pRes = -1;
  4567   4568         return SQLITE_OK;
  4568   4569       }
  4569   4570     }
         4571  +
         4572  +  if( pIdxKey ){
         4573  +    xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);
         4574  +    assert( pIdxKey->default_rc==1 
         4575  +         || pIdxKey->default_rc==0 
         4576  +         || pIdxKey->default_rc==-1
         4577  +    );
         4578  +  }else{
         4579  +    xRecordCompare = 0; /* Not actually used.  Avoids a compiler warning. */
         4580  +  }
  4570   4581   
  4571   4582     rc = moveToRoot(pCur);
  4572   4583     if( rc ){
  4573   4584       return rc;
  4574   4585     }
  4575   4586     assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage] );
  4576   4587     assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->isInit );
................................................................................
  4648   4659           */
  4649   4660           nCell = pCell[0];
  4650   4661           if( nCell<=pPage->max1bytePayload ){
  4651   4662             /* This branch runs if the record-size field of the cell is a
  4652   4663             ** single byte varint and the record fits entirely on the main
  4653   4664             ** b-tree page.  */
  4654   4665             testcase( pCell+nCell+1==pPage->aDataEnd );
  4655         -          c = sqlite3VdbeRecordCompare(nCell, (void*)&pCell[1], pIdxKey);
         4666  +          c = xRecordCompare(nCell, (void*)&pCell[1], pIdxKey, 0);
  4656   4667           }else if( !(pCell[1] & 0x80) 
  4657   4668             && (nCell = ((nCell&0x7f)<<7) + pCell[1])<=pPage->maxLocal
  4658   4669           ){
  4659   4670             /* The record-size field is a 2 byte varint and the record 
  4660   4671             ** fits entirely on the main b-tree page.  */
  4661   4672             testcase( pCell+nCell+2==pPage->aDataEnd );
  4662         -          c = sqlite3VdbeRecordCompare(nCell, (void*)&pCell[2], pIdxKey);
         4673  +          c = xRecordCompare(nCell, (void*)&pCell[2], pIdxKey, 0);
  4663   4674           }else{
  4664   4675             /* The record flows over onto one or more overflow pages. In
  4665   4676             ** this case the whole cell needs to be parsed, a buffer allocated
  4666   4677             ** and accessPayload() used to retrieve the record into the
  4667   4678             ** buffer before VdbeRecordCompare() can be called. */
  4668   4679             void *pCellKey;
  4669   4680             u8 * const pCellBody = pCell - pPage->childPtrSize;
................................................................................
  4676   4687             }
  4677   4688             pCur->aiIdx[pCur->iPage] = (u16)idx;
  4678   4689             rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
  4679   4690             if( rc ){
  4680   4691               sqlite3_free(pCellKey);
  4681   4692               goto moveto_finish;
  4682   4693             }
  4683         -          c = sqlite3VdbeRecordCompare(nCell, pCellKey, pIdxKey);
         4694  +          c = xRecordCompare(nCell, pCellKey, pIdxKey, 0);
  4684   4695             sqlite3_free(pCellKey);
  4685   4696           }
  4686   4697           if( c<0 ){
  4687   4698             lwr = idx+1;
  4688   4699           }else if( c>0 ){
  4689   4700             upr = idx-1;
  4690   4701           }else{

Changes to src/sqliteInt.h.

  1582   1582   ** Records are used to store the content of a table row and to store
  1583   1583   ** the key of an index.  A blob encoding of a record is created by
  1584   1584   ** the OP_MakeRecord opcode of the VDBE and is disassembled by the
  1585   1585   ** OP_Column opcode.
  1586   1586   **
  1587   1587   ** This structure holds a record that has already been disassembled
  1588   1588   ** into its constituent fields.
         1589  +**
         1590  +** The r1 and r2 member variables are only used by the optimized comparison
         1591  +** functions vdbeRecordCompareInt() and vdbeRecordCompareString().
  1589   1592   */
  1590   1593   struct UnpackedRecord {
  1591   1594     KeyInfo *pKeyInfo;  /* Collation and sort-order information */
  1592   1595     u16 nField;         /* Number of entries in apMem[] */
  1593         -  u8 flags;           /* Boolean settings.  UNPACKED_... below */
         1596  +  char default_rc;    /* Comparison result if keys are equal */
  1594   1597     Mem *aMem;          /* Values */
         1598  +  int r1;             /* Value to return if (lhs > rhs) */
         1599  +  int r2;             /* Value to return if (rhs < lhs) */
  1595   1600   };
  1596   1601   
  1597         -/*
  1598         -** Allowed values of UnpackedRecord.flags
  1599         -*/
  1600         -#define UNPACKED_INCRKEY       0x01  /* Make this key an epsilon larger */
  1601         -#define UNPACKED_PREFIX_MATCH  0x02  /* A prefix match is considered OK */
  1602   1602   
  1603   1603   /*
  1604   1604   ** Each SQL index is represented in memory by an
  1605   1605   ** instance of the following structure.
  1606   1606   **
  1607   1607   ** The columns of the table that are to be indexed are described
  1608   1608   ** by the aiColumn[] field of this structure.  For example, suppose

Changes to src/vdbe.c.

  3556   3556       assert( pOp->p4type==P4_INT32 );
  3557   3557       assert( nField>0 );
  3558   3558       r.pKeyInfo = pC->pKeyInfo;
  3559   3559       r.nField = (u16)nField;
  3560   3560   
  3561   3561       /* The next line of code computes as follows, only faster:
  3562   3562       **   if( oc==OP_SeekGT || oc==OP_SeekLE ){
  3563         -    **     r.flags = UNPACKED_INCRKEY;
         3563  +    **     r.default_rc = -1;
  3564   3564       **   }else{
  3565         -    **     r.flags = 0;
         3565  +    **     r.default_rc = +1;
  3566   3566       **   }
  3567   3567       */
  3568         -    r.flags = (u8)(UNPACKED_INCRKEY * (1 & (oc - OP_SeekLT)));
  3569         -    assert( oc!=OP_SeekGT || r.flags==UNPACKED_INCRKEY );
  3570         -    assert( oc!=OP_SeekLE || r.flags==UNPACKED_INCRKEY );
  3571         -    assert( oc!=OP_SeekGE || r.flags==0 );
  3572         -    assert( oc!=OP_SeekLT || r.flags==0 );
         3568  +    r.default_rc = ((1 & (oc - OP_SeekLT)) ? -1 : +1);
         3569  +    assert( oc!=OP_SeekGT || r.default_rc==-1 );
         3570  +    assert( oc!=OP_SeekLE || r.default_rc==-1 );
         3571  +    assert( oc!=OP_SeekGE || r.default_rc==+1 );
         3572  +    assert( oc!=OP_SeekLT || r.default_rc==+1 );
  3573   3573   
  3574   3574       r.aMem = &aMem[pOp->p3];
  3575   3575   #ifdef SQLITE_DEBUG
  3576   3576       { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
  3577   3577   #endif
  3578   3578       ExpandBlob(r.aMem);
  3579   3579       rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res);
................................................................................
  3723   3723       for(ii=0; ii<r.nField; ii++){
  3724   3724         assert( memIsValid(&r.aMem[ii]) );
  3725   3725         ExpandBlob(&r.aMem[ii]);
  3726   3726   #ifdef SQLITE_DEBUG
  3727   3727         if( ii ) REGISTER_TRACE(pOp->p3+ii, &r.aMem[ii]);
  3728   3728   #endif
  3729   3729       }
  3730         -    r.flags = UNPACKED_PREFIX_MATCH;
  3731   3730       pIdxKey = &r;
  3732   3731     }else{
  3733   3732       pIdxKey = sqlite3VdbeAllocUnpackedRecord(
  3734   3733           pC->pKeyInfo, aTempRec, sizeof(aTempRec), &pFree
  3735   3734       ); 
  3736   3735       if( pIdxKey==0 ) goto no_mem;
  3737   3736       assert( pIn3->flags & MEM_Blob );
  3738   3737       assert( (pIn3->flags & MEM_Zero)==0 );  /* zeroblobs already expanded */
  3739   3738       sqlite3VdbeRecordUnpack(pC->pKeyInfo, pIn3->n, pIn3->z, pIdxKey);
  3740         -    pIdxKey->flags |= UNPACKED_PREFIX_MATCH;
  3741   3739     }
         3740  +  pIdxKey->default_rc = 0;
  3742   3741     if( pOp->opcode==OP_NoConflict ){
  3743   3742       /* For the OP_NoConflict opcode, take the jump if any of the
  3744   3743       ** input fields are NULL, since any key with a NULL will not
  3745   3744       ** conflict */
  3746   3745       for(ii=0; ii<r.nField; ii++){
  3747   3746         if( r.aMem[ii].flags & MEM_Null ){
  3748   3747           pc = pOp->p2 - 1; VdbeBranchTaken(1,2);
................................................................................
  4623   4622     pC = p->apCsr[pOp->p1];
  4624   4623     assert( pC!=0 );
  4625   4624     pCrsr = pC->pCursor;
  4626   4625     assert( pCrsr!=0 );
  4627   4626     assert( pOp->p5==0 );
  4628   4627     r.pKeyInfo = pC->pKeyInfo;
  4629   4628     r.nField = (u16)pOp->p3;
  4630         -  r.flags = UNPACKED_PREFIX_MATCH;
         4629  +  r.default_rc = 0;
  4631   4630     r.aMem = &aMem[pOp->p2];
  4632   4631   #ifdef SQLITE_DEBUG
  4633   4632     { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
  4634   4633   #endif
  4635   4634     rc = sqlite3BtreeMovetoUnpacked(pCrsr, &r, 0, 0, &res);
  4636   4635     if( rc==SQLITE_OK && res==0 ){
  4637   4636       rc = sqlite3BtreeDelete(pCrsr);
................................................................................
  4737   4736     assert( pC->deferredMoveto==0 );
  4738   4737     assert( pOp->p5==0 || pOp->p5==1 );
  4739   4738     assert( pOp->p4type==P4_INT32 );
  4740   4739     r.pKeyInfo = pC->pKeyInfo;
  4741   4740     r.nField = (u16)pOp->p4.i;
  4742   4741     if( pOp->opcode<OP_IdxLT ){
  4743   4742       assert( pOp->opcode==OP_IdxLE || pOp->opcode==OP_IdxGT );
  4744         -    r.flags = UNPACKED_INCRKEY | UNPACKED_PREFIX_MATCH;
         4743  +    r.default_rc = -1;
  4745   4744     }else{
  4746   4745       assert( pOp->opcode==OP_IdxGE || pOp->opcode==OP_IdxLT );
  4747         -    r.flags = UNPACKED_PREFIX_MATCH;
         4746  +    r.default_rc = 0;
  4748   4747     }
  4749   4748     r.aMem = &aMem[pOp->p3];
  4750   4749   #ifdef SQLITE_DEBUG
  4751   4750     { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
  4752   4751   #endif
  4753   4752     res = 0;  /* Not needed.  Only used to silence a warning. */
  4754   4753     rc = sqlite3VdbeIdxKeyCompare(pC, &r, &res);

Changes to src/vdbe.h.

   207    207   sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8);
   208    208   void sqlite3VdbeSetVarmask(Vdbe*, int);
   209    209   #ifndef SQLITE_OMIT_TRACE
   210    210     char *sqlite3VdbeExpandSql(Vdbe*, const char*);
   211    211   #endif
   212    212   
   213    213   void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*);
   214         -int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*);
          214  +int sqlite3VdbeRecordCompare(int,const void*,const UnpackedRecord*,int);
   215    215   UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **);
          216  +
          217  +typedef int (*RecordCompare)(int,const void*,const UnpackedRecord*,int);
          218  +RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*);
   216    219   
   217    220   #ifndef SQLITE_OMIT_TRIGGER
   218    221   void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *);
   219    222   #endif
   220    223   
   221    224   /* Use SQLITE_ENABLE_COMMENTS to enable generation of extra comments on
   222    225   ** each VDBE opcode.

Changes to src/vdbeInt.h.

   387    387   u32 sqlite3VdbeSerialTypeLen(u32);
   388    388   u32 sqlite3VdbeSerialType(Mem*, int);
   389    389   u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32);
   390    390   u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
   391    391   void sqlite3VdbeDeleteAuxData(Vdbe*, int, int);
   392    392   
   393    393   int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
   394         -int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*);
          394  +int sqlite3VdbeIdxKeyCompare(VdbeCursor*,const UnpackedRecord*,int*);
   395    395   int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *);
   396    396   int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
   397    397   int sqlite3VdbeExec(Vdbe*);
   398    398   int sqlite3VdbeList(Vdbe*);
   399    399   int sqlite3VdbeHalt(Vdbe*);
   400    400   int sqlite3VdbeChangeEncoding(Mem *, int);
   401    401   int sqlite3VdbeMemTooBig(Mem*);

Changes to src/vdbeaux.c.

  3099   3099     const unsigned char *aKey = (const unsigned char *)pKey;
  3100   3100     int d; 
  3101   3101     u32 idx;                        /* Offset in aKey[] to read from */
  3102   3102     u16 u;                          /* Unsigned loop counter */
  3103   3103     u32 szHdr;
  3104   3104     Mem *pMem = p->aMem;
  3105   3105   
  3106         -  p->flags = 0;
         3106  +  p->default_rc = 0;
  3107   3107     assert( EIGHT_BYTE_ALIGNMENT(pMem) );
  3108   3108     idx = getVarint32(aKey, szHdr);
  3109   3109     d = szHdr;
  3110   3110     u = 0;
  3111   3111     while( idx<szHdr && u<p->nField && d<=nKey ){
  3112   3112       u32 serial_type;
  3113   3113   
................................................................................
  3120   3120       pMem++;
  3121   3121       u++;
  3122   3122     }
  3123   3123     assert( u<=pKeyInfo->nField + 1 );
  3124   3124     p->nField = u;
  3125   3125   }
  3126   3126   
         3127  +#if SQLITE_DEBUG
  3127   3128   /*
  3128         -** This function compares the two table rows or index records
  3129         -** specified by {nKey1, pKey1} and pPKey2.  It returns a negative, zero
  3130         -** or positive integer if key1 is less than, equal to or 
  3131         -** greater than key2.  The {nKey1, pKey1} key must be a blob
  3132         -** created by th OP_MakeRecord opcode of the VDBE.  The pPKey2
  3133         -** key must be a parsed key such as obtained from
  3134         -** sqlite3VdbeParseRecord.
  3135         -**
  3136         -** Key1 and Key2 do not have to contain the same number of fields.
  3137         -** The key with fewer fields is usually compares less than the 
  3138         -** longer key.  However if the UNPACKED_INCRKEY flags in pPKey2 is set
  3139         -** and the common prefixes are equal, then key1 is less than key2.
  3140         -** Or if the UNPACKED_MATCH_PREFIX flag is set and the prefixes are
  3141         -** equal, then the keys are considered to be equal and
  3142         -** the parts beyond the common prefix are ignored.
         3129  +** This function compares two index or table record keys in the same way
         3130  +** as the sqlite3VdbeRecordCompare() routine. Unlike VdbeRecordCompare(),
         3131  +** this function deserializes and compares values using the
         3132  +** sqlite3VdbeSerialGet() and sqlite3MemCompare() functions. It is used
         3133  +** in assert() statements to ensure that the optimized code in
         3134  +** sqlite3VdbeRecordCompare() returns results with these two primitives.
  3143   3135   */
  3144         -int sqlite3VdbeRecordCompare(
         3136  +static int vdbeRecordCompareDebug(
  3145   3137     int nKey1, const void *pKey1, /* Left key */
  3146         -  UnpackedRecord *pPKey2        /* Right key */
         3138  +  const UnpackedRecord *pPKey2  /* Right key */
  3147   3139   ){
  3148   3140     u32 d1;            /* Offset into aKey[] of next data element */
  3149   3141     u32 idx1;          /* Offset into aKey[] of next header element */
  3150   3142     u32 szHdr1;        /* Number of bytes in header */
  3151   3143     int i = 0;
  3152   3144     int rc = 0;
  3153   3145     const unsigned char *aKey1 = (const unsigned char *)pKey1;
................................................................................
  3213   3205     /* No memory allocation is ever used on mem1.  Prove this using
  3214   3206     ** the following assert().  If the assert() fails, it indicates a
  3215   3207     ** memory leak and a need to call sqlite3VdbeMemRelease(&mem1).
  3216   3208     */
  3217   3209     assert( mem1.zMalloc==0 );
  3218   3210   
  3219   3211     /* rc==0 here means that one of the keys ran out of fields and
  3220         -  ** all the fields up to that point were equal. If the UNPACKED_INCRKEY
  3221         -  ** flag is set, then break the tie by treating key2 as larger.
  3222         -  ** If the UPACKED_PREFIX_MATCH flag is set, then keys with common prefixes
  3223         -  ** are considered to be equal.  Otherwise, the longer key is the 
  3224         -  ** larger.  As it happens, the pPKey2 will always be the longer
  3225         -  ** if there is a difference.
         3212  +  ** all the fields up to that point were equal. Return the the default_rc
         3213  +  ** value.  */
         3214  +  return pPKey2->default_rc;
         3215  +}
         3216  +#endif
         3217  +
         3218  +/*
         3219  +** Both *pMem1 and *pMem2 contain string values. Compare the two values
         3220  +** using the collation sequence pColl. As usual, return a negative , zero
         3221  +** or positive value if *pMem1 is less than, equal to or greater than 
         3222  +** *pMem2, respectively. Similar in spirit to "rc = (*pMem1) - (*pMem2);".
         3223  +*/
         3224  +static int vdbeCompareMemString(
         3225  +  const Mem *pMem1,
         3226  +  const Mem *pMem2,
         3227  +  const CollSeq *pColl
         3228  +){
         3229  +  if( pMem1->enc==pColl->enc ){
         3230  +    /* The strings are already in the correct encoding.  Call the
         3231  +     ** comparison function directly */
         3232  +    return pColl->xCmp(pColl->pUser,pMem1->n,pMem1->z,pMem2->n,pMem2->z);
         3233  +  }else{
         3234  +    int rc;
         3235  +    const void *v1, *v2;
         3236  +    int n1, n2;
         3237  +    Mem c1;
         3238  +    Mem c2;
         3239  +    memset(&c1, 0, sizeof(c1));
         3240  +    memset(&c2, 0, sizeof(c2));
         3241  +    sqlite3VdbeMemShallowCopy(&c1, pMem1, MEM_Ephem);
         3242  +    sqlite3VdbeMemShallowCopy(&c2, pMem2, MEM_Ephem);
         3243  +    v1 = sqlite3ValueText((sqlite3_value*)&c1, pColl->enc);
         3244  +    n1 = v1==0 ? 0 : c1.n;
         3245  +    v2 = sqlite3ValueText((sqlite3_value*)&c2, pColl->enc);
         3246  +    n2 = v2==0 ? 0 : c2.n;
         3247  +    rc = pColl->xCmp(pColl->pUser, n1, v1, n2, v2);
         3248  +    sqlite3VdbeMemRelease(&c1);
         3249  +    sqlite3VdbeMemRelease(&c2);
         3250  +    return rc;
         3251  +  }
         3252  +}
         3253  +
         3254  +/*
         3255  +** Compare the values contained by the two memory cells, returning
         3256  +** negative, zero or positive if pMem1 is less than, equal to, or greater
         3257  +** than pMem2. Sorting order is NULL's first, followed by numbers (integers
         3258  +** and reals) sorted numerically, followed by text ordered by the collating
         3259  +** sequence pColl and finally blob's ordered by memcmp().
         3260  +**
         3261  +** Two NULL values are considered equal by this function.
         3262  +*/
         3263  +int sqlite3MemCompare(const Mem *pMem1, const Mem *pMem2, const CollSeq *pColl){
         3264  +  int rc;
         3265  +  int f1, f2;
         3266  +  int combined_flags;
         3267  +
         3268  +  f1 = pMem1->flags;
         3269  +  f2 = pMem2->flags;
         3270  +  combined_flags = f1|f2;
         3271  +  assert( (combined_flags & MEM_RowSet)==0 );
         3272  + 
         3273  +  /* If one value is NULL, it is less than the other. If both values
         3274  +  ** are NULL, return 0.
         3275  +  */
         3276  +  if( combined_flags&MEM_Null ){
         3277  +    return (f2&MEM_Null) - (f1&MEM_Null);
         3278  +  }
         3279  +
         3280  +  /* If one value is a number and the other is not, the number is less.
         3281  +  ** If both are numbers, compare as reals if one is a real, or as integers
         3282  +  ** if both values are integers.
         3283  +  */
         3284  +  if( combined_flags&(MEM_Int|MEM_Real) ){
         3285  +    double r1, r2;
         3286  +    if( (f1 & f2 & MEM_Int)!=0 ){
         3287  +      if( pMem1->u.i < pMem2->u.i ) return -1;
         3288  +      if( pMem1->u.i > pMem2->u.i ) return 1;
         3289  +      return 0;
         3290  +    }
         3291  +    if( (f1&MEM_Real)!=0 ){
         3292  +      r1 = pMem1->r;
         3293  +    }else if( (f1&MEM_Int)!=0 ){
         3294  +      r1 = (double)pMem1->u.i;
         3295  +    }else{
         3296  +      return 1;
         3297  +    }
         3298  +    if( (f2&MEM_Real)!=0 ){
         3299  +      r2 = pMem2->r;
         3300  +    }else if( (f2&MEM_Int)!=0 ){
         3301  +      r2 = (double)pMem2->u.i;
         3302  +    }else{
         3303  +      return -1;
         3304  +    }
         3305  +    if( r1<r2 ) return -1;
         3306  +    if( r1>r2 ) return 1;
         3307  +    return 0;
         3308  +  }
         3309  +
         3310  +  /* If one value is a string and the other is a blob, the string is less.
         3311  +  ** If both are strings, compare using the collating functions.
  3226   3312     */
  3227         -  assert( rc==0 );
  3228         -  if( pPKey2->flags & UNPACKED_INCRKEY ){
  3229         -    rc = -1;
  3230         -  }else if( pPKey2->flags & UNPACKED_PREFIX_MATCH ){
  3231         -    /* Leave rc==0 */
  3232         -  }else if( idx1<szHdr1 ){
  3233         -    rc = 1;
         3313  +  if( combined_flags&MEM_Str ){
         3314  +    if( (f1 & MEM_Str)==0 ){
         3315  +      return 1;
         3316  +    }
         3317  +    if( (f2 & MEM_Str)==0 ){
         3318  +      return -1;
         3319  +    }
         3320  +
         3321  +    assert( pMem1->enc==pMem2->enc );
         3322  +    assert( pMem1->enc==SQLITE_UTF8 || 
         3323  +            pMem1->enc==SQLITE_UTF16LE || pMem1->enc==SQLITE_UTF16BE );
         3324  +
         3325  +    /* The collation sequence must be defined at this point, even if
         3326  +    ** the user deletes the collation sequence after the vdbe program is
         3327  +    ** compiled (this was not always the case).
         3328  +    */
         3329  +    assert( !pColl || pColl->xCmp );
         3330  +
         3331  +    if( pColl ){
         3332  +      return vdbeCompareMemString(pMem1, pMem2, pColl);
         3333  +    }
         3334  +    /* If a NULL pointer was passed as the collate function, fall through
         3335  +    ** to the blob case and use memcmp().  */
         3336  +  }
         3337  + 
         3338  +  /* Both values must be blobs.  Compare using memcmp().  */
         3339  +  rc = memcmp(pMem1->z, pMem2->z, (pMem1->n>pMem2->n)?pMem2->n:pMem1->n);
         3340  +  if( rc==0 ){
         3341  +    rc = pMem1->n - pMem2->n;
  3234   3342     }
  3235   3343     return rc;
  3236   3344   }
  3237         - 
         3345  +
         3346  +
         3347  +/*
         3348  +** The first argument passed to this function is a serial-type that
         3349  +** corresponds to an integer - all values between 1 and 9 inclusive 
         3350  +** except 7. The second points to a buffer containing an integer value
         3351  +** serialized according to serial_type. This function deserializes
         3352  +** and returns the value.
         3353  +*/
         3354  +static i64 vdbeRecordDecodeInt(u32 serial_type, const u8 *aKey){
         3355  +  assert( CORRUPT_DB || (serial_type>=1 && serial_type<=9 && serial_type!=7) );
         3356  +  switch( serial_type ){
         3357  +    case 0:
         3358  +    case 1:
         3359  +      return (char)aKey[0];
         3360  +    case 2:
         3361  +      return ((char)aKey[0] << 8) | aKey[1];
         3362  +    case 3:
         3363  +      return ((char)aKey[0] << 16) | (aKey[1] << 8) | aKey[2];
         3364  +    case 4:
         3365  +      return ((char)aKey[0]<<24) | (aKey[1]<<16) | (aKey[2]<<8)| aKey[3];
         3366  +    case 5: {
         3367  +      i64 msw = ((char)aKey[0]<<24)|(aKey[1]<<16)|(aKey[2]<<8)|aKey[3];
         3368  +      u32 lsw = (aKey[4] << 8) | aKey[5];
         3369  +      return (i64)( msw << 16 | (u64)lsw );
         3370  +    }
         3371  +    case 6: {
         3372  +      i64 msw = ((char)aKey[0]<<24)|(aKey[1]<<16)|(aKey[2]<<8)|aKey[3];
         3373  +      u32 lsw = ((unsigned)aKey[4]<<24)|(aKey[5]<<16)|(aKey[6]<<8)|aKey[7];
         3374  +      return (i64)( msw << 32 | (u64)lsw );
         3375  +    }
         3376  +  }
         3377  +
         3378  +  return (serial_type - 8);
         3379  +}
         3380  +
         3381  +/*
         3382  +** This function compares the two table rows or index records
         3383  +** specified by {nKey1, pKey1} and pPKey2.  It returns a negative, zero
         3384  +** or positive integer if key1 is less than, equal to or 
         3385  +** greater than key2.  The {nKey1, pKey1} key must be a blob
         3386  +** created by th OP_MakeRecord opcode of the VDBE.  The pPKey2
         3387  +** key must be a parsed key such as obtained from
         3388  +** sqlite3VdbeParseRecord.
         3389  +**
         3390  +** If argument bSkip is non-zero, it is assumed that the caller has already
         3391  +** determined that the first fields of the keys are equal.
         3392  +**
         3393  +** Key1 and Key2 do not have to contain the same number of fields. If all 
         3394  +** fields that appear in both keys are equal, then pPKey2->default_rc is 
         3395  +** returned.
         3396  +*/
         3397  +int sqlite3VdbeRecordCompare(
         3398  +  int nKey1, const void *pKey1,   /* Left key */
         3399  +  const UnpackedRecord *pPKey2,   /* Right key */
         3400  +  int bSkip                       /* If true, skip the first field */
         3401  +){
         3402  +  u32 d1;                         /* Offset into aKey[] of next data element */
         3403  +  int i;                          /* Index of next field to compare */
         3404  +  int szHdr1;                     /* Size of record header in bytes */
         3405  +  u32 idx1;                       /* Offset of first type in header */
         3406  +  int rc = 0;                     /* Return value */
         3407  +  Mem *pRhs = pPKey2->aMem;       /* Next field of pPKey2 to compare */
         3408  +  KeyInfo *pKeyInfo = pPKey2->pKeyInfo;
         3409  +  const unsigned char *aKey1 = (const unsigned char *)pKey1;
         3410  +  Mem mem1;
         3411  +
         3412  +  /* If bSkip is true, then the caller has already determined that the first
         3413  +  ** two elements in the keys are equal. Fix the various stack variables so
         3414  +  ** that this routine begins comparing at the second field. */
         3415  +  if( bSkip ){
         3416  +    u32 s1;
         3417  +    idx1 = 1 + getVarint32(&aKey1[1], s1);
         3418  +    szHdr1 = aKey1[0];
         3419  +    d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1);
         3420  +    i = 1;
         3421  +    pRhs++;
         3422  +  }else{
         3423  +    idx1 = getVarint32(aKey1, szHdr1);
         3424  +    d1 = szHdr1;
         3425  +    i = 0;
         3426  +  }
         3427  +
         3428  +  VVA_ONLY( mem1.zMalloc = 0; ) /* Only needed by assert() statements */
         3429  +  assert( pPKey2->pKeyInfo->nField+pPKey2->pKeyInfo->nXField>=pPKey2->nField 
         3430  +       || CORRUPT_DB );
         3431  +  assert( pPKey2->pKeyInfo->aSortOrder!=0 );
         3432  +  assert( pPKey2->pKeyInfo->nField>0 );
         3433  +  assert( idx1<=szHdr1 || CORRUPT_DB );
         3434  +  do{
         3435  +    u32 serial_type;
         3436  +
         3437  +    /* RHS is an integer */
         3438  +    if( pRhs->flags & MEM_Int ){
         3439  +      serial_type = aKey1[idx1];
         3440  +      if( serial_type>=12 ){
         3441  +        rc = +1;
         3442  +      }else if( serial_type==0 ){
         3443  +        rc = -1;
         3444  +      }else if( serial_type==7 ){
         3445  +        double rhs = (double)pRhs->u.i;
         3446  +        sqlite3VdbeSerialGet(&aKey1[d1], serial_type, &mem1);
         3447  +        if( mem1.r<rhs ){
         3448  +          rc = -1;
         3449  +        }else if( mem1.r>rhs ){
         3450  +          rc = +1;
         3451  +        }
         3452  +      }else{
         3453  +        i64 lhs = vdbeRecordDecodeInt(serial_type, &aKey1[d1]);
         3454  +        i64 rhs = pRhs->u.i;
         3455  +        if( lhs<rhs ){
         3456  +          rc = -1;
         3457  +        }else if( lhs>rhs ){
         3458  +          rc = +1;
         3459  +        }
         3460  +      }
         3461  +    }
         3462  +
         3463  +    /* RHS is real */
         3464  +    else if( pRhs->flags & MEM_Real ){
         3465  +      serial_type = aKey1[idx1];
         3466  +      if( serial_type>=12 ){
         3467  +        rc = +1;
         3468  +      }else if( serial_type==0 ){
         3469  +        rc = -1;
         3470  +      }else{
         3471  +        double rhs = pRhs->r;
         3472  +        double lhs;
         3473  +        sqlite3VdbeSerialGet(&aKey1[d1], serial_type, &mem1);
         3474  +        if( serial_type==7 ){
         3475  +          lhs = mem1.r;
         3476  +        }else{
         3477  +          lhs = (double)mem1.u.i;
         3478  +        }
         3479  +        if( lhs<rhs ){
         3480  +          rc = -1;
         3481  +        }else if( lhs>rhs ){
         3482  +          rc = +1;
         3483  +        }
         3484  +      }
         3485  +    }
         3486  +
         3487  +    /* RHS is a string */
         3488  +    else if( pRhs->flags & MEM_Str ){
         3489  +      getVarint32(&aKey1[idx1], serial_type);
         3490  +      if( serial_type<12 ){
         3491  +        rc = -1;
         3492  +      }else if( !(serial_type & 0x01) ){
         3493  +        rc = +1;
         3494  +      }else{
         3495  +        mem1.n = (serial_type - 12) / 2;
         3496  +        if( (d1+mem1.n) > (unsigned)nKey1 ){
         3497  +          rc = 1;                /* Corruption */
         3498  +        }else if( pKeyInfo->aColl[i] ){
         3499  +          mem1.enc = pKeyInfo->enc;
         3500  +          mem1.db = pKeyInfo->db;
         3501  +          mem1.flags = MEM_Str;
         3502  +          mem1.z = (char*)&aKey1[d1];
         3503  +          rc = vdbeCompareMemString(&mem1, pRhs, pKeyInfo->aColl[i]);
         3504  +        }else{
         3505  +          int nCmp = MIN(mem1.n, pRhs->n);
         3506  +          rc = memcmp(&aKey1[d1], pRhs->z, nCmp);
         3507  +          if( rc==0 ) rc = mem1.n - pRhs->n; 
         3508  +        }
         3509  +      }
         3510  +    }
         3511  +
         3512  +    /* RHS is a blob */
         3513  +    else if( pRhs->flags & MEM_Blob ){
         3514  +      getVarint32(&aKey1[idx1], serial_type);
         3515  +      if( serial_type<12 || (serial_type & 0x01) ){
         3516  +        rc = -1;
         3517  +      }else{
         3518  +        int nStr = (serial_type - 12) / 2;
         3519  +        if( (d1+nStr) > (unsigned)nKey1 ){
         3520  +          rc = 1;                /* Corruption */
         3521  +        }else{
         3522  +          int nCmp = MIN(nStr, pRhs->n);
         3523  +          rc = memcmp(&aKey1[d1], pRhs->z, nCmp);
         3524  +          if( rc==0 ) rc = nStr - pRhs->n;
         3525  +        }
         3526  +      }
         3527  +    }
         3528  +
         3529  +    /* RHS is null */
         3530  +    else{
         3531  +      serial_type = aKey1[idx1];
         3532  +      rc = (serial_type!=0);
         3533  +    }
         3534  +
         3535  +    if( rc!=0 ){
         3536  +      if( pKeyInfo->aSortOrder[i] ){
         3537  +        rc = -rc;
         3538  +      }
         3539  +      assert( CORRUPT_DB 
         3540  +          || (rc<0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)<0)
         3541  +          || (rc>0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)>0)
         3542  +      );
         3543  +      assert( mem1.zMalloc==0 );  /* See comment below */
         3544  +      return rc;
         3545  +    }
         3546  +
         3547  +    i++;
         3548  +    pRhs++;
         3549  +    d1 += sqlite3VdbeSerialTypeLen(serial_type);
         3550  +    idx1 += sqlite3VarintLen(serial_type);
         3551  +  }while( idx1<(unsigned)szHdr1 && i<pPKey2->nField && d1<=(unsigned)nKey1 );
         3552  +
         3553  +  /* No memory allocation is ever used on mem1.  Prove this using
         3554  +  ** the following assert().  If the assert() fails, it indicates a
         3555  +  ** memory leak and a need to call sqlite3VdbeMemRelease(&mem1).  */
         3556  +  assert( mem1.zMalloc==0 );
         3557  +
         3558  +  /* rc==0 here means that one or both of the keys ran out of fields and
         3559  +  ** all the fields up to that point were equal. Return the the default_rc
         3560  +  ** value.  */
         3561  +  assert( CORRUPT_DB 
         3562  +       || pPKey2->default_rc==vdbeRecordCompareDebug(nKey1, pKey1, pPKey2) 
         3563  +  );
         3564  +  return pPKey2->default_rc;
         3565  +}
         3566  +
         3567  +/*
         3568  +** This function is an optimized version of sqlite3VdbeRecordCompare() 
         3569  +** that (a) the first field of pPKey2 is an integer, and (b) the 
         3570  +** size-of-header varint at the start of (pKey1/nKey1) fits in a single
         3571  +** byte (i.e. is less than 128).
         3572  +*/
         3573  +static int vdbeRecordCompareInt(
         3574  +  int nKey1, const void *pKey1, /* Left key */
         3575  +  const UnpackedRecord *pPKey2, /* Right key */
         3576  +  int bSkip                     /* Ignored */
         3577  +){
         3578  +  const u8 *aKey = &((const u8*)pKey1)[*(const u8*)pKey1 & 0x3F];
         3579  +  int serial_type = ((const u8*)pKey1)[1];
         3580  +  int res;
         3581  +  i64 v = pPKey2->aMem[0].u.i;
         3582  +  i64 lhs;
         3583  +  UNUSED_PARAMETER(bSkip);
         3584  +
         3585  +  assert( bSkip==0 );
         3586  +  switch( serial_type ){
         3587  +    case 1:
         3588  +      lhs = (char)(aKey[0]);
         3589  +      break;
         3590  +    case 2:
         3591  +      lhs = 256*(signed char)aKey[0] + aKey[1];
         3592  +      break;
         3593  +    case 3:
         3594  +      lhs = 65536*(char)aKey[0] | (aKey[1]<<8) | aKey[2];
         3595  +      break;
         3596  +    case 4:
         3597  +      lhs = (int)(((u32)aKey[0]<<24) | (aKey[1]<<16) | (aKey[2]<<8)| aKey[3]);
         3598  +      break;
         3599  +    case 5: {
         3600  +      i64 msw = ((char)aKey[0]<<24)|(aKey[1]<<16)|(aKey[2]<<8)|aKey[3];
         3601  +      u32 lsw = (aKey[4] << 8) | aKey[5];
         3602  +      lhs = (i64)( msw << 16 | (u64)lsw );
         3603  +      break;
         3604  +    }
         3605  +    case 6: {
         3606  +      i64 msw = ((char)aKey[0]<<24)|(aKey[1]<<16)|(aKey[2]<<8)|aKey[3];
         3607  +      u32 lsw = ((unsigned)aKey[4]<<24)|(aKey[5]<<16)|(aKey[6]<<8)|aKey[7];
         3608  +      lhs = (i64)( msw << 32 | (u64)lsw );
         3609  +      break;
         3610  +    }
         3611  +    case 8: 
         3612  +      lhs = 0;
         3613  +      break;
         3614  +    case 9:
         3615  +      lhs = 1;
         3616  +      break;
         3617  +
         3618  +    /* This case could be removed without changing the results of running
         3619  +    ** this code. Including it causes gcc to generate a faster switch 
         3620  +    ** statement (since the range of switch targets now starts at zero and
         3621  +    ** is contiguous) but does not cause any duplicate code to be generated
         3622  +    ** (as gcc is clever enough to combine the two like cases). Other 
         3623  +    ** compilers might be similar.  */ 
         3624  +    case 0: case 7:
         3625  +      return sqlite3VdbeRecordCompare(nKey1, pKey1, pPKey2, 0);
         3626  +
         3627  +    default:
         3628  +      return sqlite3VdbeRecordCompare(nKey1, pKey1, pPKey2, 0);
         3629  +  }
         3630  +
         3631  +  if( v>lhs ){
         3632  +    res = pPKey2->r1;
         3633  +  }else if( v<lhs ){
         3634  +    res = pPKey2->r2;
         3635  +  }else if( pPKey2->nField>1 ){
         3636  +    /* The first fields of the two keys are equal. Compare the trailing 
         3637  +    ** fields.  */
         3638  +    res = sqlite3VdbeRecordCompare(nKey1, pKey1, pPKey2, 1);
         3639  +  }else{
         3640  +    /* The first fields of the two keys are equal and there are no trailing
         3641  +    ** fields. Return pPKey2->default_rc in this case. */
         3642  +    res = pPKey2->default_rc;
         3643  +  }
         3644  +
         3645  +  assert( (res==0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)==0)
         3646  +       || (res<0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)<0)
         3647  +       || (res>0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)>0)
         3648  +       || CORRUPT_DB
         3649  +  );
         3650  +  return res;
         3651  +}
         3652  +
         3653  +/*
         3654  +** This function is an optimized version of sqlite3VdbeRecordCompare() 
         3655  +** that (a) the first field of pPKey2 is a string, that (b) the first field
         3656  +** uses the collation sequence BINARY and (c) that the size-of-header varint 
         3657  +** at the start of (pKey1/nKey1) fits in a single byte.
         3658  +*/
         3659  +static int vdbeRecordCompareString(
         3660  +  int nKey1, const void *pKey1, /* Left key */
         3661  +  const UnpackedRecord *pPKey2, /* Right key */
         3662  +  int bSkip
         3663  +){
         3664  +  const u8 *aKey1 = (const u8*)pKey1;
         3665  +  int serial_type;
         3666  +  int res;
         3667  +  UNUSED_PARAMETER(bSkip);
         3668  +
         3669  +  assert( bSkip==0 );
         3670  +  getVarint32(&aKey1[1], serial_type);
         3671  +
         3672  +  if( serial_type<12 ){
         3673  +    res = pPKey2->r1;      /* (pKey1/nKey1) is a number or a null */
         3674  +  }else if( !(serial_type & 0x01) ){ 
         3675  +    res = pPKey2->r2;      /* (pKey1/nKey1) is a blob */
         3676  +  }else{
         3677  +    int nCmp;
         3678  +    int nStr;
         3679  +    int szHdr = aKey1[0];
         3680  +
         3681  +    nStr = (serial_type-12) / 2;
         3682  +    if( (szHdr + nStr) > nKey1 ) return 0;    /* Corruption */
         3683  +    nCmp = MIN( pPKey2->aMem[0].n, nStr );
         3684  +    res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp);
         3685  +
         3686  +    if( res==0 ){
         3687  +      res = nStr - pPKey2->aMem[0].n;
         3688  +      if( res==0 ){
         3689  +        if( pPKey2->nField>1 ){
         3690  +          res = sqlite3VdbeRecordCompare(nKey1, pKey1, pPKey2, 1);
         3691  +        }else{
         3692  +          res = pPKey2->default_rc;
         3693  +        }
         3694  +      }else if( res>0 ){
         3695  +        res = pPKey2->r2;
         3696  +      }else{
         3697  +        res = pPKey2->r1;
         3698  +      }
         3699  +    }else if( res>0 ){
         3700  +      res = pPKey2->r2;
         3701  +    }else{
         3702  +      res = pPKey2->r1;
         3703  +    }
         3704  +  }
         3705  +
         3706  +  assert( (res==0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)==0)
         3707  +       || (res<0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)<0)
         3708  +       || (res>0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)>0)
         3709  +       || CORRUPT_DB
         3710  +  );
         3711  +  return res;
         3712  +}
         3713  +
         3714  +/*
         3715  +** Return a pointer to an sqlite3VdbeRecordCompare() compatible function
         3716  +** suitable for comparing serialized records to the unpacked record passed
         3717  +** as the only argument.
         3718  +*/
         3719  +RecordCompare sqlite3VdbeFindCompare(UnpackedRecord *p){
         3720  +  /* varintRecordCompareInt() and varintRecordCompareString() both assume
         3721  +  ** that the size-of-header varint that occurs at the start of each record
         3722  +  ** fits in a single byte (i.e. is 127 or less). varintRecordCompareInt()
         3723  +  ** also assumes that it is safe to overread a buffer by at least the 
         3724  +  ** maximum possible legal header size plus 8 bytes. Because there is
         3725  +  ** guaranteed to be at least 74 (but not 136) bytes of padding following each
         3726  +  ** buffer passed to varintRecordCompareInt() this makes it convenient to
         3727  +  ** limit the size of the header to 64 bytes in cases where the first field
         3728  +  ** is an integer.
         3729  +  **
         3730  +  ** The easiest way to enforce this limit is to consider only records with
         3731  +  ** 13 fields or less. If the first field is an integer, the maximum legal
         3732  +  ** header size is (12*5 + 1 + 1) bytes.  */
         3733  +  if( (p->pKeyInfo->nField + p->pKeyInfo->nXField)<=13 ){
         3734  +    int flags = p->aMem[0].flags;
         3735  +    if( p->pKeyInfo->aSortOrder[0] ){
         3736  +      p->r1 = 1;
         3737  +      p->r2 = -1;
         3738  +    }else{
         3739  +      p->r1 = -1;
         3740  +      p->r2 = 1;
         3741  +    }
         3742  +    if( (flags & MEM_Int) ){
         3743  +      return vdbeRecordCompareInt;
         3744  +    }
         3745  +    if( (flags & (MEM_Int|MEM_Real|MEM_Null|MEM_Blob))==0 
         3746  +        && p->pKeyInfo->aColl[0]==0 
         3747  +    ){
         3748  +      return vdbeRecordCompareString;
         3749  +    }
         3750  +  }
         3751  +
         3752  +  return sqlite3VdbeRecordCompare;
         3753  +}
  3238   3754   
  3239   3755   /*
  3240   3756   ** pCur points at an index entry created using the OP_MakeRecord opcode.
  3241   3757   ** Read the rowid (the last field in the record) and store it in *rowid.
  3242   3758   ** Return SQLITE_OK if everything works, or an error code otherwise.
  3243   3759   **
  3244   3760   ** pCur might be pointing to text obtained from a corrupt database file.
................................................................................
  3321   3837   **
  3322   3838   ** pUnpacked is either created without a rowid or is truncated so that it
  3323   3839   ** omits the rowid at the end.  The rowid at the end of the index entry
  3324   3840   ** is ignored as well.  Hence, this routine only compares the prefixes 
  3325   3841   ** of the keys prior to the final rowid, not the entire key.
  3326   3842   */
  3327   3843   int sqlite3VdbeIdxKeyCompare(
  3328         -  VdbeCursor *pC,             /* The cursor to compare against */
  3329         -  UnpackedRecord *pUnpacked,  /* Unpacked version of key to compare against */
  3330         -  int *res                    /* Write the comparison result here */
         3844  +  VdbeCursor *pC,                  /* The cursor to compare against */
         3845  +  const UnpackedRecord *pUnpacked, /* Unpacked version of key */
         3846  +  int *res                         /* Write the comparison result here */
  3331   3847   ){
  3332   3848     i64 nCellKey = 0;
  3333   3849     int rc;
  3334   3850     BtCursor *pCur = pC->pCursor;
  3335   3851     Mem m;
  3336   3852   
  3337   3853     assert( sqlite3BtreeCursorIsValid(pCur) );
  3338   3854     VVA_ONLY(rc =) sqlite3BtreeKeySize(pCur, &nCellKey);
  3339   3855     assert( rc==SQLITE_OK );    /* pCur is always valid so KeySize cannot fail */
  3340         -  /* nCellKey will always be between 0 and 0xffffffff because of the say
         3856  +  /* nCellKey will always be between 0 and 0xffffffff because of the way
  3341   3857     ** that btreeParseCellPtr() and sqlite3GetVarint32() are implemented */
  3342   3858     if( nCellKey<=0 || nCellKey>0x7fffffff ){
  3343   3859       *res = 0;
  3344   3860       return SQLITE_CORRUPT_BKPT;
  3345   3861     }
  3346   3862     memset(&m, 0, sizeof(m));
  3347   3863     rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, (u32)nCellKey, 1, &m);
  3348   3864     if( rc ){
  3349   3865       return rc;
  3350   3866     }
  3351         -  assert( pUnpacked->flags & UNPACKED_PREFIX_MATCH );
  3352         -  *res = sqlite3VdbeRecordCompare(m.n, m.z, pUnpacked);
         3867  +  *res = sqlite3VdbeRecordCompare(m.n, m.z, pUnpacked, 0);
  3353   3868     sqlite3VdbeMemRelease(&m);
  3354   3869     return SQLITE_OK;
  3355   3870   }
  3356   3871   
  3357   3872   /*
  3358   3873   ** This routine sets the value to be returned by subsequent calls to
  3359   3874   ** sqlite3_changes() on the database handle 'db'. 

Changes to src/vdbemem.c.

   783    783     if( nByte>iLimit ){
   784    784       return SQLITE_TOOBIG;
   785    785     }
   786    786   
   787    787     return SQLITE_OK;
   788    788   }
   789    789   
   790         -/*
   791         -** Compare the values contained by the two memory cells, returning
   792         -** negative, zero or positive if pMem1 is less than, equal to, or greater
   793         -** than pMem2. Sorting order is NULL's first, followed by numbers (integers
   794         -** and reals) sorted numerically, followed by text ordered by the collating
   795         -** sequence pColl and finally blob's ordered by memcmp().
   796         -**
   797         -** Two NULL values are considered equal by this function.
   798         -*/
   799         -int sqlite3MemCompare(const Mem *pMem1, const Mem *pMem2, const CollSeq *pColl){
   800         -  int rc;
   801         -  int f1, f2;
   802         -  int combined_flags;
   803         -
   804         -  f1 = pMem1->flags;
   805         -  f2 = pMem2->flags;
   806         -  combined_flags = f1|f2;
   807         -  assert( (combined_flags & MEM_RowSet)==0 );
   808         - 
   809         -  /* If one value is NULL, it is less than the other. If both values
   810         -  ** are NULL, return 0.
   811         -  */
   812         -  if( combined_flags&MEM_Null ){
   813         -    return (f2&MEM_Null) - (f1&MEM_Null);
   814         -  }
   815         -
   816         -  /* If one value is a number and the other is not, the number is less.
   817         -  ** If both are numbers, compare as reals if one is a real, or as integers
   818         -  ** if both values are integers.
   819         -  */
   820         -  if( combined_flags&(MEM_Int|MEM_Real) ){
   821         -    double r1, r2;
   822         -    if( (f1 & f2 & MEM_Int)!=0 ){
   823         -      if( pMem1->u.i < pMem2->u.i ) return -1;
   824         -      if( pMem1->u.i > pMem2->u.i ) return 1;
   825         -      return 0;
   826         -    }
   827         -    if( (f1&MEM_Real)!=0 ){
   828         -      r1 = pMem1->r;
   829         -    }else if( (f1&MEM_Int)!=0 ){
   830         -      r1 = (double)pMem1->u.i;
   831         -    }else{
   832         -      return 1;
   833         -    }
   834         -    if( (f2&MEM_Real)!=0 ){
   835         -      r2 = pMem2->r;
   836         -    }else if( (f2&MEM_Int)!=0 ){
   837         -      r2 = (double)pMem2->u.i;
   838         -    }else{
   839         -      return -1;
   840         -    }
   841         -    if( r1<r2 ) return -1;
   842         -    if( r1>r2 ) return 1;
   843         -    return 0;
   844         -  }
   845         -
   846         -  /* If one value is a string and the other is a blob, the string is less.
   847         -  ** If both are strings, compare using the collating functions.
   848         -  */
   849         -  if( combined_flags&MEM_Str ){
   850         -    if( (f1 & MEM_Str)==0 ){
   851         -      return 1;
   852         -    }
   853         -    if( (f2 & MEM_Str)==0 ){
   854         -      return -1;
   855         -    }
   856         -
   857         -    assert( pMem1->enc==pMem2->enc );
   858         -    assert( pMem1->enc==SQLITE_UTF8 || 
   859         -            pMem1->enc==SQLITE_UTF16LE || pMem1->enc==SQLITE_UTF16BE );
   860         -
   861         -    /* The collation sequence must be defined at this point, even if
   862         -    ** the user deletes the collation sequence after the vdbe program is
   863         -    ** compiled (this was not always the case).
   864         -    */
   865         -    assert( !pColl || pColl->xCmp );
   866         -
   867         -    if( pColl ){
   868         -      if( pMem1->enc==pColl->enc ){
   869         -        /* The strings are already in the correct encoding.  Call the
   870         -        ** comparison function directly */
   871         -        return pColl->xCmp(pColl->pUser,pMem1->n,pMem1->z,pMem2->n,pMem2->z);
   872         -      }else{
   873         -        const void *v1, *v2;
   874         -        int n1, n2;
   875         -        Mem c1;
   876         -        Mem c2;
   877         -        memset(&c1, 0, sizeof(c1));
   878         -        memset(&c2, 0, sizeof(c2));
   879         -        sqlite3VdbeMemShallowCopy(&c1, pMem1, MEM_Ephem);
   880         -        sqlite3VdbeMemShallowCopy(&c2, pMem2, MEM_Ephem);
   881         -        v1 = sqlite3ValueText((sqlite3_value*)&c1, pColl->enc);
   882         -        n1 = v1==0 ? 0 : c1.n;
   883         -        v2 = sqlite3ValueText((sqlite3_value*)&c2, pColl->enc);
   884         -        n2 = v2==0 ? 0 : c2.n;
   885         -        rc = pColl->xCmp(pColl->pUser, n1, v1, n2, v2);
   886         -        sqlite3VdbeMemRelease(&c1);
   887         -        sqlite3VdbeMemRelease(&c2);
   888         -        return rc;
   889         -      }
   890         -    }
   891         -    /* If a NULL pointer was passed as the collate function, fall through
   892         -    ** to the blob case and use memcmp().  */
   893         -  }
   894         - 
   895         -  /* Both values must be blobs.  Compare using memcmp().  */
   896         -  rc = memcmp(pMem1->z, pMem2->z, (pMem1->n>pMem2->n)?pMem2->n:pMem1->n);
   897         -  if( rc==0 ){
   898         -    rc = pMem1->n - pMem2->n;
   899         -  }
   900         -  return rc;
   901         -}
   902         -
   903    790   /*
   904    791   ** Move data out of a btree key or data field and into a Mem structure.
   905    792   ** The data or key is taken from the entry that pCur is currently pointing
   906    793   ** to.  offset and amt determine what portion of the data or key to retrieve.
   907    794   ** key is true to get the key or false to get data.  The result is written
   908    795   ** into the pMem element.
   909    796   **
................................................................................
  1055    942         nByte = sizeof(Mem) * nCol + ROUND8(sizeof(UnpackedRecord));
  1056    943         pRec = (UnpackedRecord*)sqlite3DbMallocZero(db, nByte);
  1057    944         if( pRec ){
  1058    945           pRec->pKeyInfo = sqlite3KeyInfoOfIndex(p->pParse, pIdx);
  1059    946           if( pRec->pKeyInfo ){
  1060    947             assert( pRec->pKeyInfo->nField+pRec->pKeyInfo->nXField==nCol );
  1061    948             assert( pRec->pKeyInfo->enc==ENC(db) );
  1062         -          pRec->flags = UNPACKED_PREFIX_MATCH;
  1063    949             pRec->aMem = (Mem *)((u8*)pRec + ROUND8(sizeof(UnpackedRecord)));
  1064    950             for(i=0; i<nCol; i++){
  1065    951               pRec->aMem[i].flags = MEM_Null;
  1066    952               pRec->aMem[i].memType = MEM_Null;
  1067    953               pRec->aMem[i].db = db;
  1068    954             }
  1069    955           }else{

Changes to src/vdbesort.c.

   405    405       assert( r2->nField>0 );
   406    406       for(i=0; i<r2->nField; i++){
   407    407         if( r2->aMem[i].flags & MEM_Null ){
   408    408           *pRes = -1;
   409    409           return;
   410    410         }
   411    411       }
   412         -    r2->flags |= UNPACKED_PREFIX_MATCH;
          412  +    assert( r2->default_rc==0 );
   413    413     }
   414    414   
   415         -  *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2);
          415  +  *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2, 0);
   416    416   }
   417    417   
   418    418   /*
   419    419   ** This function is called to compare two iterator keys when merging 
   420    420   ** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
   421    421   ** value to recalculate.
   422    422   */

Changes to src/where.c.

  1909   1909   #endif
  1910   1910     assert( pRec!=0 );
  1911   1911     iCol = pRec->nField - 1;
  1912   1912     assert( pIdx->nSample>0 );
  1913   1913     assert( pRec->nField>0 && iCol<pIdx->nSampleCol );
  1914   1914     do{
  1915   1915       iTest = (iMin+i)/2;
  1916         -    res = sqlite3VdbeRecordCompare(aSample[iTest].n, aSample[iTest].p, pRec);
         1916  +    res = sqlite3VdbeRecordCompare(aSample[iTest].n, aSample[iTest].p, pRec, 0);
  1917   1917       if( res<0 ){
  1918   1918         iMin = iTest+1;
  1919   1919       }else{
  1920   1920         i = iTest;
  1921   1921       }
  1922   1922     }while( res && iMin<i );
  1923   1923   
................................................................................
  1924   1924   #ifdef SQLITE_DEBUG
  1925   1925     /* The following assert statements check that the binary search code
  1926   1926     ** above found the right answer. This block serves no purpose other
  1927   1927     ** than to invoke the asserts.  */
  1928   1928     if( res==0 ){
  1929   1929       /* If (res==0) is true, then sample $i must be equal to pRec */
  1930   1930       assert( i<pIdx->nSample );
  1931         -    assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)
         1931  +    assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec, 0)
  1932   1932            || pParse->db->mallocFailed );
  1933   1933     }else{
  1934   1934       /* Otherwise, pRec must be smaller than sample $i and larger than
  1935   1935       ** sample ($i-1).  */
  1936   1936       assert( i==pIdx->nSample 
  1937         -         || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0
         1937  +         || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec, 0)>0
  1938   1938            || pParse->db->mallocFailed );
  1939   1939       assert( i==0
  1940         -         || sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0
         1940  +         || sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec, 0)<0
  1941   1941            || pParse->db->mallocFailed );
  1942   1942     }
  1943   1943   #endif /* ifdef SQLITE_DEBUG */
  1944   1944   
  1945   1945     /* At this point, aSample[i] is the first sample that is greater than
  1946   1946     ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  1947   1947     ** than pVal.  If aSample[i]==pVal, then res==0.

Changes to test/analyze9.test.

   322    322   #-------------------------------------------------------------------------
   323    323   # The following tests experiment with adding corrupted records to the
   324    324   # 'sample' column of the sqlite_stat4 table.
   325    325   #
   326    326   reset_db
   327    327   sqlite3_db_config_lookaside db 0 0 0
   328    328   
          329  +database_may_be_corrupt
   329    330   do_execsql_test 7.1 {
   330    331     CREATE TABLE t1(a, b);
   331    332     CREATE INDEX i1 ON t1(a, b);
   332    333     INSERT INTO t1 VALUES(1, 1);
   333    334     INSERT INTO t1 VALUES(2, 2);
   334    335     INSERT INTO t1 VALUES(3, 3);
   335    336     INSERT INTO t1 VALUES(4, 4);
................................................................................
   361    362   
   362    363   do_execsql_test 7.5 {
   363    364     ANALYZE;
   364    365     UPDATE sqlite_stat4 SET nlt = '0 0 0';
   365    366     ANALYZE sqlite_master;
   366    367     SELECT * FROM t1 WHERE a = 5;
   367    368   } {5 5}
          369  +
          370  +database_never_corrupt
   368    371   
   369    372   #-------------------------------------------------------------------------
   370    373   #
   371    374   reset_db
   372    375   do_execsql_test 8.1 {
   373    376     CREATE TABLE t1(x TEXT);
   374    377     CREATE INDEX i1 ON t1(x);

Changes to test/corruptG.test.

    72     72       SELECT rowid FROM t1 WHERE a='abc' and b='xyz123456789XYZ';
    73     73     }
    74     74     # The following test result is brittle.  The point above is to try to
    75     75     # force a buffer overread by a corrupt database file.  If we get an
    76     76     # incorrect answer from a corrupt database file, that is OK.  If the
    77     77     # result below changes, that just means that "undefined behavior" has
    78     78     # changed.
    79         -} {0 52}
           79  +} {/0 .*/}
    80     80   
    81     81   finish_test

Added test/corruptI.test.

            1  +# 2014-01-20
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +
           13  +set testdir [file dirname $argv0]
           14  +source $testdir/tester.tcl
           15  +set testprefix corruptI
           16  +
           17  +# Do not use a codec for tests in this file, as the database file is
           18  +# manipulated directly using tcl scripts (using the [hexio_write] command).
           19  +#
           20  +do_not_use_codec
           21  +database_may_be_corrupt
           22  +
           23  +# Initialize the database.
           24  +#
           25  +do_execsql_test 1.1 {
           26  +  PRAGMA page_size=1024;
           27  +  PRAGMA auto_vacuum=0;
           28  +  CREATE TABLE t1(a);
           29  +  CREATE INDEX i1 ON t1(a);
           30  +  INSERT INTO t1 VALUES('a');
           31  +} {}
           32  +db close
           33  +
           34  +do_test 1.2 {
           35  +  set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]]
           36  +  set off [expr 2*1024 + $offset + 1]
           37  +  hexio_write test.db $off FF06
           38  +
           39  +  breakpoint
           40  +
           41  +  sqlite3 db test.db
           42  +  catchsql { SELECT * FROM t1 WHERE a = 10 }
           43  +} {1 {database disk image is malformed}}
           44  +
           45  +
           46  +finish_test
           47  +

Changes to test/pragma.test.

  1571   1571   do_test pragma-20.8 {
  1572   1572     catchsql {PRAGMA data_store_directory}
  1573   1573   } {0 {}}
  1574   1574   
  1575   1575   forcedelete data_dir
  1576   1576   } ;# endif windows
  1577   1577   
         1578  +database_may_be_corrupt
         1579  +
  1578   1580   do_test 21.1 {
  1579   1581     # Create a corrupt database in testerr.db. And a non-corrupt at test.db.
  1580   1582     #
  1581   1583     db close
  1582   1584     forcedelete test.db
  1583   1585     sqlite3 db test.db
  1584   1586     execsql { 
................................................................................
  1596   1598   } {100}
  1597   1599   
  1598   1600   set mainerr {*** in database main ***
  1599   1601   Multiple uses for byte 672 of page 15}
  1600   1602   set auxerr {*** in database aux ***
  1601   1603   Multiple uses for byte 672 of page 15}
  1602   1604   
         1605  +set mainerr {/{\*\*\* in database main \*\*\*
         1606  +Multiple uses for byte 672 of page 15}.*/}
         1607  +set auxerr {/{\*\*\* in database aux \*\*\*
         1608  +Multiple uses for byte 672 of page 15}.*/}
         1609  +
  1603   1610   do_test 22.2 {
  1604   1611     catch { db close }
  1605   1612     sqlite3 db testerr.db
  1606   1613     execsql { PRAGMA integrity_check }
  1607         -} [list $mainerr]
         1614  +} $mainerr
  1608   1615   
  1609   1616   do_test 22.3.1 {
  1610   1617     catch { db close }
  1611   1618     sqlite3 db test.db
  1612   1619     execsql { 
  1613   1620       ATTACH 'testerr.db' AS 'aux';
  1614   1621       PRAGMA integrity_check;
  1615   1622     }
  1616         -} [list $auxerr]
         1623  +} $auxerr
  1617   1624   do_test 22.3.2 {
  1618   1625     execsql { PRAGMA main.integrity_check; }
  1619   1626   } {ok}
  1620   1627   do_test 22.3.3 {
  1621   1628     execsql { PRAGMA aux.integrity_check; }
  1622         -} [list $auxerr]
         1629  +} $auxerr
  1623   1630   
  1624   1631   do_test 22.4.1 {
  1625   1632     catch { db close }
  1626   1633     sqlite3 db testerr.db
  1627   1634     execsql { 
  1628   1635       ATTACH 'test.db' AS 'aux';
  1629   1636       PRAGMA integrity_check;
  1630   1637     }
  1631         -} [list $mainerr]
         1638  +} $mainerr
  1632   1639   do_test 22.4.2 {
  1633   1640     execsql { PRAGMA main.integrity_check; }
  1634         -} [list $mainerr]
         1641  +} $mainerr
  1635   1642   do_test 22.4.3 {
  1636   1643     execsql { PRAGMA aux.integrity_check; }
  1637   1644   } {ok}
  1638   1645   
  1639   1646   db close
  1640   1647   forcedelete test.db test.db-wal test.db-journal
  1641   1648   sqlite3 db test.db
................................................................................
  1676   1683       CREATE TABLE t2(x, y INTEGER REFERENCES t1);
  1677   1684     }
  1678   1685     db2 eval {
  1679   1686       PRAGMA foreign_key_list(t2);
  1680   1687     }
  1681   1688   } {0 0 t1 y {} {NO ACTION} {NO ACTION} NONE}
  1682   1689   
         1690  +database_never_corrupt
  1683   1691   finish_test