SQLite

  if( argv==0 || argv[0]==0 || argv[2]==0 ){
    return 0;
  }
  pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
  if( pTable==0 ){
    return 0;
  }
  if( argv[1]==0 ){
    pIndex = 0;
  }else if( sqlite3_stricmp(argv[0],argv[1])==0 ){
    pIndex = sqlite3PrimaryKeyIndex(pTable);
  }else{
    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  }
  z = argv[2];

  if( pIndex ){
    decodeIntArray((char*)z, pIndex->nKeyCol+1, pIndex->aiRowEst, pIndex);
    if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
  }else{

**
** The indenting rules are:
**
**     * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent
**       all opcodes that occur between the p2 jump destination and the opcode
**       itself by 2 spaces.
**
**     * For each "Goto", if the jump destination is a "Yield", "SeekGt",
**       or "SeekLt" instruction that occurs earlier in the program than
**       the Goto itself, indent all opcodes between the earlier instruction
**       and "Goto" by 2 spaces.
*/
static void explain_data_prepare(struct callback_data *p, sqlite3_stmt *pSql){
  const char *zSql;               /* The text of the SQL statement */
  const char *z;                  /* Used to check if this is an EXPLAIN */
  int *abYield = 0;               /* True if op is an OP_Yield */
  int nAlloc = 0;                 /* Allocated size of p->aiIndent[], abYield */
  int iOp;

  const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", 0 };
  const char *azYield[] = { "Yield", "SeekLt", "SeekGt", 0 };
  const char *azGoto[] = { "Goto", 0 };

  /* Try to figure out if this is really an EXPLAIN statement. If this
  ** cannot be verified, return early.  */
  zSql = sqlite3_sql(pSql);
  if( zSql==0 ) return;
  for(z=zSql; *z==' ' || *z=='\t' || *z=='\n' || *z=='\f' || *z=='\r'; z++);

  }
  disableTerm(pLevel, pTerm);
  return iReg;
}

