SQLite

Check-in [01afbf97c0]
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
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 01afbf97c0ff29667806e9a7c4d74ca717819de5
User & Date: drh 2014-03-19 23:24:49.240
Context
2014-03-19
23:42
Merge the vdbesort.c optimization from trunk. (check-in: e4bfffb988 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: 01afbf97c0 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: 7ce2daafd3 user: drh tags: orderby-planning)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
  sqlite3 *db = pParse->db;
  int i;

  nExpr = pList->nExpr;
  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1);
  if( pInfo ){
    assert( sqlite3KeyInfoIsWriteable(pInfo) );
    for(i=iStart, pItem=pList->a; i<nExpr; i++, pItem++){
      CollSeq *pColl;
      pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      pInfo->aColl[i] = pColl;
      pInfo->aSortOrder[i] = pItem->sortOrder;
    }
  }
  return pInfo;
}

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*







|



|
|







1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
  sqlite3 *db = pParse->db;
  int i;

  nExpr = pList->nExpr;
  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1);
  if( pInfo ){
    assert( sqlite3KeyInfoIsWriteable(pInfo) );
    for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
      CollSeq *pColl;
      pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      pInfo->aColl[i-iStart] = pColl;
      pInfo->aSortOrder[i-iStart] = pItem->sortOrder;
    }
  }
  return pInfo;
}

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
    explainTempTable(pParse, "DISTINCT");
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( sSort.pOrderBy ){
    explainTempTable(pParse, "ORDER BY");
    generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
  }

  /* Jump here to skip this query
  */
  sqlite3VdbeResolveLabel(v, iEnd);








|







5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
    explainTempTable(pParse, "DISTINCT");
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( sSort.pOrderBy ){
    explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
    generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
  }

  /* Jump here to skip this query
  */
  sqlite3VdbeResolveLabel(v, iEnd);

Changes to src/where.c.
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044

5045
5046






5047
5048
5049
5050
5051
5052
5053
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly 4*N*log(N).
            ** If some but not all of the columns are in sorted order, then
            ** scale down the log(N) term. */

            LogEst rSortCost = 20 + nRowEst +
                                estLog(nRowEst)*(nOrderBy-isOrdered)/nOrderBy;






            WHERETRACE(0x002,
               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{







|


>
|
<
>
>
>
>
>
>







5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046

5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).
            ** If some but not all of the columns are in sorted order, then
            ** scale down the log(N) term. */
            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;

            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,
               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{
Changes to test/distinct.test.
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
  INSERT INTO t1 VALUES('a', 'b', 'c');
  INSERT INTO t1 VALUES('A', 'B', 'C');
}

foreach {tn sql temptables res} {
  1   "a, b FROM t1"                                       {}      {A B a b}
  2   "b, a FROM t1"                                       {}      {B A b a}
  3   "a, b, c FROM t1"                                    {hash}  {a b c A B C}
  4   "a, b, c FROM t1 ORDER BY a, b, c"                   {btree} {A B C a b c}
  5   "b FROM t1 WHERE a = 'a'"                            {}      {b}
  6   "b FROM t1 ORDER BY +b COLLATE binary"          {btree hash} {B b}
  7   "a FROM t1"                                          {}      {A a}
  8   "b COLLATE nocase FROM t1"                           {}      {b}
  9   "b COLLATE nocase FROM t1 ORDER BY b COLLATE nocase" {}      {b}
} {







|







158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
  INSERT INTO t1 VALUES('a', 'b', 'c');
  INSERT INTO t1 VALUES('A', 'B', 'C');
}

foreach {tn sql temptables res} {
  1   "a, b FROM t1"                                       {}      {A B a b}
  2   "b, a FROM t1"                                       {}      {B A b a}
  3   "a, b, c FROM t1"                                    {hash}  {A B C a b c}
  4   "a, b, c FROM t1 ORDER BY a, b, c"                   {btree} {A B C a b c}
  5   "b FROM t1 WHERE a = 'a'"                            {}      {b}
  6   "b FROM t1 ORDER BY +b COLLATE binary"          {btree hash} {B b}
  7   "a FROM t1"                                          {}      {A a}
  8   "b COLLATE nocase FROM t1"                           {}      {b}
  9   "b COLLATE nocase FROM t1 ORDER BY b COLLATE nocase" {}      {b}
} {
Changes to test/orderby5.test.
60
61
62
63
64
65
66





67







68




69
70


71
72
73
74
75
76
77
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.7 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE +a=0;
} {/B-TREE/}





do_execsql_test 2.1 {







  EXPLAIN QUERY PLAN




  SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}


do_execsql_test 2.2 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
} {/B-TREE/}
do_execsql_test 2.3 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;







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

>
>
>
>

|
>
>







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
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.7 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE +a=0;
} {/B-TREE/}

# In some cases, it is faster to do repeated index lookups than it is to
# sort.  But in other cases, it is faster to sort than to do repeated index
# lookups.
#
do_execsql_test 2.1a {
  CREATE TABLE t2(a,b,c);
  CREATE INDEX t2bc ON t2(b,c);
  ANALYZE;
  INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9');
  INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5');
  ANALYZE sqlite_master;

  EXPLAIN QUERY PLAN
  SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}
do_execsql_test 2.1b {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c;
} {/B-TREE/}


do_execsql_test 2.2 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
} {/B-TREE/}
do_execsql_test 2.3 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;
Changes to test/whereG.test.
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

do_eqp_test whereG-1.5 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {/.*track.*composer.*album.*/}
do_execsql_test whereG-1.6 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {{Mass in B Minor, BWV 232}}

do_eqp_test whereG-1.7 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {/.*track.*composer.*album.*/}
do_execsql_test whereG-1.8 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {{Mass in B Minor, BWV 232}}







|














|







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

do_eqp_test whereG-1.5 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {/.*track.*(composer.*album|album.*composer).*/}
do_execsql_test whereG-1.6 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {{Mass in B Minor, BWV 232}}

do_eqp_test whereG-1.7 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {/.*track.*(composer.*album|album.*composer).*/}
do_execsql_test whereG-1.8 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {{Mass in B Minor, BWV 232}}