SQLite

   && sqlite3ExprCompare(pE1->pLeft, pE2->pLeft, iTab)==0
   && (pE1->op!=TK_ISNULL && pE1->op!=TK_IS)
  ){
    return 1;
  }
  return 0;
}

/*
** An instance of the following structure is used by the tree walker
** to determine if an expression can be evaluated by reference to the
** index only, without having to do a search for the corresponding
** table entry.  The IdxCover.pIdx field is the index.  IdxCover.iCur
** is the cursor for the table.
*/
struct IdxCover {
  Index *pIdx;     /* The index to be tested for coverage */
  int iCur;        /* Cursor number for the table corresponding to the index */
};

/*
** Check to see if there are references to columns in table 
** pWalker->u.pIdxCover->iCur can be satisfied using the index
** pWalker->u.pIdxCover->pIdx.
*/
static int exprIdxCover(Walker *pWalker, Expr *pExpr){
  if( pExpr->op==TK_COLUMN
   && pExpr->iTable==pWalker->u.pIdxCover->iCur
   && sqlite3ColumnOfIndex(pWalker->u.pIdxCover->pIdx, pExpr->iColumn)<0
  ){
    pWalker->eCode = 1;
    return WRC_Abort;
  }
  return WRC_Continue;
}

/*
** Determine if an index pIdx on table with cursor iCur contains will
** the expression pExpr.  Return true if the index does cover the
** expression and false if the pExpr expression references table columns
** that are not found in the index pIdx.
**
** An index covering an expression means that the expression can be
** evaluated using only the index and without having to lookup the
** corresponding table entry.
*/
int sqlite3ExprCoveredByIndex(
  Expr *pExpr,        /* The index to be tested */
  int iCur,           /* The cursor number for the corresponding table */
  Index *pIdx         /* The index that might be used for coverage */
){
  Walker w;
  struct IdxCover xcov;
  memset(&w, 0, sizeof(w));
  xcov.iCur = iCur;
  xcov.pIdx = pIdx;
  w.xExprCallback = exprIdxCover;
  w.u.pIdxCover = &xcov;
  sqlite3WalkExpr(&w, pExpr);
  return !w.eCode;
}


/*
** An instance of the following structure is used by the tree walker
** to count references to table columns in the arguments of an 
** aggregate function, in order to implement the
** sqlite3FunctionThisSrc() routine.
*/

    NameContext *pNC;                          /* Naming context */
    int n;                                     /* A counter */
    int iCur;                                  /* A cursor number */
    SrcList *pSrcList;                         /* FROM clause */
    struct SrcCount *pSrcCount;                /* Counting column references */
    struct CCurHint *pCCurHint;                /* Used by codeCursorHint() */
    int *aiCol;                                /* array of column indexes */
    struct IdxCover *pIdxCover;                /* Check for index coverage */
  } u;
};

/* Forward declarations */
int sqlite3WalkExpr(Walker*, Expr*);
int sqlite3WalkExprList(Walker*, ExprList*);
int sqlite3WalkSelect(Walker*, Select*);

int sqlite3RunVacuum(char**, sqlite3*);
char *sqlite3NameFromToken(sqlite3*, Token*);
int sqlite3ExprCompare(Expr*, Expr*, int);
int sqlite3ExprListCompare(ExprList*, ExprList*, int);
int sqlite3ExprImpliesExpr(Expr*, Expr*, int);
void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
Vdbe *sqlite3GetVdbe(Parse*);
#ifndef SQLITE_OMIT_BUILTIN_TEST
void sqlite3PrngSaveState(void);
void sqlite3PrngRestoreState(void);
#endif
void sqlite3RollbackAll(sqlite3*,int);

   && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq]+1 - pProbe->aiRowLogEst[saved_nEq+1];
    pNew->nOut -= nIter;
    /* TUNING:  Because uncertainties in the estimates for skip-scan queries,
    ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
    nIter += 4;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
    pNew->nOut = saved_nOut;
    pNew->u.btree.nEq = saved_nEq;
    pNew->nSkip = saved_nSkip;
    pNew->wsFlags = saved_wsFlags;
  }

         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;

        /* The cost of visiting the index rows is N*K, where K is
        ** between 1.1 and 3.0, depending on the relative sizes of the
        ** index and table rows. */

        pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
        if( m!=0 ){
          /* If this is a non-covering index scan, add in the cost of
          ** doing table lookups.  The cost will be 3x the number of
          ** lookups.  Take into account WHERE clause terms that can be
          ** satisfied using just the index, and that do not require a
          ** table lookup. */
          LogEst nLookup = rSize + 16;  /* Base cost:  N*3 */
          int ii;
          int iCur = pSrc->iCursor;
          WhereClause *pWC = &pWInfo->sWC;
          for(ii=0; ii<pWC->nTerm; ii++){
            WhereTerm *pTerm = &pWC->a[ii];
            if( !sqlite3ExprCoveredByIndex(pTerm->pExpr, iCur, pProbe) ){
              break;
            }
            /* pTerm can be evaluated using just the index.  So reduce
            ** the expected number of table lookups accordingly */
            if( pTerm->truthProb<=0 ){
              nLookup += pTerm->truthProb;
            }else{
              nLookup--;
              if( pTerm->eOperator & (WO_EQ|WO_IS) ) nLookup -= 19;
            }
          }
          
          pNew->rRun = sqlite3LogEstAdd(pNew->rRun, nLookup);
        }
        ApplyCostMultiplier(pNew->rRun, pTab->costMult);
        whereLoopOutputAdjust(pWC, pNew, rSize);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }

