/ Check-in [d1248165]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add code to actually use the sqlite_stat2.cnt field in the query planner. This changes some plans resulting in a few failures in analyze5.test.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | query-planner-tweaks
Files: files | file ages | folders
SHA1:d1248165e3e02aaf8a2a7872793918b4a9f102a8
User & Date: drh 2011-08-08 17:18:40
Original Comment: Add code to actually use the sqlite_stat2.cnt field in the query planner. This changes some plans resulting in a few failures in analyze5.test.
Context
2011-08-08
17:18
Add code to actually use the sqlite_stat2.cnt field in the query planner. This changes some plans resulting in a few failures in analyze5.test. Closed-Leaf check-in: d1248165 user: drh tags: query-planner-tweaks
2011-08-07
00:21
The ANALYZE command adds the sqlite_stat2.cnt column if it does not already exist. check-in: 794fde6f user: drh tags: query-planner-tweaks
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

835
836
837
838
839
840
841
842
843


844
845
846
847
848
849
850
          pSample = allocIndexSample(db, &pIdx->comkey, pIdx->comkey.n);
        }else{
          pSample = allocIndexSample(db, &pIdx->sample, iSample);
        }
        if( pSample==0 ) break;
        eType = sqlite3_column_type(pStmt, 2);
        pSample->eType = (u8)eType;
        pSample->nCopy = sqlite3_column_int(pStmt, 4);
        if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){


          pSample->u.r = sqlite3_column_double(pStmt, 2);
        }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
          const char *z = (const char *)(
             (eType==SQLITE_BLOB) ?
              sqlite3_column_blob(pStmt, 2):
              sqlite3_column_text(pStmt, 2)
          );







|
|
>
>







835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
          pSample = allocIndexSample(db, &pIdx->comkey, pIdx->comkey.n);
        }else{
          pSample = allocIndexSample(db, &pIdx->sample, iSample);
        }
        if( pSample==0 ) break;
        eType = sqlite3_column_type(pStmt, 2);
        pSample->eType = (u8)eType;
        pSample->nCopy = sqlite3_column_int(pStmt, 3);
        if( eType==SQLITE_INTEGER ){
          pSample->u.i = sqlite3_column_int64(pStmt, 2);
        }else if( eType==SQLITE_FLOAT ){
          pSample->u.r = sqlite3_column_double(pStmt, 2);
        }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
          const char *z = (const char *)(
             (eType==SQLITE_BLOB) ?
              sqlite3_column_blob(pStmt, 2):
              sqlite3_column_text(pStmt, 2)
          );

Changes to src/sqliteInt.h.

1454
1455
1456
1457
1458
1459
1460
1461

1462
1463
1464
1465
1466
1467
1468
/*
** Each sample stored in the sqlite_stat2 table is represented in memory 
** using a structure of this type.
*/
struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
    double r;       /* Value if eType is SQLITE_FLOAT or SQLITE_INTEGER */

  } u;
  u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  u8 nByte;         /* Size in byte of text or blob. */
  u32 nCopy;        /* How many copies of this sample are in the database */
};

/*







|
>







1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
/*
** Each sample stored in the sqlite_stat2 table is represented in memory 
** using a structure of this type.
*/
struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
    double r;       /* Value if eType is SQLITE_FLOAT */
    i64 i;          /* Value if eType is SQLITE_INTEGER */
  } u;
  u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  u8 nByte;         /* Size in byte of text or blob. */
  u32 nCopy;        /* How many copies of this sample are in the database */
};

