/ Check-in [499edcbc]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Merge the stat2 query planner enhancements into the trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 499edcbc8ab70fcf35431d4e672c68dbcb6c5aad
User & Date: drh 2011-02-04 06:36:44
References
2018-11-05
08:09 Fixed ticket [65eb38f6]: Incorrect answer on LEFT JOIN when STAT4 is enabled plus 6 other changes artifact: 88c47ba1 user: drh
2011-08-02
01:26 New ticket [6c14288a] Virtual tables do not handle IS NOT NULL correctly. artifact: 9bfe9ae2 user: drh
Context
2011-02-04
14:28
Significant changes have occurred since the 3.7.5 release so go ahead and increase the version number to 3.7.6. check-in: 999c915a user: drh tags: trunk
06:36
Merge the stat2 query planner enhancements into the trunk. check-in: 499edcbc user: drh tags: trunk
05:47
If a deferred foreign key constraint fails on a statement that is not part of a larger transation, make sure that the statement fully ends so that subsequent invocations of the same statement will not pass the constraint because they think the transaction is not closed. This is a merge of the deferred-fk-quirk branch together with a test case. check-in: 2f94d462 user: drh tags: trunk
2011-01-28
03:13
Reactivate the analyze5.test script. Closed-Leaf check-in: a2a9f640 user: drh tags: stat2-enhancement
Changes
Hide Diffs Unified Diffs Ignore Whitespace 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.

113
114
115
116
117
118
119

120
121
122
123
124
125
126
...
206
207
208
209
210
211
212

213
214
215
216
217
218
219
....
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
....
1320
1321
1322
1323
1324
1325
1326




































1327
1328
1329
1330
1331
1332
1333
....
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206


2207
2208






2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220

2221
2222

2223
2224
2225
2226
2227
2228
2229
2230
2231
2232










2233
2234
2235
2236
2237
2238
2239
....
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
....
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
....
2382
2383
2384
2385
2386
2387
2388


2389
2390
2391
2392
2393


2394
2395
2396
2397


2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415

2416
2417
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
....
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
....
2506
2507
2508
2509
2510
2511
2512
2513
2514


2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525


2526
2527
2528
2529
2530
2531
2532
....
2536
2537
2538
2539
2540
2541
2542

2543
2544
2545
2546
2547
2548
2549
2550
2551


2552
2553
2554
2555
2556
2557
2558
....
2568
2569
2570
2571
2572
2573
2574
2575


2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593

2594
2595
2596
2597
2598


2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610



2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621

2622
2623
2624

2625
2626
2627
2628
2629



2630
2631
2632
2633
2634
2635
2636
....
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708


2709
2710








2711
2712
2713
2714
2715
2716
2717
2718








2719

2720
2721












2722






2723
2724
2725
2726





2727
2728
2729


2730

2731
2732
2733
2734
2735
2736
2737
....
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776




2777
2778
2779

2780
2781
2782
2783
2784
2785
2786
....
3610
3611
3612
3613
3614
3615
3616

3617

3618
3619
3620
3621
3622
3623
3624
....
3649
3650
3651
3652
3653
3654
3655

3656

3657
3658
3659
3660
3661
3662
3663
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */
#define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
#define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
#define TERM_OR_OK      0x40   /* Used during OR-clause processing */


/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
................................................................................
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100       /* Two or more OR-connected terms */
#define WO_AND    0x200       /* Two or more AND-connected terms */


#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
................................................................................
        exprAnalyze(pSrc, pWC, idxNew);
        pTerm = &pWC->a[idxTerm];
        pWC->a[idxNew].iParent = idxTerm;
        pTerm->nChild = 1;
      }else{
        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = 0;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
................................................................................
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_OMIT_VIRTUALTABLE */





































  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

/*
................................................................................
  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
** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
** stored in Index.aSample. The domain of values stored in said column
** may be thought of as divided into (SQLITE_INDEX_SAMPLES+1) regions.
** Region 0 contains all values smaller than the first sample value. Region


** 1 contains values larger than or equal to the value of the first sample,
** but smaller than the value of the second. And so on.






**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and SQLITE_INDEX_SAMPLES+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 *piRegion               /* OUT: Region of domain in which value lies */
){

  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->aSample;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT || aSample[i].u.r>r ) break;










      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;

................................................................................
          return SQLITE_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        int r;
        int eSampletype = aSample[i].eType;
        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
        if( (eSampletype!=eType) ) break;
#ifndef SQLITE_OMIT_UTF16
        if( pColl->enc!=SQLITE_UTF8 ){
          int nSample;
          char *zSample = sqlite3Utf8to16(
              db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
          );
          if( !zSample ){
            assert( db->mallocFailed );
            return SQLITE_NOMEM;
          }
          r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( r>0 ) break;
      }
    }

    assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
    *piRegion = i;
  }
  return SQLITE_OK;
................................................................................
** value of 1 indicates that the proposed range scan is expected to visit
** approximately 1/100th (1%) of the rows selected by the nEq equality
** constraints (if any). A return value of 100 indicates that it is expected
** that the range scan will visit every row (100%) selected by the equality
** constraints.
**
** In the absence of sqlite_stat2 ANALYZE data, each range inequality
** reduces the search space by 2/3rds.  Hence a single constraint (x>?)
** results in a return of 33 and a range constraint (x>? AND x<?) results
** in a return of 11.
*/
static int whereRangeScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index containing the range-compared column; "x" */
  int nEq,             /* index into p->aCol[] of the range-compared column */
  WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
................................................................................

  if( nEq==0 && p->aSample ){
    sqlite3_value *pLowerVal = 0;
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int iUpper = SQLITE_INDEX_SAMPLES;


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

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);


    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);


    }

    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, &iUpper);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
      if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
    }else{
      rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
      if( rc==SQLITE_OK ){
        rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
      }
    }


    iEst = iUpper - iLower;
    testcase( iEst==SQLITE_INDEX_SAMPLES );
    assert( iEst<=SQLITE_INDEX_SAMPLES );
    if( iEst<1 ){
      iEst = 1;
    }


    sqlite3ValueFree(pLowerVal);
    sqlite3ValueFree(pUpperVal);
    *piEst = (iEst * 100)/SQLITE_INDEX_SAMPLES;
    return rc;
  }
range_est_fallback:
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(p);
  UNUSED_PARAMETER(nEq);
#endif
  assert( pLower || pUpper );
  if( pLower && pUpper ){
    *piEst = 11;















































  }else{
    *piEst = 33;


  }



  return rc;
}

















































































