**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.213 2005/07/21 18:23:20 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
          Expr *pE2 = pItem->pExpr;

          /* If the expression is not constant then we will need to
          ** disable the test that was generated above that makes sure
          ** this code only executes once.  Because for a non-constant
          ** expression we need to rerun this code each time.
          */
          if( testAddr>=0 && !sqlite3ExprIsConstant(pE2) ){
            VdbeOp *aOp = sqlite3VdbeGetOp(v, testAddr-1);
            int i;
            for(i=0; i<4; i++){
              aOp[i].opcode = OP_Noop;
            }
            testAddr = 0;
          }

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.214 2005/07/29 15:10:18 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
          Expr *pE2 = pItem->pExpr;

          /* If the expression is not constant then we will need to
          ** disable the test that was generated above that makes sure
          ** this code only executes once.  Because for a non-constant
          ** expression we need to rerun this code each time.
          */
          if( testAddr>0 && !sqlite3ExprIsConstant(pE2) ){
            VdbeOp *aOp = sqlite3VdbeGetOp(v, testAddr-1);
            int i;
            for(i=0; i<4; i++){
              aOp[i].opcode = OP_Noop;
            }
            testAddr = 0;
          }

** 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.156 2005/07/28 23:12:08 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** would be mapped into integers 0 through 7.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression */
  u16 idx;                /* Index of this term in pWC->a[] */
  i16 iPartner;           /* Disable pWC->a[iPartner] when this term disabled */
  u16 flags;              /* Bit flags.  See below */
  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
  u16 operator;           /* A WO_xx value describing <op> */

  u8 nPartner;            /* Number of partners that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by p */
};

/*
** Allowed values of WhereTerm.flags
*/
#define TERM_DYNAMIC    0x0001   /* Need to call sqlite3ExprDelete(pExpr) */
#define TERM_VIRTUAL    0x0002   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x0004   /* This term is already coded */



/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
................................................................................
  pTerm->pWC = pWC;
  pTerm->iPartner = -1;
  return pTerm;
}

/*
** This routine identifies subexpressions in the WHERE clause where
** each subexpression is separate by the AND operator.  aSlot is 

** filled with pointers to the subexpressions.  For example:
**
**    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
**           \________/     \_______________/     \________________/
**            slot[0]            slot[1]               slot[2]
**
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make slot[] entries point to substructure within pExpr.
**
** In the previous sentence and in the diagram, "slot[]" refers to
** the WhereClause.a[] array.  This array grows as needed to contain
** all terms of the WHERE clause.
*/
static void whereSplit(WhereClause *pWC, Expr *pExpr){
  if( pExpr==0 ) return;
  if( pExpr->op!=TK_AND ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft);
    whereSplit(pWC, pExpr->pRight);
  }
}

/*
** Initialize an expression mask set
*/
#define initMaskSet(P)  memset(P, 0, sizeof(*P))
................................................................................
        if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
      }
      return pTerm;
    }
  }
  return 0;
}





















/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
................................................................................
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        pDup = sqlite3ExprDup(pExpr);
        pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( pNew==0 ) return;
        pNew->iPartner = pTerm->idx;
        pTerm->nPartner = 1;

      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pDup);
      pLeft = pDup->pLeft;
      pNew->leftCursor = pLeft->iTable;
................................................................................
                                   TERM_VIRTUAL|TERM_DYNAMIC);
      exprAnalyze(pSrc, pMaskSet, pNewTerm);
      pNewTerm->iPartner = pTerm->idx;
    }
    pTerm->nPartner = 2;
  }










  















































}


/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
** ORDER BY clause, this routine returns 0.
................................................................................
  }

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(&maskSet);
  whereClauseInit(&wc, pParse);
  whereSplit(&wc, pWhere);
    
  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite3_malloc_failed ){
    goto whereBeginNoMem;
................................................................................
  ** add new virtual terms onto the end of the WHERE clause.  We do not
  ** want to analyze these virtual terms, so start analyzing at the end
  ** and work forward so that they added virtual terms are never processed.
  */
  for(i=0; i<pTabList->nSrc; i++){
    createMask(&maskSet, pTabList->a[i].iCursor);
  }
  for(i=wc.nTerm-1; i>=0; i--){
    exprAnalyze(pTabList, &maskSet, &wc.a[i]);
  }

  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].flags     WHERE_xxx flags associated with pIdx

** 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.157 2005/07/29 15:10:18 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** would be mapped into integers 0 through 7.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression */
  u16 idx;                /* Index of this term in pWC->a[] */
  i16 iPartner;           /* Disable pWC->a[iPartner] when this term disabled */

  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
  u16 operator;           /* A WO_xx value describing <op> */
  u8 flags;               /* Bit flags.  See below */
  u8 nPartner;            /* Number of partners that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by p */
};

/*
** Allowed values of WhereTerm.flags
*/
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_PARTNERED  0x08   /* Has a virtual partner */
#define TERM_OR_OK      0x10   /* Used during OR-clause processing */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
................................................................................
  pTerm->pWC = pWC;
  pTerm->iPartner = -1;
  return pTerm;
}

/*
** This routine identifies subexpressions in the WHERE clause where
** each subexpression is separate by the AND operator or some other
** operator specified in the op parameter.  The WhereClause structure
** is filled with pointers to subexpressions.  For example:
**
**    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
**           \________/     \_______________/     \________________/
**            slot[0]            slot[1]               slot[2]
**
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make slot[] entries point to substructure within pExpr.
**
** In the previous sentence and in the diagram, "slot[]" refers to
** the WhereClause.a[] array.  This array grows as needed to contain
** all terms of the WHERE clause.
*/
static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
  if( pExpr==0 ) return;
  if( pExpr->op!=op ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft, op);
    whereSplit(pWC, pExpr->pRight, op);
  }
}