/*

Changes to src/where.c.

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

2466
2467
2468
2469
2470
2471
2472
2473

2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
....
2520
2521
2522
2523
2524
2525
2526

2527
2528
2529
2530
2531
2532
2533
....
2628
2629
2630
2631
2632
2633
2634

2635
2636
2637
2638
2639
2640
2641
....
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
....
2716
2717
2718
2719
2720
2721
2722

2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735

2736
2737





2738
2739
2740
2741
2742
2743
2744

2745
2746
2747
2748
2749
2750
2751
....
2778
2779
2780
2781
2782
2783
2784

2785
2786
2787
2788
2789
2790
2791
....
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** pIdx->sample.n evenly spaced samples of the first indexed column
** stored in Index.sample. These samples divide the domain of values stored
** the index into (pIdx->sample.n+1) regions.
** Region 0 contains all values less than the first sample value. Region
** 1 contains values between the first and second samples.  Region 2 contains
** values between samples 2 and 3.  And so on.  Region pIdx->sample.n
** contains values larger than the last sample.





**
** If the index contains many duplicates of a single value, then it is
** possible that two or more adjacent samples can hold the same value.
** When that is the case, the smallest possible region code is returned
** when roundUp is false and the largest possible region code is returned
** when roundUp is true.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and S+1, inclusive) and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned and *piRegion is undefined.
*/
#ifdef SQLITE_ENABLE_STAT2
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Return largest valid region if true */
  int *piRegion               /* OUT: Region of domain in which value lies */

){
  assert( roundUp==0 || roundUp==1 );
  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->sample.a;
    int nSample = pIdx->sample.n;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    assert( nSample>0 );
    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){












      double r = sqlite3_value_double(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        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<nSample && 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 */
      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );

      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
        pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){
................................................................................
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }

        if( c-roundUp>=0 ) break;
      }
    }

    assert( i>=0 && i<=pIdx->sample.n );
    *piRegion = i;
  }
................................................................................
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int nSample = p->sample.n;
    int iUpper = p->sample.n;
    int roundUpUpper = 0;
    int roundUpLower = 0;

    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
................................................................................
    }

    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
      sqlite3ValueFree(pLowerVal);
      sqlite3ValueFree(pUpperVal);
      goto range_est_fallback;
    }else if( pLowerVal==0 ){
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
      if( pUpper ) iUpper = (iLower + p->sample.n + 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==nSample );
    assert( iEst<=nSample );
    assert( nSample>0 );
    if( iEst<1 ){
      *piEst = 50/nSample;
    }else{
................................................................................
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */


  assert( p->sample.a!=0 );
  assert( p->sample.n>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){
    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
  if( rc ) goto whereEqualScanEst_cancel;

  rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
  if( rc ) goto whereEqualScanEst_cancel;





  WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
  if( iLower>=iUpper ){
    nRowEst = p->aiRowEst[0]/(p->sample.n*3);
    if( nRowEst<*pnRow ) *pnRow = nRowEst;
  }else{
    nRowEst = (iUpper-iLower)*p->aiRowEst[0]/p->sample.n;
    *pnRow = nRowEst;

  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */
................................................................................
  u8 aff;                   /* Column affinity */
  int rc = SQLITE_OK;       /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  int nSpan = 0;            /* Number of histogram regions spanned */
  int nSingle = 0;          /* Histogram regions hit by a single value */
  int nNotFound = 0;        /* Count of values that are not constants */
  int i;                             /* Loop counter */

  int nSample = p->sample.n;         /* Number of samples */
  u8 aSpan[SQLITE_MAX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_MAX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->sample.a!=0 );
  assert( nSample>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
................................................................................
    sqlite3ValueFree(pVal);
    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
    if( rc ) break;
    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
      nNotFound++;
      continue;
    }
    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
    if( rc ) break;
    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
    if( rc ) break;
    if( iLower>=iUpper ){
      aSingle[iLower] = 1;
    }else{
      assert( iLower>=0 && iUpper<=nSample );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }







|
|
<
|
|
|
|
>
>
>
>
>









|









|
>









|
>
>
>
>
>
>
>
>
>
>
>
>




>








>









<

<







 







>







 







>







 







|


|


|

|



<







 







>











|

>
|
|
>
>
>
>
>
|
|
|
|
|
|
|
>







 







>







 







|

|







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
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501

2502

2503
2504
2505
2506
2507
2508
2509
....
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
....
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
....
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685

2686
2687
2688
2689
2690
2691
2692
....
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
....
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
....
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** pIdx->sample.n (hereafter "S") evenly spaced samples of the first indexed
** column stored in Index.sample. These samples divide the domain of values

** stored the index into S+1 regions.  Region 0 contains all values less than
** the first sample value. Region 1 contains values between the first and
** second samples.  Region 2 contains values between samples 2 and 3.  And so
** on.  Region S contains values larger than the last sample.
**
** Note that samples are computed as being centered on S buckets where each
** bucket contains the nearly same number of rows.  This routine takes samples
** to be dividers between regions, though.  Hence, region 0 and region S
** contain half as many rows as the interior regions.
**
** If the index contains many duplicates of a single value, then it is
** possible that two or more adjacent samples can hold the same value.
** When that is the case, the smallest possible region code is returned
** when roundUp is false and the largest possible region code is returned
** when roundUp is true.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and S, inclusive) and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned and *piRegion is undefined.
*/
#ifdef SQLITE_ENABLE_STAT2
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Return largest valid region if true */
  int *piRegion,              /* OUT: Region of domain in which value lies */
  u32 *pnCopy                 /* OUT: Number of rows with pVal, or -1 if unk */
){
  assert( roundUp==0 || roundUp==1 );
  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->sample.a;
    int nSample = pIdx->sample.n;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    assert( nSample>0 );
    if( eType==SQLITE_INTEGER ){
      i64 x = sqlite3_value_int64(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.i==x ) *pnCopy = aSample[i].nCopy;
        if( roundUp ){
          if( aSample[i].u.i>x ) break;
        }else{
          if( aSample[i].u.i>=x ) break;
        }
      }
    }else if( eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.r==r ) *pnCopy = aSample[i].nCopy;
        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( aSample[0].eType==SQLITE_NULL ) *pnCopy = aSample[0].nCopy;
      if( roundUp ){
        while( i<nSample && aSample[i].eType==SQLITE_NULL ) i++;
      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;


      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );

      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
        pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){
................................................................................
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( c==0 ) *pnCopy = aSample[i].nCopy;
        if( c-roundUp>=0 ) break;
      }
    }

    assert( i>=0 && i<=pIdx->sample.n );
    *piRegion = i;
  }
