Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Fix query planner weights associated with choosing block-sorting. Fix block sorting of tables with collating functions. Fix various test cases. All "veryquick" tests are now passing, though more tests need to be added. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | orderby-planning |
| Files: | files | file ages | folders |
| SHA1: |
01afbf97c0ff29667806e9a7c4d74ca7 |
| User & Date: | drh 2014-03-19 23:24:49 |
Context
|
2014-03-19
| ||
| 23:42 | Merge the vdbesort.c optimization from trunk. (check-in: e4bfffb9 user: drh tags: orderby-planning) | |
| 23:24 | Fix query planner weights associated with choosing block-sorting. Fix block sorting of tables with collating functions. Fix various test cases. All "veryquick" tests are now passing, though more tests need to be added. (check-in: 01afbf97 user: drh tags: orderby-planning) | |
| 17:41 | Make it possible for block-sort to use the OP_SorterOpen sorter in addition to a generic OP_OpenEphemeral. (check-in: 7ce2daaf user: drh tags: orderby-planning) | |
Changes
Changes to src/select.c.
1000 1000 sqlite3 *db = pParse->db; 1001 1001 int i; 1002 1002 1003 1003 nExpr = pList->nExpr; 1004 1004 pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1); 1005 1005 if( pInfo ){ 1006 1006 assert( sqlite3KeyInfoIsWriteable(pInfo) ); 1007 - for(i=iStart, pItem=pList->a; i<nExpr; i++, pItem++){ 1007 + for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){ 1008 1008 CollSeq *pColl; 1009 1009 pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr); 1010 1010 if( !pColl ) pColl = db->pDfltColl; 1011 - pInfo->aColl[i] = pColl; 1012 - pInfo->aSortOrder[i] = pItem->sortOrder; 1011 + pInfo->aColl[i-iStart] = pColl; 1012 + pInfo->aSortOrder[i-iStart] = pItem->sortOrder; 1013 1013 } 1014 1014 } 1015 1015 return pInfo; 1016 1016 } 1017 1017 1018 1018 #ifndef SQLITE_OMIT_COMPOUND_SELECT 1019 1019 /* ................................................................................ 5253 5253 explainTempTable(pParse, "DISTINCT"); 5254 5254 } 5255 5255 5256 5256 /* If there is an ORDER BY clause, then we need to sort the results 5257 5257 ** and send them to the callback one by one. 5258 5258 */ 5259 5259 if( sSort.pOrderBy ){ 5260 - explainTempTable(pParse, "ORDER BY"); 5260 + explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY"); 5261 5261 generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest); 5262 5262 } 5263 5263 5264 5264 /* Jump here to skip this query 5265 5265 */ 5266 5266 sqlite3VdbeResolveLabel(v, iEnd); 5267 5267
Changes to src/where.c.
5035 5035 nOut = pFrom->nRow + pWLoop->nOut; 5036 5036 maskNew = pFrom->maskLoop | pWLoop->maskSelf; 5037 5037 if( isOrdered<0 ){ 5038 5038 isOrdered = wherePathSatisfiesOrderBy(pWInfo, 5039 5039 pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, 5040 5040 iLoop, pWLoop, &revMask); 5041 5041 if( isOrdered>=0 && isOrdered<nOrderBy ){ 5042 - /* TUNING: Estimated cost of sorting cost as roughly 4*N*log(N). 5042 + /* TUNING: Estimated cost of sorting cost as roughly N*log(N). 5043 5043 ** If some but not all of the columns are in sorted order, then 5044 5044 ** scale down the log(N) term. */ 5045 - LogEst rSortCost = 20 + nRowEst + 5046 - estLog(nRowEst)*(nOrderBy-isOrdered)/nOrderBy; 5045 + LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy); 5046 + LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66; 5047 + /* TUNING: The cost of implementing DISTINCT using a B-TREE is 5048 + ** also N*log(N) but it has a larger constant of proportionality. 5049 + ** Multiply by 3.0. */ 5050 + if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ 5051 + rSortCost += 16; 5052 + } 5047 5053 WHERETRACE(0x002, 5048 5054 ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", 5049 5055 rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost, 5050 5056 sqlite3LogEstAdd(rCost,rSortCost))); 5051 5057 rCost = sqlite3LogEstAdd(rCost, rSortCost); 5052 5058 } 5053 5059 }else{
Changes to test/distinct.test.
158 158 INSERT INTO t1 VALUES('a', 'b', 'c'); 159 159 INSERT INTO t1 VALUES('A', 'B', 'C'); 160 160 } 161 161 162 162 foreach {tn sql temptables res} { 163 163 1 "a, b FROM t1" {} {A B a b} 164 164 2 "b, a FROM t1" {} {B A b a} 165 - 3 "a, b, c FROM t1" {hash} {a b c A B C} 165 + 3 "a, b, c FROM t1" {hash} {A B C a b c} 166 166 4 "a, b, c FROM t1 ORDER BY a, b, c" {btree} {A B C a b c} 167 167 5 "b FROM t1 WHERE a = 'a'" {} {b} 168 168 6 "b FROM t1 ORDER BY +b COLLATE binary" {btree hash} {B b} 169 169 7 "a FROM t1" {} {A a} 170 170 8 "b COLLATE nocase FROM t1" {} {b} 171 171 9 "b COLLATE nocase FROM t1 ORDER BY b COLLATE nocase" {} {b} 172 172 } {
Changes to test/orderby5.test.
60 60 EXPLAIN QUERY PLAN 61 61 SELECT DISTINCT c, b, a FROM t1 WHERE a=0; 62 62 } {~/B-TREE/} 63 63 do_execsql_test 1.7 { 64 64 EXPLAIN QUERY PLAN 65 65 SELECT DISTINCT c, b, a FROM t1 WHERE +a=0; 66 66 } {/B-TREE/} 67 -do_execsql_test 2.1 { 67 + 68 +# In some cases, it is faster to do repeated index lookups than it is to 69 +# sort. But in other cases, it is faster to sort than to do repeated index 70 +# lookups. 71 +# 72 +do_execsql_test 2.1a { 73 + CREATE TABLE t2(a,b,c); 74 + CREATE INDEX t2bc ON t2(b,c); 75 + ANALYZE; 76 + INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9'); 77 + INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5'); 78 + ANALYZE sqlite_master; 79 + 80 + EXPLAIN QUERY PLAN 81 + SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c; 82 +} {~/B-TREE/} 83 +do_execsql_test 2.1b { 68 84 EXPLAIN QUERY PLAN 69 85 SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c; 70 -} {~/B-TREE/} 86 +} {/B-TREE/} 87 + 88 + 71 89 do_execsql_test 2.2 { 72 90 EXPLAIN QUERY PLAN 73 91 SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c; 74 92 } {/B-TREE/} 75 93 do_execsql_test 2.3 { 76 94 EXPLAIN QUERY PLAN 77 95 SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;
Changes to test/whereG.test.
91 91 92 92 do_eqp_test whereG-1.5 { 93 93 SELECT DISTINCT aname 94 94 FROM album, composer, track 95 95 WHERE cname LIKE '%bach%' 96 96 AND composer.cid=track.cid 97 97 AND album.aid=track.aid; 98 -} {/.*track.*composer.*album.*/} 98 +} {/.*track.*(composer.*album|album.*composer).*/} 99 99 do_execsql_test whereG-1.6 { 100 100 SELECT DISTINCT aname 101 101 FROM album, composer, track 102 102 WHERE cname LIKE '%bach%' 103 103 AND composer.cid=track.cid 104 104 AND album.aid=track.aid; 105 105 } {{Mass in B Minor, BWV 232}} ................................................................................ 106 106 107 107 do_eqp_test whereG-1.7 { 108 108 SELECT DISTINCT aname 109 109 FROM album, composer, track 110 110 WHERE cname LIKE '%bach%' 111 111 AND unlikely(composer.cid=track.cid) 112 112 AND unlikely(album.aid=track.aid); 113 -} {/.*track.*composer.*album.*/} 113 +} {/.*track.*(composer.*album|album.*composer).*/} 114 114 do_execsql_test whereG-1.8 { 115 115 SELECT DISTINCT aname 116 116 FROM album, composer, track 117 117 WHERE cname LIKE '%bach%' 118 118 AND unlikely(composer.cid=track.cid) 119 119 AND unlikely(album.aid=track.aid); 120 120 } {{Mass in B Minor, BWV 232}}