/ 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 Unified Diffs Show Whitespace Changes Patch

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]);
    }