/*
** Generate code that will evaluate all == and IN constraints for an
** index scan.
**
** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
** The index has as many as three equality constraints, but in this
** example, the third "c" value is an inequality.  So only two 
** constraints are coded.  This routine will generate code to evaluate
** a==5 and b IN (1,2,3).  The current values for a and b will be stored
** in consecutive registers and the index of the first register is returned.
**
** In the example above nEq==2.  But this subroutine works for any value
** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
** The only thing it does is allocate the pLevel->iMem memory cell and
** compute the affinity string.
**
** The nExtraReg parameter is 0 or 1.  It is 0 if all WHERE clause constraints
** are == or IN and are covered by the nEq.  nExtraReg is 1 if there is
** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
** occurs after the nEq quality constraints.
**
** This routine allocates a range of nEq+nExtraReg memory cells and returns
** the index of the first memory cell in that range. The code that
** calls this routine will use that memory range to store keys for
** start and termination conditions of the loop.
** key value of the loop.  If one or more IN operators appear, then
** this routine allocates an additional nEq memory cells for internal
** use.
**
** Before returning, *pzAff is set to point to a buffer containing a
** copy of the column affinity string of the index allocated using
** sqlite3DbMalloc(). Except, entries in the copy of the string associated

static int codeAllEqualityTerms(
  Parse *pParse,        /* Parsing context */
  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  int bRev,             /* Reverse the order of IN operators */
  int nExtraReg,        /* Number of extra registers to allocate */
  char **pzAff          /* OUT: Set to point to affinity string */
){
  u16 nEq;                      /* The number of == or IN constraints to code */
  u16 nSkip;                    /* Number of left-most columns to skip */
  Vdbe *v = pParse->pVdbe;      /* The vm under construction */
  Index *pIdx;                  /* The index being used for this loop */
  WhereTerm *pTerm;             /* A single constraint term */
  WhereLoop *pLoop;             /* The WhereLoop object */
  int j;                        /* Loop counter */
  int regBase;                  /* Base register */
  int nReg;                     /* Number of registers to allocate */
  char *zAff;                   /* Affinity string to return */

  /* This module is only called on query plans that use an index. */
  pLoop = pLevel->pWLoop;
  assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
  nEq = pLoop->u.btree.nEq;
  nSkip = pLoop->u.btree.nSkip;
  pIdx = pLoop->u.btree.pIndex;
  assert( pIdx!=0 );

  /* Figure out how many memory cells we will need then allocate them.
  */
  regBase = pParse->nMem + 1;
  nReg = pLoop->u.btree.nEq + nExtraReg;
  pParse->nMem += nReg;

  zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  if( nSkip ){
    int iIdxCur = pLevel->iIdxCur;
    sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
    VdbeComment((v, "begin skip-scan on %s", pIdx->zName));
    j = sqlite3VdbeAddOp0(v, OP_Goto);
    pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLt:OP_SeekGt),
                            iIdxCur, 0, regBase, nSkip);
    sqlite3VdbeJumpHere(v, j);
    for(j=0; j<nSkip; j++){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
      assert( pIdx->aiColumn[j]>=0 );
      VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName));
    }
  }    

  /* Evaluate the equality constraints
  */
  assert( zAff==0 || (int)strlen(zAff)>=nEq );
  for(j=nSkip; j<nEq; j++){
    int r1;
    pTerm = pLoop->aLTerm[j];
    assert( pTerm!=0 );
    /* The following testcase is true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL );
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
    if( r1!=regBase+j ){
      if( nReg==1 ){
        sqlite3ReleaseTempReg(pParse, regBase);

**
** The returned pointer points to memory obtained from sqlite3DbMalloc().
** It is the responsibility of the caller to free the buffer when it is
** no longer required.
*/
static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){
  Index *pIndex = pLoop->u.btree.pIndex;
  u16 nEq = pLoop->u.btree.nEq;
  u16 nSkip = pLoop->u.btree.nSkip;
  int i, j;
  Column *aCol = pTab->aCol;
  i16 *aiColumn = pIndex->aiColumn;
  StrAccum txt;

  if( nEq==0 && (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
    return 0;
  }
  sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
  txt.db = db;
  sqlite3StrAccumAppend(&txt, " (", 2);
  for(i=0; i<nEq; i++){
    char *z = (i==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[i]].zName;
    if( i>=nSkip ){
      explainAppendTerm(&txt, i, z, "=");
    }else{
      if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5);
      sqlite3StrAccumAppend(&txt, "ANY(", 4);
      sqlite3StrAccumAppend(&txt, z, -1);
      sqlite3StrAccumAppend(&txt, ")", 1);
    }
  }

  j = i;
  if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
    char *z = (j==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[j]].zName;
    explainAppendTerm(&txt, i++, z, ">");
  }

      OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
    };
    static const u8 aEndOp[] = {
      OP_Noop,             /* 0: (!end_constraints) */
      OP_IdxGE,            /* 1: (end_constraints && !bRev) */
      OP_IdxLT             /* 2: (end_constraints && bRev) */
    };
    u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
    u16 nSkip = pLoop->u.btree.nSkip; /* Number of left index terms to skip */
    int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
    int regBase;                 /* Base register holding constraint values */
    int r1;                      /* Temp register */
    WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
    WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
    int startEq;                 /* True if range start uses ==, >= or <= */
    int endEq;                   /* True if range end uses ==, >= or <= */
    int start_constraints;       /* Start of range is constrained */
    int nConstraint;             /* Number of constraint terms */
    Index *pIdx;                 /* The index we will be using */
    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff;               /* Affinity for end of range constraint */

    pIdx = pLoop->u.btree.pIndex;
    iIdxCur = pLevel->iIdxCur;
    assert( nEq>=nSkip );

    /* If this loop satisfies a sort order (pOrderBy) request that 
    ** was passed to this function to implement a "SELECT min(x) ..." 
    ** query, then the caller will only allow the loop to run for
    ** a single iteration. This means that the first row returned
    ** should not have a NULL value stored in 'x'. If column 'x' is
    ** the first one after the nEq equality constraints in the index,
    ** this requires some special handling.
    */
    if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
     && (pWInfo->bOBSat!=0)
     && (pIdx->nKeyCol>nEq)
    ){
      assert( nSkip==0 );

      isMinQuery = 1;
      nExtraReg = 1;
    }

    /* Find any inequality constraint terms for the start and end 
    ** of the range. 
    */

  */
  if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){  /* WHERETRACE 0x100 */
    int i;
    Vdbe *v = pWInfo->pParse->pVdbe;
    sqlite3ExplainBegin(v);
    for(i=0; i<p->nLTerm; i++){
      WhereTerm *pTerm = p->aLTerm[i];
      if( pTerm==0 ) continue;
      sqlite3ExplainPrintf(v, "  (%d) #%-2d ", i+1, (int)(pTerm-pWC->a));
      sqlite3ExplainPush(v);
      whereExplainTerm(v, pTerm);
      sqlite3ExplainPop(v);
      sqlite3ExplainNL(v);
    }
    sqlite3ExplainFinish(v);

  }
  for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
    if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
    for(j=pLoop->nLTerm-1; j>=0; j--){
      pX = pLoop->aLTerm[j];
      if( pX==0 ) continue;
      if( pX==pTerm ) break;
      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
    }
    if( j<0 ) pLoop->nOut += pTerm->truthProb;
  }
}

  sqlite3 *db = pParse->db;       /* Database connection malloc context */
  WhereLoop *pNew;                /* Template WhereLoop under construction */
  WhereTerm *pTerm;               /* A WhereTerm under consideration */
  int opMask;                     /* Valid operators for constraints */
  WhereScan scan;                 /* Iterator for WHERE terms */
  Bitmask saved_prereq;           /* Original value of pNew->prereq */
  u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
  u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
  u16 saved_nSkip;                /* Original value of pNew->u.btree.nSkip */
  u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  LogEst saved_nOut;              /* Original value of pNew->nOut */
  int iCol;                       /* Index of the column in the table */
  int rc = SQLITE_OK;             /* Return code */
  LogEst nRowEst;                 /* Estimated index selectivity */
  LogEst rLogSize;                /* Logarithm of table size */
  WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */

  }else{
    iCol = -1;
    nRowEst = 0;
  }
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, pProbe);
  saved_nEq = pNew->u.btree.nEq;
  saved_nSkip = pNew->u.btree.nSkip;
  saved_nLTerm = pNew->nLTerm;
  saved_wsFlags = pNew->wsFlags;
  saved_prereq = pNew->prereq;
  saved_nOut = pNew->nOut;
  pNew->rSetup = 0;
  rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
  if( pTerm==0
   && saved_nEq==saved_nSkip
   && saved_nEq+1<pProbe->nKeyCol
   && pProbe->aiRowEst[saved_nEq+1]>50
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
     && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)

        /* "x IN (value, value, ...)" */
        nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
      }
      pNew->rRun += nIn;
      pNew->u.btree.nEq++;
      pNew->nOut = nRowEst + nInMul + nIn;
    }else if( pTerm->eOperator & (WO_EQ) ){
      assert(
        (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0
        || nInMul==0
      );
      pNew->wsFlags |= WHERE_COLUMN_EQ;
      if( iCol<0  
       || (pProbe->onError!=OE_None && nInMul==0
           && pNew->u.btree.nEq==pProbe->nKeyCol-1)
      ){
        assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
        pNew->wsFlags |= WHERE_ONEROW;

    pNew->nOut = saved_nOut;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    pBuilder->nRecValid = nRecValid;
#endif
  }
  pNew->prereq = saved_prereq;
  pNew->u.btree.nEq = saved_nEq;
  pNew->u.btree.nSkip = saved_nSkip;
  pNew->wsFlags = saved_wsFlags;
  pNew->nOut = saved_nOut;
  pNew->nLTerm = saved_nLTerm;
  return rc;
}

/*

    /* Generate auto-index WhereLoops */
    WhereTerm *pTerm;
    WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
    for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
      if( pTerm->prereqRight & pNew->maskSelf ) continue;
      if( termCanDriveIndex(pTerm, pSrc, 0) ){
        pNew->u.btree.nEq = 1;
        pNew->u.btree.nSkip = 0;
        pNew->u.btree.pIndex = 0;
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        /* TUNING: One-time cost for computing the automatic index is
        ** approximately 7*N*log2(N) where N is the number of rows in
        ** the table being indexed. */
        pNew->rSetup = rLogSize + rSize + 28;  assert( 28==sqlite3LogEst(7) );

  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    if( pProbe->pPartIdxWhere!=0
     && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
      continue;  /* Partial index inappropriate for this query */
    }
    pNew->u.btree.nEq = 0;
    pNew->u.btree.nSkip = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);

      rev = revSet = 0;
      distinctColumns = 0;
      for(j=0; j<nColumn; j++){
        u8 bOnce;   /* True to run the ORDER BY search loop */

        /* Skip over == and IS NULL terms */
        if( j<pLoop->u.btree.nEq
         && pLoop->u.btree.nSkip==0
         && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
        ){
          if( i & WO_ISNULL ){
            testcase( isOrderDistinct );
            isOrderDistinct = 0;
          }
          continue;  

  pTab = pItem->pTab;
  if( IsVirtual(pTab) ) return 0;
  if( pItem->zIndex ) return 0;
  iCur = pItem->iCursor;
  pWC = &pWInfo->sWC;
  pLoop = pBuilder->pNew;
  pLoop->wsFlags = 0;
  pLoop->u.btree.nSkip = 0;
  pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0);
  if( pTerm ){
    pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
    pLoop->aLTerm[0] = pTerm;
    pLoop->nLTerm = 1;
    pLoop->u.btree.nEq = 1;
    /* TUNING: Cost of a rowid lookup is 10 */

  sqlite3 *db = pParse->db;

  /* Generate loop termination code.
  */
  VdbeNoopComment((v, "End WHERE-core"));
  sqlite3ExprCacheClear(pParse);
  for(i=pWInfo->nLevel-1; i>=0; i--){
    int addr;
    pLevel = &pWInfo->a[i];
    pLoop = pLevel->pWLoop;
    sqlite3VdbeResolveLabel(v, pLevel->addrCont);
    if( pLevel->op!=OP_Noop ){
      sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
      sqlite3VdbeChangeP5(v, pLevel->p5);
    }
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
      struct InLoop *pIn;
      int j;
      sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
      for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
        sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
        sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
      sqlite3DbFree(db, pLevel->u.in.aInLoop);
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->addrSkip ){
      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip);
      VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));
      sqlite3VdbeJumpHere(v, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
    }
    if( pLevel->iLeftJoin ){

      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
      if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
      }
      if( pLoop->wsFlags & WHERE_INDEXED ){

*/
struct WhereLevel {
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */

#define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
#define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */

# 2013-11-13
#
# 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 of the "skip-scan" query strategy.
#

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

do_execsql_test skipscan1-1.1 {
  CREATE TABLE t1(a TEXT, b INT, c INT, d INT);
  CREATE INDEX t1abc ON t1(a,b,c);
  INSERT INTO t1 VALUES('abc',123,4,5);
  INSERT INTO t1 VALUES('abc',234,5,6);
  INSERT INTO t1 VALUES('abc',234,6,7);
  INSERT INTO t1 VALUES('abc',345,7,8);
  INSERT INTO t1 VALUES('def',567,8,9);
  INSERT INTO t1 VALUES('def',345,9,10);
  INSERT INTO t1 VALUES('bcd',100,6,11);

  /* Fake the sqlite_stat1 table so that the query planner believes
  ** the table contains thousands of rows and that the first few
  ** columns are not selective. */
  ANALYZE;
  DELETE FROM sqlite_stat1;
  INSERT INTO sqlite_stat1 VALUES('t1','t1abc','10000 5000 2000 10');
  ANALYZE sqlite_master;
} {}

# Simple queries that leave the first one or two columns of the
# index unconstrainted.
#
do_execsql_test skipscan1-1.2 {
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
} {abc 345 7 8 | def 345 9 10 |}
do_execsql_test skipscan1-1.2eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
} {/* USING INDEX t1abc (ANY(a) AND b=?)*/}
do_execsql_test skipscan1-1.2sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.3 {
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a DESC;
} {def 345 9 10 | abc 345 7 8 |}
do_execsql_test skipscan1-1.3eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
} {/* USING INDEX t1abc (ANY(a) AND b=?)*/}
do_execsql_test skipscan1-1.3sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.4 {
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {abc 234 6 7 | bcd 100 6 11 |}
do_execsql_test skipscan1-1.4eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
do_execsql_test skipscan1-1.4sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.5 {
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
do_execsql_test skipscan1-1.5eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
do_execsql_test skipscan1-1.5sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.6 {
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
do_execsql_test skipscan1-1.6eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c>? AND c<?)*/}
do_execsql_test skipscan1-1.6sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.7 {
  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
   ORDER BY a, b;
} {abc 234 6 7 | abc 345 7 8 |}
do_execsql_test skipscan1-1.7eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
   ORDER BY a, b;
} {/* USING INDEX t1abc (ANY(a) AND b=? AND c>? AND c<?)*/}
do_execsql_test skipscan1-1.7sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7
   ORDER BY a, b;
} {~/*ORDER BY*/}


