Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Fix the STAT4 range scan estimates for DESC indexes. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
e3fe84005259ef9a6027d25793514ceb |
| User & Date: | drh 2014-10-08 02:53:25 |
Context
|
2014-10-08
| ||
| 11:11 | Remove some temporary code in mallocA.test that was accidentally checked in. (check-in: dedd15f7 user: dan tags: trunk) | |
| 02:53 | Fix the STAT4 range scan estimates for DESC indexes. (check-in: e3fe8400 user: drh tags: trunk) | |
| 00:08 | More intuitive labels on ".wheretrace" output. (check-in: adcb3fed user: drh tags: trunk) | |
Changes
Changes to src/where.c.
2202 2202 }else{ 2203 2203 /* Note: this call could be optimized away - since the same values must 2204 2204 ** have been requested when testing key $P in whereEqualScanEst(). */ 2205 2205 whereKeyStats(pParse, p, pRec, 0, a); 2206 2206 iLower = a[0]; 2207 2207 iUpper = a[0] + a[1]; 2208 2208 } 2209 + 2210 + assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 ); 2211 + assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); 2212 + if( p->pKeyInfo && p->pKeyInfo->aSortOrder[nEq] ){ 2213 + /* The roles of pLower and pUpper are swapped for a DESC index */ 2214 + SWAP(WhereTerm*, pLower, pUpper); 2215 + } 2209 2216 2210 2217 /* If possible, improve on the iLower estimate using ($P:$L). */ 2211 2218 if( pLower ){ 2212 2219 int bOk; /* True if value is extracted from pExpr */ 2213 2220 Expr *pExpr = pLower->pExpr->pRight; 2214 - assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); 2215 2221 rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk); 2216 2222 if( rc==SQLITE_OK && bOk ){ 2217 2223 tRowcnt iNew; 2218 2224 whereKeyStats(pParse, p, pRec, 0, a); 2219 - iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0); 2225 + iNew = a[0] + ((pLower->eOperator & (WO_GT|WO_LE)) ? a[1] : 0); 2220 2226 if( iNew>iLower ) iLower = iNew; 2221 2227 nOut--; 2222 2228 pLower = 0; 2223 2229 } 2224 2230 } 2225 2231 2226 2232 /* If possible, improve on the iUpper estimate using ($P:$U). */ 2227 2233 if( pUpper ){ 2228 2234 int bOk; /* True if value is extracted from pExpr */ 2229 2235 Expr *pExpr = pUpper->pExpr->pRight; 2230 - assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); 2231 2236 rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk); 2232 2237 if( rc==SQLITE_OK && bOk ){ 2233 2238 tRowcnt iNew; 2234 2239 whereKeyStats(pParse, p, pRec, 1, a); 2235 - iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0); 2240 + iNew = a[0] + ((pUpper->eOperator & (WO_GT|WO_LE)) ? a[1] : 0); 2236 2241 if( iNew<iUpper ) iUpper = iNew; 2237 2242 nOut--; 2238 2243 pUpper = 0; 2239 2244 } 2240 2245 } 2241 2246 2242 2247 pBuilder->pRec = pRec;
Added test/analyzeE.test.
1 +# 2014-10-08 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 +# This file implements tests for using STAT4 information 12 +# on a descending index in a range query. 13 +# 14 + 15 +set testdir [file dirname $argv0] 16 +source $testdir/tester.tcl 17 +set ::testprefix analyzeE 18 + 19 +ifcapable {!stat4} { 20 + finish_test 21 + return 22 +} 23 + 24 +# Verify that range queries on an ASCENDING index will use the 25 +# index only if the range covers only a small fraction of the 26 +# entries. 27 +# 28 +do_execsql_test analyzeE-1.0 { 29 + CREATE TABLE t1(a,b); 30 + WITH RECURSIVE 31 + cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000) 32 + INSERT INTO t1(a,b) SELECT x, x FROM cnt; 33 + CREATE INDEX t1a ON t1(a); 34 + ANALYZE; 35 +} {} 36 +do_execsql_test analyzeE-1.1 { 37 + EXPLAIN QUERY PLAN 38 + SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500; 39 +} {/SCAN TABLE t1/} 40 +do_execsql_test analyzeE-1.2 { 41 + EXPLAIN QUERY PLAN 42 + SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000; 43 +} {/SEARCH TABLE t1 USING INDEX t1a/} 44 +do_execsql_test analyzeE-1.3 { 45 + EXPLAIN QUERY PLAN 46 + SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750; 47 +} {/SEARCH TABLE t1 USING INDEX t1a/} 48 +do_execsql_test analyzeE-1.4 { 49 + EXPLAIN QUERY PLAN 50 + SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 51 +} {/SEARCH TABLE t1 USING INDEX t1a/} 52 +do_execsql_test analyzeE-1.5 { 53 + EXPLAIN QUERY PLAN 54 + SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 55 +} {/SEARCH TABLE t1 USING INDEX t1a/} 56 +do_execsql_test analyzeE-1.6 { 57 + EXPLAIN QUERY PLAN 58 + SELECT * FROM t1 WHERE a<500 59 +} {/SEARCH TABLE t1 USING INDEX t1a/} 60 +do_execsql_test analyzeE-1.7 { 61 + EXPLAIN QUERY PLAN 62 + SELECT * FROM t1 WHERE a>2500 63 +} {/SEARCH TABLE t1 USING INDEX t1a/} 64 +do_execsql_test analyzeE-1.8 { 65 + EXPLAIN QUERY PLAN 66 + SELECT * FROM t1 WHERE a>1900 67 +} {/SEARCH TABLE t1 USING INDEX t1a/} 68 +do_execsql_test analyzeE-1.9 { 69 + EXPLAIN QUERY PLAN 70 + SELECT * FROM t1 WHERE a>1100 71 +} {/SCAN TABLE t1/} 72 +do_execsql_test analyzeE-1.10 { 73 + EXPLAIN QUERY PLAN 74 + SELECT * FROM t1 WHERE a<1100 75 +} {/SEARCH TABLE t1 USING INDEX t1a/} 76 +do_execsql_test analyzeE-1.11 { 77 + EXPLAIN QUERY PLAN 78 + SELECT * FROM t1 WHERE a<1900 79 +} {/SCAN TABLE t1/} 80 + 81 +# Verify that everything works the same on a DESCENDING index. 82 +# 83 +do_execsql_test analyzeE-2.0 { 84 + DROP INDEX t1a; 85 + CREATE INDEX t1a ON t1(a DESC); 86 + ANALYZE; 87 +} {} 88 +do_execsql_test analyzeE-2.1 { 89 + EXPLAIN QUERY PLAN 90 + SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500; 91 +} {/SCAN TABLE t1/} 92 +do_execsql_test analyzeE-2.2 { 93 + EXPLAIN QUERY PLAN 94 + SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000; 95 +} {/SEARCH TABLE t1 USING INDEX t1a/} 96 +do_execsql_test analyzeE-2.3 { 97 + EXPLAIN QUERY PLAN 98 + SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750; 99 +} {/SEARCH TABLE t1 USING INDEX t1a/} 100 +do_execsql_test analyzeE-2.4 { 101 + EXPLAIN QUERY PLAN 102 + SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 103 +} {/SEARCH TABLE t1 USING INDEX t1a/} 104 +do_execsql_test analyzeE-2.5 { 105 + EXPLAIN QUERY PLAN 106 + SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 107 +} {/SEARCH TABLE t1 USING INDEX t1a/} 108 +do_execsql_test analyzeE-2.6 { 109 + EXPLAIN QUERY PLAN 110 + SELECT * FROM t1 WHERE a<500 111 +} {/SEARCH TABLE t1 USING INDEX t1a/} 112 +do_execsql_test analyzeE-2.7 { 113 + EXPLAIN QUERY PLAN 114 + SELECT * FROM t1 WHERE a>2500 115 +} {/SEARCH TABLE t1 USING INDEX t1a/} 116 +do_execsql_test analyzeE-2.8 { 117 + EXPLAIN QUERY PLAN 118 + SELECT * FROM t1 WHERE a>1900 119 +} {/SEARCH TABLE t1 USING INDEX t1a/} 120 +do_execsql_test analyzeE-2.9 { 121 + EXPLAIN QUERY PLAN 122 + SELECT * FROM t1 WHERE a>1100 123 +} {/SCAN TABLE t1/} 124 +do_execsql_test analyzeE-2.10 { 125 + EXPLAIN QUERY PLAN 126 + SELECT * FROM t1 WHERE a<1100 127 +} {/SEARCH TABLE t1 USING INDEX t1a/} 128 +do_execsql_test analyzeE-2.11 { 129 + EXPLAIN QUERY PLAN 130 + SELECT * FROM t1 WHERE a<1900 131 +} {/SCAN TABLE t1/} 132 + 133 +# Now do a range query on the second term of an ASCENDING index 134 +# where the first term is constrained by equality. 135 +# 136 +do_execsql_test analyzeE-3.0 { 137 + DROP TABLE t1; 138 + CREATE TABLE t1(a,b,c); 139 + WITH RECURSIVE 140 + cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000) 141 + INSERT INTO t1(a,b,c) SELECT x, x, 123 FROM cnt; 142 + CREATE INDEX t1ca ON t1(c,a); 143 + ANALYZE; 144 +} {} 145 +do_execsql_test analyzeE-3.1 { 146 + EXPLAIN QUERY PLAN 147 + SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500 AND c=123; 148 +} {/SCAN TABLE t1/} 149 +do_execsql_test analyzeE-3.2 { 150 + EXPLAIN QUERY PLAN 151 + SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000 AND c=123; 152 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 153 +do_execsql_test analyzeE-3.3 { 154 + EXPLAIN QUERY PLAN 155 + SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750 AND c=123; 156 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 157 +do_execsql_test analyzeE-3.4 { 158 + EXPLAIN QUERY PLAN 159 + SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 AND c=123 160 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 161 +do_execsql_test analyzeE-3.5 { 162 + EXPLAIN QUERY PLAN 163 + SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 AND c=123 164 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 165 +do_execsql_test analyzeE-3.6 { 166 + EXPLAIN QUERY PLAN 167 + SELECT * FROM t1 WHERE a<500 AND c=123 168 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 169 +do_execsql_test analyzeE-3.7 { 170 + EXPLAIN QUERY PLAN 171 + SELECT * FROM t1 WHERE a>2500 AND c=123 172 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 173 +do_execsql_test analyzeE-3.8 { 174 + EXPLAIN QUERY PLAN 175 + SELECT * FROM t1 WHERE a>1900 AND c=123 176 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 177 +do_execsql_test analyzeE-3.9 { 178 + EXPLAIN QUERY PLAN 179 + SELECT * FROM t1 WHERE a>1100 AND c=123 180 +} {/SCAN TABLE t1/} 181 +do_execsql_test analyzeE-3.10 { 182 + EXPLAIN QUERY PLAN 183 + SELECT * FROM t1 WHERE a<1100 AND c=123 184 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 185 +do_execsql_test analyzeE-3.11 { 186 + EXPLAIN QUERY PLAN 187 + SELECT * FROM t1 WHERE a<1900 AND c=123 188 +} {/SCAN TABLE t1/} 189 + 190 +# Repeat the 3.x tests using a DESCENDING index 191 +# 192 +do_execsql_test analyzeE-4.0 { 193 + DROP INDEX t1ca; 194 + CREATE INDEX t1ca ON t1(c ASC,a DESC); 195 + ANALYZE; 196 +} {} 197 +do_execsql_test analyzeE-4.1 { 198 + EXPLAIN QUERY PLAN 199 + SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500 AND c=123; 200 +} {/SCAN TABLE t1/} 201 +do_execsql_test analyzeE-4.2 { 202 + EXPLAIN QUERY PLAN 203 + SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000 AND c=123; 204 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 205 +do_execsql_test analyzeE-4.3 { 206 + EXPLAIN QUERY PLAN 207 + SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750 AND c=123; 208 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 209 +do_execsql_test analyzeE-4.4 { 210 + EXPLAIN QUERY PLAN 211 + SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 AND c=123 212 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 213 +do_execsql_test analyzeE-4.5 { 214 + EXPLAIN QUERY PLAN 215 + SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 AND c=123 216 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 217 +do_execsql_test analyzeE-4.6 { 218 + EXPLAIN QUERY PLAN 219 + SELECT * FROM t1 WHERE a<500 AND c=123 220 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 221 +do_execsql_test analyzeE-4.7 { 222 + EXPLAIN QUERY PLAN 223 + SELECT * FROM t1 WHERE a>2500 AND c=123 224 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 225 +do_execsql_test analyzeE-4.8 { 226 + EXPLAIN QUERY PLAN 227 + SELECT * FROM t1 WHERE a>1900 AND c=123 228 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 229 +do_execsql_test analyzeE-4.9 { 230 + EXPLAIN QUERY PLAN 231 + SELECT * FROM t1 WHERE a>1100 AND c=123 232 +} {/SCAN TABLE t1/} 233 +do_execsql_test analyzeE-4.10 { 234 + EXPLAIN QUERY PLAN 235 + SELECT * FROM t1 WHERE a<1100 AND c=123 236 +} {/SEARCH TABLE t1 USING INDEX t1ca/} 237 +do_execsql_test analyzeE-4.11 { 238 + EXPLAIN QUERY PLAN 239 + SELECT * FROM t1 WHERE a<1900 AND c=123 240 +} {/SCAN TABLE t1/} 241 + 242 +finish_test