/*
** Initialize an expression mask set
*/
#define initMaskSet(P)  memset(P, 0, sizeof(*P))
................................................................................
        if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
      }
      return pTerm;
    }
  }
  return 0;
}

/* Forward reference */
static void exprAnalyze(SrcList*, ExprMaskSet*, WhereTerm*);

/*
** Call exprAnalyze on all terms in a WHERE clause.  
**
**
*/
static void exprAnalyzeAll(
  SrcList *pTabList,       /* the FROM clause */
  ExprMaskSet *pMaskSet,   /* table masks */
  WhereClause *pWC         /* the WHERE clause to be analyzed */
){
  WhereTerm *pTerm;
  int i;
  for(i=pWC->nTerm-1, pTerm=pWC->a; i>=0; i--, pTerm++){
    exprAnalyze(pTabList, pMaskSet, pTerm);
  }
}

/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
................................................................................
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        pDup = sqlite3ExprDup(pExpr);
        pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( pNew==0 ) return;
        pNew->iPartner = pTerm->idx;
        pTerm->nPartner = 1;
        pTerm->flags |= TERM_PARTNERED;
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pDup);
      pLeft = pDup->pLeft;
      pNew->leftCursor = pLeft->iTable;
................................................................................
                                   TERM_VIRTUAL|TERM_DYNAMIC);
      exprAnalyze(pSrc, pMaskSet, pNewTerm);
      pNewTerm->iPartner = pTerm->idx;
    }
    pTerm->nPartner = 2;
  }

  /* Attempt to convert OR-connected terms into an IN operator so that
  ** they can make use of indices.
  */
  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->flags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pTerm->pWC->pParse);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, pMaskSet, &sOr);
    assert( sOr.nTerm>0 );
    j = 0;
    do{
      iColumn = sOr.a[j].leftColumn;
      iCursor = sOr.a[j].leftCursor;
      ok = iCursor>=0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( pOrTerm->operator!=WO_EQ ){
          goto or_not_possible;
        }
        if( pOrTerm->leftCursor==iCursor && pOrTerm->leftColumn==iColumn ){
          pOrTerm->flags |= TERM_OR_OK;
        }else if( (pOrTerm->flags & TERM_PARTNERED)!=0 ||
                    ((pOrTerm->flags & TERM_VIRTUAL)!=0 &&
                     (sOr.a[pOrTerm->iPartner].flags & TERM_OR_OK)!=0) ){
          pOrTerm->flags &= ~TERM_OR_OK;
        }else{
          ok = 0;
        }
      }
    }while( !ok && (sOr.a[j++].flags & TERM_PARTNERED)!=0 && j<sOr.nTerm );
    if( ok ){
      ExprList *pList = 0;
      Expr *pNew, *pDup;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
        pDup = sqlite3ExprDup(pOrTerm->pExpr->pRight);
        pList = sqlite3ExprListAppend(pList, pDup, 0);
      }
      pDup = sqlite3Expr(TK_COLUMN, 0, 0, 0);
      if( pDup ){
        pDup->iTable = iCursor;
        pDup->iColumn = iColumn;
      }
      pNew = sqlite3Expr(TK_IN, pDup, 0, 0);
      if( pNew ) pNew->pList = pList;
      pTerm->pExpr = pNew;
      pTerm->flags |= TERM_DYNAMIC;
      exprAnalyze(pSrc, pMaskSet, pTerm);
    }
or_not_possible:
    whereClauseClear(&sOr);
  }
}


/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
** ORDER BY clause, this routine returns 0.
................................................................................
  }

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(&maskSet);
  whereClauseInit(&wc, pParse);
  whereSplit(&wc, pWhere, TK_AND);
    
  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite3_malloc_failed ){
    goto whereBeginNoMem;
................................................................................
  ** add new virtual terms onto the end of the WHERE clause.  We do not
  ** want to analyze these virtual terms, so start analyzing at the end
  ** and work forward so that they added virtual terms are never processed.
  */
  for(i=0; i<pTabList->nSrc; i++){
    createMask(&maskSet, pTabList->a[i].iCursor);
  }

  exprAnalyzeAll(pTabList, &maskSet, &wc);


  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].flags     WHERE_xxx flags associated with pIdx

#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.2 2005/07/28 23:12:08 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
................................................................................
} {99 6 10000 10006 nosort t1 i1w}
do_test where2-5.2 {
  queryplan {
    SELECT * FROM t1 WHERE w IN (99) ORDER BY w
  }
} {99 6 10000 10006 sort t1 i1w}

integrity_check {where2-99.0}








































finish_test

#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.3 2005/07/29 15:10:19 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
................................................................................
} {99 6 10000 10006 nosort t1 i1w}
do_test where2-5.2 {
  queryplan {
    SELECT * FROM t1 WHERE w IN (99) ORDER BY w
  }
} {99 6 10000 10006 sort t1 i1w}

# Verify that OR clauses get translated into IN operators.
#
do_test where2-6.1 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 ORDER BY +w
  }
} {99 6 10000 10006 100 6 10201 10207 sort t1 i1w}
do_test where2-6.2 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=w ORDER BY +w
  }
} {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 i1w}
do_test where2-6.3 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=+w ORDER BY +w
  }
} {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}}
do_test where2-6.4 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR +w=100 OR 6=w ORDER BY +w
  }
} {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}}
if 0 {  ##### FIX ME #####
do_test where2-6.5 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}
do_test where2-6.6 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}
}



finish_test