................................................................................
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int nSample = p->sample.n;
    int iUpper = p->sample.n;
    int roundUpUpper = 0;
    int roundUpLower = 0;
    u32 nC = 0;
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
................................................................................
    }

    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
      sqlite3ValueFree(pLowerVal);
      sqlite3ValueFree(pUpperVal);
      goto range_est_fallback;
    }else if( pLowerVal==0 ){
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      if( pUpper ) iUpper = (iLower + p->sample.n + 1)/2;
    }else{
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( rc==SQLITE_OK ){
        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      }
    }
    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));

    iEst = iUpper - iLower;
    testcase( iEst==nSample );
    assert( iEst<=nSample );
    assert( nSample>0 );
    if( iEst<1 ){
      *piEst = 50/nSample;
    }else{
................................................................................
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  u32 nC = 0;               /* Key copy count */

  assert( p->sample.a!=0 );
  assert( p->sample.n>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){
    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower, &nC);
  if( rc ) goto whereEqualScanEst_cancel;
  if( nC==0 ){
    rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper, &nC);
    if( rc ) goto whereEqualScanEst_cancel;
  }
  if( nC ){
    WHERETRACE(("equality scan count: %u\n", nC));
    *pnRow = nC;
  }else{
    WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
    if( iLower>=iUpper ){
      nRowEst = p->aiRowEst[0]/(p->sample.n*3);
      if( nRowEst<*pnRow ) *pnRow = nRowEst;
    }else{
      nRowEst = (iUpper-iLower)*p->aiRowEst[0]/p->sample.n;
      *pnRow = nRowEst;
    }
  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */
................................................................................
  u8 aff;                   /* Column affinity */
  int rc = SQLITE_OK;       /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  int nSpan = 0;            /* Number of histogram regions spanned */
  int nSingle = 0;          /* Histogram regions hit by a single value */
  int nNotFound = 0;        /* Count of values that are not constants */
  int i;                             /* Loop counter */
  u32 nC;                            /* Exact count of rows for a key */
  int nSample = p->sample.n;         /* Number of samples */
  u8 aSpan[SQLITE_MAX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_MAX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->sample.a!=0 );
  assert( nSample>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
................................................................................
    sqlite3ValueFree(pVal);
    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
    if( rc ) break;
    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
      nNotFound++;
      continue;
    }
    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower, &nC);
    if( rc ) break;
    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper, &nC);
    if( rc ) break;
    if( iLower>=iUpper ){
      aSingle[iLower] = 1;
    }else{
      assert( iLower>=0 && iUpper<=nSample );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }