SQLite

Check-in [3464d369d3]
Login

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

Overview
Comment:Multi-index OR optimizer response to ORDER BY rowid. But fix in sqlite3_stmt_status(): report a full table scan when "ORDER BY rowid" is used without constraints. (CVS 6069)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 3464d369d3b6899ec726cf5b42b68b1dac2ba982
User & Date: drh 2008-12-28 20:47:03.000
Context
2008-12-29
10:39
Set the OPFLG_IN1 flag on a couple of extra opcodes. (CVS 6070) (check-in: 03d0350441 user: danielk1977 tags: trunk)
2008-12-28
20:47
Multi-index OR optimizer response to ORDER BY rowid. But fix in sqlite3_stmt_status(): report a full table scan when "ORDER BY rowid" is used without constraints. (CVS 6069) (check-in: 3464d369d3 user: drh tags: trunk)
18:35
Optimize WHERE clauses that constain AND, BETWEEN, and LIKE terms as operands of an OR. (CVS 6068) (check-in: 67cf24b30e user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
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.346 2008/12/28 18:35:09 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.347 2008/12/28 20:47:03 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
1873
1874
1875
1876
1877
1878
1879






1880
1881
1882
1883
1884
1885
1886
        nRow += sTermCost.nRow;
      }
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = WHERE_MULTI_OR;
        pCost->plan.u.pTerm = pTerm;






      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is







>
>
>
>
>
>







1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
        nRow += sTermCost.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 */

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
2422
2423
2424
2425
2426
2427
2428

2429
2430
2431
2432
2433
2434
2435
      }
      disableTerm(pLevel, pEnd);
    }
    start = sqlite3VdbeCurrentAddr(v);
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iCur;
    pLevel->p2 = start;

    codeRowSetEarly = regRowSet>=0 ? whereRowReadyForOutput(pWC) : 0;
    if( codeRowSetEarly || testOp!=OP_Noop ){
      int r1 = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);







>







2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
      }
      disableTerm(pLevel, pEnd);
    }
    start = sqlite3VdbeCurrentAddr(v);
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iCur;
    pLevel->p2 = start;
    pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;
    codeRowSetEarly = regRowSet>=0 ? whereRowReadyForOutput(pWC) : 0;
    if( codeRowSetEarly || testOp!=OP_Noop ){
      int r1 = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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
96
97
98
99
100
101
102







103
104
105
# 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.2 2008/12/28 18:35:09 drh Exp $

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

ifcapable !or_opt {
  finish_test
  return
}

# Evaluate SQL.  Return the result set followed by the
# and the number of full-scan steps.
#
proc count_steps {sql} {
  set r [db eval $sql]
  lappend r scan [db status step]
}

# Build some test data
#
do_test where7-1.1 {
  execsql {
    CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d);
    INSERT INTO t1 VALUES(1,2,3,4);
    INSERT INTO t1 VALUES(2,3,4,5);
    INSERT INTO t1 VALUES(3,4,6,8);
    INSERT INTO t1 VALUES(4,5,10,15);
    INSERT INTO t1 VALUES(5,10,100,1000);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1c ON t1(c);
    SELECT * FROM t1;
  }
} {1 2 3 4 2 3 4 5 3 4 6 8 4 5 10 15 5 10 100 1000}
do_test where7-1.2 {
  count_steps {
    SELECT a FROM t1 WHERE b=3 OR c=6
  }
} {2 3 scan 0}
do_test where7-1.3 {
  count_steps {
    SELECT a FROM t1 WHERE b=3 OR +c=6
  }
} {2 3 scan 4}
do_test where7-1.4 {
  count_steps {
    SELECT a FROM t1 WHERE +b=3 OR c=6
  }
} {2 3 scan 4}
do_test where7-1.5 {
  count_steps {
    SELECT a FROM t1 WHERE 3=b OR c=6
  }
} {2 3 scan 0}
do_test where7-1.6 {
  count_steps {
    SELECT a FROM t1 WHERE (3=b OR c=6) AND +a>0
  }
} {2 3 scan 0}
do_test where7-1.7 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>10)
  }
} {2 5 scan 0}
do_test where7-1.8 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10)
  }
} {2 4 5 scan 0}
do_test where7-1.9 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10 OR c=4)
  }
} {2 4 5 scan 0}
do_test where7-1.10 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10 OR c=4 OR b>10)
  }
} {2 4 5 scan 0}
do_test where7-1.11 {
  count_steps {
    SELECT a FROM t1 WHERE (d=5 AND b=3) OR c==100;
  }
} {2 5 scan 0}
do_test where7-1.12 {
breakpoint
  count_steps {
    SELECT a FROM t1 WHERE (b BETWEEN 2 AND 4) OR c=100
  }
} {1 2 3 5 scan 0}









finish_test













|














|



















|

|


|

|


|

|


|

|


|

|


|

|


|

|


|

|


|

|


|

|



|

|
>
>
>
>
>
>
>



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
# 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.3 2008/12/28 20:47:03 drh Exp $

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

ifcapable !or_opt {
  finish_test
  return
}

# Evaluate SQL.  Return the result set followed by the
# and the number of full-scan steps.
#
proc count_steps {sql} {
  set r [db eval $sql]
  lappend r scan [db status step] sort [db status sort]
}

# Build some test data
#
do_test where7-1.1 {
  execsql {
    CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d);
    INSERT INTO t1 VALUES(1,2,3,4);
    INSERT INTO t1 VALUES(2,3,4,5);
    INSERT INTO t1 VALUES(3,4,6,8);
    INSERT INTO t1 VALUES(4,5,10,15);
    INSERT INTO t1 VALUES(5,10,100,1000);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1c ON t1(c);
    SELECT * FROM t1;
  }
} {1 2 3 4 2 3 4 5 3 4 6 8 4 5 10 15 5 10 100 1000}
do_test where7-1.2 {
  count_steps {
    SELECT a FROM t1 WHERE b=3 OR c=6 ORDER BY a
  }
} {2 3 scan 0 sort 0}
do_test where7-1.3 {
  count_steps {
    SELECT a FROM t1 WHERE b=3 OR +c=6 ORDER BY a
  }
} {2 3 scan 4 sort 0}
do_test where7-1.4 {
  count_steps {
    SELECT a FROM t1 WHERE +b=3 OR c=6 ORDER BY 1
  }
} {2 3 scan 4 sort 0}
do_test where7-1.5 {
  count_steps {
    SELECT a FROM t1 WHERE 3=b OR c=6 ORDER BY rowid
  }
} {2 3 scan 0 sort 0}
do_test where7-1.6 {
  count_steps {
    SELECT a FROM t1 WHERE (3=b OR c=6) AND +a>0 ORDER BY a
  }
} {2 3 scan 0 sort 0}
do_test where7-1.7 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>10) ORDER BY a
  }
} {2 5 scan 0 sort 0}
do_test where7-1.8 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10) ORDER BY a
  }
} {2 4 5 scan 0 sort 0}
do_test where7-1.9 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10 OR c=4) ORDER BY a
  }
} {2 4 5 scan 0 sort 0}
do_test where7-1.10 {
  count_steps {
    SELECT a FROM t1 WHERE (b=3 OR c>=10 OR c=4 OR b>10) ORDER BY a
  }
} {2 4 5 scan 0 sort 0}
do_test where7-1.11 {
  count_steps {
    SELECT a FROM t1 WHERE (d=5 AND b=3) OR c==100 ORDER BY a;
  }
} {2 5 scan 0 sort 0}
do_test where7-1.12 {
breakpoint
  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 {
breakpoint
  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}


finish_test