** 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.354 2008/12/30 16:18:48 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  /* Search for an OR-clause that can be used to look up the table.
  */
  maskSrc = getMask(pWC->pMaskSet, iCur);
  for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    WhereClause tempWC;
    tempWC = *pWC;
    tempWC.nSlot = 1;
    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;
      double nRow = 0;
      for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
        WhereCost sTermCost;

        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;

          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        if( sTermCost.plan.wsFlags==0 ){
          rTotal = pCost->rCost;
          break;
        }
        rTotal += sTermCost.rCost;
        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)

** 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.355 2008/12/30 17:55:00 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  /* Search for an OR-clause that can be used to look up the table.
  */
  maskSrc = getMask(pWC->pMaskSet, iCur);
  for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    WhereClause tempWC;
    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;
      double 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, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        if( sTermCost.plan.wsFlags==0 ){
          rTotal = pCost->rCost;
          break;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
      }
      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)

#    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 script testing the callback-free C/C++ API.
#
# $Id: capi2.test,v 1.36 2008/09/01 15:52:11 drh Exp $
#

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

# Return the text values from the current row pointed at by STMT as a list.
proc get_row_values {STMT} {
................................................................................
  do_test capi2-12.3 {
    check_origins {SELECT col2 AS hello, col1 AS world FROM view1}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.4 {
    check_origins {SELECT b, a FROM (SELECT col1 AS a, col2 AS b FROM view1)}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.5 {
breakpoint
    check_origins {SELECT (SELECT col2 FROM view1), (SELECT col1 FROM view1)}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.6 {
    check_origins {SELECT (SELECT col2), (SELECT col1) FROM view1}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.7 {
    check_origins {SELECT * FROM view1}

#    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 script testing the callback-free C/C++ API.
#
# $Id: capi2.test,v 1.37 2008/12/30 17:55:00 drh Exp $
#

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

# Return the text values from the current row pointed at by STMT as a list.
proc get_row_values {STMT} {
................................................................................
  do_test capi2-12.3 {
    check_origins {SELECT col2 AS hello, col1 AS world FROM view1}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.4 {
    check_origins {SELECT b, a FROM (SELECT col1 AS a, col2 AS b FROM view1)}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.5 {

    check_origins {SELECT (SELECT col2 FROM view1), (SELECT col1 FROM view1)}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.6 {
    check_origins {SELECT (SELECT col2), (SELECT col1) FROM view1}
  } [list {main tab1 col2} {main tab1 col1}]
  do_test capi2-12.7 {
    check_origins {SELECT * FROM view1}

#    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 expressions.
#
# $Id: expr.test,v 1.65 2008/08/22 16:29:51 drh Exp $

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

# Create a table to work with.
#
execsql {CREATE TABLE test1(i1 int, i2 int, r1 real, r2 real, t1 text, t2 text)}
................................................................................
test_expr2 expr-7.58  {(a||'')<='1'}                  {1}

test_expr2 expr-7.59 {LIKE('10%',b)}                  {10 20}
test_expr2 expr-7.60 {LIKE('_4',b)}                   {6}
test_expr2 expr-7.61 {GLOB('1?',a)}            {10 11 12 13 14 15 16 17 18 19}
test_expr2 expr-7.62 {GLOB('1*4',b)}                  {10 14}
test_expr2 expr-7.63 {GLOB('*1[456]',b)}              {4}

breakpoint
test_expr2 expr-7.64 {b = abs(-2)}                    {1}
test_expr2 expr-7.65 {b = abs(+-2)}                   {1}
test_expr2 expr-7.66 {b = abs(++-2)}                  {1}
test_expr2 expr-7.67 {b = abs(+-+-2)}                 {1}
test_expr2 expr-7.68 {b = abs(+-++-2)}                {1}
test_expr2 expr-7.69 {b = abs(++++-2)}                {1}
test_expr2 expr-7.70 {b = 5 - abs(+3)}                {1}

#    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 expressions.
#
# $Id: expr.test,v 1.66 2008/12/30 17:55:00 drh Exp $

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

# Create a table to work with.
#
execsql {CREATE TABLE test1(i1 int, i2 int, r1 real, r2 real, t1 text, t2 text)}
................................................................................
test_expr2 expr-7.58  {(a||'')<='1'}                  {1}

test_expr2 expr-7.59 {LIKE('10%',b)}                  {10 20}
test_expr2 expr-7.60 {LIKE('_4',b)}                   {6}
test_expr2 expr-7.61 {GLOB('1?',a)}            {10 11 12 13 14 15 16 17 18 19}
test_expr2 expr-7.62 {GLOB('1*4',b)}                  {10 14}
test_expr2 expr-7.63 {GLOB('*1[456]',b)}              {4}


test_expr2 expr-7.64 {b = abs(-2)}                    {1}
test_expr2 expr-7.65 {b = abs(+-2)}                   {1}
test_expr2 expr-7.66 {b = abs(++-2)}                  {1}
test_expr2 expr-7.67 {b = abs(+-+-2)}                 {1}
test_expr2 expr-7.68 {b = abs(+-++-2)}                {1}
test_expr2 expr-7.69 {b = abs(++++-2)}                {1}
test_expr2 expr-7.70 {b = 5 - abs(+3)}                {1}

#
# Prior to version 3.6.2, calling sqlite3_release_memory() or exceeding
# the configured soft heap limit could cause sqlite to upgrade database 
# locks and flush dirty pages to the file system. As of 3.6.2, this is
# no longer the case. In version 3.6.2, sqlite3_release_memory() only
# reclaims clean pages. This test file has been updated accordingly.
#
# $Id: malloc5.test,v 1.20 2008/08/27 16:38:57 danielk1977 Exp $

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

# Only run these tests if memory debugging is turned on.
................................................................................
    [expr ([file size test.db]/1024)>20] [expr ([file size test2.db]/1024)>20]
} {1 1}
do_test malloc5-6.1.2 {
  list [execsql {PRAGMA cache_size}] [execsql {PRAGMA cache_size} db2]
} {10 10}

do_test malloc5-6.2.1 {
breakpoint
  execsql {SELECT * FROM abc} db2
  execsql {SELECT * FROM abc} db
  expr [nPage db] + [nPage db2]
} {20}

do_test malloc5-6.2.2 {
  # If we now try to reclaim some memory, it should come from the db2 cache.

#
# Prior to version 3.6.2, calling sqlite3_release_memory() or exceeding
# the configured soft heap limit could cause sqlite to upgrade database 
# locks and flush dirty pages to the file system. As of 3.6.2, this is
# no longer the case. In version 3.6.2, sqlite3_release_memory() only
# reclaims clean pages. This test file has been updated accordingly.
#
# $Id: malloc5.test,v 1.21 2008/12/30 17:55:00 drh Exp $

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

# Only run these tests if memory debugging is turned on.
................................................................................
    [expr ([file size test.db]/1024)>20] [expr ([file size test2.db]/1024)>20]
} {1 1}
do_test malloc5-6.1.2 {
  list [execsql {PRAGMA cache_size}] [execsql {PRAGMA cache_size} db2]
} {10 10}

do_test malloc5-6.2.1 {

  execsql {SELECT * FROM abc} db2
  execsql {SELECT * FROM abc} db
  expr [nPage db] + [nPage db2]
} {20}

do_test malloc5-6.2.2 {
  # If we now try to reclaim some memory, it should come from the db2 cache.

#    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 script is page cache subsystem.
#
# $Id: pager2.test,v 1.8 2008/10/17 18:51:53 danielk1977 Exp $


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

# Don't run this test file if the pager test interface [pager_open] is not
# available, or the library was compiled without in-memory database support.
................................................................................
      set shouldbe "Page-$j v[expr {$i-1}]"
      if {$value!=$shouldbe} {
        lappend res $value $shouldbe
      }
    }
    set res
  } {}
breakpoint
  do_test pager2-4.5.$i.5 {
    page_write $g1 "Page-1 v$i"
    lrange [pager_stats $p1] 8 9
  } {state 4}
  do_test pager2-4.5.$i.6 {
    for {set j 2} {$j<=20} {incr j} {
      set gx [page_get $p1 $j]

#    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 script is page cache subsystem.
#
# $Id: pager2.test,v 1.9 2008/12/30 17:55:00 drh Exp $


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

# Don't run this test file if the pager test interface [pager_open] is not
# available, or the library was compiled without in-memory database support.
................................................................................
      set shouldbe "Page-$j v[expr {$i-1}]"
      if {$value!=$shouldbe} {
        lappend res $value $shouldbe
      }
    }
    set res
  } {}

  do_test pager2-4.5.$i.5 {
    page_write $g1 "Page-1 v$i"
    lrange [pager_stats $p1] 8 9
  } {state 4}
  do_test pager2-4.5.$i.6 {
    for {set j 2} {$j<=20} {incr j} {
      set gx [page_get $p1 $j]

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for the PRAGMA command.
#
# $Id: pragma.test,v 1.70 2008/11/21 00:10:35 aswift Exp $

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

# Test organization:
#
# pragma-1.*: Test cache_size, default_cache_size and synchronous on main db.
................................................................................
  do_test pragma-6.6.4 {
    execsql {
      PRAGMA main.table_info(trial);
    }
  } {0 col_main {} 0 {} 0}
}

breakpoint
do_test pragma-6.7 {
  execsql {
    CREATE TABLE test_table(
      one INT NOT NULL DEFAULT -1, 
      two text,
      three VARCHAR(45, 65) DEFAULT 'abcde',
      four REAL DEFAULT X'abcdef',

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for the PRAGMA command.
#
# $Id: pragma.test,v 1.71 2008/12/30 17:55:00 drh Exp $

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

# Test organization:
#
# pragma-1.*: Test cache_size, default_cache_size and synchronous on main db.
................................................................................
  do_test pragma-6.6.4 {
    execsql {
      PRAGMA main.table_info(trial);
    }
  } {0 col_main {} 0 {} 0}
}


do_test pragma-6.7 {
  execsql {
    CREATE TABLE test_table(
      one INT NOT NULL DEFAULT -1, 
      two text,
      three VARCHAR(45, 65) DEFAULT 'abcde',
      four REAL DEFAULT X'abcdef',

#    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.5 2008/12/30 14:40:07 drh Exp $

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

ifcapable !or_opt {
  finish_test
  return
................................................................................
} {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.20 {
  set sql "SELECT a FROM t1 WHERE a=11 OR b=11"
  for {set i 12} {$i<400} {incr i} {
    append sql " OR a=$i OR b=$i"
  }
  append sql " ORDER BY a"

#    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
................................................................................
} {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
  }
} {3 scan 4 sort 0}
do_test where7-1.15 {
  count_steps {
    SELECT a FROM t1 WHERE +a>=0 AND (d=8 OR c=6 OR b=4)
  }
} {3 scan 4 sort 0}

do_test where7-1.20 {
  set sql "SELECT a FROM t1 WHERE a=11 OR b=11"
  for {set i 12} {$i<400} {incr i} {
    append sql " OR a=$i OR b=$i"
  }
  append sql " ORDER BY a"

#    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: where9.test,v 1.2 2008/12/30 16:35:53 drh Exp $

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

ifcapable !or_opt {
  finish_test
  return
................................................................................
    set a [expr {[lsearch $r {TABLE t2 VIA MULTI-INDEX UNION}]>=0}]
    set b [expr {[lsearch $r {TABLE t2 WITH INDEX t2f}]>=0}]
    set c [expr {([lsearch $r {TABLE t2 WITH INDEX t2c}]>=0)+
                  [lsearch $r {TABLE t2 WITH INDEX t2d}]>=0}]
    concat $a $b $c
  } {1 1 1}
} 



















































































































finish_test

#    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: where9.test,v 1.3 2008/12/30 17:55:00 drh Exp $

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

ifcapable !or_opt {
  finish_test
  return
................................................................................
    set a [expr {[lsearch $r {TABLE t2 VIA MULTI-INDEX UNION}]>=0}]
    set b [expr {[lsearch $r {TABLE t2 WITH INDEX t2f}]>=0}]
    set c [expr {([lsearch $r {TABLE t2 WITH INDEX t2c}]>=0)+
                  [lsearch $r {TABLE t2 WITH INDEX t2d}]>=0}]
    concat $a $b $c
  } {1 1 1}
} 

# Make sure that INDEXED BY and multi-index OR clauses play well with
# one another.
#
do_test where9-4.1 {
  count_steps {
    SELECT a FROM t1
     WHERE b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {92 93 97 scan 0 sort 1}
do_test where9-4.2 {
  count_steps {
    SELECT a FROM t1
     WHERE b>1000
       AND (c=31031 OR +d IS NULL)
     ORDER BY +a
  }
} {92 93 97 scan 0 sort 1}
do_test where9-4.3 {
  count_steps {
    SELECT a FROM t1
     WHERE +b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {92 93 97 scan 0 sort 1}
do_test where9-4.4 {
  count_steps {
    SELECT a FROM t1 INDEXED BY t1b
     WHERE b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {92 93 97 scan 0 sort 1}
do_test where9-4.5 {
  catchsql {
    SELECT a FROM t1 INDEXED BY t1b
     WHERE +b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {1 {cannot use index: t1b}}
do_test where9-4.6 {
  count_steps {
    SELECT a FROM t1 NOT INDEXED
     WHERE b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {92 93 97 scan 98 sort 1}
do_test where9-4.7 {
  catchsql {
    SELECT a FROM t1 INDEXED BY t1c
     WHERE b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {1 {cannot use index: t1c}}
do_test where9-4.8 {
  catchsql {
    SELECT a FROM t1 INDEXED BY t1d
     WHERE b>1000
       AND (c=31031 OR d IS NULL)
     ORDER BY +a
  }
} {1 {cannot use index: t1d}}

ifcapable explain {
  # The (c=31031 OR d IS NULL) clause is preferred over b>1000 because
  # the former is an equality test which is expected to return fewer rows.
  #
  do_test where9-5.1 {
    set r [db eval {
      EXPLAIN QUERY PLAN
      SELECT a FROM t1
       WHERE b>1000
         AND (c=31031 OR d IS NULL)
    }]
    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
    concat $a $b
  } {1 0}

  # In contrast, b=1000 is preferred over any OR-clause.
  #
  do_test where9-5.2 {
    set r [db eval {
      EXPLAIN QUERY PLAN
      SELECT a FROM t1
       WHERE b=1000
         AND (c=31031 OR d IS NULL)
    }]
    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
    concat $a $b
  } {0 1}

  # Likewise, inequalities in an AND are preferred over inequalities in
  # an OR.
  #
  do_test where9-5.3 {
    set r [db eval {
      EXPLAIN QUERY PLAN
      SELECT a FROM t1
       WHERE b>1000
         AND (c>=31031 OR d IS NULL)
    }]
    set a [expr {[lsearch $r {TABLE t1 VIA MULTI-INDEX UNION}]>=0}]
    set b [expr {[lsearch $r {TABLE t1 WITH INDEX t1b}]>=0}]
    concat $a $b
  } {0 1}
}

finish_test