** 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.377 2009/03/25 16:51:43 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
int sqlite3WhereTrace = 0;
#endif
#if 0
# define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
#else
# define WHERETRACE(X)
#endif

/* Forward reference
*/
................................................................................

  /* Look at each index.
  */
  if( pSrc->pIndex ){
    pProbe = pSrc->pIndex;
  }
  for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
    double inMultiplier = 1;


    WHERETRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.





    */
    wsFlags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      wsFlags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
          inMultiplier *= 25;

        }else if( pExpr->x.pList ){
          inMultiplier *= pExpr->x.pList->nExpr + 1;
        }
      }
    }
    nRow = pProbe->aiRowEst[i] * inMultiplier;
    cost = nRow * estLog(inMultiplier);







    nEq = i;
    if( pProbe->onError!=OE_None && (wsFlags & WHERE_COLUMN_IN)==0
         && nEq==pProbe->nColumn ){
      wsFlags |= WHERE_UNIQUE;
    }
    WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n",nEq,inMultiplier,cost));


    /* Look for range constraints

    */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
      if( pTerm ){
        wsFlags |= WHERE_COLUMN_RANGE;
        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
................................................................................
          nRow /= 3;
        }
        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
          wsFlags |= WHERE_BTM_LIMIT;
          cost /= 3;
          nRow /= 3;
        }
        WHERETRACE(("...... range reduces cost to %.9g\n", cost));

      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (wsFlags & WHERE_COLUMN_IN)==0 &&

** 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.378 2009/03/29 00:13:03 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
int sqlite3WhereTrace = 0;
#endif
#if 1
# define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
#else
# define WHERETRACE(X)
#endif

/* Forward reference
*/
................................................................................

  /* Look at each index.
  */
  if( pSrc->pIndex ){
    pProbe = pSrc->pIndex;
  }
  for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
    double inMultiplier = 1;  /* Number of equality look-ups needed */
    int inMultIsEst = 0;      /* True if inMultiplier is an estimate */

    WHERETRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.  For a term
    ** of the form x=EXPR we only have to do a single binary search.
    ** But for x IN (...) we have to do a number of binary searched
    ** equal to the number of entries on the RHS of the IN operator.
    ** The inMultipler variable with try to estimate the number of
    ** binary searches needed.
    */
    wsFlags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      wsFlags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
          inMultiplier *= 25;
          inMultIsEst = 1;
        }else if( pExpr->x.pList ){
          inMultiplier *= pExpr->x.pList->nExpr + 1;
        }
      }
    }
    nRow = pProbe->aiRowEst[i] * inMultiplier;
    /* If inMultiplier is an estimate and that estimate results in an
    ** nRow it that is more than half number of rows in the table,
    ** then reduce inMultipler */
    if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
      nRow = pProbe->aiRowEst[0]/2;
      inMultiplier = nRow/pProbe->aiRowEst[i];
    }
    cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
    nEq = i;
    if( pProbe->onError!=OE_None && (wsFlags & WHERE_COLUMN_IN)==0
         && nEq==pProbe->nColumn ){
      wsFlags |= WHERE_UNIQUE;
    }
    WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
                nEq, inMultiplier, nRow, cost));

    /* Look for range constraints.  Assume that each range constraint
    ** makes the search space 1/3rd smaller.
    */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
      if( pTerm ){
        wsFlags |= WHERE_COLUMN_RANGE;
        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
................................................................................
          nRow /= 3;
        }
        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
          wsFlags |= WHERE_BTM_LIMIT;
          cost /= 3;
          nRow /= 3;
        }
        WHERETRACE(("...... range reduces nRow to %.9g and cost to %.9g\n",
                    nRow, cost));
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (wsFlags & WHERE_COLUMN_IN)==0 &&

# 2009 March 28
#
# 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.
#
#***********************************************************************
#
# Ticket #3757:  The cost functions on the query optimizer for the
# IN operator can be improved.
#
# $Id: tkt3757.test,v 1.1 2009/03/29 00:13:04 drh Exp $

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

# 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 tables
#
do_test tkt3757-1.1 {
  db eval {
     CREATE TABLE t1(x INTEGER, y INTEGER, z TEXT);
     CREATE INDEX t1i1 ON t1(y,z);
     INSERT INTO t1 VALUES(1,2,'three');
     CREATE TABLE t2(a INTEGER, b TEXT);
     INSERT INTO t2 VALUES(2, 'two');
     ANALYZE;
     SELECT * FROM sqlite_stat1;
  }
} {t1 t1i1 {1 1 1}}

# Modify statistics in order to make the optimizer then that:
#
#   (1)  Table T1 has about 250K entries
#   (2)  There are only about 5 distinct values of T1.
#
# Then run a query with "t1.y IN (SELECT ..)" in the WHERE clause.
# Make sure the index is used.
#
do_test tkt3757-1.2 {
  db eval {
    DELETE FROM sqlite_stat1;
    INSERT INTO sqlite_stat1 VALUES('t1','t1i1','250000 50000 30');
  }
  count_steps {
    SELECT * FROM t1 WHERE y IN (SELECT a FROM t2)
  }
} {1 2 three scan 0 sort 0}

finish_test