# 2016-07-27
#
# 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.
#
#***********************************************************************
#
# Test cases for ORDER BY and LIMIT on an index scan.
#


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

# Performance regression reported at
# http://www.mail-archive.com/sqlite-users@mailinglists.sqlite.org/msg98615.html
#
# Caused by the ORDER BY LIMIT optionation for check-in
# https://sqlite.org/src/info/bf46179d44843769
#
# Fixed on approximately 2016-07-27 by changes that compute a better score
# for index scans by taking into account WHERE clause constraints that can
# be handled by the index and do not require a table lookup.
#
do_execsql_test 1.0 {
  CREATE TABLE t1(a,b,c,d);
  WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<100)
  INSERT INTO t1(a,b,c,d)
     SELECT x/10, x%10, x%19, x FROM c;
  CREATE INDEX t1abc ON t1(a,b,c);
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {0 4 4 4 2 3 4 23}

# Prior to the fix, the following EQP would show a table scan and a sort
# rather than an index scan.
#
do_execsql_test 1.0eqp {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {/SCAN TABLE t1 USING INDEX t1abc/}

# If we change the index so that it no longer covers the WHERE clause,
# then we should (correctly) revert to using a table scan.
#
do_execsql_test 1.1 {
  DROP INDEX t1abc;
  CREATE INDEX t1abd ON t1(a,b,d);
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {0 4 4 4 2 3 4 23}
do_execsql_test 1.1eqp {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {~/USING INDEX/}


finish_test

} {1 {syntax error after column name "x"}}
do_catchsql_test parser1-2.2 {
  WITH RECURSIVE
    c(x ASC) AS (VALUES(1) UNION SELECT x+1 FROM c WHERE x<5)
  SELECT x FROM c;
} {1 {syntax error after column name "x"}}

# Verify that the comma between multiple table constraints is
# optional.
#
# The missing comma is technically a syntax error.  But we have to support
# it because there might be legacy databases that omit the commas in their
# sqlite_master tables.
#
do_execsql_test parser1-3.1 {
  CREATE TABLE t300(id INTEGER PRIMARY KEY);
  CREATE TABLE t301(
    id INTEGER PRIMARY KEY,
    c1 INTEGER NOT NULL,
    c2 INTEGER NOT NULL,
    c3 BOOLEAN NOT NULL DEFAULT 0,
    FOREIGN KEY(c1) REFERENCES t300(id) ON DELETE CASCADE ON UPDATE RESTRICT
        /* no comma */
    FOREIGN KEY(c2) REFERENCES t300(id) ON DELETE CASCADE ON UPDATE RESTRICT
        /* no comma */
    UNIQUE(c1, c2)
  );
  PRAGMA foreign_key_list(t301);
} {0 0 t300 c2 id RESTRICT CASCADE NONE 1 0 t300 c1 id RESTRICT CASCADE NONE}

finish_test

do_eqp_test 5.3.1 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {0 0 0 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}}
do_execsql_test 5.3.2 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {19}
do_scanstatus_test 5.3.3 { 
  nLoop 1 nVisit 19 nEst 52.0 zName t2xy zExplain
  {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.4.1 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {
  0 0 0 {SCAN TABLE t1 USING COVERING INDEX t1bc}
  0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}
do_execsql_test 5.4.2 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {200}
do_scanstatus_test 5.4.3 { 
  nLoop 1 nVisit 10 nEst 10.0 zName t1bc 
  zExplain {SCAN TABLE t1 USING COVERING INDEX t1bc}
  nLoop 10 nVisit 200 nEst 52.0 zName t2xy 
  zExplain {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.5.1 {
  SELECT count(*) FROM t1, t3 WHERE y = c;
} {
  0 0 1 {SCAN TABLE t3}