SQLite

    int iField;
    int i;
    u8 *a = (u8*)pRec;

    iHdr = getVarint32(a, nHdr);
    iField = nHdr;
    for(i=0; i<iCol; i++){
      iHdr += getVarint32(&a[iHdr], t);
      iField += sqlite3VdbeSerialTypeLen(t);
    }

    iHdr = getVarint32(&a[iHdr], t);
    sqlite3VdbeSerialGet(&a[iField], t, pMem);
  }

  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  WhereLoop *pLoop,    /* Update the .nOut value of this loop */
  int *pbDone          /* Set to true if at least one expr. value extracted */
){
  Index *p = pLoop->u.btree.pIndex;
  int nEq = pLoop->u.btree.nEq;
  sqlite3 *db = pParse->db;
  int nLower = -1;
  int nUpper = p->nSample+1;
  int rc = SQLITE_OK;
  u8 aff = p->pTable->aCol[ p->aiColumn[nEq] ].affinity;
  CollSeq *pColl;
  
  sqlite3_value *p1 = 0;          /* Value extracted from pLower */
  sqlite3_value *p2 = 0;          /* Value extracted from pUpper */
  sqlite3_value *pVal = 0;        /* Value extracted from record */

  pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]);
  if( pLower ){
    rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1);
    nLower = 0;
  }
  if( pUpper && rc==SQLITE_OK ){
    rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2);
    nUpper = p2 ? 0 : p->nSample;
  }

  if( p1 || p2 ){
    int i;
    int nDiff;
    for(i=0; rc==SQLITE_OK && i<p->nSample; i++){
      rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal);
      if( rc==SQLITE_OK && p1 ){
        int res = sqlite3MemCompare(p1, pVal, pColl);
        if( res>=0 ) nLower++;
      }
      if( rc==SQLITE_OK && p2 ){
        int res = sqlite3MemCompare(p2, pVal, pColl);
        if( res>=0 ) nUpper++;
      }
    }

    nDiff = (nUpper - nLower);
    if( nDiff<=0 ) nDiff = 1;

    /* If there is both an upper and lower bound specified, and the 
    ** comparisons indicate that they are close together, use the fallback
    ** method (assume that the scan visits 1/64 of the rows) for estimating
    ** the number of rows visited. Otherwise, estimate the number of rows
    ** using the method described in the header comment for this function. */
    if( nDiff!=1 || pUpper==0 || pLower==0 ){
      int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));
      pLoop->nOut -= nAdjust;
      *pbDone = 1;
      WHERETRACE(0x10, ("range skip-scan regions: %u..%u  adjust=%d est=%d\n",
                           (u32)nLower, (u32)nUpper, nAdjust*-1, pLoop->nOut));
    }

  }else{
    assert( *pbDone==0 );
  }

  sqlite3ValueFree(p1);
  sqlite3ValueFree(p2);
  sqlite3ValueFree(pVal);

# 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. In 
# particular it tests that stat4 data can be used by a range query
# that uses the skip-scan approach.
#

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

ifcapable !stat4 {
  finish_test
  return
}

do_execsql_test 1.1 {
  CREATE TABLE t1(a INT, b INT, c INT);
  CREATE INDEX i1 ON t1(a, b);
} {}

expr srand(4)
do_test 1.2 {
  for {set i 0} {$i < 100} {incr i} {
    set a [expr int(rand()*4.0) + 1]
    set b [expr int(rand()*20.0) + 1]
    execsql { INSERT INTO t1 VALUES($a, $b, NULL) }
  }
  execsql ANALYZE
} {}

do_eqp_test 1.3 {
  SELECT * FROM t1 WHERE b = 5;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b=?)}
}

do_eqp_test 1.4 {
  SELECT * FROM t1 WHERE b > 12 AND b < 16;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
}

do_eqp_test 1.5 {
  SELECT * FROM t1 WHERE b > 2 AND b < 16;
} {
  0 0 0 {SCAN TABLE t1}
}

do_eqp_test 1.6 {
  SELECT * FROM t1 WHERE b > 18 AND b < 25;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
}

do_eqp_test 1.7 {
  SELECT * FROM t1 WHERE b > 18 AND b < 25;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
}

do_eqp_test 1.8 {
  SELECT * FROM t1 WHERE b > 15;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>?)}
}

do_eqp_test 1.9 {
  SELECT * FROM t1 WHERE b > 5;
} {
  0 0 0 {SCAN TABLE t1}
}

do_eqp_test 1.10 {
  SELECT * FROM t1 WHERE b < 5;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b<?)}
}

do_eqp_test 1.11 {
  SELECT * FROM t1 WHERE b < 15;
} {
  0 0 0 {SCAN TABLE t1}
}

finish_test