Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add the ability to use indices when a range contraint is bounded on the lower end by NULL. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | stat2-enhancement |
| Files: | files | file ages | folders |
| SHA1: |
f73a167b434fadcbbd15e3891c4b7f4f |
| User & Date: | drh 2011-01-21 14:37:04 |
References
|
2011-04-08
| ||
| 23:05 | Make sure the query planner is able to correctly analyze NULL value samples in the sqlite_stat2 table. This is a backport of changes from check-in [f73a167b434f] (check-in: 1d637889 user: drh tags: branch-3.7.2) | |
Context
|
2011-01-21
| ||
| 16:27 | Make use of histogram data to make better estimates for the number of rows that will be returned from "x IN (v1,v2,v3,...)" constraints. (check-in: fd3977a2 user: drh tags: stat2-enhancement) | |
| 14:37 | Add the ability to use indices when a range contraint is bounded on the lower end by NULL. (check-in: f73a167b user: drh tags: stat2-enhancement) | |
|
2011-01-20
| ||
| 20:36 | Update ANALYZE test cases to check out the use of histograms for equality constraints. (check-in: c7b59afa user: drh tags: stat2-enhancement) | |
Changes
Changes to src/vdbemem.c.
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 |
if( SQLITE_OK==sqlite3ValueFromExpr(db,pExpr->pLeft,enc,affinity,&pVal) ){
sqlite3VdbeMemNumerify(pVal);
pVal->u.i = -1 * pVal->u.i;
/* (double)-1 In case of SQLITE_OMIT_FLOATING_POINT... */
pVal->r = (double)-1 * pVal->r;
sqlite3ValueApplyAffinity(pVal, affinity, enc);
}
}
#ifndef SQLITE_OMIT_BLOB_LITERAL
else if( op==TK_BLOB ){
int nVal;
assert( pExpr->u.zToken[0]=='x' || pExpr->u.zToken[0]=='X' );
assert( pExpr->u.zToken[1]=='\'' );
pVal = sqlite3ValueNew(db);
|
> > |
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 |
if( SQLITE_OK==sqlite3ValueFromExpr(db,pExpr->pLeft,enc,affinity,&pVal) ){
sqlite3VdbeMemNumerify(pVal);
pVal->u.i = -1 * pVal->u.i;
/* (double)-1 In case of SQLITE_OMIT_FLOATING_POINT... */
pVal->r = (double)-1 * pVal->r;
sqlite3ValueApplyAffinity(pVal, affinity, enc);
}
}else if( op==TK_NULL ){
pVal = sqlite3ValueNew(db);
}
#ifndef SQLITE_OMIT_BLOB_LITERAL
else if( op==TK_BLOB ){
int nVal;
assert( pExpr->u.zToken[0]=='x' || pExpr->u.zToken[0]=='X' );
assert( pExpr->u.zToken[1]=='\'' );
pVal = sqlite3ValueNew(db);
|
Changes to src/where.c.
2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 .... 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 .... 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 .... 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 .... 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 .... 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 |
if( aSample[i].eType>=SQLITE_TEXT ) break;
if( roundUp ){
if( aSample[i].u.r>r ) break;
}else{
if( aSample[i].u.r>=r ) break;
}
}
}else{
sqlite3 *db = pParse->db;
CollSeq *pColl;
const u8 *z;
int n;
/* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
................................................................................
if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
}else{
rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
if( rc==SQLITE_OK ){
rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
}
}
iEst = iUpper - iLower;
testcase( iEst==SQLITE_INDEX_SAMPLES );
assert( iEst<=SQLITE_INDEX_SAMPLES );
if( iEst<1 ){
*piEst = 50/SQLITE_INDEX_SAMPLES;
}else{
................................................................................
** an equality constraint x=VALUE and where that VALUE occurs in
** the histogram data. This only works when x is the left-most
** column of an index and sqlite_stat2 histogram data is available
** for that index.
**
** Write the estimated row count into *pnRow. If unable to make
** an estimate, leave *pnRow unchanged.
*/
void whereEqScanEst(
Parse *pParse, /* Parsing & code generating context */
Index *p, /* The index whose left-most column is pTerm */
WhereTerm *pTerm, /* The x=VALUE constraint */
double *pnRow /* Write the revised row estimate here */
){
................................................................................
aff = p->pTable->aCol[p->aiColumn[0]].affinity;
rc = valueFromExpr(pParse, pTerm->pExpr->pRight, aff, &pRhs);
if( rc ) goto whereEqScanEst_cancel;
rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
if( rc ) goto whereEqScanEst_cancel;
rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
if( rc ) goto whereEqScanEst_cancel;
if( iLower>=iUpper ){
nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
if( nRowEst<*pnRow ) *pnRow = nRowEst;
}else{
nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
*pnRow = nRowEst;
}
................................................................................
pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
if( pTerm==0 ) break;
wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
if( pTerm->eOperator & WO_IN ){
Expr *pExpr = pTerm->pExpr;
wsFlags |= WHERE_COLUMN_IN;
if( ExprHasProperty(pExpr, EP_xIsSelect) ){
nInMul *= 25;
bInEst = 1;
}else if( ALWAYS(pExpr->x.pList) ){
nInMul *= pExpr->x.pList->nExpr + 1;
}
}else if( pTerm->eOperator & WO_ISNULL ){
wsFlags |= WHERE_COLUMN_NULL;
}
#ifdef SQLITE_ENABLE_STAT2
else if( nEq==0 && pProbe->aSample ){
................................................................................
wsFlags |= WHERE_IDX_ONLY;
}else{
bLookup = 1;
}
}
/*
** Estimate the number of rows of output. For an IN operator,
** do not let the estimate exceed half the rows in the table.
*/
nRow = (double)(aiRowEst[nEq] * nInMul);
if( bInEst && nRow*2>aiRowEst[0] ){
nRow = aiRowEst[0]/2;
nInMul = (int)(nRow / aiRowEst[nEq]);
}
|
> > > > > > > > > > > > > > | | |
2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 .... 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 .... 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 .... 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 .... 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 .... 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 |
if( aSample[i].eType>=SQLITE_TEXT ) break;
if( roundUp ){
if( aSample[i].u.r>r ) break;
}else{
if( aSample[i].u.r>=r ) break;
}
}
}else if( eType==SQLITE_NULL ){
i = 0;
if( roundUp ){
while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
}
}else{
sqlite3 *db = pParse->db;
CollSeq *pColl;
const u8 *z;
int n;
/* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
................................................................................
if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
}else{
rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
if( rc==SQLITE_OK ){
rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
}
}
WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
iEst = iUpper - iLower;
testcase( iEst==SQLITE_INDEX_SAMPLES );
assert( iEst<=SQLITE_INDEX_SAMPLES );
if( iEst<1 ){
*piEst = 50/SQLITE_INDEX_SAMPLES;
}else{
................................................................................
** an equality constraint x=VALUE and where that VALUE occurs in
** the histogram data. This only works when x is the left-most
** column of an index and sqlite_stat2 histogram data is available
** for that index.
**
** Write the estimated row count into *pnRow. If unable to make
** an estimate, leave *pnRow unchanged.
**
** This routine can fail if it is unable to load a collating sequence
** required for string comparison, or if unable to allocate memory
** for a UTF conversion required for comparison. The error is stored
** in the pParse structure.
*/
void whereEqScanEst(
Parse *pParse, /* Parsing & code generating context */
Index *p, /* The index whose left-most column is pTerm */
WhereTerm *pTerm, /* The x=VALUE constraint */
double *pnRow /* Write the revised row estimate here */
){
................................................................................
aff = p->pTable->aCol[p->aiColumn[0]].affinity;
rc = valueFromExpr(pParse, pTerm->pExpr->pRight, aff, &pRhs);
if( rc ) goto whereEqScanEst_cancel;
rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
if( rc ) goto whereEqScanEst_cancel;
rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
if( rc ) goto whereEqScanEst_cancel;
WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
if( iLower>=iUpper ){
nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
if( nRowEst<*pnRow ) *pnRow = nRowEst;
}else{
nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
*pnRow = nRowEst;
}
................................................................................
pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
if( pTerm==0 ) break;
wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
if( pTerm->eOperator & WO_IN ){
Expr *pExpr = pTerm->pExpr;
wsFlags |= WHERE_COLUMN_IN;
if( ExprHasProperty(pExpr, EP_xIsSelect) ){
/* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */
nInMul *= 25;
bInEst = 1;
}else if( ALWAYS(pExpr->x.pList) ){
/* "x IN (value, value, ...)" */
nInMul *= pExpr->x.pList->nExpr + 1;
}
}else if( pTerm->eOperator & WO_ISNULL ){
wsFlags |= WHERE_COLUMN_NULL;
}
#ifdef SQLITE_ENABLE_STAT2
else if( nEq==0 && pProbe->aSample ){
................................................................................
wsFlags |= WHERE_IDX_ONLY;
}else{
bLookup = 1;
}
}
/*
** Estimate the number of rows of output. For an "x IN (SELECT...)"
** constraint, do not let the estimate exceed half the rows in the table.
*/
nRow = (double)(aiRowEst[nEq] * nInMul);
if( bInEst && nRow*2>aiRowEst[0] ){
nRow = aiRowEst[0]/2;
nInMul = (int)(nRow / aiRowEst[nEq]);
}
|