Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Improvements to query planning, especially in regards to estimating the cost and benefit of automatic indexes. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
1272fb8991b3888c72dcebf947415883 |
User & Date: | drh 2014-06-17 15:53:33.099 |
Context
2014-06-17
| ||
16:11 | Add the likely() function for symmetry with unlikely(). The likely(X) function means the same thing as likelihood(X,0.9375). (check-in: 3896548419 user: drh tags: trunk) | |
15:53 | Improvements to query planning, especially in regards to estimating the cost and benefit of automatic indexes. (check-in: 1272fb8991 user: drh tags: trunk) | |
13:23 | Add the autoindex2.test testing module. (check-in: ffe3fea47b user: drh tags: autoindex-improvements) | |
2014-06-16
| ||
22:45 | Fix CSV import issue, reported via the mailing list, in the shell when the file to be imported ends with an empty line. (check-in: fc918f7d33 user: mistachkin tags: trunk) | |
Changes
Changes to ext/rtree/rtree6.test.
︙ | ︙ | |||
88 89 90 91 92 93 94 | do_eqp_test rtree6.2.3 { SELECT * FROM t1,t2 WHERE k=ii } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)} } | | > > > > > > | 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | do_eqp_test rtree6.2.3 { SELECT * FROM t1,t2 WHERE k=ii } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)} } do_eqp_test rtree6.2.4.1 { SELECT * FROM t1,t2 WHERE v=+ii and x1<10 and x2>10 } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)} } do_eqp_test rtree6.2.4.2 { SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10 } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)} } do_eqp_test rtree6.2.5 { |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
5274 5275 5276 5277 5278 5279 5280 | int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ int nOrderBy; /* Number of ORDER BY clause terms */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ | < | 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 | int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ int nOrderBy; /* Number of ORDER BY clause terms */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ WhereLoop *pWLoop; /* One of the WhereLoop objects */ WhereLoop **pX; /* Used to divy up the pSpace memory */ |
︙ | ︙ | |||
5384 5385 5386 5387 5388 5389 5390 | }else{ revMask = pFrom->revLoop; } /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ if( pTo->maskLoop==maskNew && ((pTo->isOrdered^isOrdered)&80)==0 | < < | 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 | }else{ revMask = pFrom->revLoop; } /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ if( pTo->maskLoop==maskNew && ((pTo->isOrdered^isOrdered)&80)==0 ){ testcase( jj==nTo-1 ); break; } } if( jj>=nTo ){ if( nTo>=mxChoice && rCost>=mxCost ){ |
︙ | ︙ | |||
5419 5420 5421 5422 5423 5424 5425 | if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); } #endif }else{ | | | 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 | if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); } #endif }else{ if( pTo->rCost<=rCost ){ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( "Skip %s cost=%-3d,%3d order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); sqlite3DebugPrintf(" vs %s cost=%-3d,%d order=%c\n", |
︙ | ︙ | |||
5459 5460 5461 5462 5463 5464 5465 | pTo->rCost = rCost; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; mxCost = aTo[0].rCost; | < | < | 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468 5469 5470 5471 5472 | pTo->rCost = rCost; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; mxCost = aTo[0].rCost; for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ if( pTo->rCost>mxCost ){ mxCost = pTo->rCost; mxI = jj; } } } } } |
︙ | ︙ |
Added test/autoindex2.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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 | # 2014-06-17 # # 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 regression tests for SQLite library. The # focus of this script is testing automatic index creation logic. # # This file contains a single real-world test case that was giving # suboptimal performance because of over-use of automatic indexes. # set testdir [file dirname $argv0] source $testdir/tester.tcl do_execsql_test autoindex2-100 { CREATE TABLE t1( t1_id largeint, did char(9), ptime largeint, exbyte char(4), pe_id int, field_id int, mass float, param10 float, param11 float, exmass float, deviation float, trange float, vstatus int, commit_status int, formula char(329), tier int DEFAULT 2, ssid int DEFAULT 0, last_operation largeint DEFAULT 0, admin_uuid int DEFAULT 0, previous_value float, job_id largeint, last_t1 largeint DEFAULT 0, data_t1 int, previous_date largeint DEFAULT 0, flg8 int DEFAULT 1, failed_fields char(100) ); CREATE INDEX t1x0 on t1 (t1_id); CREATE INDEX t1x1 on t1 (ptime, vstatus); CREATE INDEX t1x2 on t1 (did, ssid, ptime, vstatus, exbyte, t1_id); CREATE INDEX t1x3 on t1 (job_id); CREATE TABLE t2( did char(9), client_did char(30), description char(49), uid int, tzid int, privilege int, param2 int, type char(30), subtype char(32), dparam1 char(7) DEFAULT '', param5 char(3) DEFAULT '', notional float DEFAULT 0.000000, create_time largeint, sample_time largeint DEFAULT 0, param6 largeint, frequency int, expiration largeint, uw_status int, next_sample largeint, last_sample largeint, reserve1 char(29) DEFAULT '', reserve2 char(29) DEFAULT '', reserve3 char(29) DEFAULT '', bxcdr char(19) DEFAULT 'XY', ssid int DEFAULT 1, last_t1_id largeint, reserve4 char(29) DEFAULT '', reserve5 char(29) DEFAULT '', param12 int DEFAULT 0, long_did char(100) DEFAULT '', gr_code int DEFAULT 0, drx char(100) DEFAULT '', parent_id char(9) DEFAULT '', param13 int DEFAULT 0, position float DEFAULT 1.000000, client_did3 char(100) DEFAULT '', client_did4 char(100) DEFAULT '', dlib_id char(9) DEFAULT '' ); CREATE INDEX t2x0 on t2 (did); CREATE INDEX t2x1 on t2 (client_did); CREATE INDEX t2x2 on t2 (long_did); CREATE INDEX t2x3 on t2 (uid); CREATE INDEX t2x4 on t2 (param2); CREATE INDEX t2x5 on t2 (type); CREATE INDEX t2x6 on t2 (subtype); CREATE INDEX t2x7 on t2 (last_sample); CREATE INDEX t2x8 on t2 (param6); CREATE INDEX t2x9 on t2 (frequency); CREATE INDEX t2x10 on t2 (privilege); CREATE INDEX t2x11 on t2 (sample_time); CREATE INDEX t2x12 on t2 (notional); CREATE INDEX t2x13 on t2 (tzid); CREATE INDEX t2x14 on t2 (gr_code); CREATE INDEX t2x15 on t2 (parent_id); CREATE TABLE t3( uid int, param3 int, uuid int, acc_id int, cust_num int, numerix_id int, pfy char(29), param4 char(29), param15 int DEFAULT 0, flg7 int DEFAULT 0, param21 int DEFAULT 0, bxcdr char(2) DEFAULT 'PC', c31 int DEFAULT 0, c33 int DEFAULT 0, c35 int DEFAULT 0, c37 int, mgr_uuid int, back_up_uuid int, priv_mars int DEFAULT 0, is_qc int DEFAULT 0, c41 int DEFAULT 0, deleted int DEFAULT 0, c47 int DEFAULT 1 ); CREATE INDEX t3x0 on t3 (uid); CREATE INDEX t3x1 on t3 (param3); CREATE INDEX t3x2 on t3 (uuid); CREATE INDEX t3x3 on t3 (acc_id); CREATE INDEX t3x4 on t3 (param4); CREATE INDEX t3x5 on t3 (pfy); CREATE INDEX t3x6 on t3 (is_qc); SELECT count(*) FROM sqlite_master; } {30} do_execsql_test autoindex2-110 { ANALYZE sqlite_master; INSERT INTO sqlite_stat1 VALUES('t1','t1x3','10747267 260'); INSERT INTO sqlite_stat1 VALUES('t1','t1x2','10747267 121 113 2 2 2 1'); INSERT INTO sqlite_stat1 VALUES('t1','t1x1','10747267 50 40'); INSERT INTO sqlite_stat1 VALUES('t1','t1x0','10747267 1'); INSERT INTO sqlite_stat1 VALUES('t2','t2x15','39667 253'); INSERT INTO sqlite_stat1 VALUES('t2','t2x14','39667 19834'); INSERT INTO sqlite_stat1 VALUES('t2','t2x13','39667 13223'); INSERT INTO sqlite_stat1 VALUES('t2','t2x12','39667 7'); INSERT INTO sqlite_stat1 VALUES('t2','t2x11','39667 17'); INSERT INTO sqlite_stat1 VALUES('t2','t2x10','39667 19834'); INSERT INTO sqlite_stat1 VALUES('t2','t2x9','39667 7934'); INSERT INTO sqlite_stat1 VALUES('t2','t2x8','39667 11'); INSERT INTO sqlite_stat1 VALUES('t2','t2x7','39667 5'); INSERT INTO sqlite_stat1 VALUES('t2','t2x6','39667 242'); INSERT INTO sqlite_stat1 VALUES('t2','t2x5','39667 1984'); INSERT INTO sqlite_stat1 VALUES('t2','t2x4','39667 4408'); INSERT INTO sqlite_stat1 VALUES('t2','t2x3','39667 81'); INSERT INTO sqlite_stat1 VALUES('t2','t2x2','39667 551'); INSERT INTO sqlite_stat1 VALUES('t2','t2x1','39667 2'); INSERT INTO sqlite_stat1 VALUES('t2','t2x0','39667 1'); INSERT INTO sqlite_stat1 VALUES('t3','t3x6','569 285'); INSERT INTO sqlite_stat1 VALUES('t3','t3x5','569 2'); INSERT INTO sqlite_stat1 VALUES('t3','t3x4','569 2'); INSERT INTO sqlite_stat1 VALUES('t3','t3x3','569 5'); INSERT INTO sqlite_stat1 VALUES('t3','t3x2','569 3'); INSERT INTO sqlite_stat1 VALUES('t3','t3x1','569 6'); INSERT INTO sqlite_stat1 VALUES('t3','t3x0','569 1'); ANALYZE sqlite_master; } {} do_execsql_test autoindex2-120 { EXPLAIN QUERY PLAN SELECT t1_id, t1.did, param2, param3, t1.ptime, t1.trange, t1.exmass, t1.mass, t1.vstatus, type, subtype, t1.deviation, t1.formula, dparam1, reserve1, reserve2, param4, t1.last_operation, t1.admin_uuid, t1.previous_value, t1.job_id, client_did, t1.last_t1, t1.data_t1, t1.previous_date, param5, param6, mgr_uuid FROM t1, t2, t3 WHERE t1.ptime > 1393520400 AND param3<>9001 AND t3.flg7 = 1 AND t1.did = t2.did AND t2.uid = t3.uid ORDER BY t1.ptime desc LIMIT 500; } {0 0 0 {SEARCH TABLE t1 USING INDEX t1x1 (ptime>?)} 0 1 1 {SEARCH TABLE t2 USING INDEX t2x0 (did=?)} 0 2 2 {SEARCH TABLE t3 USING INDEX t3x0 (uid=?)}} # # ^^^--- Before being fixed, the above was using an automatic covering # on t3 and reordering the tables so that t3 was in the outer loop and # implementing the ORDER BY clause using a B-Tree. do_execsql_test autoindex2-120 { EXPLAIN QUERY PLAN SELECT t1_id, t1.did, param2, param3, t1.ptime, t1.trange, t1.exmass, t1.mass, t1.vstatus, type, subtype, t1.deviation, t1.formula, dparam1, reserve1, reserve2, param4, t1.last_operation, t1.admin_uuid, t1.previous_value, t1.job_id, client_did, t1.last_t1, t1.data_t1, t1.previous_date, param5, param6, mgr_uuid FROM t3, t2, t1 WHERE t1.ptime > 1393520400 AND param3<>9001 AND t3.flg7 = 1 AND t1.did = t2.did AND t2.uid = t3.uid ORDER BY t1.ptime desc LIMIT 500; } {0 0 2 {SEARCH TABLE t1 USING INDEX t1x1 (ptime>?)} 0 1 1 {SEARCH TABLE t2 USING INDEX t2x0 (did=?)} 0 2 0 {SEARCH TABLE t3 USING INDEX t3x0 (uid=?)}} finish_test |
Changes to test/tpch01.test.
︙ | ︙ | |||
164 165 166 167 168 169 170 | o_year order by o_year;}] set ::eqpres } {/0 0 0 {SEARCH TABLE part USING INDEX bootleg_pti .P_TYPE=..} 0 1 2 {SEARCH TABLE lineitem USING INDEX lpki2 .L_PARTKEY=..}.*/} do_test tpch01-1.1b { set ::eqpres | | > > > > > | 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 | o_year order by o_year;}] set ::eqpres } {/0 0 0 {SEARCH TABLE part USING INDEX bootleg_pti .P_TYPE=..} 0 1 2 {SEARCH TABLE lineitem USING INDEX lpki2 .L_PARTKEY=..}.*/} do_test tpch01-1.1b { set ::eqpres } {/.* customer .* nation AS n1 .*/} do_test tpch01-1.1c { set ::eqpres } {/.* supplier .* nation AS n2 .*/} do_eqp_test tpch01-1.2 { select c_custkey, c_name, sum(l_extendedprice * (1 - l_discount)) as revenue, c_acctbal, n_name, c_address, c_phone, c_comment from customer, orders, lineitem, nation where c_custkey = o_custkey and l_orderkey = o_orderkey and o_orderdate >= '1994-08-01' and o_orderdate < date('1994-08-01', '+3 month') and l_returnflag = 'R' and c_nationkey = n_nationkey group by c_custkey, c_name, c_acctbal, c_phone, n_name, c_address, c_comment order by revenue desc; } {0 0 1 {SEARCH TABLE orders USING INDEX odi (O_ORDERDATE>? AND O_ORDERDATE<?)} 0 1 0 {SEARCH TABLE customer USING INDEX cpki (C_CUSTKEY=?)} 0 2 3 {SEARCH TABLE nation USING INDEX npki (N_NATIONKEY=?)} 0 3 2 {SEARCH TABLE lineitem USING INDEX lpki (L_ORDERKEY=?)} 0 0 0 {USE TEMP B-TREE FOR GROUP BY} 0 0 0 {USE TEMP B-TREE FOR ORDER BY}} finish_test |