/ Check-in [d28b5820]
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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d28b58209bf5eb575d0cad8dc71ac043395c6471
User & Date: drh 2009-01-14 00:55:10
Context
2009-01-14
01:10
Here is the test case to prove that ticket #3581 is fixed. (CVS 6174) check-in: f5f5ef64 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: d28b5820 user: drh tags: trunk
2009-01-13
20:14
Updates to comments as suggested by tickets #3578 and #3579. (CVS 6172) check-in: b5927213 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs 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
....
3904
3905
3906
3907
3908
3909
3910

3911
3912
3913
3914
3915
3916
3917
....
3954
3955
3956
3957
3958
3959
3960

3961
3962
3963
3964
3965
3966
3967
**
** 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
................................................................................
  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;
}

................................................................................
  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;







|







 







>







 







>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
....
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
**
** 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
................................................................................
  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;
}

................................................................................
  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
....
1842
1843
1844
1845
1846
1847
1848

1849
1850
1851
1852
1853
1854
1855
....
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
** 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)
................................................................................
    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, &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 */








|







 







>







 







>
>
>
>
>
>
>
>








|
<
<
<







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
....
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
** 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)
................................................................................
    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, &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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
95
96
97
98
99
100
101
102
103
104
105






106
107
108
109
110
111
112
#    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
................................................................................
  }
} {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
  }







|







 







|



>
>
>
>
>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#    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
................................................................................
  }
} {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
  }