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 | SQL archive |
| Timelines: | family | ancestors | descendants | both | sqlite_stat4 |
| Files: | files | file ages | folders |
| SHA1: | e50dc30523210ba12324d5d837950361 |
| User & Date: | dan 2013-08-08 16:17:12 |
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: 9228aaf5 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: e50dc305 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: 9fec3e38 user: dan tags: sqlite_stat4 | |
Changes
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];
|