/ Check-in [219736f5]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 Unified Diffs Ignore Whitespace Patch

Changes to src/vdbemem.c.

1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
    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);
  }








|







1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
    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);
  }

Changes to src/where.c.

2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060

2061
2062
2063

2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082







2083

2084




2085
2086
2087
2088
2089
2090
2091
  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 = 0;
  int nUpper = 0;
  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);

  }
  if( pUpper && rc==SQLITE_OK ){
    rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2);

  }

  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++;
      }
    }
    if( p2==0 ) nUpper = p->nSample;
    nDiff = (nUpper - nLower);
    if( nDiff<=0 ) nDiff = 1;







    pLoop->nOut -= (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));

    *pbDone = 1;




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

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







|
|











>



>









|



|


<


>
>
>
>
>
>
>
|
>
|
>
>
>
>







2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081

2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
  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);

Added test/skipscan5.test.































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# 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