/ Check-in [952f5e8c]
Login

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

Overview
Comment:Do a better job of choosing the join table order when the tables having very different numbers of rows.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 952f5e8c69904c48f2decfabf8ea60a2e9f3e134
User & Date: drh 2011-03-04 00:56:58
References
2011-03-04
01:23
Backport the query planner enhancement of [952f5e8c69904] to the 3.7.2 branch. check-in: 440d9956 user: drh tags: branch-3.7.2
Context
2011-03-05
13:54
Fix an instance of signed arithmetic overflow and an one bit-shift overflow. Mark six other signed arithmetic overflow locations that need fixing. check-in: 04abab71 user: drh tags: trunk
2011-03-04
00:56
Do a better job of choosing the join table order when the tables having very different numbers of rows. check-in: 952f5e8c user: drh tags: trunk
2011-03-02
22:07
Fix quoting of the result in rtreeB.test. check-in: c6532b35 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  4606   4606           }
  4607   4607   
  4608   4608           /* Conditions under which this table becomes the best so far:
  4609   4609           **
  4610   4610           **   (1) The table must not depend on other tables that have not
  4611   4611           **       yet run.
  4612   4612           **
  4613         -        **   (2) A full-table-scan plan cannot supercede another plan unless
  4614         -        **       it is an "optimal" plan as defined above.
         4613  +        **   (2) A full-table-scan plan cannot supercede indexed plan unless
         4614  +        **       the full-table-scan is an "optimal" plan as defined above.
  4615   4615           **
  4616   4616           **   (3) All tables have an INDEXED BY clause or this table lacks an
  4617   4617           **       INDEXED BY clause or this table uses the specific
  4618   4618           **       index specified by its INDEXED BY clause.  This rule ensures
  4619   4619           **       that a best-so-far is always selected even if an impossible
  4620   4620           **       combination of INDEXED BY clauses are given.  The error
  4621   4621           **       will be detected and relayed back to the application later.
................................................................................
  4623   4623           **       An indexable full-table-scan from reaching rule (3).
  4624   4624           **
  4625   4625           **   (4) The plan cost must be lower than prior plans or else the
  4626   4626           **       cost must be the same and the number of rows must be lower.
  4627   4627           */
  4628   4628           if( (sCost.used&notReady)==0                       /* (1) */
  4629   4629               && (bestJ<0 || (notIndexed&m)!=0               /* (2) */
         4630  +                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
  4630   4631                   || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
  4631   4632               && (nUnconstrained==0 || pTabItem->pIndex==0   /* (3) */
  4632   4633                   || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
  4633   4634               && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (4) */
  4634   4635                   || (sCost.rCost<=bestPlan.rCost 
  4635   4636                    && sCost.plan.nRow<bestPlan.plan.nRow))
  4636   4637           ){

Added test/analyze6.test.

            1  +# 2011 March 3
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# This file implements tests for SQLite library.  The focus of the tests
           13  +# in this file a corner-case query planner optimization involving the
           14  +# join order of two tables of different sizes.
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +
           20  +ifcapable !stat2 {
           21  +  finish_test
           22  +  return
           23  +}
           24  +
           25  +set testprefix analyze6
           26  +
           27  +proc eqp {sql {db db}} {
           28  +  uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db
           29  +}
           30  +
           31  +do_test analyze6-1.0 {
           32  +  db eval {
           33  +    CREATE TABLE cat(x INT);
           34  +    CREATE UNIQUE INDEX catx ON cat(x);
           35  +    /* Give cat 16 unique integers */
           36  +    INSERT INTO cat VALUES(1);
           37  +    INSERT INTO cat VALUES(2);
           38  +    INSERT INTO cat SELECT x+2 FROM cat;
           39  +    INSERT INTO cat SELECT x+4 FROM cat;
           40  +    INSERT INTO cat SELECT x+8 FROM cat;
           41  +
           42  +    CREATE TABLE ev(y INT);
           43  +    CREATE INDEX evy ON ev(y);
           44  +    /* ev will hold 32 copies of 16 integers found in cat */
           45  +    INSERT INTO ev SELECT x FROM cat;
           46  +    INSERT INTO ev SELECT x FROM cat;
           47  +    INSERT INTO ev SELECT y FROM ev;
           48  +    INSERT INTO ev SELECT y FROM ev;
           49  +    INSERT INTO ev SELECT y FROM ev;
           50  +    INSERT INTO ev SELECT y FROM ev;
           51  +    ANALYZE;
           52  +    SELECT count(*) FROM cat;
           53  +    SELECT count(*) FROM ev;
           54  +  }
           55  +} {16 512}
           56  +
           57  +# The lowest cost plan is to scan CAT and for each integer there, do a single
           58  +# lookup of the first corresponding entry in EV then read off the equal values
           59  +# in EV.  (Prior to the 2011-03-04 enhancement to where.c, this query would
           60  +# have used EV for the outer loop instead of CAT - which was about 3x slower.)
           61  +#
           62  +do_test analyze6-1.1 {
           63  +  eqp {SELECT count(*) FROM ev, cat WHERE x=y}
           64  +} {0 0 1 {SCAN TABLE cat (~16 rows)} 0 1 0 {SEARCH TABLE ev USING COVERING INDEX evy (y=?) (~32 rows)}}
           65  +
           66  +# The same plan is chosen regardless of the order of the tables in the
           67  +# FROM clause.
           68  +#
           69  +do_test analyze6-1.2 {
           70  +  eqp {SELECT count(*) FROM cat, ev WHERE x=y}
           71  +} {0 0 0 {SCAN TABLE cat (~16 rows)} 0 1 1 {SEARCH TABLE ev USING COVERING INDEX evy (y=?) (~32 rows)}}
           72  +
           73  +
           74  +finish_test