Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1965,10 +1965,11 @@ int addrInTop; /* Top of the IN loop */ } *aInLoop; /* Information about each nested IN operator */ } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ } u; + double rOptCost; /* "Optimal" cost for this level */ /* The following field is really not part of the current level. But ** we need a place to cache virtual table index information for each ** virtual table in the FROM clause and the WhereLevel structure is ** a convenient place since there is one WhereLevel for each FROM clause Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -5100,19 +5100,32 @@ || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex ); if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){ notIndexed |= m; } + if( isOptimal ){ + pWInfo->a[j].rOptCost = sWBI.cost.rCost; + }else if( iFroma[j].rOptCost)); + sWBI.cost.rCost /= pWInfo->a[j].rOptCost; + } /* Conditions under which this table becomes the best so far: ** ** (1) The table must not depend on other tables that have not ** yet run. (In other words, it must not depend on tables ** in inner loops.) ** - ** (2) A full-table-scan plan cannot supercede indexed plan unless - ** the full-table-scan is an "optimal" plan as defined above. + ** (2) (This rule was removed on 2012-11-09. The scaling of the + ** cost using the optimal scan cost made this rule obsolete.) ** ** (3) All tables have an INDEXED BY clause or this table lacks an ** INDEXED BY clause or this table uses the specific ** index specified by its INDEXED BY clause. This rule ensures ** that a best-so-far is always selected even if an impossible @@ -5123,13 +5136,10 @@ ** ** (4) The plan cost must be lower than prior plans, where "cost" ** is defined by the compareCost() function above. */ if( (sWBI.cost.used&sWBI.notValid)==0 /* (1) */ - && (bestJ<0 || (notIndexed&m)!=0 /* (2) */ - || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 - || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0) && (nUnconstrained==0 || sWBI.pSrc->pIndex==0 /* (3) */ || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)) && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan)) /* (4) */ ){ WHERETRACE((" === table %d (%s) is best so far\n" Index: test/orderby1.test ================================================================== --- test/orderby1.test +++ test/orderby1.test @@ -46,110 +46,110 @@ COMMIT; } } {} do_test 1.1a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} # Verify that the ORDER BY clause is optimized out # do_test 1.1b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 1.2a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} # The output is sorted manually in this case. # do_test 1.2b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 1.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 1.3b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Reverse order sorts # do_test 1.4a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 1.4b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 1.4c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {~/ORDER BY/} ;# optimized out do_test 1.5a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 1.5b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting do_test 1.5c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {~/ORDER BY/} ;# optimized out do_test 1.6a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 1.6b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 1.6c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized-out # Reconstruct the test data to use indices rather than integer primary keys. @@ -181,122 +181,122 @@ COMMIT; } } {} do_test 2.1a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} # Verify that the ORDER BY clause is optimized out # do_test 2.1b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {~/ORDER BY/} ;# ORDER BY optimized out do_test 2.1c { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, aid, tn } } {one-a one-c two-a two-b three-a three-c} do_test 2.1d { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, aid, tn } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 2.2a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} # The output is sorted manually in this case. # do_test 2.2b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 2.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 2.3b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Reverse order sorts # do_test 2.4a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 2.4b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 2.4c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {~/ORDER BY/} ;# optimized out do_test 2.5a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 2.5b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting do_test 2.5c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {~/ORDER BY/} ;# optimized out do_test 2.6a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 2.6b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 2.6c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized out # Generate another test dataset, but this time using mixed ASC/DESC indices. @@ -328,111 +328,111 @@ COMMIT; } } {} do_test 3.1a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} # Verify that the ORDER BY clause is optimized out # do_test 3.1b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 3.2a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} # The output is sorted manually in this case. # do_test 3.2b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 3.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 3.3b { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Without the mixed ASC/DESC on ORDER BY # do_test 3.4a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 3.4b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} ;# verify same order after sorting do_test 3.4c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn } } {~/ORDER BY/} ;# optimized out do_test 3.5a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 3.5b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 3.5c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {~/ORDER BY/} ;# optimzed out do_test 3.6a { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 3.6b { db eval { - SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 3.6c { db eval { EXPLAIN QUERY PLAN - SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn + SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn } } {~/ORDER BY/} ;# inverted ASC/DESC is optimized out finish_test ADDED test/whereE.test Index: test/whereE.test ================================================================== --- /dev/null +++ test/whereE.test @@ -0,0 +1,62 @@ +# 2012 November 9 +# +# 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 query planner to make sure it +# is making good planning decisions. +# + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix whereE + +do_execsql_test 1.1 { + CREATE TABLE t1(a,b); + INSERT INTO t1 VALUES(1,10), (2,20), (3,30), (2,22), (3, 33); + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + INSERT INTO t1 SELECT * FROM t1; + ALTER TABLE t1 ADD COLUMN c; + UPDATE t1 SET c=a*rowid+10000; + CREATE INDEX t1ab ON t1(a,b); + + CREATE TABLE t2(x,y); + INSERT INTO t2 VALUES(4,44),(5,55),(6,66),(7,77); + INSERT INTO t2 SELECT x+4, (x+4)*11 FROM t2; + INSERT INTO t2 SELECT x+8, (x+8)*11 FROM t2; + INSERT INTO t2 SELECT x+16, (x+16)*11 FROM t2; + INSERT INTO t2 SELECT x+32, (x+32)*11 FROM t2; + INSERT INTO t2 SELECT x+64, (x+32)*11 FROM t2; + ALTER TABLE t2 ADD COLUMN z; + UPDATE t2 SET z=2; + CREATE UNIQUE INDEX t2zx ON t2(z,x); + + EXPLAIN QUERY PLAN SELECT x FROM t1, t2 WHERE a=z AND c=x; +} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/} +do_execsql_test 1.2 { + EXPLAIN QUERY PLAN SELECT x FROM t2, t1 WHERE a=z AND c=x; +} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/} +do_execsql_test 1.3 { + ANALYZE; + EXPLAIN QUERY PLAN SELECT x FROM t1, t2 WHERE a=z AND c=x; +} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/} +do_execsql_test 1.4 { + EXPLAIN QUERY PLAN SELECT x FROM t2, t1 WHERE a=z AND c=x; +} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/} + +finish_test ADDED test/whereF.test Index: test/whereF.test ================================================================== --- /dev/null +++ test/whereF.test @@ -0,0 +1,115 @@ +# 2012 November 9 +# +# 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. +# +#*********************************************************************** +# +# Test cases for query planning decisions. + + +# +# The tests in this file demonstrate the behaviour of the query planner +# in determining the order in which joined tables are scanned. +# +# Assume there are two tables being joined - t1 and t2. Each has a cost +# if it is the outer loop, and a cost if it is the inner loop. As follows: +# +# t1(outer) - cost of scanning t1 as the outer loop. +# t1(inner) - cost of scanning t1 as the inner loop. +# t2(outer) - cost of scanning t2 as the outer loop. +# t2(inner) - cost of scanning t2 as the inner loop. +# +# Depending on the order in which the planner nests the scans, the total +# cost of the join query is one of: +# +# t1(outer) * t2(inner) +# t2(outer) * t1(inner) +# +# The tests in this file attempt to verify that the planner nests joins in +# the correct order when the following are true: +# +# + (t1(outer) * t2(inner)) > (t1(inner) * t2(outer) +# + t1(outer) < t2(outer) +# +# In other words, when the best overall query plan has t2 as the outer loop, +# but when the outer loop is considered independent of the inner, t1 is the +# most efficient choice. +# +# In order to make them more predictable, automatic indexes are turned off for +# the tests in this file. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set testprefix x + +do_execsql_test 1.0 { + PRAGMA automatic_index = 0; + CREATE TABLE t1(a, b, c); + CREATE TABLE t2(d, e, f); + CREATE UNIQUE INDEX i1 ON t1(a); + CREATE UNIQUE INDEX i2 ON t2(d); +} {} + +foreach {tn sql} { + 1 "SELECT * FROM t1, t2 WHERE t1.a=t2.e AND t2.d? AND t2.d>t1.c AND t1.b=t2.e" + 2 "SELECT * FROM t2, t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e" + 3 "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e" +} { + do_test 2.$tn { + db eval "EXPLAIN QUERY PLAN $sql" + } {/.*SCAN TABLE t2 .*SEARCH TABLE t1 .*/} +} + +do_execsql_test 3.0 { + DROP TABLE t1; + DROP TABLE t2; + CREATE TABLE t1(a, b, c); + CREATE TABLE t2(d, e, f); + + CREATE UNIQUE INDEX i1 ON t1(a, b); + CREATE INDEX i2 ON t2(d); +} {} + +foreach {tn sql} { + 1 {SELECT t1.a, t1.b, t2.d, t2.e FROM t1, t2 + WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} + + 2 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2, t1 + WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} + + 3 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2 CROSS JOIN t1 + WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} +} { + do_test 3.$tn { + db eval "EXPLAIN QUERY PLAN $sql" + } {/.*SCAN TABLE t2 .*SEARCH TABLE t1 .*/} +} + +finish_test