** 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.353 2008/12/30 15:26:30 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
      zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
      if( pItem->zAlias ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
      }
      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
           zMsg, pLevel->plan.u.pIdx->zName);


      }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
        sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
        zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,

** 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)
................................................................................
      zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
      if( pItem->zAlias ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
      }
      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
           zMsg, pLevel->plan.u.pIdx->zName);
      }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg);
      }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
        sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
        zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,

# 2008 December 30
#
# 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: where9.test,v 1.1 2008/12/30 16:18:48 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]
}


# Construct test data.  
# 
do_test where9-1.1 {
  db eval {
    CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d,e,f,g);
    INSERT INTO t1 VALUES(1,11,1001,1.001,100.1,'bcdefghij','yxwvuts');
    INSERT INTO t1 VALUES(2,22,1001,2.002,100.1,'cdefghijk','yxwvuts');
    INSERT INTO t1 VALUES(3,33,1001,3.003,100.1,'defghijkl','xwvutsr');
    INSERT INTO t1 VALUES(4,44,2002,4.004,200.2,'efghijklm','xwvutsr');
    INSERT INTO t1 VALUES(5,55,2002,5.005,200.2,'fghijklmn','xwvutsr');
    INSERT INTO t1 VALUES(6,66,2002,6.006,200.2,'ghijklmno','xwvutsr');
    INSERT INTO t1 VALUES(7,77,3003,7.007,300.3,'hijklmnop','xwvutsr');
    INSERT INTO t1 VALUES(8,88,3003,8.008,300.3,'ijklmnopq','wvutsrq');
    INSERT INTO t1 VALUES(9,99,3003,9.009,300.3,'jklmnopqr','wvutsrq');
    INSERT INTO t1 VALUES(10,110,4004,10.01,400.4,'klmnopqrs','wvutsrq');
    INSERT INTO t1 VALUES(11,121,4004,11.011,400.4,'lmnopqrst','wvutsrq');
    INSERT INTO t1 VALUES(12,132,4004,12.012,400.4,'mnopqrstu','wvutsrq');
    INSERT INTO t1 VALUES(13,143,5005,13.013,500.5,'nopqrstuv','vutsrqp');
    INSERT INTO t1 VALUES(14,154,5005,14.014,500.5,'opqrstuvw','vutsrqp');
    INSERT INTO t1 VALUES(15,165,5005,15.015,500.5,'pqrstuvwx','vutsrqp');
    INSERT INTO t1 VALUES(16,176,6006,16.016,600.6,'qrstuvwxy','vutsrqp');
    INSERT INTO t1 VALUES(17,187,6006,17.017,600.6,'rstuvwxyz','vutsrqp');
    INSERT INTO t1 VALUES(18,198,6006,18.018,600.6,'stuvwxyza','utsrqpo');
    INSERT INTO t1 VALUES(19,209,7007,19.019,700.7,'tuvwxyzab','utsrqpo');
    INSERT INTO t1 VALUES(20,220,7007,20.02,700.7,'uvwxyzabc','utsrqpo');
    INSERT INTO t1 VALUES(21,231,7007,21.021,700.7,'vwxyzabcd','utsrqpo');
    INSERT INTO t1 VALUES(22,242,8008,22.022,800.8,'wxyzabcde','utsrqpo');
    INSERT INTO t1 VALUES(23,253,8008,23.023,800.8,'xyzabcdef','tsrqpon');
    INSERT INTO t1 VALUES(24,264,8008,24.024,800.8,'yzabcdefg','tsrqpon');
    INSERT INTO t1 VALUES(25,275,9009,25.025,900.9,'zabcdefgh','tsrqpon');
    INSERT INTO t1 VALUES(26,286,9009,26.026,900.9,'abcdefghi','tsrqpon');
    INSERT INTO t1 VALUES(27,297,9009,27.027,900.9,'bcdefghij','tsrqpon');
    INSERT INTO t1 VALUES(28,308,10010,28.028,1001.0,'cdefghijk','srqponm');
    INSERT INTO t1 VALUES(29,319,10010,29.029,1001.0,'defghijkl','srqponm');
    INSERT INTO t1 VALUES(30,330,10010,30.03,1001.0,'efghijklm','srqponm');
    INSERT INTO t1 VALUES(31,341,11011,31.031,1101.1,'fghijklmn','srqponm');
    INSERT INTO t1 VALUES(32,352,11011,32.032,1101.1,'ghijklmno','srqponm');
    INSERT INTO t1 VALUES(33,363,11011,33.033,1101.1,'hijklmnop','rqponml');
    INSERT INTO t1 VALUES(34,374,12012,34.034,1201.2,'ijklmnopq','rqponml');
    INSERT INTO t1 VALUES(35,385,12012,35.035,1201.2,'jklmnopqr','rqponml');
    INSERT INTO t1 VALUES(36,396,12012,36.036,1201.2,'klmnopqrs','rqponml');
    INSERT INTO t1 VALUES(37,407,13013,37.037,1301.3,'lmnopqrst','rqponml');
    INSERT INTO t1 VALUES(38,418,13013,38.038,1301.3,'mnopqrstu','qponmlk');
    INSERT INTO t1 VALUES(39,429,13013,39.039,1301.3,'nopqrstuv','qponmlk');
    INSERT INTO t1 VALUES(40,440,14014,40.04,1401.4,'opqrstuvw','qponmlk');
    INSERT INTO t1 VALUES(41,451,14014,41.041,1401.4,'pqrstuvwx','qponmlk');
    INSERT INTO t1 VALUES(42,462,14014,42.042,1401.4,'qrstuvwxy','qponmlk');
    INSERT INTO t1 VALUES(43,473,15015,43.043,1501.5,'rstuvwxyz','ponmlkj');
    INSERT INTO t1 VALUES(44,484,15015,44.044,1501.5,'stuvwxyza','ponmlkj');
    INSERT INTO t1 VALUES(45,495,15015,45.045,1501.5,'tuvwxyzab','ponmlkj');
    INSERT INTO t1 VALUES(46,506,16016,46.046,1601.6,'uvwxyzabc','ponmlkj');
    INSERT INTO t1 VALUES(47,517,16016,47.047,1601.6,'vwxyzabcd','ponmlkj');
    INSERT INTO t1 VALUES(48,528,16016,48.048,1601.6,'wxyzabcde','onmlkji');
    INSERT INTO t1 VALUES(49,539,17017,49.049,1701.7,'xyzabcdef','onmlkji');
    INSERT INTO t1 VALUES(50,550,17017,50.05,1701.7,'yzabcdefg','onmlkji');
    INSERT INTO t1 VALUES(51,561,17017,51.051,1701.7,'zabcdefgh','onmlkji');
    INSERT INTO t1 VALUES(52,572,18018,52.052,1801.8,'abcdefghi','onmlkji');
    INSERT INTO t1 VALUES(53,583,18018,53.053,1801.8,'bcdefghij','nmlkjih');
    INSERT INTO t1 VALUES(54,594,18018,54.054,1801.8,'cdefghijk','nmlkjih');
    INSERT INTO t1 VALUES(55,605,19019,55.055,1901.9,'defghijkl','nmlkjih');
    INSERT INTO t1 VALUES(56,616,19019,56.056,1901.9,'efghijklm','nmlkjih');
    INSERT INTO t1 VALUES(57,627,19019,57.057,1901.9,'fghijklmn','nmlkjih');
    INSERT INTO t1 VALUES(58,638,20020,58.058,2002.0,'ghijklmno','mlkjihg');
    INSERT INTO t1 VALUES(59,649,20020,59.059,2002.0,'hijklmnop','mlkjihg');
    INSERT INTO t1 VALUES(60,660,20020,60.06,2002.0,'ijklmnopq','mlkjihg');
    INSERT INTO t1 VALUES(61,671,21021,61.061,2102.1,'jklmnopqr','mlkjihg');
    INSERT INTO t1 VALUES(62,682,21021,62.062,2102.1,'klmnopqrs','mlkjihg');
    INSERT INTO t1 VALUES(63,693,21021,63.063,2102.1,'lmnopqrst','lkjihgf');
    INSERT INTO t1 VALUES(64,704,22022,64.064,2202.2,'mnopqrstu','lkjihgf');
    INSERT INTO t1 VALUES(65,715,22022,65.065,2202.2,'nopqrstuv','lkjihgf');
    INSERT INTO t1 VALUES(66,726,22022,66.066,2202.2,'opqrstuvw','lkjihgf');
    INSERT INTO t1 VALUES(67,737,23023,67.067,2302.3,'pqrstuvwx','lkjihgf');
    INSERT INTO t1 VALUES(68,748,23023,68.068,2302.3,'qrstuvwxy','kjihgfe');
    INSERT INTO t1 VALUES(69,759,23023,69.069,2302.3,'rstuvwxyz','kjihgfe');
    INSERT INTO t1 VALUES(70,770,24024,70.07,2402.4,'stuvwxyza','kjihgfe');
    INSERT INTO t1 VALUES(71,781,24024,71.071,2402.4,'tuvwxyzab','kjihgfe');
    INSERT INTO t1 VALUES(72,792,24024,72.072,2402.4,'uvwxyzabc','kjihgfe');
    INSERT INTO t1 VALUES(73,803,25025,73.073,2502.5,'vwxyzabcd','jihgfed');
    INSERT INTO t1 VALUES(74,814,25025,74.074,2502.5,'wxyzabcde','jihgfed');
    INSERT INTO t1 VALUES(75,825,25025,75.075,2502.5,'xyzabcdef','jihgfed');
    INSERT INTO t1 VALUES(76,836,26026,76.076,2602.6,'yzabcdefg','jihgfed');
    INSERT INTO t1 VALUES(77,847,26026,77.077,2602.6,'zabcdefgh','jihgfed');
    INSERT INTO t1 VALUES(78,858,26026,78.078,2602.6,'abcdefghi','ihgfedc');
    INSERT INTO t1 VALUES(79,869,27027,79.079,2702.7,'bcdefghij','ihgfedc');
    INSERT INTO t1 VALUES(80,880,27027,80.08,2702.7,'cdefghijk','ihgfedc');
    INSERT INTO t1 VALUES(81,891,27027,81.081,2702.7,'defghijkl','ihgfedc');
    INSERT INTO t1 VALUES(82,902,28028,82.082,2802.8,'efghijklm','ihgfedc');
    INSERT INTO t1 VALUES(83,913,28028,83.083,2802.8,'fghijklmn','hgfedcb');
    INSERT INTO t1 VALUES(84,924,28028,84.084,2802.8,'ghijklmno','hgfedcb');
    INSERT INTO t1 VALUES(85,935,29029,85.085,2902.9,'hijklmnop','hgfedcb');
    INSERT INTO t1 VALUES(86,946,29029,86.086,2902.9,'ijklmnopq','hgfedcb');
    INSERT INTO t1 VALUES(87,957,29029,87.087,2902.9,'jklmnopqr','hgfedcb');
    INSERT INTO t1 VALUES(88,968,30030,88.088,3003.0,'klmnopqrs','gfedcba');
    INSERT INTO t1 VALUES(89,979,30030,89.089,3003.0,'lmnopqrst','gfedcba');
    INSERT INTO t1 VALUES(90,NULL,30030,90.09,3003.0,'mnopqrstu','gfedcba');
    INSERT INTO t1 VALUES(91,1001,NULL,91.091,3103.1,'nopqrstuv','gfedcba');
    INSERT INTO t1 VALUES(92,1012,31031,NULL,3103.1,'opqrstuvw','gfedcba');
    INSERT INTO t1 VALUES(93,1023,31031,93.093,NULL,'pqrstuvwx','fedcbaz');
    INSERT INTO t1 VALUES(94,1034,32032,94.094,3203.2,NULL,'fedcbaz');
    INSERT INTO t1 VALUES(95,1045,32032,95.095,3203.2,'rstuvwxyz',NULL);
    INSERT INTO t1 VALUES(96,NULL,NULL,96.096,3203.2,'stuvwxyza','fedcbaz');
    INSERT INTO t1 VALUES(97,1067,33033,NULL,NULL,'tuvwxyzab','fedcbaz');
    INSERT INTO t1 VALUES(98,1078,33033,98.098,3303.3,NULL,NULL);
    INSERT INTO t1 VALUES(99,NULL,NULL,NULL,NULL,NULL,NULL);
    CREATE INDEX t1b ON t1(b);
    CREATE INDEX t1c ON t1(c);
    CREATE INDEX t1d ON t1(d);
    CREATE INDEX t1e ON t1(e);
    CREATE INDEX t1f ON t1(f);
    CREATE INDEX t1g ON t1(g);
    CREATE TABLE t2(a INTEGER PRIMARY KEY,b,c,d,e,f,g);
    INSERT INTO t2 SELECT * FROM t1;
    CREATE INDEX t2b ON t2(b,c);
    CREATE INDEX t2c ON t2(c,e);
    CREATE INDEX t2d ON t2(d,g);
    CREATE INDEX t2e ON t2(e,f,g);
    CREATE INDEX t2f ON t2(f,b,d,c);
    CREATE INDEX t2g ON t2(g,f);
  }
} {}

