SQLite

Check-in [d28b58209b]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Make sure the OR-clause optimizer takes the cost of sorting into account. Reset the rowid cache on the OP_Rewind and OP_Last opcodes. Bump the version number so that we can do an emergency release. Ticket #3581. (CVS 6173)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d28b58209bf5eb575d0cad8dc71ac043395c6471
User & Date: drh 2009-01-14 00:55:10.000
Context
2009-01-14
01:10
Here is the test case to prove that ticket #3581 is fixed. (CVS 6174) (check-in: f5f5ef646b user: drh tags: trunk)
00:55
Make sure the OR-clause optimizer takes the cost of sorting into account. Reset the rowid cache on the OP_Rewind and OP_Last opcodes. Bump the version number so that we can do an emergency release. Ticket #3581. (CVS 6173) (check-in: d28b58209b user: drh tags: trunk)
2009-01-13
20:14
Updates to comments as suggested by tickets #3578 and #3579. (CVS 6172) (check-in: b5927213b6 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to VERSION.
1
3.6.8
|
1
3.6.9
Changes to src/vdbe.c.
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.810 2009/01/05 22:30:39 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor







|







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.811 2009/01/14 00:55:10 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
3904
3905
3906
3907
3908
3909
3910

3911
3912
3913
3914
3915
3916
3917
  pC = p->apCsr[i];
  assert( pC!=0 );
  pCrsr = pC->pCursor;
  assert( pCrsr!=0 );
  rc = sqlite3BtreeLast(pCrsr, &res);
  pC->nullRow = (u8)res;
  pC->deferredMoveto = 0;

  pC->cacheStatus = CACHE_STALE;
  if( res && pOp->p2>0 ){
    pc = pOp->p2 - 1;
  }
  break;
}








>







3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
  pC = p->apCsr[i];
  assert( pC!=0 );
  pCrsr = pC->pCursor;
  assert( pCrsr!=0 );
  rc = sqlite3BtreeLast(pCrsr, &res);
  pC->nullRow = (u8)res;
  pC->deferredMoveto = 0;
  pC->rowidIsValid = 0;
  pC->cacheStatus = CACHE_STALE;
  if( res && pOp->p2>0 ){
    pc = pOp->p2 - 1;
  }
  break;
}

3954
3955
3956
3957
3958
3959
3960

3961
3962
3963
3964
3965
3966
3967
  pC = p->apCsr[i];
  assert( pC!=0 );
  if( (pCrsr = pC->pCursor)!=0 ){
    rc = sqlite3BtreeFirst(pCrsr, &res);
    pC->atFirst = res==0 ?1:0;
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;

  }else{
    res = 1;
  }
  pC->nullRow = (u8)res;
  assert( pOp->p2>0 && pOp->p2<p->nOp );
  if( res ){
    pc = pOp->p2 - 1;







>







3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
  pC = p->apCsr[i];
  assert( pC!=0 );
  if( (pCrsr = pC->pCursor)!=0 ){
    rc = sqlite3BtreeFirst(pCrsr, &res);
    pC->atFirst = res==0 ?1:0;
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
    pC->rowidIsValid = 0;
  }else{
    res = 1;
  }
  pC->nullRow = (u8)res;
  assert( pOp->p2>0 && pOp->p2<p->nOp );
  if( res ){
    pc = pOp->p2 - 1;
Changes to src/where.c.
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.363 2009/01/10 15:34:12 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.364 2009/01/14 00:55:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
1842
1843
1844
1845
1846
1847
1848

1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866








1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
    tempWC = *pWC;
    if( pTerm->eOperator==WO_OR 
        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){
      WhereClause *pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm *pOrTerm;
      int j;

      double rTotal = 0;
      nRow = 0;
      for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
        WhereCost sTermCost;
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", j,i));
        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
        if( rTotal>=pCost->rCost ) break;








      }
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n",
                  rTotal, nRow));
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = WHERE_MULTI_OR;
        pCost->plan.u.pTerm = pTerm;
        if( pOrderBy!=0
         && sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)
         && !rev
        ){
          pCost->plan.wsFlags = WHERE_ORDERBY|WHERE_MULTI_OR;
        }
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */








>


















>
>
>
>
>
>
>
>








|
<
<
<







1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884



1885
1886
1887
1888
1889
1890
1891
    tempWC = *pWC;
    if( pTerm->eOperator==WO_OR 
        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){
      WhereClause *pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm *pOrTerm;
      int j;
      int sortable = 0;
      double rTotal = 0;
      nRow = 0;
      for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
        WhereCost sTermCost;
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", j,i));
        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
        if( rTotal>=pCost->rCost ) break;
      }
      if( pOrderBy!=0 ){
        if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) && !rev ){
          sortable = 1;
        }else{
          rTotal += nRow*estLog(nRow);
          WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
        }
      }
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n",
                  rTotal, nRow));
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = WHERE_MULTI_OR;
        pCost->plan.u.pTerm = pTerm;
        if( sortable ){



          pCost->plan.wsFlags = WHERE_ORDERBY|WHERE_MULTI_OR;
        }
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

Changes to test/where7.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2008 December 23
#
# 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 file is testing the multi-index OR clause optimizer.
#
# $Id: where7.test,v 1.6 2008/12/30 17:55:00 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !or_opt {
  finish_test
  return













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2008 December 23
#
# 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 file is testing the multi-index OR clause optimizer.
#
# $Id: where7.test,v 1.7 2009/01/14 00:55:10 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !or_opt {
  finish_test
  return
95
96
97
98
99
100
101
102
103
104
105






106
107
108
109
110
111
112
  }
} {2 5 scan 0 sort 0}
do_test where7-1.12 {
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
  }
} {1 2 3 5 scan 0 sort 0}
do_test where7-1.13 {
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
    ORDER BY a DESC






  }
} {5 4 1 scan 0 sort 1}

do_test where7-1.14 {
  count_steps {
    SELECT a FROM t1 WHERE (d=8 OR c=6 OR b=4) AND +a>0
  }







|



>
>
>
>
>
>







95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
  }
} {2 5 scan 0 sort 0}
do_test where7-1.12 {
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
  }
} {1 2 3 5 scan 0 sort 0}
do_test where7-1.13.1 {
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
    ORDER BY a DESC
  }
} {5 4 1 scan 4 sort 0}
do_test where7-1.13.2 {
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
    ORDER BY +a DESC
  }
} {5 4 1 scan 0 sort 1}

do_test where7-1.14 {
  count_steps {
    SELECT a FROM t1 WHERE (d=8 OR c=6 OR b=4) AND +a>0
  }