/ Check-in [b090d573]
Login

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

Overview
Comment:Fix a bug in the multi-index OR cost estimator. Remove leftover "breakpoint" commands from test scripts. (CVS 6086)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b090d5736d7eaec17a39d3133e1587b1d2a42acb
User & Date: drh 2008-12-30 17:55:00
Context
2008-12-31
16:01
Fix the FTS3 module with parenthesis syntax so that it will work in the amalgamation. (CVS 6087) check-in: c2b9891f user: drh tags: trunk
2008-12-30
17:55
Fix a bug in the multi-index OR cost estimator. Remove leftover "breakpoint" commands from test scripts. (CVS 6086) check-in: b090d573 user: drh tags: trunk
16:35
Add LEFT JOIN test cases for multi-index OR in where9.test. (CVS 6085) check-in: 96f3b629 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is responsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.354 2008/12/30 16:18:48 drh Exp $
           19  +** $Id: where.c,v 1.355 2008/12/30 17:55:00 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** Trace output macros
    25     25   */
    26     26   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
  1836   1836   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  1837   1837     /* Search for an OR-clause that can be used to look up the table.
  1838   1838     */
  1839   1839     maskSrc = getMask(pWC->pMaskSet, iCur);
  1840   1840     for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  1841   1841       WhereClause tempWC;
  1842   1842       tempWC = *pWC;
  1843         -    tempWC.nSlot = 1;
  1844   1843       if( pTerm->eOperator==WO_OR 
  1845   1844           && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
  1846   1845           && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){
  1847   1846         WhereClause *pOrWC = &pTerm->u.pOrInfo->wc;
  1848   1847         WhereTerm *pOrTerm;
  1849   1848         int j;
  1850   1849         double rTotal = 0;
  1851   1850         double nRow = 0;
  1852   1851         for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
  1853   1852           WhereCost sTermCost;
         1853  +        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", j,i));
  1854   1854           if( pOrTerm->eOperator==WO_AND ){
  1855   1855             WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
  1856   1856             bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
  1857   1857           }else if( pOrTerm->leftCursor==iCur ){
  1858   1858             tempWC.a = pOrTerm;
         1859  +          tempWC.nTerm = 1;
  1859   1860             bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
  1860   1861           }else{
  1861   1862             continue;
  1862   1863           }
  1863   1864           if( sTermCost.plan.wsFlags==0 ){
  1864   1865             rTotal = pCost->rCost;
  1865   1866             break;
  1866   1867           }
  1867   1868           rTotal += sTermCost.rCost;
  1868   1869           nRow += sTermCost.nRow;
  1869   1870         }
         1871  +      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n",
         1872  +                  rTotal, nRow));
  1870   1873         if( rTotal<pCost->rCost ){
  1871   1874           pCost->rCost = rTotal;
  1872   1875           pCost->nRow = nRow;
  1873   1876           pCost->plan.wsFlags = WHERE_MULTI_OR;
  1874   1877           pCost->plan.u.pTerm = pTerm;
  1875   1878           if( pOrderBy!=0
  1876   1879            && sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)

Changes to test/capi2.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script testing the callback-free C/C++ API.
    13     13   #
    14         -# $Id: capi2.test,v 1.36 2008/09/01 15:52:11 drh Exp $
           14  +# $Id: capi2.test,v 1.37 2008/12/30 17:55:00 drh Exp $
    15     15   #
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # Return the text values from the current row pointed at by STMT as a list.
    21     21   proc get_row_values {STMT} {
................................................................................
   718    718     do_test capi2-12.3 {
   719    719       check_origins {SELECT col2 AS hello, col1 AS world FROM view1}
   720    720     } [list {main tab1 col2} {main tab1 col1}]
   721    721     do_test capi2-12.4 {
   722    722       check_origins {SELECT b, a FROM (SELECT col1 AS a, col2 AS b FROM view1)}
   723    723     } [list {main tab1 col2} {main tab1 col1}]
   724    724     do_test capi2-12.5 {
   725         -breakpoint
   726    725       check_origins {SELECT (SELECT col2 FROM view1), (SELECT col1 FROM view1)}
   727    726     } [list {main tab1 col2} {main tab1 col1}]
   728    727     do_test capi2-12.6 {
   729    728       check_origins {SELECT (SELECT col2), (SELECT col1) FROM view1}
   730    729     } [list {main tab1 col2} {main tab1 col1}]
   731    730     do_test capi2-12.7 {
   732    731       check_origins {SELECT * FROM view1}

Changes to test/expr.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing expressions.
    13     13   #
    14         -# $Id: expr.test,v 1.65 2008/08/22 16:29:51 drh Exp $
           14  +# $Id: expr.test,v 1.66 2008/12/30 17:55:00 drh Exp $
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   
    19     19   # Create a table to work with.
    20     20   #
    21     21   execsql {CREATE TABLE test1(i1 int, i2 int, r1 real, r2 real, t1 text, t2 text)}
................................................................................
   602    602   test_expr2 expr-7.58  {(a||'')<='1'}                  {1}
   603    603   
   604    604   test_expr2 expr-7.59 {LIKE('10%',b)}                  {10 20}
   605    605   test_expr2 expr-7.60 {LIKE('_4',b)}                   {6}
   606    606   test_expr2 expr-7.61 {GLOB('1?',a)}            {10 11 12 13 14 15 16 17 18 19}
   607    607   test_expr2 expr-7.62 {GLOB('1*4',b)}                  {10 14}
   608    608   test_expr2 expr-7.63 {GLOB('*1[456]',b)}              {4}
   609         -
   610         -breakpoint
   611    609   test_expr2 expr-7.64 {b = abs(-2)}                    {1}
   612    610   test_expr2 expr-7.65 {b = abs(+-2)}                   {1}
   613    611   test_expr2 expr-7.66 {b = abs(++-2)}                  {1}
   614    612   test_expr2 expr-7.67 {b = abs(+-+-2)}                 {1}
   615    613   test_expr2 expr-7.68 {b = abs(+-++-2)}                {1}
   616    614   test_expr2 expr-7.69 {b = abs(++++-2)}                {1}
   617    615   test_expr2 expr-7.70 {b = 5 - abs(+3)}                {1}

Changes to test/malloc5.test.

    14     14   #
    15     15   # Prior to version 3.6.2, calling sqlite3_release_memory() or exceeding
    16     16   # the configured soft heap limit could cause sqlite to upgrade database 
    17     17   # locks and flush dirty pages to the file system. As of 3.6.2, this is
    18     18   # no longer the case. In version 3.6.2, sqlite3_release_memory() only
    19     19   # reclaims clean pages. This test file has been updated accordingly.
    20     20   #
    21         -# $Id: malloc5.test,v 1.20 2008/08/27 16:38:57 danielk1977 Exp $
           21  +# $Id: malloc5.test,v 1.21 2008/12/30 17:55:00 drh Exp $
    22     22   
    23     23   set testdir [file dirname $argv0]
    24     24   source $testdir/tester.tcl
    25     25   source $testdir/malloc_common.tcl
    26     26   db close
    27     27   
    28     28   # Only run these tests if memory debugging is turned on.
................................................................................
   310    310       [expr ([file size test.db]/1024)>20] [expr ([file size test2.db]/1024)>20]
   311    311   } {1 1}
   312    312   do_test malloc5-6.1.2 {
   313    313     list [execsql {PRAGMA cache_size}] [execsql {PRAGMA cache_size} db2]
   314    314   } {10 10}
   315    315   
   316    316   do_test malloc5-6.2.1 {
   317         -breakpoint
   318    317     execsql {SELECT * FROM abc} db2
   319    318     execsql {SELECT * FROM abc} db
   320    319     expr [nPage db] + [nPage db2]
   321    320   } {20}
   322    321   
   323    322   do_test malloc5-6.2.2 {
   324    323     # If we now try to reclaim some memory, it should come from the db2 cache.

Changes to test/pager2.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script is page cache subsystem.
    13     13   #
    14         -# $Id: pager2.test,v 1.8 2008/10/17 18:51:53 danielk1977 Exp $
           14  +# $Id: pager2.test,v 1.9 2008/12/30 17:55:00 drh Exp $
    15     15   
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # Don't run this test file if the pager test interface [pager_open] is not
    21     21   # available, or the library was compiled without in-memory database support.
................................................................................
   338    338         set shouldbe "Page-$j v[expr {$i-1}]"
   339    339         if {$value!=$shouldbe} {
   340    340           lappend res $value $shouldbe
   341    341         }
   342    342       }
   343    343       set res
   344    344     } {}
   345         -breakpoint
   346    345     do_test pager2-4.5.$i.5 {
   347    346       page_write $g1 "Page-1 v$i"
   348    347       lrange [pager_stats $p1] 8 9
   349    348     } {state 4}
   350    349     do_test pager2-4.5.$i.6 {
   351    350       for {set j 2} {$j<=20} {incr j} {
   352    351         set gx [page_get $p1 $j]

Changes to test/pragma.test.

     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.
    12     12   #
    13     13   # This file implements tests for the PRAGMA command.
    14     14   #
    15         -# $Id: pragma.test,v 1.70 2008/11/21 00:10:35 aswift Exp $
           15  +# $Id: pragma.test,v 1.71 2008/12/30 17:55:00 drh Exp $
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # Test organization:
    21     21   #
    22     22   # pragma-1.*: Test cache_size, default_cache_size and synchronous on main db.
................................................................................
   566    566     do_test pragma-6.6.4 {
   567    567       execsql {
   568    568         PRAGMA main.table_info(trial);
   569    569       }
   570    570     } {0 col_main {} 0 {} 0}
   571    571   }
   572    572   
   573         -breakpoint
   574    573   do_test pragma-6.7 {
   575    574     execsql {
   576    575       CREATE TABLE test_table(
   577    576         one INT NOT NULL DEFAULT -1, 
   578    577         two text,
   579    578         three VARCHAR(45, 65) DEFAULT 'abcde',
   580    579         four REAL DEFAULT X'abcdef',

Changes to test/where7.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing the multi-index OR clause optimizer.
    13     13   #
    14         -# $Id: where7.test,v 1.5 2008/12/30 14:40:07 drh Exp $
           14  +# $Id: where7.test,v 1.6 2008/12/30 17:55:00 drh Exp $
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   
    19     19   ifcapable !or_opt {
    20     20     finish_test
    21     21     return
................................................................................
   101    101   } {1 2 3 5 scan 0 sort 0}
   102    102   do_test where7-1.13 {
   103    103     count_steps {
   104    104       SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
   105    105       ORDER BY a DESC
   106    106     }
   107    107   } {5 4 1 scan 0 sort 1}
          108  +
          109  +do_test where7-1.14 {
          110  +  count_steps {
          111  +    SELECT a FROM t1 WHERE (d=8 OR c=6 OR b=4) AND +a>0
          112  +  }
          113  +} {3 scan 4 sort 0}
          114  +do_test where7-1.15 {
          115  +  count_steps {
          116  +    SELECT a FROM t1 WHERE +a>=0 AND (d=8 OR c=6 OR b=4)
          117  +  }
          118  +} {3 scan 4 sort 0}
   108    119   
   109    120   do_test where7-1.20 {
   110    121     set sql "SELECT a FROM t1 WHERE a=11 OR b=11"
   111    122     for {set i 12} {$i<400} {incr i} {
   112    123       append sql " OR a=$i OR b=$i"
   113    124     }
   114    125     append sql " ORDER BY a"

Changes to test/where9.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing the multi-index OR clause optimizer.
    13     13   #
    14         -# $Id: where9.test,v 1.2 2008/12/30 16:35:53 drh Exp $
           14  +# $Id: where9.test,v 1.3 2008/12/30 17:55:00 drh Exp $
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   
    19     19   ifcapable !or_opt {
    20     20     finish_test
    21     21     return
................................................................................
   333    333       set a [expr {[lsearch $r {TABLE t2 VIA MULTI-INDEX UNION}]>=0}]
   334    334       set b [expr {[lsearch $r {TABLE t2 WITH INDEX t2f}]>=0}]
   335    335       set c [expr {([lsearch $r {TABLE t2 WITH INDEX t2c}]>=0)+
   336    336                     [lsearch $r {TABLE t2 WITH INDEX t2d}]>=0}]
   337    337       concat $a $b $c
   338    338     } {1 1 1}
   339    339   } 
          340  +
          341  +# Make sure that INDEXED BY and multi-index OR clauses play well with
          342  +# one another.
          343  +#
          344  +do_test where9-4.1 {
          345  +  count_steps {
          346  +    SELECT a FROM t1
          347  +     WHERE b>1000
          348  +       AND (c=31031 OR d IS NULL)
          349  +     ORDER BY +a
          350  +  }
          351  +} {92 93 97 scan 0 sort 1}
          352  +do_test where9-4.2 {
          353  +  count_steps {
          354  +    SELECT a FROM t1
          355  +     WHERE b>1000
          356  +       AND (c=31031 OR +d IS NULL)
          357  +     ORDER BY +a
          358  +  }
          359  +} {92 93 97 scan 0 sort 1}
          360  +do_test where9-4.3 {
          361  +  count_steps {
          362  +    SELECT a FROM t1
          363  +     WHERE +b>1000
          364  +       AND (c=31031 OR d IS NULL)
          365  +     ORDER BY +a
          366  +  }
          367  +} {92 93 97 scan 0 sort 1}
          368  +do_test where9-4.4 {
          369  +  count_steps {
          370  +    SELECT a FROM t1 INDEXED BY t1b
          371  +     WHERE b>1000
          372  +       AND (c=31031 OR d IS NULL)
          373  +     ORDER BY +a
          374  +  }
          375  +} {92 93 97 scan 0 sort 1}
          376  +do_test where9-4.5 {
          377  +  catchsql {
          378  +    SELECT a FROM t1 INDEXED BY t1b
          379  +     WHERE +b>1000
          380  +       AND (c=31031 OR d IS NULL)
          381  +     ORDER BY +a
          382  +  }
          383  +} {1 {cannot use index: t1b}}
          384  +do_test where9-4.6 {
          385  +  count_steps {
          386  +    SELECT a FROM t1 NOT INDEXED
          387  +     WHERE b>1000
          388  +       AND (c=31031 OR d IS NULL)
          389  +     ORDER BY +a
          390  +  }
          391  +} {92 93 97 scan 98 sort 1}
          392  +do_test where9-4.7 {
          393  +  catchsql {
          394  +    SELECT a FROM t1 INDEXED BY t1c
          395  +     WHERE b>1000
          396  +       AND (c=31031 OR d IS NULL)
          397  +     ORDER BY +a
          398  +  }
          399  +} {1 {cannot use index: t1c}}
          400  +do_test where9-4.8 {
          401  +  catchsql {
          402  +    SELECT a FROM t1 INDEXED BY t1d
          403  +     WHERE b>1000
          404  +       AND (c=31031 OR d IS NULL)
          405  +     ORDER BY +a
          406  +  }
          407  +} {1 {cannot use index: t1d}}
          408  +
          409  +ifcapable explain {
          410  +  # The (c=31031 OR d IS NULL) clause is preferred over b>1000 because
          411  +  # the former is an equality test which is expected to return fewer rows.
          412  +  #
          413  +  do_test where9-5.1 {
          414  +    set r [db eval {
          415  +      EXPLAIN QUERY PLAN
          416  +      SELECT a FROM t1
          417  +       WHERE b>1000
          418  +         AND (c=31031 OR d IS NULL)
          419  +    }]
          420  +    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
          421  +    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
          422  +    concat $a $b
          423  +  } {1 0}
          424  +
          425  +  # In contrast, b=1000 is preferred over any OR-clause.
          426  +  #
          427  +  do_test where9-5.2 {
          428  +    set r [db eval {
          429  +      EXPLAIN QUERY PLAN
          430  +      SELECT a FROM t1
          431  +       WHERE b=1000
          432  +         AND (c=31031 OR d IS NULL)
          433  +    }]
          434  +    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
          435  +    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
          436  +    concat $a $b
          437  +  } {0 1}
          438  +
          439  +  # Likewise, inequalities in an AND are preferred over inequalities in
          440  +  # an OR.
          441  +  #
          442  +  do_test where9-5.3 {
          443  +    set r [db eval {
          444  +      EXPLAIN QUERY PLAN
          445  +      SELECT a FROM t1
          446  +       WHERE b>1000
          447  +         AND (c>=31031 OR d IS NULL)
          448  +    }]
          449  +    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
          450  +    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
          451  +    concat $a $b
          452  +  } {0 1}
          453  +}
   340    454   
   341    455   finish_test