SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.428 2008/04/17 19:14:02 drh Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.

** for helping to understand what is happening inside the code generator
** during the execution of complex SELECT statements.
**
** These routine are not called anywhere from within the normal
** code base.  Then are intended to be called from within the debugger
** or from temporary "printf" statements inserted for debugging.
*/
void sqlite3PrintExpr(Expr *p){
  if( p->token.z && p->token.n>0 ){
    sqlite3DebugPrintf("(%.*s", p->token.n, p->token.z);
  }else{
    sqlite3DebugPrintf("(%d", p->op);
  }
  if( p->pLeft ){
    sqlite3DebugPrintf(" ");
    sqlite3PrintExpr(p->pLeft);
  }
  if( p->pRight ){
    sqlite3DebugPrintf(" ");
    sqlite3PrintExpr(p->pRight);
  }
  sqlite3DebugPrintf(")");
}
void sqlite3PrintExprList(ExprList *pList){
  int i;
  for(i=0; i<pList->nExpr; i++){
    sqlite3PrintExpr(pList->a[i].pExpr);
    if( i<pList->nExpr-1 ){
      sqlite3DebugPrintf(", ");
    }
  }
}
void sqlite3PrintSelect(Select *p, int indent){
  sqlite3DebugPrintf("%*sSELECT(%p) ", indent, "", p);
  sqlite3PrintExprList(p->pEList);
  sqlite3DebugPrintf("\n");
  if( p->pSrc ){
    char *zPrefix;
    int i;
    zPrefix = "FROM";

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.299 2008/04/17 19:14:02 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

  int idxTerm               /* Index of the term to be analyzed */
){
  WhereTerm *pTerm;
  ExprMaskSet *pMaskSet;
  Expr *pExpr;
  Bitmask prereqLeft;
  Bitmask prereqAll;
  Bitmask extraRight = 0;
  int nPattern;
  int isComplete;
  int noCase;
  int op;
  Parse *pParse = pWC->pParse;
  sqlite3 *db = pParse->db;

  }else{
    pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
  }
  prereqAll = exprTableUsage(pMaskSet, pExpr);
  if( ExprHasProperty(pExpr, EP_FromJoin) ){
    Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
    prereqAll |= x;
    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;

      pTerm = &pWC->a[idxTerm];
      pTerm->nChild = 1;
      pTerm->flags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

/*
** Return TRUE if any of the expressions in pList->a[iFirst...] contain
** a reference to any table other than the iBase table.
*/
static int referencesOtherTables(

# 2001 September 15
#
# 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 some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.116 2008/04/17 19:14:02 drh Exp $

#
# What for user input before continuing.  This gives an opportunity
# to connect profiling tools to the process.
#
for {set i 0} {$i<[llength $argv]} {incr i} {
  if {[regexp {^-+pause$} [lindex $argv $i] all value]} {

  puts "----  ------------  ------  ------  ------  ---------------  --  -"
  $db eval "explain $sql" {} {
    puts [format {%-4d  %-12.12s  %-6d  %-6d  %-6d  % -17s %s  %s} \
      $addr $opcode $p1 $p2 $p3 $p4 $p5 $comment
    ]
  }
}

# Show the VDBE program for an SQL statement but omit the Trace
# opcode at the beginning.  This procedure can be used to prove
# that different SQL statements generate exactly the same VDBE code.
#
proc explain_no_trace {sql} {
  set tr [db eval "EXPLAIN $sql"]
  return [lrange $tr 7 end]
}

# Another procedure to execute SQL.  This one includes the field
# names in the returned list.
#
proc execsql2 {sql} {
  set result {}
  db eval $sql data {

#    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 join reordering optimization
# in cases that include a LEFT JOIN.
#
# $Id: where3.test,v 1.4 2008/04/17 19:14:02 drh Exp $

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

# The following is from ticket #1652.
#
# A comma join then a left outer join:  A,B left join C.

    
    INSERT INTO t3 VALUES(999,'nine');
    CREATE INDEX t3i1 ON t3(x);
    
    SELECT * FROM t1, t2 LEFT JOIN t3 ON q=x WHERE p=2 AND a=q;
  }
} {222 two 2 222 {} {}}

ifcapable explain {
  do_test where3-1.1.1 {
     explain_no_trace {SELECT * FROM t1, t2 LEFT JOIN t3 ON q=x
                        WHERE p=2 AND a=q}
  } [explain_no_trace {SELECT * FROM t1, t2 LEFT JOIN t3 ON x=q
                        WHERE p=2 AND a=q}]
}

# Ticket #1830
#
# This is similar to the above but with the LEFT JOIN on the
# other side.
#
do_test where3-1.2 {

    SELECT parent1.parent1key, child1.value, child2.value
    FROM parent1
    LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key
    INNER JOIN child2 ON child2.child2key = parent1.child2key;
  }
} {1 {Value for C1.1} {Value for C2.1} 2 {} {Value for C2.2} 3 {Value for C1.3} {Value for C2.3}}

ifcapable explain {
  do_test where3-1.2.1 {
     explain_no_trace {
       SELECT parent1.parent1key, child1.value, child2.value
       FROM parent1
       LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key
       INNER JOIN child2 ON child2.child2key = parent1.child2key;
     }
  } [explain_no_trace {
       SELECT parent1.parent1key, child1.value, child2.value
       FROM parent1
       LEFT OUTER JOIN child1 ON parent1.child1key = child1.child1key 
       INNER JOIN child2 ON child2.child2key = parent1.child2key;
     }]
}

# This procedure executes the SQL.  Then it appends 
# the ::sqlite_query_plan variable.
#
proc queryplan {sql} {
  set ::sqlite_sort_count 0
  set data [execsql $sql]

    CREATE TABLE tC(cpk integer primary key, cx);
    CREATE TABLE tD(dpk integer primary key, dx);
  }
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND bpk=ax
  }
} {tA {} tB * tC * tD *}
do_test where3-2.1.1 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON cx=dpk
     WHERE cpk=bx AND bpk=ax
  }
} {tA {} tB * tC * tD *}
do_test where3-2.1.2 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON cx=dpk
     WHERE bx=cpk AND bpk=ax
  }
} {tA {} tB * tC * tD *}
do_test where3-2.1.3 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON cx=dpk
     WHERE bx=cpk AND ax=bpk
  }
} {tA {} tB * tC * tD *}
do_test where3-2.1.4 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE bx=cpk AND ax=bpk
  }
} {tA {} tB * tC * tD *}
do_test where3-2.1.5 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND ax=bpk
  }
} {tA {} tB * tC * tD *}
do_test where3-2.2 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND apk=bx
  }
} {tB {} tA * tC * tD *}

