/ Check-in [219736f5]
Login

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

Overview
Comment:Fix a couple of problems in estimating the number of rows visited by a range query that uses a skip-scan.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | stat4-skipscan
Files: files | file ages | folders
SHA1: 219736f54dcd1448af3400e699f1c20755ac6876
User & Date: dan 2014-06-27 20:14:25
Context
2014-06-28
14:25
Merge fixes from trunk with this branch. check-in: 6af219d1 user: dan tags: stat4-skipscan
2014-06-27
20:14
Fix a couple of problems in estimating the number of rows visited by a range query that uses a skip-scan. check-in: 219736f5 user: dan tags: stat4-skipscan
2014-06-26
21:32
Fix compilation issue when STAT4 is not enabled. check-in: 74a5454a user: mistachkin tags: stat4-skipscan
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbemem.c.

  1292   1292       int iField;
  1293   1293       int i;
  1294   1294       u8 *a = (u8*)pRec;
  1295   1295   
  1296   1296       iHdr = getVarint32(a, nHdr);
  1297   1297       iField = nHdr;
  1298   1298       for(i=0; i<iCol; i++){
  1299         -      iHdr = getVarint32(&a[iHdr], t);
         1299  +      iHdr += getVarint32(&a[iHdr], t);
  1300   1300         iField += sqlite3VdbeSerialTypeLen(t);
  1301   1301       }
  1302   1302   
  1303   1303       iHdr = getVarint32(&a[iHdr], t);
  1304   1304       sqlite3VdbeSerialGet(&a[iField], t, pMem);
  1305   1305     }
  1306   1306   

Changes to src/where.c.

  2041   2041     WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  2042   2042     WhereLoop *pLoop,    /* Update the .nOut value of this loop */
  2043   2043     int *pbDone          /* Set to true if at least one expr. value extracted */
  2044   2044   ){
  2045   2045     Index *p = pLoop->u.btree.pIndex;
  2046   2046     int nEq = pLoop->u.btree.nEq;
  2047   2047     sqlite3 *db = pParse->db;
  2048         -  int nLower = 0;
  2049         -  int nUpper = 0;
         2048  +  int nLower = -1;
         2049  +  int nUpper = p->nSample+1;
  2050   2050     int rc = SQLITE_OK;
  2051   2051     u8 aff = p->pTable->aCol[ p->aiColumn[nEq] ].affinity;
  2052   2052     CollSeq *pColl;
  2053   2053     
  2054   2054     sqlite3_value *p1 = 0;          /* Value extracted from pLower */
  2055   2055     sqlite3_value *p2 = 0;          /* Value extracted from pUpper */
  2056   2056     sqlite3_value *pVal = 0;        /* Value extracted from record */
  2057   2057   
  2058   2058     pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]);
  2059   2059     if( pLower ){
  2060   2060       rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1);
         2061  +    nLower = 0;
  2061   2062     }
  2062   2063     if( pUpper && rc==SQLITE_OK ){
  2063   2064       rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2);
         2065  +    nUpper = p2 ? 0 : p->nSample;
  2064   2066     }
  2065   2067   
  2066   2068     if( p1 || p2 ){
  2067   2069       int i;
  2068   2070       int nDiff;
  2069   2071       for(i=0; rc==SQLITE_OK && i<p->nSample; i++){
  2070   2072         rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal);
  2071   2073         if( rc==SQLITE_OK && p1 ){
  2072   2074           int res = sqlite3MemCompare(p1, pVal, pColl);
  2073         -        if( res<=0 ) nLower++;
         2075  +        if( res>=0 ) nLower++;
  2074   2076         }
  2075   2077         if( rc==SQLITE_OK && p2 ){
  2076   2078           int res = sqlite3MemCompare(p2, pVal, pColl);
  2077         -        if( res<=0 ) nUpper++;
         2079  +        if( res>=0 ) nUpper++;
  2078   2080         }
  2079   2081       }
  2080         -    if( p2==0 ) nUpper = p->nSample;
  2081   2082       nDiff = (nUpper - nLower);
  2082   2083       if( nDiff<=0 ) nDiff = 1;
  2083         -    pLoop->nOut -= (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));
  2084         -    *pbDone = 1;
         2084  +
         2085  +    /* If there is both an upper and lower bound specified, and the 
         2086  +    ** comparisons indicate that they are close together, use the fallback
         2087  +    ** method (assume that the scan visits 1/64 of the rows) for estimating
         2088  +    ** the number of rows visited. Otherwise, estimate the number of rows
         2089  +    ** using the method described in the header comment for this function. */
         2090  +    if( nDiff!=1 || pUpper==0 || pLower==0 ){
         2091  +      int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));
         2092  +      pLoop->nOut -= nAdjust;
         2093  +      *pbDone = 1;
         2094  +      WHERETRACE(0x10, ("range skip-scan regions: %u..%u  adjust=%d est=%d\n",
         2095  +                           (u32)nLower, (u32)nUpper, nAdjust*-1, pLoop->nOut));
         2096  +    }
         2097  +
  2085   2098     }else{
  2086   2099       assert( *pbDone==0 );
  2087   2100     }
  2088   2101   
  2089   2102     sqlite3ValueFree(p1);
  2090   2103     sqlite3ValueFree(p2);
  2091   2104     sqlite3ValueFree(pVal);

