/ Check-in [01afbf97]
Login

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:01afbf97c0ff29667806e9a7c4d74ca717819de5
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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}}