/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O need to process the request using the selected plan.
** Factors that influence cost include:
**
**    *  The estimated number of rows that will be retrieved.  (The
**       fewer the better.)
**
**    *  Whether or not sorting must occur.
**
................................................................................
** the SQL statement, then this function only considers plans using the 
** named index. If no such plan is found, then the returned cost is
** SQLITE_BIG_DBL. If a plan is found that uses the named index, 
** then the cost is calculated in the usual way.
**
** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
** in the SELECT statement, then no indexes are considered. However, the 
** selected plan may still take advantage of the tables built-in rowid
** index.
*/
static void bestBtreeIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors not available for indexing */
................................................................................

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pIdx = pProbe = pSrc->pIndex;
    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
    eqTermMask = idxEqTermMask;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object to
    ** represent the primary key */


    Index *pFirst;                /* Any other index on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nColumn = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;
    sPk.onError = OE_Replace;
    sPk.pTable = pSrc->pTab;
    aiRowEstPk[0] = pSrc->pTab->nRowEst;
    aiRowEstPk[1] = 1;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){


      sPk.pNext = pFirst;
    }
    pProbe = &sPk;
    wsFlagMask = ~(
        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
    );
    eqTermMask = WO_EQ|WO_IN;
................................................................................
  /* Loop over all indices looking for the best one to use
  */
  for(; pProbe; pIdx=pProbe=pProbe->pNext){
    const unsigned int * const aiRowEst = pProbe->aiRowEst;
    double cost;                /* Cost of using pProbe */
    double nRow;                /* Estimated number of rows in result set */
    int rev;                    /* True to scan in reverse order */

    int wsFlags = 0;
    Bitmask used = 0;

    /* The following variables are populated based on the properties of
    ** scan being evaluated. They are then used to determine the expected
    ** cost and number of rows returned.
    **
    **  nEq: 
    **    Number of equality terms that can be implemented using the index.


    **
    **  nInMul:  
    **    The "in-multiplier". This is an estimate of how many seek operations 
    **    SQLite must perform on the index in question. For example, if the 
    **    WHERE clause is:
    **
    **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
................................................................................
    **
    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
    **    the sub-select is assumed to return 25 rows for the purposes of 
    **    determining nInMul.
    **
    **  bInEst:  
    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
    **    in determining the value of nInMul.


    **
    **  estBound:
    **    An estimate on the amount of the table that must be searched.  A
    **    value of 100 means the entire table is searched.  Range constraints
    **    might reduce this to a value less than 100 to indicate that only
    **    a fraction of the table needs searching.  In the absence of
    **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
    **    space to 1/3rd its original size.  So an x>? constraint reduces
    **    estBound to 33.  Two constraints (x>? AND x<?) reduce estBound to 11.
    **
    **  bSort:   
    **    Boolean. True if there is an ORDER BY clause that will require an 
    **    external sort (i.e. scanning the index being evaluated will not 
    **    correctly order records).
    **
    **  bLookup: 
    **    Boolean. True if for each index entry visited a lookup on the 
    **    corresponding table b-tree is required. This is always false 

    **    for the rowid index. For other indexes, it is true unless all the 
    **    columns of the table used by the SELECT statement are present in 
    **    the index (such an index is sometimes described as a covering index).
    **    For example, given the index on (a, b), the second of the following 
    **    two queries requires table b-tree lookups, but the first does not.


    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nEq;
    int bInEst = 0;
    int nInMul = 1;
    int estBound = 100;
    int nBound = 0;             /* Number of range constraints seen */
    int bSort = 0;
    int bLookup = 0;
    WhereTerm *pTerm;           /* A single term of the WHERE clause */




    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];
      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;
      }



      used |= pTerm->prereqRight;
    }

    /* Determine the value of estBound. */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
................................................................................
        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]);
    }

    /* Assume constant cost to access a row and logarithmic cost to
    ** do a binary search.  Hence, the initial cost is the number of output
    ** rows plus log2(table-size) times the number of binary searches.


    */
    cost = nRow + nInMul*estLog(aiRowEst[0]);









    /* Adjust the number of rows and the cost downward to reflect rows
    ** that are excluded by range constraints.
    */
    nRow = (nRow * (double)estBound) / (double)100;
    cost = (cost * (double)estBound) / (double)100;

    /* Add in the estimated cost of sorting the result








    */

    if( bSort ){
      cost += cost*estLog(cost);












    }







    /* If all information can be taken directly from the index, we avoid
    ** doing table lookups.  This reduces the cost by half.  (Not really -
    ** this needs to be fixed.)





    */
    if( pIdx && bLookup==0 ){
      cost /= (double)2;


    }

    /**** Cost of using this index has now been computed ****/

    /* If there are additional constraints on this table that cannot
    ** be used with the current index, but which might lower the number
    ** of output rows, adjust the nRow value accordingly.  This only 
    ** matters if the current index is the least costly, so do not bother
    ** with this step if we already know this index will not be chosen.
................................................................................
          }else{
            /* Assume each additional equality match reduces the result
            ** set size by a factor of 10 */
            nRow /= 10;
          }
        }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
          if( nSkipRange ){
            /* Ignore the first nBound range constraints since the index
            ** has already accounted for these */
            nSkipRange--;
          }else{
            /* Assume each additional range constraint reduces the result
            ** set size by a factor of 3 */




            nRow /= 3;
          }
        }else{

          /* Any other expression lowers the output row count by half */
          nRow /= 2;
        }
      }
      if( nRow<2 ) nRow = 2;
    }

................................................................................
    start_constraints = pRangeStart || nEq>0;

    /* Seek the index cursor to the start of the range. */
    nConstraint = nEq;
    if( pRangeStart ){
      Expr *pRight = pRangeStart->pExpr->pRight;
      sqlite3ExprCode(pParse, pRight, regBase+nEq);

      sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);

      if( zStartAff ){
        if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
          /* Since the comparison is to be performed with no conversions
          ** applied to the operands, set the affinity to apply to pRight to 
          ** SQLITE_AFF_NONE.  */
          zStartAff[nEq] = SQLITE_AFF_NONE;
        }
................................................................................
    ** range (if any).
    */
    nConstraint = nEq;
    if( pRangeEnd ){
      Expr *pRight = pRangeEnd->pExpr->pRight;
      sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
      sqlite3ExprCode(pParse, pRight, regBase+nEq);

      sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);

      if( zEndAff ){
        if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){
          /* Since the comparison is to be performed with no conversions
          ** applied to the operands, set the affinity to apply to pRight to 
          ** SQLITE_AFF_NONE.  */
          zEndAff[nEq] = SQLITE_AFF_NONE;
        }







>







 







>







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







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












>


>









|
>
>
>
>
>
>
>
>
>
>







 







|













|




|

|







 







|
|
|







 







>
>





>
>




>
>







|


|


|

|


>





|
|
>
|


<









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

<
>
>

>
>
>


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|




|







 







|







 







|
|
>
>
|










>
>







 







>




|




>
>







 







|
>
>







|
|







|
|
>
|
|
|

|
>
>




|
|
|
|
|
|
|
|
>
>
>











>


|
>
|




>
>
>







 







|
|







|
|
|
>
>

<
>
>
>
>
>
>
>
>





|

|
>
>
>
>
>
>
>
>

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

<
<
>
>

>







 







|




|
>
>
>
>


<
>







 







>
|
>







 







>
|
>







113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
...
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
....
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
....
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
....
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247

2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
....
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
....
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
....
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
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548

2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
....
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
....
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
....
2733
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
....
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
....
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924

2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951

2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971



2972
2973
2974
2975
2976
2977


2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
....
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033

3034
3035
3036
3037
3038
3039
3040
3041
....
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
....
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */
#define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
#define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
#define TERM_OR_OK      0x40   /* Used during OR-clause processing */
#define TERM_VNULL      0x80   /* Manufactured x>NULL or x<=NULL term */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
................................................................................
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100       /* Two or more OR-connected terms */
#define WO_AND    0x200       /* Two or more AND-connected terms */
#define WO_NOOP   0x800       /* This term does not restrict search space */

