SQLite4  Check-in [2fbe583868]

  WhereTerm **aLTerm;   /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
  WhereTerm *aLTermSpace[4];  /* Initial aLTerm[] space */
};

/* This object holds the prerequisites and the cost of running a
** subquery on one operand of an OR operator in the WHERE clause.
** See WhereOrSet for additional information
*/
struct WhereOrCost {
  Bitmask prereq;     /* Prerequisites */
  WhereCost rRun;     /* Cost of running this subquery */
  WhereCost nOut;     /* Number of outputs for this subquery */
};

  sqlite4DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif


/*
** Return TRUE if the WHERE clause term pTerm is of a form where it
** could be used with an index to access pSrc, assuming an appropriate
** index existed.
*/
static int termCanDriveIndex(
  WhereTerm *pTerm,              /* WHERE clause term to check */
  struct SrcListItem *pSrc,     /* Table we are trying to access */
  Bitmask notReady               /* Tables in outer loops of the join */
){
  char aff;
  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  if( pTerm->u.leftColumn<0 ) return 0;
  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  if( !sqlite4IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  return 1;
}



#ifndef SQLITE4_OMIT_AUTOMATIC_INDEX
/*
** Generate code to construct the Index object for an automatic index
** and to set up the WhereLevel object pLevel so that the code generator
** makes use of the automatic index.

**    aStat[1]      Est. number of rows equal to pVal
**
** Return SQLITE4_OK on success.
*/
static int whereKeyStats(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite4_value *pVal,        /* Value to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  tRowcnt n;
  IndexSample *aSample;
  int i, eType;
  int isEq = 0;
  i64 v;
  double r, rS;

  assert( roundUp==0 || roundUp==1 );
  assert( pIdx->nSample>0 );

  if( pVal==0 ) return SQLITE4_ERROR;
  n = pIdx->aiRowEst[0];
  aSample = pIdx->aSample;
  eType = sqlite4_value_type(pVal);

  if( eType==SQLITE4_INTEGER ){
    v = sqlite4_value_int64(pVal);
    r = (i64)v;
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_NULL ) continue;
      if( aSample[i].eType>=SQLITE4_TEXT ) break;
      if( aSample[i].eType==SQLITE4_INTEGER ){
        if( aSample[i].u.i>=v ){
          isEq = aSample[i].u.i==v;
          break;
        }
      }else{
        assert( aSample[i].eType==SQLITE4_FLOAT );
        if( aSample[i].u.r>=r ){
          isEq = aSample[i].u.r==r;
          break;
        }
      }
    }
  }else if( eType==SQLITE4_FLOAT ){
    r = sqlite4_value_double(pVal);
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_NULL ) continue;
      if( aSample[i].eType>=SQLITE4_TEXT ) break;
      if( aSample[i].eType==SQLITE4_FLOAT ){
        rS = aSample[i].u.r;
      }else{
        rS = aSample[i].u.i;
      }
      if( rS>=r ){
        isEq = rS==r;
        break;
      }
    }
  }else if( eType==SQLITE4_NULL ){
    i = 0;
    if( aSample[0].eType==SQLITE4_NULL ) isEq = 1;
  }else{
    assert( eType==SQLITE4_TEXT || eType==SQLITE4_BLOB );
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_TEXT || aSample[i].eType==SQLITE4_BLOB ){
        break;
      }
    }
    if( i<pIdx->nSample ){      
      sqlite4 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      if( eType==SQLITE4_BLOB ){
        z = (const u8 *)sqlite4_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE4_UTF8 );
      }else{
        pColl = sqlite4GetCollSeq(pParse, SQLITE4_UTF8, 0, *pIdx->azColl);
        /* If the collating sequence was unavailable, we should have failed
        ** long ago and never reached this point.  But we'll check just to
        ** be doubly sure. */
        if( NEVER(pColl==0) ) return SQLITE4_ERROR;
        z = (const u8 *)sqlite4ValueText(pVal, pColl->enc);
        if( !z ){
          return SQLITE4_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite4ValueBytes(pVal, pColl->enc);
  
      for(; i<pIdx->nSample; i++){
        int c;
        int eSampletype = aSample[i].eType;
        if( eSampletype<eType ) continue;
        if( eSampletype!=eType ) break;
#ifndef SQLITE4_OMIT_UTF16
        if( pColl->enc!=SQLITE4_UTF8 ){
          int nSample;
          char *zSample = sqlite4Utf8to16(
              db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
          );
          if( !zSample ){
            assert( db->mallocFailed );
            return SQLITE4_NOMEM;
          }
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite4DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( c>=0 ){
          if( c==0 ) isEq = 1;
          break;
        }
      }
    }
  }

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */

    aStat[0] = iLower + iGap;
  }
  return SQLITE4_OK;
}
#endif /* SQLITE4_ENABLE_STAT3 */