#    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 that terms in the ON clause of
# a LEFT OUTER JOIN are not used with indices.  See ticket #3015.
#
# $Id: where6.test,v 1.2 2008/04/17 19:14:02 drh Exp $

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

# Build some test data
#
do_test where6-1.1 {
  execsql {
    CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c);
    INSERT INTO t1 VALUES(1,3,1);
    INSERT INTO t1 VALUES(2,4,2);
    CREATE TABLE t2(x INTEGER PRIMARY KEY);
    INSERT INTO t2 VALUES(3);

    SELECT * FROM t1 LEFT JOIN t2 ON b=x AND c=1;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-1.2 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b AND c=1;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-1.3 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b AND 1=c;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-1.4 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x AND 1=c;
  }
} {1 3 1 3 2 4 2 {}}

ifcapable explain {
  do_test where6-1.5 {
     explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON x=b AND 1=c}
  } [explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON b=x AND c=1}]
  do_test where6-1.6 {
     explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON x=b WHERE 1=c}
  } [explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE c=1}]
}

do_test where6-1.11 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE c=1;
  }
} {1 3 1 3}
do_test where6-1.12 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b WHERE c=1;
  }
} {1 3 1 3}
do_test where6-1.13 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE 1=c;
  }
} {1 3 1 3}



do_test where6-2.1 {
  execsql {
    CREATE INDEX i1 ON t1(c);

    SELECT * FROM t1 LEFT JOIN t2 ON b=x AND c=1;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-2.2 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b AND c=1;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-2.3 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b AND 1=c;
  }
} {1 3 1 3 2 4 2 {}}
do_test where6-2.4 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x AND 1=c;
  }
} {1 3 1 3 2 4 2 {}}

ifcapable explain {
  do_test where6-2.5 {
     explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON x=b AND 1=c}
  } [explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON b=x AND c=1}]
  do_test where6-2.6 {
     explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON x=b WHERE 1=c}
  } [explain_no_trace {SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE c=1}]
}


do_test where6-2.11 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE c=1;
  }
} {1 3 1 3}
do_test where6-2.12 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b WHERE c=1;
  }
} {1 3 1 3}
do_test where6-2.13 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON x=b WHERE 1=c;
  }
} {1 3 1 3}
do_test where6-2.14 {
  execsql {
    SELECT * FROM t1 LEFT JOIN t2 ON b=x WHERE 1=c;
  }
} {1 3 1 3}

finish_test