#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
................................................................................
        exprAnalyze(pSrc, pWC, idxNew);
        pTerm = &pWC->a[idxTerm];
        pWC->a[idxNew].iParent = idxTerm;
        pTerm->nChild = 1;
      }else{
        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
................................................................................
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifdef SQLITE_ENABLE_STAT2
  /* When sqlite_stat2 histogram data is available an operator of the
  ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
  ** as "x>NULL" if x is not an INTEGER PRIMARY KEY.  So construct a
  ** virtual term of that form.
  **
  ** Note that the virtual term must be tagged with TERM_VNULL.  This
  ** TERM_VNULL tag will suppress the not-null check at the beginning
  ** of the loop.  Without the TERM_VNULL flag, the not-null check at
  ** the start of the loop will prevent any results from being returned.
  */
  if( pExpr->op==TK_NOTNULL && pExpr->pLeft->iColumn>=0 ){
    Expr *pNewExpr;
    Expr *pLeft = pExpr->pLeft;
    int idxNew;
    WhereTerm *pNewTerm;

    pNewExpr = sqlite3PExpr(pParse, TK_GT,
                            sqlite3ExprDup(db, pLeft, 0),
                            sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);

    idxNew = whereClauseInsert(pWC, pNewExpr,
                              TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
    testcase( idxNew==0 );
    pNewTerm = &pWC->a[idxNew];
    pNewTerm->leftCursor = pLeft->iTable;
    pNewTerm->u.leftColumn = pLeft->iColumn;
    pNewTerm->eOperator = WO_GT;
    pNewTerm->iParent = idxTerm;
    pTerm = &pWC->a[idxTerm];
    pTerm->nChild = 1;
    pTerm->wtFlags |= TERM_COPIED;
    pNewTerm->prereqAll = pTerm->prereqAll;
  }
#endif /* SQLITE_ENABLE_STAT2 */

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

/*
................................................................................
  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
** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
** stored in Index.aSample. These samples divide the domain of values stored
** the index into (SQLITE_INDEX_SAMPLES+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 SQLITE_INDEX_SAMPLES
** 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 SQLITE_INDEX_SAMPLES+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->aSample;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<SQLITE_INDEX_SAMPLES; 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<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;

................................................................................
          return SQLITE_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        int c;
        int eSampletype = aSample[i].eType;
        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
        if( (eSampletype!=eType) ) break;
#ifndef SQLITE_OMIT_UTF16
        if( pColl->enc!=SQLITE_UTF8 ){
          int nSample;
          char *zSample = sqlite3Utf8to16(
              db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
          );
          if( !zSample ){
            assert( db->mallocFailed );
            return SQLITE_NOMEM;
          }
          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<=SQLITE_INDEX_SAMPLES );
    *piRegion = i;
  }
  return SQLITE_OK;
................................................................................
** value of 1 indicates that the proposed range scan is expected to visit
** approximately 1/100th (1%) of the rows selected by the nEq equality
** constraints (if any). A return value of 100 indicates that it is expected
** that the range scan will visit every row (100%) selected by the equality
** constraints.
**
** In the absence of sqlite_stat2 ANALYZE data, each range inequality
** reduces the search space by 3/4ths.  Hence a single constraint (x>?)
** results in a return of 25 and a range constraint (x>? AND x<?) results
** in a return of 6.
*/
static int whereRangeScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index containing the range-compared column; "x" */
  int nEq,             /* index into p->aCol[] of the range-compared column */
  WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
................................................................................

  if( nEq==0 && p->aSample ){
    sqlite3_value *pLowerVal = 0;
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int iUpper = SQLITE_INDEX_SAMPLES;
    int roundUpUpper;
    int roundUpLower;
    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 && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
      roundUpUpper = (pUpper->eOperator==WO_LE) ?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 + 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{
      *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
    }
    sqlite3ValueFree(pLowerVal);
    sqlite3ValueFree(pUpperVal);

    return rc;
  }
range_est_fallback:
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(p);
  UNUSED_PARAMETER(nEq);
#endif
  assert( pLower || pUpper );

  *piEst = 100;
  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
  if( pUpper ) *piEst /= 4;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT2
/*
** Estimate the number of rows that will be returned based on
** 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 and return SQLITE_OK. 
** If unable to make an estimate, leave *pnRow unchanged and return
** non-zero.
**
** 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.
*/
int whereEqualScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  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->aSample!=0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
  if( rc ) goto whereEqualScanEst_cancel;
  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]/(SQLITE_INDEX_SAMPLES*2);
    if( nRowEst<*pnRow ) *pnRow = nRowEst;
  }else{

    nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
    *pnRow = nRowEst;
  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */

#ifdef SQLITE_ENABLE_STAT2
/*
** Estimate the number of rows that will be returned based on
** an IN constraint where the right-hand side of the IN operator
** is a list of values.  Example:
**
**        WHERE x IN (1,2,3,4)
**
** Write the estimated row count into *pnRow and return SQLITE_OK. 
** If unable to make an estimate, leave *pnRow unchanged and return
** non-zero.
**
** 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.
*/
int whereInScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pVal = 0;  /* One value from list */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  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 */
  u8 aSpan[SQLITE_INDEX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_INDEX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->aSample!=0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  memset(aSpan, 0, sizeof(aSpan));
  memset(aSingle, 0, sizeof(aSingle));
  for(i=0; i<pList->nExpr; i++){
    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<=SQLITE_INDEX_SAMPLES );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }
  }
  if( rc==SQLITE_OK ){
    for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
      if( aSpan[i] ){
        nSpan++;
      }else if( aSingle[i] ){
        nSingle++;
      }
    }
    nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
               + nNotFound*p->aiRowEst[1];
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
                 nSpan, nSingle, nNotFound, nRowEst));
  }
  sqlite3ValueFree(pVal);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */


/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
** Factors that influence cost include:
**
**    *  The estimated number of rows that will be retrieved.  (The
**       fewer the better.)
**
**    *  Whether or not sorting must occur.
**
................................................................................
** the SQL statement, then this function only considers plans using the 
** named index. If no such plan is found, then the returned cost is
** SQLITE_BIG_DBL. If a plan is found that uses the named index, 
** then the cost is calculated in the usual way.
**
** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
** in the SELECT statement, then no indexes are considered. However, the 
** selected plan may still take advantage of the built-in rowid primary key
** index.
*/
static void bestBtreeIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors not available for indexing */
................................................................................

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pIdx = pProbe = pSrc->pIndex;
    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
    eqTermMask = idxEqTermMask;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this
    ** fake index the first in a chain of Index objects with all of the real
    ** indices to follow */
    Index *pFirst;                  /* First of real indices on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nColumn = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;
    sPk.onError = OE_Replace;
    sPk.pTable = pSrc->pTab;
    aiRowEstPk[0] = pSrc->pTab->nRowEst;
    aiRowEstPk[1] = 1;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      /* The real indices of the table are only considered if the
      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;
    }
    pProbe = &sPk;
    wsFlagMask = ~(
        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
    );
    eqTermMask = WO_EQ|WO_IN;
................................................................................
  /* Loop over all indices looking for the best one to use
  */
  for(; pProbe; pIdx=pProbe=pProbe->pNext){
    const unsigned int * const aiRowEst = pProbe->aiRowEst;
    double cost;                /* Cost of using pProbe */
    double nRow;                /* Estimated number of rows in result set */
    int rev;                    /* True to scan in reverse order */
    double nSearch;             /* Estimated number of binary searches */
    int wsFlags = 0;
    Bitmask used = 0;

    /* The following variables are populated based on the properties of
    ** index being evaluated. They are then used to determine the expected
    ** cost and number of rows returned.
    **
    **  nEq: 
    **    Number of equality terms that can be implemented using the index.
    **    In other words, the number of initial fields in the index that
    **    are used in == or IN or NOT NULL constraints of the WHERE clause.
    **
    **  nInMul:  
    **    The "in-multiplier". This is an estimate of how many seek operations 
    **    SQLite must perform on the index in question. For example, if the 
    **    WHERE clause is:
    **
    **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
................................................................................
    **
    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
    **    the sub-select is assumed to return 25 rows for the purposes of 
    **    determining nInMul.
    **
    **  bInEst:  
    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
    **    in determining the value of nInMul.  Note that the RHS of the
    **    IN operator must be a SELECT, not a value list, for this variable
    **    to be true.
    **
    **  estBound:
    **    An estimate on the amount of the table that must be searched.  A
    **    value of 100 means the entire table is searched.  Range constraints
    **    might reduce this to a value less than 100 to indicate that only
    **    a fraction of the table needs searching.  In the absence of
    **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
    **    space to 1/4rd its original size.  So an x>? constraint reduces
    **    estBound to 25.  Two constraints (x>? AND x<?) reduce estBound to 6.
    **
    **  bSort:   
    **    Boolean. True if there is an ORDER BY clause that will require an 
    **    external sort (i.e. scanning the index being evaluated will not 
    **    correctly order records).
    **
    **  bLookup: 
    **    Boolean. True if a table lookup is required for each index entry
    **    visited.  In other words, true if this is not a covering index.
    **    This is always false for the rowid primary key index of a table.
    **    For other indexes, it is true unless all the columns of the table
    **    used by the SELECT statement are present in the index (such an
    **    index is sometimes described as a covering index).
    **    For example, given the index on (a, b), the second of the following 
    **    two queries requires table b-tree lookups in order to find the value
    **    of column c, but the first does not because columns a and b are
    **    both available in the index.
    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nEq;                      /* Number of == or IN terms matching index */
    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
    int nInMul = 1;               /* Number of distinct equalities to lookup */
    int estBound = 100;           /* Estimated reduction in search space */
    int nBound = 0;               /* Number of range constraints seen */
    int bSort = 0;                /* True if external sort required */
    int bLookup = 0;              /* True if not a covering index */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT2
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];
      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 && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        wsFlags |= WHERE_COLUMN_NULL;
      }