# Joins
#
do_execsql_test skipscan1-1.51 {
  CREATE TABLE t1j(x TEXT, y INTEGER);
  INSERT INTO t1j VALUES('one',1),('six',6),('ninty-nine',99);
  INSERT INTO sqlite_stat1 VALUES('t1j',null,'3');
  ANALYZE sqlite_master;
  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {six abc 234 6 7 | six bcd 100 6 11 |}
do_execsql_test skipscan1-1.51eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-1.52 {
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {one {} {} {} {} | six abc 234 6 7 | six bcd 100 6 11 | ninty-nine {} {} {} {} |}
do_execsql_test skipscan1-1.52eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-2.1 {
  CREATE TABLE t2(a TEXT, b INT, c INT, d INT,
                  PRIMARY KEY(a,b,c));
  INSERT INTO t2 SELECT * FROM t1;

  /* Fake the sqlite_stat1 table so that the query planner believes
  ** the table contains thousands of rows and that the first few
  ** columns are not selective. */
  ANALYZE;
  UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL;
  ANALYZE sqlite_master;
} {}

do_execsql_test skipscan1-2.2 {
  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
} {abc 345 7 8 | def 345 9 10 |}
do_execsql_test skipscan1-2.2eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
} {/* USING INDEX sqlite_autoindex_t2_1 (ANY(a) AND b=?)*/}
do_execsql_test skipscan1-2.2sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t2 WHERE b=345 ORDER BY a;
} {~/*ORDER BY*/}