/*
** If expression pExpr represents a literal value, set *pp to point to
** an sqlite4_value structure containing the same value, with affinity
** aff applied to it, before returning. It is the responsibility of the 
** caller to eventually release this structure by passing it to 
** sqlite4ValueFree().
**
** If the current parse is a recompile (sqlite4Reprepare()) and pExpr
** is an SQL variable that currently has a non-NULL value bound to it,
** create an sqlite4_value structure containing this value, again with
** affinity aff applied to it, instead.
**
** If neither of the above apply, set *pp to NULL.
**
** If an error occurs, return an error code. Otherwise, SQLITE4_OK.
*/
#ifdef SQLITE4_ENABLE_STAT3
static int valueFromExpr(
  Parse *pParse, 

  Expr *pExpr, 
  u8 aff, 
  sqlite4_value **pp
){






  if( pExpr->op==TK_VARIABLE
   || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
  ){
    int iVar = pExpr->iColumn;
    sqlite4VdbeSetVarmask(pParse->pVdbe, iVar);
    *pp = sqlite4VdbeGetValue(pParse->pReprepare, iVar, aff);








    return SQLITE4_OK;

  }


  return sqlite4ValueFromExpr(pParse->db, pExpr, SQLITE4_UTF8, aff, pp);


}
#endif


