#ifdef SQLITE_ENABLE_STAT2
      if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
      used |= pTerm->prereqRight;
    }

    /* Determine the value of estBound. */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
................................................................................
        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]);
    }

#ifdef SQLITE_ENABLE_STAT2
    /* If the constraint is of the form x=VALUE and histogram
    ** data is available for column x, then it might be possible
    ** to get a better estimate on the number of rows based on
    ** VALUE and how common that value is according to the histogram.
    */

    if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 ){
      if( pFirstTerm->eOperator==WO_EQ ){
        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
      }else if( pFirstTerm->eOperator==WO_IN && bInEst==0 ){
        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
      }
    }
#endif /* SQLITE_ENABLE_STAT2 */

    /* Adjust the number of rows and the cost downward to reflect rows
    ** that are excluded by range constraints.
    */
    nRow = (nRow * (double)estBound) / (double)100;
    if( nRow<1 ) nRow = 1;

    /* Assume constant cost to advance from one row to the next and
    ** logarithmic cost to do a binary search.  Hence, the initial cost
    ** is the number of output rows plus log2(table-size) times the
    ** number of binary searches.
    **
    ** Because fan-out on tables is so much higher than the fan-out on
    ** indices (because table btrees contain only integer keys in non-leaf
    ** nodes) we weight the cost of a table binary search as 1/10th the
    ** cost of an index binary search.
    */
    if( pIdx ){
      if( bLookup ){

        /* For an index lookup followed by a table lookup:
        **    nInMul index searches to find the start of each index range
        **  + nRow steps through the index
        **  + nRow table searches to lookup the table entry using the rowid
        */
        nSearch = nInMul + nRow/10;
      }else{
        /* For a covering index:
        **     nInMul binary searches to find the initial entry 
        **   + nRow steps through the index
        */
        nSearch = nInMul;
      }
    }else{
      /* For a rowid primary key lookup:
      **    nInMult binary searches to find the initial entry scaled by 1/10th
      **  + nRow steps through the table
      */
      nSearch = nInMul/10;
    }



    cost = nRow + nSearch*estLog(aiRowEst[0]);

    /* Add in the estimated cost of sorting the result.  This cost is expanded
    ** by a fudge factor of 3.0 to account for the fact that a sorting step 
    ** involves a write and is thus more expensive than a lookup step.
    */


    if( bSort ){
      cost += nRow*estLog(nRow)*(double)3;
    }

    /**** Cost of using this index has now been computed ****/

    /* If there are additional constraints on this table that cannot
    ** be used with the current index, but which might lower the number
    ** of output rows, adjust the nRow value accordingly.  This only 
    ** matters if the current index is the least costly, so do not bother
    ** with this step if we already know this index will not be chosen.
................................................................................
          }else{
            /* Assume each additional equality match reduces the result
            ** set size by a factor of 10 */
            nRow /= 10;
          }
        }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
          if( nSkipRange ){
            /* Ignore the first nSkipRange range constraints since the index
            ** has already accounted for these */
            nSkipRange--;
          }else{
            /* Assume each additional range constraint reduces the result
            ** set size by a factor of 3.  Indexed range constraints reduce
            ** the search space by a larger factor: 4.  We make indexed range
            ** more selective intentionally because of the subjective 
            ** observation that indexed range constraints really are more
            ** selective in practice, on average. */
            nRow /= 3;
          }

        }else if( pTerm->eOperator!=WO_NOOP ){
          /* Any other expression lowers the output row count by half */
          nRow /= 2;
        }
      }
      if( nRow<2 ) nRow = 2;
    }

................................................................................
    start_constraints = pRangeStart || nEq>0;

    /* Seek the index cursor to the start of the range. */
    nConstraint = nEq;
    if( pRangeStart ){
      Expr *pRight = pRangeStart->pExpr->pRight;
      sqlite3ExprCode(pParse, pRight, regBase+nEq);
      if( (pRangeStart->wtFlags & TERM_VNULL)==0 ){
        sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
      }
      if( zStartAff ){
        if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
          /* Since the comparison is to be performed with no conversions
          ** applied to the operands, set the affinity to apply to pRight to 
          ** SQLITE_AFF_NONE.  */
          zStartAff[nEq] = SQLITE_AFF_NONE;
        }
................................................................................
    ** range (if any).
    */
    nConstraint = nEq;
    if( pRangeEnd ){
      Expr *pRight = pRangeEnd->pExpr->pRight;
      sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
      sqlite3ExprCode(pParse, pRight, regBase+nEq);
      if( (pRangeEnd->wtFlags & TERM_VNULL)==0 ){
        sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
      }
      if( zEndAff ){
        if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){
          /* Since the comparison is to be performed with no conversions
          ** applied to the operands, set the affinity to apply to pRight to 
          ** SQLITE_AFF_NONE.  */
          zEndAff[nEq] = SQLITE_AFF_NONE;
        }

Changes to test/analyze2.test.

150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
...
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
...
238
239
240
241
242
243
244

245
246
247
248

249
250
251
252
253
254
255
...
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
...
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 400 AND 700
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~75 rows)}
}
do_eqp_test 2.7 {
  SELECT * FROM t1 WHERE x BETWEEN -400 AND -300 AND y BETWEEN 100 AND 300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~25 rows)}
}
do_eqp_test 2.8 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN -400 AND -300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~25 rows)}
}
do_eqp_test 2.9 {
  SELECT * FROM t1 WHERE x BETWEEN 500 AND 100 AND y BETWEEN 100 AND 300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~25 rows)}
}
do_eqp_test 2.10 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN 500 AND 100
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~25 rows)}
}