do_execsql_test skipscan1-3.1 {
  CREATE TABLE t3(a TEXT, b INT, c INT, d INT,
                  PRIMARY KEY(a,b,c)) WITHOUT ROWID;
  INSERT INTO t3 SELECT * FROM t1;

  /* Fake the sqlite_stat1 table so that the query planner believes
  ** the table contains thousands of rows and that the first few
  ** columns are not selective. */
  ANALYZE;
  UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL;
  ANALYZE sqlite_master;
} {}

do_execsql_test skipscan1-3.2 {
  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
} {abc 345 7 8 | def 345 9 10 |}
do_execsql_test skipscan1-3.2eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
} {/* INDEX sqlite_autoindex_t3_1 (ANY(a) AND b=?)*/}
do_execsql_test skipscan1-3.2sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a;
} {~/*ORDER BY*/}

finish_test

      fail_test $name
    } else {
      if {[regexp {^~?/.*/$} $expected]} {
        # "expected" is of the form "/PATTERN/" then the result if correct if
        # regular expression PATTERN matches the result.  "~/PATTERN/" means
        # the regular expression must not match.
        if {[string index $expected 0]=="~"} {
          set re [string range $expected 2 end-1]
          if {[string index $re 0]=="*"} {
            # If the regular expression begins with * then treat it as a glob instead
            set ok [string match $re $result]
          } else {
            set re [string map {# {[-0-9.]+}} $re]
            set ok [regexp $re $result]
          }
          set ok [expr {!$ok}]
        } else {
          set re [string range $expected 1 end-1]
          if {[string index $re 0]=="*"} {
            # If the regular expression begins with * then treat it as a glob instead
            set ok [string match $re $result]
          } else {
            set re [string map {# {[-0-9.]+}} $re]
            set ok [regexp $re $result]
          }
        }
      } elseif {[regexp {^~?\*.*\*$} $expected]} {
        # "expected" is of the form "*GLOB*" then the result if correct if
        # glob pattern GLOB matches the result.  "~/GLOB/" means
        # the glob must not match.
        if {[string index $expected 0]=="~"} {
          set e [string range $expected 1 end]