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 |
Timelines: | family | ancestors | descendants | both | stat2-enhancement |
Files: | files | file ages | folders |
SHA1: |
f73a167b434fadcbbd15e3891c4b7f4f |
User & Date: | drh 2011-01-21 14:37:04.663 |
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: 1d6378898a 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: fd3977a27a 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: f73a167b43 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: c7b59afaf0 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 | 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 */ | > > > > > | 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 | 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 */ |
︙ | ︙ | |||
2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 | 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{ | > | 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 | 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{ |
︙ | ︙ | |||
2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 | ** 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 */ ){ | > > > > > | 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 | ** 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 */ ){ |
︙ | ︙ | |||
2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 | 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; } | > | 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 | 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; } |
︙ | ︙ | |||
2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 | 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 ){ | > > | 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 | 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 ){ |
︙ | ︙ | |||
2763 2764 2765 2766 2767 2768 2769 | wsFlags |= WHERE_IDX_ONLY; }else{ bLookup = 1; } } /* | | | | 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 | 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]); } |
︙ | ︙ |