do_test analyze2-3.1 {
  set alphabet [list a b c d e f g h i j]
  execsql BEGIN
  for {set i 0} {$i < 1000} {incr i} {
    set str    [lindex $alphabet [expr ($i/100)%10]] 
................................................................................
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~50 rows)}
}
do_eqp_test 3.4 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~50 rows)}
}
do_eqp_test 3.5 {
  SELECT * FROM t1 WHERE x<'a' AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~66 rows)}
}
do_eqp_test 3.6 {
................................................................................
    execsql { INSERT INTO t3 VALUES($str, $str) }
  }
  execsql COMMIT
  execsql ANALYZE
} {}
do_test analyze2-4.2 {
  execsql { 

    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3a' 
    GROUP BY tbl,idx

  }
} {t3 t3a {AfA bEj CEj dEj EEj fEj GEj hEj IEj jEj}}
do_test analyze2-4.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3b' 
................................................................................
    DELETE FROM sqlite_stat2;
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.2 {
  db cache flush
  execsql ANALYZE
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.3 {
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.4 {
  execsql { 
    PRAGMA writable_schema = 1;
    DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat1';
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.5 {
  execsql { 
    PRAGMA writable_schema = 1;
    DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat2';
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.6 {
  execsql { 
    PRAGMA writable_schema = 1;
    INSERT INTO sqlite_master SELECT * FROM master;
  }
  sqlite3 db test.db
  execsql ANALYZE
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

#--------------------------------------------------------------------
# These tests, analyze2-7.*, test that the sqlite_stat2 functionality
# works in shared-cache mode. Note that these tests reuse the database
# created for the analyze2-6.* tests.
#
ifcapable shared_cache {
................................................................................
  } {20}

  do_test analyze2-7.5 {
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.6 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db2
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db2
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.7 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  do_test analyze2-7.8 {
    execsql { DELETE FROM sqlite_stat2 } db2
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.9 {
    execsql { SELECT * FROM sqlite_master } db2
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db2
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  do_test analyze2-7.10 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~2 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  db1 close
  db2 close
  sqlite3_enable_shared_cache $::enable_shared_cache
}

finish_test







|




|




|




|







 







|







 







>



|
>







 







|







|






|










|










|











|







 







|







|







|








|






|








|







150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
...
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
...
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
...
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
...
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 400 AND 700
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~75 rows)}
}
do_eqp_test 2.7 {
  SELECT * FROM t1 WHERE x BETWEEN -400 AND -300 AND y BETWEEN 100 AND 300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~12 rows)}
}
do_eqp_test 2.8 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN -400 AND -300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~12 rows)}
}
do_eqp_test 2.9 {
  SELECT * FROM t1 WHERE x BETWEEN 500 AND 100 AND y BETWEEN 100 AND 300
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~12 rows)}
}
do_eqp_test 2.10 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN 500 AND 100
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~12 rows)}
}

do_test analyze2-3.1 {
  set alphabet [list a b c d e f g h i j]
  execsql BEGIN
  for {set i 0} {$i < 1000} {incr i} {
    set str    [lindex $alphabet [expr ($i/100)%10]] 
................................................................................
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~50 rows)}
}
do_eqp_test 3.4 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~100 rows)}
}
do_eqp_test 3.5 {
  SELECT * FROM t1 WHERE x<'a' AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~66 rows)}
}
do_eqp_test 3.6 {
................................................................................
    execsql { INSERT INTO t3 VALUES($str, $str) }
  }
  execsql COMMIT
  execsql ANALYZE
} {}
do_test analyze2-4.2 {
  execsql { 
    PRAGMA automatic_index=OFF;
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3a' 
    GROUP BY tbl,idx;
    PRAGMA automatic_index=ON;
  }
} {t3 t3a {AfA bEj CEj dEj EEj fEj GEj hEj IEj jEj}}
do_test analyze2-4.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3b' 
................................................................................
    DELETE FROM sqlite_stat2;
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.2 {
  db cache flush
  execsql ANALYZE
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.3 {
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.4 {
  execsql { 
    PRAGMA writable_schema = 1;
    DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat1';
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.5 {
  execsql { 
    PRAGMA writable_schema = 1;
    DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat2';
  }
  sqlite3 db test.db
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
do_test analyze2-6.2.6 {
  execsql { 
    PRAGMA writable_schema = 1;
    INSERT INTO sqlite_master SELECT * FROM master;
  }
  sqlite3 db test.db
  execsql ANALYZE
  eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
        t5.a>1 AND t5.a<15 AND
        t6.a>1
  }
} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

#--------------------------------------------------------------------
# These tests, analyze2-7.*, test that the sqlite_stat2 functionality
# works in shared-cache mode. Note that these tests reuse the database
# created for the analyze2-6.* tests.
#
ifcapable shared_cache {
................................................................................
  } {20}

  do_test analyze2-7.5 {
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.6 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db2
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db2
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.7 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  do_test analyze2-7.8 {
    execsql { DELETE FROM sqlite_stat2 } db2
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
  do_test analyze2-7.9 {
    execsql { SELECT * FROM sqlite_master } db2
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db2
  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  do_test analyze2-7.10 {
    incr_schema_cookie test.db
    execsql { SELECT * FROM sqlite_master } db1
    eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
          t5.a>1 AND t5.a<15 AND
          t6.a>1
    } db1
  } {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~1 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}

  db1 close
  db2 close
  sqlite3_enable_shared_cache $::enable_shared_cache
}

finish_test

Changes to test/analyze3.test.

244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
    append t [lindex {a b c d e f g h i j} [expr ($i%10)]]
    execsql { INSERT INTO t1 VALUES($i, $t) }
  }
  execsql COMMIT
} {}
do_eqp_test analyze3-2.2 {
  SELECT count(a) FROM t1 WHERE b LIKE 'a%'
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b>? AND b<?) (~55000 rows)}}
do_eqp_test analyze3-2.3 {
  SELECT count(a) FROM t1 WHERE b LIKE '%a'
} {0 0 0 {SCAN TABLE t1 (~500000 rows)}}

do_test analyze3-2.4 {
  sf_execsql { SELECT count(*) FROM t1 WHERE b LIKE 'a%' }
} {101 0 100}







|







244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
    append t [lindex {a b c d e f g h i j} [expr ($i%10)]]
    execsql { INSERT INTO t1 VALUES($i, $t) }
  }
  execsql COMMIT
} {}
do_eqp_test analyze3-2.2 {
  SELECT count(a) FROM t1 WHERE b LIKE 'a%'
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b>? AND b<?) (~30000 rows)}}
do_eqp_test analyze3-2.3 {
  SELECT count(a) FROM t1 WHERE b LIKE '%a'
} {0 0 0 {SCAN TABLE t1 (~500000 rows)}}

do_test analyze3-2.4 {
  sf_execsql { SELECT count(*) FROM t1 WHERE b LIKE 'a%' }
} {101 0 100}

Added test/analyze5.test.





































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
# 2011 January 19
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file implements tests for SQLite library.  The focus of the tests
# in this file is the use of the sqlite_stat2 histogram data on tables
# with many repeated values and only a few distinct values.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !stat2 {
  finish_test
  return
}

set testprefix analyze5

proc eqp {sql {db db}} {
  uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db
}