Added test/skipscan5.test.

            1  +# 2013-11-13
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# This file implements tests of the "skip-scan" query strategy. In 
           13  +# particular it tests that stat4 data can be used by a range query
           14  +# that uses the skip-scan approach.
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +set testprefix skipscan5
           20  +
           21  +ifcapable !stat4 {
           22  +  finish_test
           23  +  return
           24  +}
           25  +
           26  +do_execsql_test 1.1 {
           27  +  CREATE TABLE t1(a INT, b INT, c INT);
           28  +  CREATE INDEX i1 ON t1(a, b);
           29  +} {}
           30  +
           31  +expr srand(4)
           32  +do_test 1.2 {
           33  +  for {set i 0} {$i < 100} {incr i} {
           34  +    set a [expr int(rand()*4.0) + 1]
           35  +    set b [expr int(rand()*20.0) + 1]
           36  +    execsql { INSERT INTO t1 VALUES($a, $b, NULL) }
           37  +  }
           38  +  execsql ANALYZE
           39  +} {}
           40  +
           41  +do_eqp_test 1.3 {
           42  +  SELECT * FROM t1 WHERE b = 5;
           43  +} {
           44  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b=?)}
           45  +}
           46  +
           47  +do_eqp_test 1.4 {
           48  +  SELECT * FROM t1 WHERE b > 12 AND b < 16;
           49  +} {
           50  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
           51  +}
           52  +
           53  +do_eqp_test 1.5 {
           54  +  SELECT * FROM t1 WHERE b > 2 AND b < 16;
           55  +} {
           56  +  0 0 0 {SCAN TABLE t1}
           57  +}
           58  +
           59  +do_eqp_test 1.6 {
           60  +  SELECT * FROM t1 WHERE b > 18 AND b < 25;
           61  +} {
           62  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
           63  +}
           64  +
           65  +do_eqp_test 1.7 {
           66  +  SELECT * FROM t1 WHERE b > 18 AND b < 25;
           67  +} {
           68  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>? AND b<?)}
           69  +}
           70  +
           71  +do_eqp_test 1.8 {
           72  +  SELECT * FROM t1 WHERE b > 15;
           73  +} {
           74  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>?)}
           75  +}
           76  +
           77  +do_eqp_test 1.9 {
           78  +  SELECT * FROM t1 WHERE b > 5;
           79  +} {
           80  +  0 0 0 {SCAN TABLE t1}
           81  +}
           82  +
           83  +do_eqp_test 1.10 {
           84  +  SELECT * FROM t1 WHERE b < 5;
           85  +} {
           86  +  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b<?)}
           87  +}
           88  +
           89  +do_eqp_test 1.11 {
           90  +  SELECT * FROM t1 WHERE b < 15;
           91  +} {
           92  +  0 0 0 {SCAN TABLE t1}
           93  +}
           94  +
           95  +finish_test