SQLite

Check-in [e50dc30523]
Login

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

Overview
Comment:Use a binary search instead of a linear scan when comparing a sample key against data from the sqlite_stat4 table.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | sqlite_stat4
Files: files | file ages | folders
SHA1: e50dc30523210ba12324d5d8379503610f13aa34
User & Date: dan 2013-08-08 16:17:12.293
Context
2013-08-08
19:38
Fix problems in estimating the number of rows visited by a range query using sqlite_stat4 data when the column subject to the range query is not the leftmost of the index. (check-in: 9228aaf54d user: dan tags: sqlite_stat4)
16:17
Use a binary search instead of a linear scan when comparing a sample key against data from the sqlite_stat4 table. (check-in: e50dc30523 user: dan tags: sqlite_stat4)
12:21
Fix a segfault in "ALTER TABLE t1 ADD COLUMN b DEFAULT (-+1)". Also an assert() failure that could occur if SQLITE_ENABLE_STAT4 were not defined. (check-in: 9fec3e3828 user: dan tags: sqlite_stat4)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420




2421

2422
2423


2424
2425
2426
2427

2428

2429

















2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  UnpackedRecord *pRec,       /* Vector of values to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  IndexSample *aSample = pIdx->aSample;
  int i;
  int isEq = 0;
  int iCol = pRec->nField-1;






  assert( pRec->nField>0 && iCol<pIdx->nColumn );
  for(i=0; i<pIdx->nSample; i++){


    int res = sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec);
    if( res>=0 ){
      isEq = (res==0);
      break;

    }

  }


















  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */
  if( isEq ){
    assert( i<pIdx->nSample );
    aStat[0] = aSample[i].anLt[iCol];
    aStat[1] = aSample[i].anEq[iCol];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[iCol];







<
<
|
>
>
>
>

>

<
>
>
|
|
|
|
>

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



|

|
<







2411
2412
2413
2414
2415
2416
2417


2418
2419
2420
2421
2422
2423
2424
2425

2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458

2459
2460
2461
2462
2463
2464
2465
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  UnpackedRecord *pRec,       /* Vector of values to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  IndexSample *aSample = pIdx->aSample;


  int iCol = pRec->nField-1;  /* Index of required stats in anEq[] etc. */
  int iMin = 0;               /* Smallest sample not yet tested */
  int i = pIdx->nSample;      /* Smallest sample larger than or equal to pRec */
  int iTest;                  /* Next sample to test */
  int res;                    /* Result of comparison operation */

  assert( pIdx->nSample>0 );
  assert( pRec->nField>0 && iCol<pIdx->nColumn );

  do{
    iTest = (iMin+i)/2;
    res = sqlite3VdbeRecordCompare(aSample[iTest].n, aSample[iTest].p, pRec);
    if( res<0 ){
      iMin = iTest+1;
    }else{
      i = iTest;
    }
  }while( res && iMin<i );

#ifdef SQLITE_DEBUG
  /* The following assert statements check that the binary search code
  ** above found the right answer. This block serves no purpose other
  ** than to invoke the asserts.  */
  if( res==0 ){
    /* If (res==0) is true, then sample $i must be equal to pRec */
    assert( i<pIdx->nSample );
    assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec) );
  }else{
    /* Otherwise, pRec must be smaller than sample $i and larger than
    ** sample ($i-1).  */
    assert( i==pIdx->nSample 
         || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0 );
    assert( i==0
         || sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0 );
  }
#endif /* ifdef SQLITE_DEBUG */

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then res==0.
  */
  if( res==0 ){

    aStat[0] = aSample[i].anLt[iCol];
    aStat[1] = aSample[i].anEq[iCol];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[iCol];