unset -nocomplain i t u v w x y z
do_test analyze5-1.0 {
  db eval {CREATE TABLE t1(t,u,v TEXT COLLATE nocase,w,x,y,z)}
  for {set i 0} {$i < 1000} {incr i} {
    set y [expr {$i>=25 && $i<=50}]
    set z [expr {($i>=400) + ($i>=700) + ($i>=875)}]
    set x $z
    set w $z
    set t [expr {$z+0.5}]
    switch $z {
      0 {set u "alpha"; unset x}
      1 {set u "bravo"}
      2 {set u "charlie"}
      3 {set u "delta"; unset w}
    }
    if {$i%2} {set v $u} {set v [string toupper $u]}
    db eval {INSERT INTO t1 VALUES($t,$u,$v,$w,$x,$y,$z)}
  }
  db eval { 
    CREATE INDEX t1t ON t1(t);  -- 0.5, 1.5, 2.5, and 3.5
    CREATE INDEX t1u ON t1(u);  -- text
    CREATE INDEX t1v ON t1(v);  -- mixed case text
    CREATE INDEX t1w ON t1(w);  -- integers 0, 1, 2 and a few NULLs
    CREATE INDEX t1x ON t1(x);  -- integers 1, 2, 3 and many NULLs
    CREATE INDEX t1y ON t1(y);  -- integers 0 and very few 1s
    CREATE INDEX t1z ON t1(z);  -- integers 0, 1, 2, and 3
    ANALYZE;
    SELECT sample FROM sqlite_stat2 WHERE idx='t1u' ORDER BY sampleno;
  }
} {alpha alpha alpha alpha bravo bravo bravo charlie charlie delta}
do_test analyze5-1.1 {
  string tolower \
   [db eval {SELECT sample from sqlite_stat2 WHERE idx='t1v' ORDER BY sampleno}]
} {alpha alpha alpha alpha bravo bravo bravo charlie charlie delta}
do_test analyze5-1.2 {
  db eval {SELECT sample from sqlite_stat2 WHERE idx='t1w' ORDER BY sampleno}
} {{} 0 0 0 0 1 1 1 2 2}
do_test analyze5-1.3 {
  db eval {SELECT sample from sqlite_stat2 WHERE idx='t1x' ORDER BY sampleno}
} {{} {} {} {} 1 1 1 2 2 3}
do_test analyze5-1.4 {
  db eval {SELECT sample from sqlite_stat2 WHERE idx='t1y' ORDER BY sampleno}
} {0 0 0 0 0 0 0 0 0 0}
do_test analyze5-1.5 {
  db eval {SELECT sample from sqlite_stat2 WHERE idx='t1z' ORDER BY sampleno}
} {0 0 0 0 1 1 1 2 2 3}
do_test analyze5-1.6 {
  db eval {SELECT sample from sqlite_stat2 WHERE idx='t1t' ORDER BY sampleno}
} {0.5 0.5 0.5 0.5 1.5 1.5 1.5 2.5 2.5 3.5}


# Verify that range queries generate the correct row count estimates
#
foreach {testid where index rows} {
    1  {z>=0 AND z<=0}       t1z  400
    2  {z>=1 AND z<=1}       t1z  300
    3  {z>=2 AND z<=2}       t1z  200
    4  {z>=3 AND z<=3}       t1z  100
    5  {z>=4 AND z<=4}       t1z   50
    6  {z>=-1 AND z<=-1}     t1z   50
    7  {z>1 AND z<3}         t1z  200
    8  {z>0 AND z<100}       t1z  600
    9  {z>=1 AND z<100}      t1z  600
   10  {z>1 AND z<100}       t1z  300
   11  {z>=2 AND z<100}      t1z  300
   12  {z>2 AND z<100}       t1z  100
   13  {z>=3 AND z<100}      t1z  100
   14  {z>3 AND z<100}       t1z   50
   15  {z>=4 AND z<100}      t1z   50
   16  {z>=-100 AND z<=-1}   t1z   50
   17  {z>=-100 AND z<=0}    t1z  400
   18  {z>=-100 AND z<0}     t1z   50
   19  {z>=-100 AND z<=1}    t1z  700
   20  {z>=-100 AND z<2}     t1z  700
   21  {z>=-100 AND z<=2}    {}   111
   22  {z>=-100 AND z<3}     {}   111
  
   31  {z>=0.0 AND z<=0.0}   t1z  400
   32  {z>=1.0 AND z<=1.0}   t1z  300
   33  {z>=2.0 AND z<=2.0}   t1z  200
   34  {z>=3.0 AND z<=3.0}   t1z  100
   35  {z>=4.0 AND z<=4.0}   t1z   50
   36  {z>=-1.0 AND z<=-1.0} t1z   50
   37  {z>1.5 AND z<3.0}     t1z  200
   38  {z>0.5 AND z<100}     t1z  600
   39  {z>=1.0 AND z<100}    t1z  600
   40  {z>1.5 AND z<100}     t1z  300
   41  {z>=2.0 AND z<100}    t1z  300
   42  {z>2.1 AND z<100}     t1z  100
   43  {z>=3.0 AND z<100}    t1z  100
   44  {z>3.2 AND z<100}     t1z   50
   45  {z>=4.0 AND z<100}    t1z   50
   46  {z>=-100 AND z<=-1.0} t1z   50
   47  {z>=-100 AND z<=0.0}  t1z  400
   48  {z>=-100 AND z<0.0}   t1z   50
   49  {z>=-100 AND z<=1.0}  t1z  700
   50  {z>=-100 AND z<2.0}   t1z  700
   51  {z>=-100 AND z<=2.0}  {}   111
   52  {z>=-100 AND z<3.0}   {}   111
  
  101  {z=-1}                t1z   50
  102  {z=0}                 t1z  400
  103  {z=1}                 t1z  300
  104  {z=2}                 t1z  200
  105  {z=3}                 t1z  100
  106  {z=4}                 t1z   50
  107  {z=-10.0}             t1z   50
  108  {z=0.0}               t1z  400
  109  {z=1.0}               t1z  300
  110  {z=2.0}               t1z  200
  111  {z=3.0}               t1z  100
  112  {z=4.0}               t1z   50
  113  {z=1.5}               t1z   50
  114  {z=2.5}               t1z   50
  
  201  {z IN (-1)}           t1z   50
  202  {z IN (0)}            t1z  400
  203  {z IN (1)}            t1z  300
  204  {z IN (2)}            t1z  200
  205  {z IN (3)}            t1z  100
  206  {z IN (4)}            t1z   50
  207  {z IN (0.5)}          t1z   50
  208  {z IN (0,1)}          t1z  700
  209  {z IN (0,1,2)}        {}   100
  210  {z IN (0,1,2,3)}      {}   100
  211  {z IN (0,1,2,3,4,5)}  {}   100
  212  {z IN (1,2)}          t1z  500
  213  {z IN (2,3)}          t1z  300
  214  {z=3 OR z=2}          t1z  300
  215  {z IN (-1,3)}         t1z  150
  216  {z=-1 OR z=3}         t1z  150

  300  {y=0}                 {}   100
  301  {y=1}                 t1y   50
  302  {y=0.1}               t1y   50

} {
  # Verify that the expected index is used with the expected row count
  do_test analyze5-1.${testid}a {
    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
    set idx {}
    regexp {INDEX (t1.) } $x all idx
    regexp {~([0-9]+) rows} $x all nrow
    list $idx $nrow
  } [list $index $rows]

  # Verify that the same result is achieved regardless of whether or not
  # the index is used
  do_test analyze5-1.${testid}b {
    set w2 [string map {y +y z +z} $where]
    set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
                     ORDER BY +rowid"]
    set a2 [db eval "SELECT rowid FROM t1 WHERE $where ORDER BY +rowid"]
    if {$a1==$a2} {
      set res ok
    } else {
      set res "a1=\[$a1\] a2=\[$a2\]"
    }
    set res
  } {ok}
}


finish_test

Changes to test/e_createtable.test.

1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
  1    "EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b = 5" 
       {0 0 0 {SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (b=?) (~1 rows)}}

  2    "EXPLAIN QUERY PLAN SELECT * FROM t2 ORDER BY b, c"
       {0 0 0 {SCAN TABLE t2 USING INDEX sqlite_autoindex_t2_1 (~1000000 rows)}}

  3    "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE b=10 AND c>10"
       {0 0 0 {SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (b=? AND c>?) (~3 rows)}}
}

