/ Check-in [f73a167b]
Login

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: f73a167b434fadcbbd15e3891c4b7f4f87f6363c
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbemem.c.

  1078   1078       if( SQLITE_OK==sqlite3ValueFromExpr(db,pExpr->pLeft,enc,affinity,&pVal) ){
  1079   1079         sqlite3VdbeMemNumerify(pVal);
  1080   1080         pVal->u.i = -1 * pVal->u.i;
  1081   1081         /* (double)-1 In case of SQLITE_OMIT_FLOATING_POINT... */
  1082   1082         pVal->r = (double)-1 * pVal->r;
  1083   1083         sqlite3ValueApplyAffinity(pVal, affinity, enc);
  1084   1084       }
         1085  +  }else if( op==TK_NULL ){
         1086  +    pVal = sqlite3ValueNew(db);
  1085   1087     }
  1086   1088   #ifndef SQLITE_OMIT_BLOB_LITERAL
  1087   1089     else if( op==TK_BLOB ){
  1088   1090       int nVal;
  1089   1091       assert( pExpr->u.zToken[0]=='x' || pExpr->u.zToken[0]=='X' );
  1090   1092       assert( pExpr->u.zToken[1]=='\'' );
  1091   1093       pVal = sqlite3ValueNew(db);

Changes to src/where.c.

  2241   2241           if( aSample[i].eType>=SQLITE_TEXT ) break;
  2242   2242           if( roundUp ){
  2243   2243             if( aSample[i].u.r>r ) break;
  2244   2244           }else{
  2245   2245             if( aSample[i].u.r>=r ) break;
  2246   2246           }
  2247   2247         }
         2248  +    }else if( eType==SQLITE_NULL ){
         2249  +      i = 0;
         2250  +      if( roundUp ){
         2251  +        while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
         2252  +      }
  2248   2253       }else{ 
  2249   2254         sqlite3 *db = pParse->db;
  2250   2255         CollSeq *pColl;
  2251   2256         const u8 *z;
  2252   2257         int n;
  2253   2258   
  2254   2259         /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
................................................................................
  2429   2434         if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
  2430   2435       }else{
  2431   2436         rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
  2432   2437         if( rc==SQLITE_OK ){
  2433   2438           rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
  2434   2439         }
  2435   2440       }
         2441  +    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
  2436   2442   
  2437   2443       iEst = iUpper - iLower;
  2438   2444       testcase( iEst==SQLITE_INDEX_SAMPLES );
  2439   2445       assert( iEst<=SQLITE_INDEX_SAMPLES );
  2440   2446       if( iEst<1 ){
  2441   2447         *piEst = 50/SQLITE_INDEX_SAMPLES;
  2442   2448       }else{
................................................................................
  2467   2473   ** an equality constraint x=VALUE and where that VALUE occurs in
  2468   2474   ** the histogram data.  This only works when x is the left-most
  2469   2475   ** column of an index and sqlite_stat2 histogram data is available
  2470   2476   ** for that index.
  2471   2477   **
  2472   2478   ** Write the estimated row count into *pnRow.  If unable to make
  2473   2479   ** an estimate, leave *pnRow unchanged.
         2480  +**
         2481  +** This routine can fail if it is unable to load a collating sequence
         2482  +** required for string comparison, or if unable to allocate memory
         2483  +** for a UTF conversion required for comparison.  The error is stored
         2484  +** in the pParse structure.
  2474   2485   */
  2475   2486   void whereEqScanEst(
  2476   2487     Parse *pParse,       /* Parsing & code generating context */
  2477   2488     Index *p,            /* The index whose left-most column is pTerm */
  2478   2489     WhereTerm *pTerm,    /* The x=VALUE constraint */
  2479   2490     double *pnRow        /* Write the revised row estimate here */
  2480   2491   ){
................................................................................
  2489   2500     aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2490   2501     rc = valueFromExpr(pParse, pTerm->pExpr->pRight, aff, &pRhs);
  2491   2502     if( rc ) goto whereEqScanEst_cancel;
  2492   2503     rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
  2493   2504     if( rc ) goto whereEqScanEst_cancel;
  2494   2505     rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
  2495   2506     if( rc ) goto whereEqScanEst_cancel;
         2507  +  WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
  2496   2508     if( iLower>=iUpper ){
  2497   2509       nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
  2498   2510       if( nRowEst<*pnRow ) *pnRow = nRowEst;
  2499   2511     }else{
  2500   2512       nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
  2501   2513       *pnRow = nRowEst;
  2502   2514     }
................................................................................
  2683   2695         pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
  2684   2696         if( pTerm==0 ) break;
  2685   2697         wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
  2686   2698         if( pTerm->eOperator & WO_IN ){
  2687   2699           Expr *pExpr = pTerm->pExpr;
  2688   2700           wsFlags |= WHERE_COLUMN_IN;
  2689   2701           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
         2702  +          /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  2690   2703             nInMul *= 25;
  2691   2704             bInEst = 1;
  2692   2705           }else if( ALWAYS(pExpr->x.pList) ){
         2706  +          /* "x IN (value, value, ...)" */
  2693   2707             nInMul *= pExpr->x.pList->nExpr + 1;
  2694   2708           }
  2695   2709         }else if( pTerm->eOperator & WO_ISNULL ){
  2696   2710           wsFlags |= WHERE_COLUMN_NULL;
  2697   2711         }
  2698   2712   #ifdef SQLITE_ENABLE_STAT2
  2699   2713         else if( nEq==0 && pProbe->aSample ){
................................................................................
  2763   2777           wsFlags |= WHERE_IDX_ONLY;
  2764   2778         }else{
  2765   2779           bLookup = 1;
  2766   2780         }
  2767   2781       }
  2768   2782   
  2769   2783       /*
  2770         -    ** Estimate the number of rows of output.  For an IN operator,
  2771         -    ** do not let the estimate exceed half the rows in the table.
         2784  +    ** Estimate the number of rows of output.  For an "x IN (SELECT...)"
         2785  +    ** constraint, do not let the estimate exceed half the rows in the table.
  2772   2786       */
  2773   2787       nRow = (double)(aiRowEst[nEq] * nInMul);
  2774   2788       if( bInEst && nRow*2>aiRowEst[0] ){
  2775   2789         nRow = aiRowEst[0]/2;
  2776   2790         nInMul = (int)(nRow / aiRowEst[nEq]);
  2777   2791       }
  2778   2792