/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):

  WhereCost *pRangeDiv /* OUT: Reduce search space by this divisor */
){
  int rc = SQLITE4_OK;

#ifdef SQLITE4_ENABLE_STAT3

  if( nEq==0 && p->nSample && OptimizationEnabled(pParse->db, SQLITE4_Stat3) ){


    sqlite4_value *pRangeVal;
    tRowcnt iLower = 0;
    tRowcnt iUpper = p->aiRowEst[0];
    tRowcnt a[2];
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;




    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      if( rc==SQLITE4_OK
       && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE4_OK
      ){
        iLower = a[0];
        if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
      }
      sqlite4ValueFree(pRangeVal);
    }
    if( rc==SQLITE4_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      if( rc==SQLITE4_OK
       && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE4_OK
      ){
        iUpper = a[0];
        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
      }
      sqlite4ValueFree(pRangeVal);
    }

    if( rc==SQLITE4_OK ){
      WhereCost iBase = whereCost(p->aiRowEst[0]);
      if( iUpper>iLower ){
        iBase -= whereCost(iUpper - iLower);
      }
      *pRangeDiv = iBase;
      WHERETRACE(0x100, ("range scan regions: %u..%u  div=%d\n",

*/
static 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 */
  tRowcnt *pnRow       /* Write the revised row estimate here */
){
  sqlite4_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  tRowcnt a[2];             /* Statistics */

  assert( p->aSample!=0 );
  assert( p->nSample>0 );

  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){



    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;

  }else{


    pRhs = sqlite4ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE4_NOTFOUND;

  rc = whereKeyStats(pParse, p, pRhs, 0, a);
  if( rc==SQLITE4_OK ){
    WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
  }

whereEqualScanEst_cancel:
  sqlite4ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE4_ENABLE_STAT3) */

#ifdef SQLITE4_ENABLE_STAT3
/*
** Estimate the number of rows that will be returned based on

    if( pItem->zAlias ){
      zMsg = sqlite4MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
    }
    if( (flags & WHERE_VIRTUALTABLE)==0
     && ALWAYS(pLoop->u.btree.pIndex!=0)
    ){
      char *zWhere = explainIndexRange(db, pLoop, pItem->pTab);
      zMsg = sqlite4MAppendf(db, zMsg,
               ((flags & WHERE_AUTO_INDEX) ? 
                   "%s USING AUTOMATIC %sINDEX%.0s%s" :




                   "%s USING %sINDEX %s%s"), 




               zMsg, ((flags & WHERE_IDX_ONLY) ? "COVERING " : ""),

               pLoop->u.btree.pIndex->zName, zWhere);



      sqlite4DbFree(db, zWhere);
#if 0
    }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){
      zMsg = sqlite4MAppendf(db, zMsg, "%s USING INTEGER PRIMARY KEY", zMsg);

      if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){
        zMsg = sqlite4MAppendf(db, zMsg, "%s (rowid=?)", zMsg);

  }
  execsql COMMIT
  execsql ANALYZE
} {}

do_eqp_test analyze3-1.1.2 {
  SELECT sum(y) FROM t1 WHERE x>200 AND x<300
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (x>? AND x<?) (~160 rows)}}
do_eqp_test analyze3-1.1.3 {
  SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (x>? AND x<?) (~985 rows)}}
do_test analyze3-1.1.4 {
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>200 AND x<300 }
} {199 0 14850}
do_test analyze3-1.1.5 {
  set l [string range "200" 0 end]
  set u [string range "300" 0 end]
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u }

      CREATE INDEX i2 ON t2(x);
    COMMIT;
    ANALYZE;
  }
} {}
do_eqp_test analyze3-1.2.2 {
  SELECT sum(y) FROM t2 WHERE x>1 AND x<2
} {0 0 0 {SEARCH TABLE t2 USING INDEX i2 (x>? AND x<?) (~193 rows)}}
do_eqp_test analyze3-1.2.3 {
  SELECT sum(y) FROM t2 WHERE x>0 AND x<99
} {0 0 0 {SEARCH TABLE t2 USING INDEX i2 (x>? AND x<?) (~972 rows)}}
do_test analyze3-1.2.4 {
  sf_execsql { SELECT sum(y) FROM t2 WHERE x>12 AND x<20 }
} {161 0 4760}
do_test analyze3-1.2.5 {
  set l [string range "12" 0 end]
  set u [string range "20" 0 end]
  sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u}

      CREATE INDEX i3 ON t3(x);
    COMMIT;
    ANALYZE;
  }
} {}
do_eqp_test analyze3-1.3.2 {
  SELECT sum(y) FROM t3 WHERE x>200 AND x<300
} {0 0 0 {SEARCH TABLE t3 USING INDEX i3 (x>? AND x<?) (~107 rows)}}
do_eqp_test analyze3-1.3.3 {
  SELECT sum(y) FROM t3 WHERE x>0 AND x<1100
} {0 0 0 {SEARCH TABLE t3 USING INDEX i3 (x>? AND x<?) (~972 rows)}}

do_test analyze3-1.3.4 {
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>200 AND x<300 }
} {199 0 14850}
do_test analyze3-1.3.5 {
  set l [string range "200" 0 end]
  set u [string range "300" 0 end]

    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<?) (~31250 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%' }
} {201 0 100}
do_test analyze3-2.5 {
  sf_execsql { SELECT count(*) FROM t1 WHERE b LIKE '%a' }
} {1001 999 100}

do_test analyze3-3.2.5 {
  set S [sqlite4_prepare db "SELECT * FROM t1 WHERE b=?" -1 dummy]
  test_for_recompile $S
} {0}
do_test analyze3-3.2.6 {
  sqlite4_bind_text $S 1 "abc" 3
  test_for_recompile $S
} {0}
do_test analyze3-3.2.7 {
  sqlite4_finalize $S
} {SQLITE4_OK}

do_test analyze3-3.4.1 {
  set S [sqlite4_prepare db "SELECT * FROM t1 WHERE a=? AND b>?" -1 dummy]
  test_for_recompile $S

set testprefix analyze5

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

# This command is registered as a user-defined function with the database
# handle. The blob passed as the only argument is a text-value encoded
# using the sqlite4 key-encoding with collation sequence BINARY. This
# command extracts and returns the text value.
#
proc decode {blob} {

  binary scan $blob c* vars
  binary format c* [lrange $vars 1 end-1]

}


db func decode decode

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

    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 decode(sample) FROM sqlite_stat3 WHERE idx='t1u' ORDER BY nlt;
  }
} {alpha bravo charlie delta}

do_test analyze5-1.1 {


  db eval {SELECT DISTINCT decode(sample) FROM sqlite_stat3 WHERE idx='t1v'
             ORDER BY 1}

} {alpha bravo charlie delta}
do_test analyze5-1.2 {
  db eval {SELECT idx, count(*) FROM sqlite_stat3 GROUP BY 1 ORDER BY 1}
} {t1 24 t1t 4 t1u 4 t1v 4 t1w 4 t1x 4 t1y 2 t1z 4}

# Verify that range queries generate the correct row count estimates
#

  301  {y=1}                 t1y   26
  302  {y=0.1}               t1y    1

  400  {x IS NULL}           t1x  400

} {
  # 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"]

  503  {x=1}                               t1x   1
  504  {x IS NOT NULL}                     t1x   2
  505  {+x IS NOT NULL}                     {} 500
  506  {upper(x) IS NOT NULL}               {} 500

} {
  # Verify that the expected index is used with the expected row count
if {$testid==50299} {breakpoint; set sqlite_where_trace 1}
  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]
if {$testid==50299} exit

  # 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"]

# The lowest cost plan is to scan CAT and for each integer there, do a single
# lookup of the first corresponding entry in EV then read off the equal values
# in EV.  (Prior to the 2011-03-04 enhancement to where.c, this query would
# have used EV for the outer loop instead of CAT - which was about 3x slower.)
#
do_test analyze6-1.1 {
  eqp {SELECT count(*) FROM ev, cat WHERE x=y}
} {0 0 1 {SCAN TABLE cat (~16 rows)} 0 1 0 {SEARCH TABLE ev USING INDEX evy (y=?) (~32 rows)}}

# The same plan is chosen regardless of the order of the tables in the
# FROM clause.
#
do_test analyze6-1.2 {
  eqp {SELECT count(*) FROM cat, ev WHERE x=y}
} {0 0 0 {SCAN TABLE cat (~16 rows)} 0 1 1 {SEARCH TABLE ev USING INDEX evy (y=?) (~32 rows)}}


# Ticket [83ea97620bd3101645138b7b0e71c12c5498fe3d] 2011-03-30
# If ANALYZE is run on an empty table, make sure indices are used
# on the table.
#
do_test analyze6-2.1 {
  execsql {
    CREATE TABLE t201(x INTEGER PRIMARY KEY, y UNIQUE, z);
    CREATE INDEX t201z ON t201(z);
    ANALYZE;
  }
  eqp {SELECT * FROM t201 WHERE z=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX t201z (z=?) (~10 rows)}}
do_test analyze6-2.2 {
  eqp {SELECT * FROM t201 WHERE y=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX sqlite_t201_unique2 (y=?) (~1 rows)}}
do_test analyze6-2.3 {
  eqp {SELECT * FROM t201 WHERE x=5}
} {0 0 0 {SEARCH TABLE t201 USING PRIMARY KEY (x=?) (~1 rows)}}
do_test analyze6-2.4 {
  execsql {
    INSERT INTO t201 VALUES(1,2,3);
    ANALYZE t201;
  }
  eqp {SELECT * FROM t201 WHERE z=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX t201z (z=?) (~10 rows)}}
do_test analyze6-2.5 {
  eqp {SELECT * FROM t201 WHERE y=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX sqlite_t201_unique2 (y=?) (~1 rows)}}
do_test analyze6-2.6 {
  eqp {SELECT * FROM t201 WHERE x=5}
} {0 0 0 {SEARCH TABLE t201 USING PRIMARY KEY (x=?) (~1 rows)}}
do_test analyze6-2.7 {
  execsql {
    INSERT INTO t201 VALUES(4,5,7);
    INSERT INTO t201 SELECT x+100, y+100, z+100 FROM t201;
    INSERT INTO t201 SELECT x+200, y+200, z+200 FROM t201;
    INSERT INTO t201 SELECT x+400, y+400, z+400 FROM t201;
    ANALYZE t201;
  }
  eqp {SELECT * FROM t201 WHERE z=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX t201z (z=?) (~10 rows)}}
do_test analyze6-2.8 {
  eqp {SELECT * FROM t201 WHERE y=5}
} {0 0 0 {SEARCH TABLE t201 USING INDEX sqlite_t201_unique2 (y=?) (~1 rows)}}
do_test analyze6-2.9 {
  eqp {SELECT * FROM t201 WHERE x=5}
} {0 0 0 {SEARCH TABLE t201 USING PRIMARY KEY (x=?) (~1 rows)}}

finish_test

# with a==100.  And so for those cases, choose the t1b index.
#
# Buf ro a==99 and a==101, there are far fewer rows so choose
# the t1a index.
#
do_test 1.1 {
  eqp {SELECT * FROM t1 WHERE a=100 AND b=55}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?) (~2 rows)}}
do_test 1.2 {
  eqp {SELECT * FROM t1 WHERE a=99 AND b=55}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test 1.3 {
  eqp {SELECT * FROM t1 WHERE a=101 AND b=55}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test 1.4 {
  eqp {SELECT * FROM t1 WHERE a=100 AND b=56}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?) (~2 rows)}}
do_test 1.5 {
  eqp {SELECT * FROM t1 WHERE a=99 AND b=56}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test 1.6 {
  eqp {SELECT * FROM t1 WHERE a=101 AND b=56}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test 2.1 {
  eqp {SELECT * FROM t1 WHERE a=100 AND b BETWEEN 50 AND 54}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?) (~2 rows)}}

# There are many more values of c between 0 and 100000 than there are
# between 800000 and 900000.  So t1c is more selective for the latter
# range.
#
do_test 3.1 {
  eqp {SELECT * FROM t1 WHERE b BETWEEN 50 AND 54 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?) (~6 rows)}}
do_test 3.2 {
  eqp {SELECT * FROM t1
       WHERE b BETWEEN 50 AND 54 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?) (~5 rows)}}
do_test 3.3 {
  eqp {SELECT * FROM t1 WHERE a=100 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~63 rows)}}
do_test 3.4 {
  eqp {SELECT * FROM t1
       WHERE a=100 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?) (~2 rows)}}

finish_test

  INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t501','t501','1000000');
  INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t502','t502','1000');
  ANALYZE sqlite_master;
  EXPLAIN QUERY PLAN
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=?);
} {
  0 0 0 {SEARCH TABLE t501 USING INDEX t501 (a=?)} 
  0 0 0 {EXECUTE LIST SUBQUERY 1} 
  1 0 0 {SCAN TABLE t502 USING INDEX t502}
}
do_execsql_test autoindex1-501 {
  EXPLAIN QUERY PLAN
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  0 0 0 {SCAN TABLE t501 USING INDEX t501} 
  0 0 0 {EXECUTE CORRELATED LIST SUBQUERY 1} 
  1 0 0 {SEARCH TABLE t502 USING AUTOMATIC COVERING INDEX (y=?)}
}
do_execsql_test autoindex1-502 {
  EXPLAIN QUERY PLAN
  SELECT b FROM t501
   WHERE t501.a=123
     AND t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  0 0 0 {SEARCH TABLE t501 USING INDEX t501 (a=?)}
  0 0 0 {EXECUTE CORRELATED LIST SUBQUERY 1} 
  1 0 0 {SCAN TABLE t502 USING INDEX t502}
}


# The following code checks a performance regression reported on the
# mailing list on 2010-10-19.  The problem is that the nRowEst field
# of ephermeral tables was not being initialized correctly and so no
# automatic index was being created for the emphemeral table when it was

           WHERE prev.flock_no = later.flock_no
           AND later.owner_change_date > prev.owner_change_date
           AND later.owner_change_date <= s.date_of_registration||' 00:00:00')
       ) y ON x.sheep_no = y.sheep_no
   WHERE y.sheep_no IS NULL
   ORDER BY x.registering_flock;
} {
  1 0 0 {SCAN TABLE sheep AS s USING INDEX sheep}
  1 1 1 {SEARCH TABLE flock_owner AS prev USING INDEX sqlite_flock_owner_unique2 (flock_no=? AND owner_change_date<?)} 
  1 0 0 {EXECUTE CORRELATED SCALAR SUBQUERY 2}
  2 0 0 {SEARCH TABLE flock_owner AS later USING INDEX sqlite_flock_owner_unique2 (flock_no=? AND owner_change_date>? AND owner_change_date<?)} 
  0 0 0 {SCAN TABLE sheep AS x USING INDEX sheep_reg_flock_index} 
  0 1 1 {SEARCH SUBQUERY 1 AS y USING AUTOMATIC COVERING INDEX (sheep_no=?)}
}


do_execsql_test autoindex1-700 {
  CREATE TABLE t5(a, b, c);
  EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
} {
  0 0 0 {SCAN TABLE t5 USING INDEX t5} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

# The following checks a performance issue reported on the sqlite-dev
# mailing list on 2013-01-10
#
do_execsql_test autoindex1-800 {

    SELECT * FROM t1 WHERE w BETWEEN 5 AND 6 ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 i1w}
do_test between-1.1.2 {
  queryplan {
    SELECT * FROM t1 WHERE +w BETWEEN 5 AND 6 ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 t1}
do_test between-1.2.1 {
  queryplan {
    SELECT * FROM t1 WHERE w BETWEEN 5 AND 65-y ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 i1w}
do_test between-1.2.2 {
  queryplan {
    SELECT * FROM t1 WHERE +w BETWEEN 5 AND 65-y ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 t1}
do_test between-1.3.1 {
  queryplan {
    SELECT * FROM t1 WHERE w BETWEEN 41-y AND 6 ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 i1w}
do_test between-1.3.2 {
  queryplan {
    SELECT * FROM t1 WHERE +w BETWEEN 41-y AND 6 ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 t1}
do_test between-1.4 {
  queryplan {
    SELECT * FROM t1 WHERE w BETWEEN 41-y AND 65-y ORDER BY +w
  }
} {5 2 36 38 6 2 49 51 sort t1 t1}
do_test between-1.5.1 {
  queryplan {
    SELECT * FROM t1 WHERE 26 BETWEEN y AND z ORDER BY +w
  }
} {4 2 25 27 sort t1 i1zyx}
do_test between-1.5.2 {
  queryplan {
    SELECT * FROM t1 WHERE 26 BETWEEN +y AND z ORDER BY +w
  }
} {4 2 25 27 sort t1 i1zyx}
do_test between-1.5.3 {
  queryplan {
    SELECT * FROM t1 WHERE 26 BETWEEN y AND +z ORDER BY +w
  }
} {4 2 25 27 sort t1 t1}


finish_test

#
do_execsql_test 4.10.0 {
  CREATE TABLE t1(a, b PRIMARY KEY);
  CREATE TABLE t2(a, b, c, UNIQUE(b, c));
}
do_createtable_tests 4.10 {
  1    "EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b = 5" 
       {0 0 0 {SEARCH TABLE t1 USING INDEX t1 (b=?)}}

  2    "EXPLAIN QUERY PLAN SELECT * FROM t2 ORDER BY b, c"
       {0 0 0 {SCAN TABLE t2 USING INDEX sqlite_t2_unique1}}

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

  }
} {}
do_execsql_test e_fkey-25.2 {
  PRAGMA foreign_keys = OFF;
  EXPLAIN QUERY PLAN DELETE FROM artist WHERE 1;
  EXPLAIN QUERY PLAN SELECT rowid FROM track WHERE trackartist = ?;
} {
  0 0 0 {SCAN TABLE artist USING INDEX artist} 
  0 0 0 {SCAN TABLE track USING INDEX track}
}
do_execsql_test e_fkey-25.3 {
  PRAGMA foreign_keys = ON;
  EXPLAIN QUERY PLAN DELETE FROM artist WHERE 1;
} {
  0 0 0 {SCAN TABLE artist USING INDEX artist}
  0 0 0 {SCAN TABLE track USING INDEX track}
}
do_test e_fkey-25.4 {
  execsql {
    INSERT INTO artist VALUES(5, 'artist 5');
    INSERT INTO artist VALUES(6, 'artist 6');
    INSERT INTO artist VALUES(7, 'artist 7');
    INSERT INTO track VALUES(1, 'track 1', 5);

} {}
do_test e_fkey-27.2 {
  eqp { INSERT INTO artist VALUES(?, ?) }
} {}
do_execsql_test e_fkey-27.3 {
  EXPLAIN QUERY PLAN UPDATE artist SET artistid = ?, artistname = ?
} {
  0 0 0 {SCAN TABLE artist USING INDEX artist}
  0 0 0 {SEARCH TABLE track USING INDEX trackindex (trackartist=?)} 
  0 0 0 {SEARCH TABLE track USING INDEX trackindex (trackartist=?)}
}
do_execsql_test e_fkey-27.4 {
  EXPLAIN QUERY PLAN DELETE FROM artist
} {
  0 0 0 {SCAN TABLE artist USING INDEX artist} 
  0 0 0 {SEARCH TABLE track USING INDEX trackindex (trackartist=?)}
}


###########################################################################
### SECTION 4.1: Composite Foreign Key Constraints
###########################################################################

# is performed.
#
do_test like-3.1 {
  set sqlite_like_count 0
  queryplan {
    SELECT x FROM t1 WHERE x LIKE 'abc%' ORDER BY 1;
  }
} {ABC {ABC abc xyz} abc abcd sort t1 t1}
do_test like-3.2 {
  set sqlite_like_count
} {12}

# With an index on t1.x and case sensitivity on, optimize completely.
#
do_test like-3.3 {

  db eval {
    PRAGMA case_sensitive_like=on;
    DROP INDEX i1;
  }
  queryplan {
    SELECT x FROM t1 WHERE x LIKE 'abc%' ORDER BY 1;
  }
} {abc abcd sort t1 t1}
do_test like-3.16 {
  set sqlite_like_count
} 12

# No GLOB optimization without an index.
#
do_test like-3.17 {
  set sqlite_like_count 0
  queryplan {
    SELECT x FROM t1 WHERE x GLOB 'abc*' ORDER BY 1;
  }
} {abc abcd sort t1 t1}
do_test like-3.18 {
  set sqlite_like_count
} 12

# GLOB is optimized regardless of the case_sensitive_like setting.
#
do_test like-3.19 {

  }
} {12}
do_test like-11.1 {
  db eval {PRAGMA case_sensitive_like=OFF;}
  queryplan {
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd ABC ABCD nosort t11 t11}
do_test like-11.2 {
  db eval {PRAGMA case_sensitive_like=ON;}
  queryplan {
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 t11}
do_test like-11.3 {
  db eval {
    PRAGMA case_sensitive_like=OFF;
    CREATE INDEX t11b ON t11(b);
  }
  queryplan {
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
  }
} {abc abcd ABC ABCD sort t11 t11b}
do_test like-11.4 {
  db eval {PRAGMA case_sensitive_like=ON;}
  queryplan {
    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
  }
} {abc abcd nosort t11 t11}
do_test like-11.5 {
  db eval {
    PRAGMA case_sensitive_like=OFF;
    DROP INDEX t11b;
    CREATE INDEX t11bnc ON t11(b COLLATE nocase);
  }
  queryplan {

} {10.0}
do_test subquery-2.5.3.2 {
  # Verify that the t4i index was not used in the previous query
  execsql {
    EXPLAIN QUERY PLAN
    SELECT * FROM t4 WHERE x IN (SELECT a FROM t3);
  }
} {/SCAN TABLE t4 /}
do_test subquery-2.5.4 {
  execsql {
    DROP TABLE t3;
    DROP TABLE t4;
  }
} {}

    WHERE t302.c2 = 19571
      AND t302.c3 > 1287603136
      AND (t301.c4 = 1407449685622784
           OR t301.c8 = 1407424651264000)
   ORDER BY t302.c5 LIMIT 200;
} {
  0 0 1 {SEARCH TABLE t301 USING INDEX t301_c4 (c4=?)}
  0 0 1 {SEARCH TABLE t301 USING INDEX t301 (c8=?)}
  0 1 0 {SEARCH TABLE t302 USING INDEX t302_c8_c3 (c8=? AND c3>?)}
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

finish_test