# EVIDENCE-OF: R-45493-35653 A CHECK constraint may be attached to a
# column definition or specified as a table constraint. In practice it
# makes no difference.
#
#   All the tests that deal with CHECK constraints below (4.11.* and 







|







1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
  1    "EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b = 5" 
       {0 0 0 {SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (b=?) (~1 rows)}}

  2    "EXPLAIN QUERY PLAN SELECT * FROM t2 ORDER BY b, c"
       {0 0 0 {SCAN TABLE t2 USING INDEX sqlite_autoindex_t2_1 (~1000000 rows)}}

  3    "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE b=10 AND c>10"
       {0 0 0 {SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (b=? AND c>?) (~2 rows)}}
}

# EVIDENCE-OF: R-45493-35653 A CHECK constraint may be attached to a
# column definition or specified as a table constraint. In practice it
# makes no difference.
#
#   All the tests that deal with CHECK constraints below (4.11.* and 

Changes to test/eqp.test.

388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411

# EVIDENCE-OF: R-22253-05302 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
# t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2; 0|0|0|SEARCH TABLE t1
# USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|1|SCAN TABLE t2
# (~1000000 rows)
do_execsql_test 5.4.0 {CREATE TABLE t2(c, d)}
det 5.4.1 "SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2" {
  0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)}
  0 1 1 {SCAN TABLE t2 (~1000000 rows)}
}

# EVIDENCE-OF: R-21040-07025 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
# t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2; 0|0|1|SEARCH TABLE t1
# USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|0|SCAN TABLE t2
# (~1000000 rows)
det 5.5 "SELECT t1.*, t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2" {
  0 0 1 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)}
  0 1 0 {SCAN TABLE t2 (~1000000 rows)}
}

# EVIDENCE-OF: R-39007-61103 sqlite> CREATE INDEX i3 ON t1(b);
# sqlite> EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=1 OR b=2;
# 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
# 0|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) (~10 rows)







|








|







388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411

# EVIDENCE-OF: R-22253-05302 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
# t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2; 0|0|0|SEARCH TABLE t1
# USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|1|SCAN TABLE t2
# (~1000000 rows)
do_execsql_test 5.4.0 {CREATE TABLE t2(c, d)}
det 5.4.1 "SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2" {
  0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~2 rows)}
  0 1 1 {SCAN TABLE t2 (~1000000 rows)}
}

# EVIDENCE-OF: R-21040-07025 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
# t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2; 0|0|1|SEARCH TABLE t1
# USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|0|SCAN TABLE t2
# (~1000000 rows)
det 5.5 "SELECT t1.*, t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2" {
  0 0 1 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~2 rows)}
  0 1 0 {SCAN TABLE t2 (~1000000 rows)}
}

# EVIDENCE-OF: R-39007-61103 sqlite> CREATE INDEX i3 ON t1(b);
# sqlite> EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=1 OR b=2;
# 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
# 0|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) (~10 rows)

Changes to test/indexedby.test.