do_test where9-1.2.1 {
  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 0 sort 0}
do_test where9-1.2.2 {
  count_steps {
    SELECT a FROM t1
     WHERE +b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 98 sort 0}
do_test where9-1.2.3 {
  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR +c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 98 sort 0}
do_test where9-1.2.4 {
  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR c IS NULL
        OR +d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 98 sort 0}
do_test where9-1.3 {
  count_steps {
    SELECT a FROM t1
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
  }
} {90 91 92 97 scan 0 sort 0}
do_test where9-1.4 {
  count_steps {
    SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
    ORDER BY a
  }
} {87 88 89 90 91 scan 0 sort 0}
do_test where9-1.5 {
  count_steps {
    SELECT a FROM t1
     WHERE a=83
        OR b=913
        OR c=28028
        OR (d>=82 AND d<83)
        OR (e>2802 AND e<2803) 
        OR f='fghijklmn'
        OR g='hgfedcb'
    ORDER BY a
  }
} {5 31 57 82 83 84 85 86 87 scan 0 sort 0}
do_test where9-1.6 {
  count_steps {
    SELECT a FROM t1
     WHERE b=1012
        OR (d IS NULL AND e IS NOT NULL)
  }
} {92 scan 0 sort 0}
do_test where9-1.7 {
  count_steps {
    SELECT a FROM t1
     WHERE (b=1012 OR (d IS NULL AND e IS NOT NULL))
       AND f!=g
  }
} {92 scan 0 sort 0}
do_test where9-1.8 {
  count_steps {
    SELECT a FROM t1
     WHERE (b=1012 OR (d IS NULL AND e IS NOT NULL))
       AND f==g
  }
} {scan 0 sort 0}

do_test where9-2.1 {
  count_steps {
    SELECT t2.a FROM t1, t2
     WHERE t1.a=80
       AND (t1.c=t2.c OR t1.d=t2.d)
    ORDER BY 1
  }
} {79 80 81 scan 0 sort 1}
do_test where9-2.2 {
  count_steps {
    SELECT t2.a FROM t1, t2
     WHERE t1.a=80
       AND ((t1.c=t2.c AND t1.d=t2.d) OR t1.f=t2.f)
    ORDER BY 1
  }
} {2 28 54 80 scan 0 sort 1}
do_test where9-2.3 {
  count_steps {
    SELECT coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR t1.f=t2.f
     WHERE t1.a=80
    ORDER BY 1
  }
} {2 28 54 80 scan 0 sort 1}
do_test where9-2.4 {
  count_steps {
    SELECT coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=80
    ORDER BY 1
  }
} {9999 scan 0 sort 1}


ifcapable explain {
  do_test where9-3.1 {
    set r [db eval {
      EXPLAIN QUERY PLAN
      SELECT t2.a FROM t1, t2
       WHERE t1.a=80
         AND ((t1.c=t2.c AND t1.d=t2.d) OR t1.f=t2.f)
    }]
    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}
  do_test where9-3.2 {
    set r [db eval {
      EXPLAIN QUERY PLAN
      SELECT coalesce(t2.a,9999)
        FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
       WHERE t1.a=80
    }]
    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