150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
# Test embedding an INDEXED BY in a CREATE VIEW statement. This block
# also tests that nothing bad happens if an index refered to by
# a CREATE VIEW statement is dropped and recreated.
#
do_execsql_test indexedby-5.1 {
  CREATE VIEW v2 AS SELECT * FROM t1 INDEXED BY i1 WHERE a > 5;
  EXPLAIN QUERY PLAN SELECT * FROM v2 
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~330000 rows)}}
do_execsql_test indexedby-5.2 {
  EXPLAIN QUERY PLAN SELECT * FROM v2 WHERE b = 10 
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~33000 rows)}}
do_test indexedby-5.3 {
  execsql { DROP INDEX i1 }
  catchsql { SELECT * FROM v2 }
} {1 {no such index: i1}}
do_test indexedby-5.4 {
  # Recreate index i1 in such a way as it cannot be used by the view query.
  execsql { CREATE INDEX i1 ON t1(b) }







|


|







150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
# Test embedding an INDEXED BY in a CREATE VIEW statement. This block
# also tests that nothing bad happens if an index refered to by
# a CREATE VIEW statement is dropped and recreated.
#
do_execsql_test indexedby-5.1 {
  CREATE VIEW v2 AS SELECT * FROM t1 INDEXED BY i1 WHERE a > 5;
  EXPLAIN QUERY PLAN SELECT * FROM v2 
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~250000 rows)}}
do_execsql_test indexedby-5.2 {
  EXPLAIN QUERY PLAN SELECT * FROM v2 WHERE b = 10 
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~25000 rows)}}
do_test indexedby-5.3 {
  execsql { DROP INDEX i1 }
  catchsql { SELECT * FROM v2 }
} {1 {no such index: i1}}
do_test indexedby-5.4 {
  # Recreate index i1 in such a way as it cannot be used by the view query.
  execsql { CREATE INDEX i1 ON t1(b) }

Changes to test/like.test.

703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
...
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
...
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
      INSERT INTO t10 VALUES(12,12,12,12,12,12);
      INSERT INTO t10 VALUES(123,123,123,123,123,123);
      INSERT INTO t10 VALUES(234,234,234,234,234,234);
      INSERT INTO t10 VALUES(345,345,345,345,345,345);
      INSERT INTO t10 VALUES(45,45,45,45,45,45);
    }
    count {
      SELECT a FROM t10 WHERE b LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.2 {
    count {
      SELECT a FROM t10 WHERE c LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.3 {
    count {
      SELECT a FROM t10 WHERE d LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.4 {
    count {
      SELECT a FROM t10 WHERE e LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.5 {
    count {
      SELECT a FROM t10 WHERE f LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 3 like 0}
  do_test like-10.6 {
    count {
      SELECT a FROM t10 WHERE a LIKE '12%' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.10 {
    execsql {
      CREATE TABLE t10b(
        a INTEGER PRIMARY KEY,
        b INTEGER UNIQUE,
................................................................................
        d BLOB UNIQUE,
        e UNIQUE,
        f TEXT UNIQUE
      );
      INSERT INTO t10b SELECT * FROM t10;
    }
    count {
      SELECT a FROM t10b WHERE b GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.11 {
    count {
      SELECT a FROM t10b WHERE c GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.12 {
    count {
      SELECT a FROM t10b WHERE d GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.13 {
    count {
      SELECT a FROM t10b WHERE e GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.14 {
    count {
      SELECT a FROM t10b WHERE f GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 3 like 0}
  do_test like-10.15 {
    count {
      SELECT a FROM t10b WHERE a GLOB '12*' ORDER BY a;
    }
  } {12 123 scan 5 like 6}
}

# LIKE and GLOB where the default collating sequence is not appropriate
# but an index with the appropriate collating sequence exists.
#
................................................................................
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 *}
do_test like-11.3 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    CREATE INDEX t11b ON t11(b);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd ABC ABCD sort {} t11b}
do_test like-11.4 {
  queryplan {
    PRAGMA case_sensitive_like=ON;
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 *}
do_test like-11.5 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    DROP INDEX t11b;
    CREATE INDEX t11bnc ON t11(b COLLATE nocase);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd ABC ABCD sort {} t11bnc}
do_test like-11.6 {
  queryplan {
    CREATE INDEX t11bb ON t11(b COLLATE binary);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd ABC ABCD sort {} t11bnc}
do_test like-11.7 {
  queryplan {
    PRAGMA case_sensitive_like=ON;
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd sort {} t11bb}
do_test like-11.8 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    SELECT b FROM t11 WHERE b GLOB 'abc*' ORDER BY a;
  }
} {abc abcd sort {} t11bb}
do_test like-11.9 {
  queryplan {
    CREATE INDEX t11cnc ON t11(c COLLATE nocase);
    CREATE INDEX t11cb ON t11(c COLLATE binary);
    SELECT c FROM t11 WHERE c LIKE 'abc%' ORDER BY a;
  }
} {abc abcd ABC ABCD sort {} t11cnc}
do_test like-11.10 {
  queryplan {
    SELECT c FROM t11 WHERE c GLOB 'abc*' ORDER BY a;
  }
} {abc abcd sort {} t11cb}


finish_test







|




|




|




|




|




|







 







|




|




|




|




|




|







 







|













|





|





|





|






|




|





703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
...
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
...
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
      INSERT INTO t10 VALUES(12,12,12,12,12,12);
      INSERT INTO t10 VALUES(123,123,123,123,123,123);
      INSERT INTO t10 VALUES(234,234,234,234,234,234);
      INSERT INTO t10 VALUES(345,345,345,345,345,345);
      INSERT INTO t10 VALUES(45,45,45,45,45,45);
    }
    count {
      SELECT a FROM t10 WHERE b LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.2 {
    count {
      SELECT a FROM t10 WHERE c LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.3 {
    count {
      SELECT a FROM t10 WHERE d LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.4 {
    count {
      SELECT a FROM t10 WHERE e LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.5 {
    count {
      SELECT a FROM t10 WHERE f LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 3 like 0}
  do_test like-10.6 {
    count {
      SELECT a FROM t10 WHERE a LIKE '12%' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.10 {
    execsql {
      CREATE TABLE t10b(
        a INTEGER PRIMARY KEY,
        b INTEGER UNIQUE,
................................................................................
        d BLOB UNIQUE,
        e UNIQUE,
        f TEXT UNIQUE
      );
      INSERT INTO t10b SELECT * FROM t10;
    }
    count {
      SELECT a FROM t10b WHERE b GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.11 {
    count {
      SELECT a FROM t10b WHERE c GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.12 {
    count {
      SELECT a FROM t10b WHERE d GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.13 {
    count {
      SELECT a FROM t10b WHERE e GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
  do_test like-10.14 {
    count {
      SELECT a FROM t10b WHERE f GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 3 like 0}
  do_test like-10.15 {
    count {
      SELECT a FROM t10b WHERE a GLOB '12*' ORDER BY +a;
    }
  } {12 123 scan 5 like 6}
}

# LIKE and GLOB where the default collating sequence is not appropriate
# but an index with the appropriate collating sequence exists.
#
................................................................................
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 *}
do_test like-11.3 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    CREATE INDEX t11b ON t11(b);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd ABC ABCD sort {} t11b}
do_test like-11.4 {
  queryplan {
    PRAGMA case_sensitive_like=ON;
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 *}
do_test like-11.5 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    DROP INDEX t11b;
    CREATE INDEX t11bnc ON t11(b COLLATE nocase);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd ABC ABCD sort {} t11bnc}
do_test like-11.6 {
  queryplan {
    CREATE INDEX t11bb ON t11(b COLLATE binary);
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd ABC ABCD sort {} t11bnc}
do_test like-11.7 {
  queryplan {
    PRAGMA case_sensitive_like=ON;
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd sort {} t11bb}
do_test like-11.8 {
  queryplan {
    PRAGMA case_sensitive_like=OFF;
    SELECT b FROM t11 WHERE b GLOB 'abc*' ORDER BY +a;
  }
} {abc abcd sort {} t11bb}
do_test like-11.9 {
  queryplan {
    CREATE INDEX t11cnc ON t11(c COLLATE nocase);
    CREATE INDEX t11cb ON t11(c COLLATE binary);
    SELECT c FROM t11 WHERE c LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd ABC ABCD sort {} t11cnc}
do_test like-11.10 {
  queryplan {
    SELECT c FROM t11 WHERE c GLOB 'abc*' ORDER BY +a;
  }
} {abc abcd sort {} t11cb}


finish_test

Changes to test/minmax3.test.

48
49
50
51
52
53
54

55
56
57
58
59
60
61
    INSERT INTO t1 VALUES('1', 'I',   'one');
    INSERT INTO t1 VALUES('2', 'IV',  'four');
    INSERT INTO t1 VALUES('2', NULL,  'three');
    INSERT INTO t1 VALUES('2', 'II',  'two');
    INSERT INTO t1 VALUES('2', 'V',   'five');
    INSERT INTO t1 VALUES('3', 'VI',  'six');
    COMMIT;

  }
} {}
do_test minmax3-1.1.1 {
  # Linear scan.
  count { SELECT max(y) FROM t1 WHERE x = '2'; }
} {V 5}
do_test minmax3-1.1.2 {







>







48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
    INSERT INTO t1 VALUES('1', 'I',   'one');
    INSERT INTO t1 VALUES('2', 'IV',  'four');
    INSERT INTO t1 VALUES('2', NULL,  'three');
    INSERT INTO t1 VALUES('2', 'II',  'two');
    INSERT INTO t1 VALUES('2', 'V',   'five');
    INSERT INTO t1 VALUES('3', 'VI',  'six');
    COMMIT;
    PRAGMA automatic_index=OFF;
  }
} {}
do_test minmax3-1.1.1 {
  # Linear scan.
  count { SELECT max(y) FROM t1 WHERE x = '2'; }
} {V 5}
do_test minmax3-1.1.2 {

Changes to test/where3.test.

221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
  CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
  CREATE INDEX t301c ON t301(c);
  INSERT INTO t301 VALUES(1,2,3);
  CREATE TABLE t302(x, y);
  ANALYZE;
  explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 0 {SCAN TABLE t302 (~0 rows)} 
  0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
}
do_execsql_test where3-3.1 {
  explain query plan
  SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 1 {SCAN TABLE t302 (~0 rows)} 
  0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
}

# Verify that when there are multiple tables in a join which must be
# full table scans that the query planner attempts put the table with
# the fewest number of output rows as the outer loop.
#







|






|







221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
  CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
  CREATE INDEX t301c ON t301(c);
  INSERT INTO t301 VALUES(1,2,3);
  CREATE TABLE t302(x, y);
  ANALYZE;
  explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 0 {SCAN TABLE t302 (~1 rows)} 
  0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
}
do_execsql_test where3-3.1 {
  explain query plan
  SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 1 {SCAN TABLE t302 (~1 rows)} 
  0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
}

# Verify that when there are multiple tables in a join which must be
# full table scans that the query planner attempts put the table with
# the fewest number of output rows as the outer loop.
#

Changes to test/where9.test.

468
469
470
471
472
473
474
475
476
477
478
479
480
481
482

  # Likewise, inequalities in an AND are preferred over inequalities in
  # an OR.
  #
  do_execsql_test where9-5.3 {
    EXPLAIN QUERY PLAN SELECT a FROM t1 WHERE b>1000 AND (c>=31031 OR d IS NULL)
  } {
    0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>?) (~165000 rows)}
  }
}

############################################################################
# Make sure OR-clauses work correctly on UPDATE and DELETE statements.

do_test where9-6.2.1 {







|







468
469
470
471
472
473
474
475
476
477
478
479
480
481
482

  # Likewise, inequalities in an AND are preferred over inequalities in
  # an OR.
  #
  do_execsql_test where9-5.3 {
    EXPLAIN QUERY PLAN SELECT a FROM t1 WHERE b>1000 AND (c>=31031 OR d IS NULL)
  } {
    0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>?) (~125000 rows)}
  }
}

############################################################################
# Make sure OR-clauses work correctly on UPDATE and DELETE statements.

do_test where9-6.2.1 {