SQLite

/*
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.545 2007/03/27 13:36:37 drh Exp $
** @(#) $Id: sqliteInt.h,v 1.546 2007/03/28 14:30:07 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

#if defined(SQLITE_TCL) || defined(TCLSH)
# include <tcl.h>
#endif

  int flags;            /* Flags associated with this level */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to acesss pIdx */
  int brk;              /* Jump here to break out of the loop */
  int nxt;              /* Jump here to start the next IN combination */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  struct InLoop {
    int iCur;              /* The VDBE cursor used by this IN operator */
    int topAddr;           /* Top of the IN loop */
  int *aInLoop;         /* Loop terminators for IN operators */
  } *aInLoop;           /* Information about each nested IN operator */
  sqlite3_index_info *pBestIdx;  /* Index information for this level */

  /* The following field is really not part of the current level.  But
  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */
  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.594 2007/03/27 14:44:51 drh Exp $
** $Id: vdbe.c,v 1.595 2007/03/28 14:30:07 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*

case OP_Next: {        /* no-push */
  Cursor *pC;
  BtCursor *pCrsr;

  CHECK_FOR_INTERRUPT;
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  if( pC==0 ){
    break;  /* See ticket #2273 */
  }
  if( (pCrsr = pC->pCursor)!=0 ){
    int res;
    if( pC->nullRow ){
      res = 1;
    }else{
      assert( pC->deferredMoveto==0 );
      rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :

** 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.241 2007/03/27 13:36:37 drh Exp $
** $Id: where.c,v 1.242 2007/03/28 14:30:09 drh Exp $
*/
#include "sqliteInt.h"

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

** For a constraint of the form X=expr, the expression is evaluated and its
** result is left on the stack.  For constraints of the form X IN (...)
** this routine sets up a loop that will iterate over all values of X.
*/
static void codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
  WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  int brk,            /* Jump here to abandon the loop */
  WhereLevel *pLevel  /* When level of the FROM clause we are working on */
){
  Expr *pX = pTerm->pExpr;
  Vdbe *v = pParse->pVdbe;
  if( pX->op==TK_EQ ){
    sqlite3ExprCode(pParse, pX->pRight);
  }else if( pX->op==TK_ISNULL ){
    sqlite3VdbeAddOp(v, OP_Null, 0, 0);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{
    int iTab;
    int *aIn;
    struct InLoop *pIn;

    assert( pX->op==TK_IN );
    sqlite3CodeSubselect(pParse, pX);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->nxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqliteReallocOrFree(pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*2*pLevel->nIn);
    aIn = pLevel->aInLoop;
    if( aIn ){
      aIn += pLevel->nIn*2 - 2;
      aIn[0] = iTab;
      aIn[1] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){
      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      pIn->topAddr = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
      sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);
}

** this routine allocates an additional nEq memory cells for internal
** use.
*/
static void codeAllEqualityTerms(
  Parse *pParse,        /* Parsing context */
  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  WhereClause *pWC,     /* The WHERE clause */
  Bitmask notReady,     /* Which parts of FROM have not yet been coded */
  Bitmask notReady      /* Which parts of FROM have not yet been coded */
  int brk               /* Jump here to end the loop */
){
  int nEq = pLevel->nEq;        /* The number of == or IN constraints to code */
  int termsInMem = 0;           /* If true, store value in mem[] cells */
  Vdbe *v = pParse->pVdbe;      /* The virtual machine under construction */
  Index *pIdx = pLevel->pIdx;   /* The index being used for this loop */
  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  WhereTerm *pTerm;             /* A single constraint term */

  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->flags, pIdx);
    if( pTerm==0 ) break;
    assert( (pTerm->flags & TERM_CODED)==0 );
    codeEqualityTerm(pParse, pTerm, brk, pLevel);
    if( (pTerm->eOperator & WO_ISNULL)==0 ){
      sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), brk);
    codeEqualityTerm(pParse, pTerm, pLevel);
    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
      sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), pLevel->brk);
    }
    if( termsInMem ){
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
    }
  }

  /* Make sure all the constraint values are on the top of the stack

  ** program.
  */
  notReady = ~(Bitmask)0;
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    int j;
    int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
    Index *pIdx;       /* The index we will be using */
    int nxt;           /* Where to jump to continue with the next IN case */
    int iIdxCur;       /* The VDBE cursor for the index */
    int omitTable;     /* True if we use the index only */
    int bRev;          /* True if we need to scan in reverse order */

    pTabItem = &pTabList->a[pLevel->iFrom];
    iCur = pTabItem->iCursor;
    pIdx = pLevel->pIdx;
    iIdxCur = pLevel->iIdxCur;
    bRev = (pLevel->flags & WHERE_REVERSE)!=0;
    omitTable = (pLevel->flags & WHERE_IDX_ONLY)!=0;

    /* Create labels for the "break" and "continue" instructions
    ** for the current loop.  Jump to brk to break out of a loop.
    ** Jump to cont to go immediately to the next iteration of the
    ** loop.
    **
    ** When there is an IN operator, we also have a "nxt" label that
    ** means to continue with the next IN value combination.  When
    ** there are no IN operators in the constraints, the "nxt" label
    ** is the same as "brk".
    */
    brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
    brk = pLevel->brk = pLevel->nxt = sqlite3VdbeMakeLabel(v);
    cont = pLevel->cont = sqlite3VdbeMakeLabel(v);

    /* If this is the right table of a LEFT OUTER JOIN, allocate and
    ** initialize a memory cell that records if this table matches any
    ** row of the left table of the join.
    */
    if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){

      **          construct.
      */
      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
      assert( pTerm!=0 );
      assert( pTerm->pExpr!=0 );
      assert( pTerm->leftCursor==iCur );
      assert( omitTable==0 );
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      codeEqualityTerm(pParse, pTerm, pLevel);
      nxt = pLevel->nxt;
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, nxt);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, nxt);
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->flags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;

      int testOp;
      int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
      int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and level the values of those terms on the stack.
      */
      codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk);
      codeAllEqualityTerms(pParse, pLevel, &wc, notReady);

      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the
      ** start key.
      */
      for(j=0; j<nEq; j++){
        sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0);

      /* Generate the termination key.  This is the key value that
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
      ** key computed here really ends up being the start key.
      */
      nxt = pLevel->nxt;
      if( topLimit ){
        Expr *pX;
        int k = pIdx->aiColumn[j];
        pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), brk);
        sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt);
        topEq = pTerm->eOperator & (WO_LE|WO_GE);
        disableTerm(pLevel, pTerm);
        testOp = OP_IdxGE;
      }else{
        testOp = nEq>0 ? OP_IdxGE : OP_Noop;
        topEq = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEq + topLimit;
        pLevel->iMem = pParse->nMem++;
        buildIndexProbe(v, nCol, pIdx);
        if( bRev ){
          int op = topEq ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
          sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
        }else{
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
        }
      }else if( bRev ){
        sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk);
      }

        Expr *pX;
        int k = pIdx->aiColumn[j];
        pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), brk);
        sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt);
        btmEq = pTerm->eOperator & (WO_LE|WO_GE);
        disableTerm(pLevel, pTerm);
      }else{
        btmEq = 1;
      }
      if( nEq>0 || btmLimit ){
        int nCol = nEq + btmLimit;
        buildIndexProbe(v, nCol, pIdx);
        if( bRev ){
          pLevel->iMem = pParse->nMem++;
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
          testOp = OP_IdxLT;
        }else{
          int op = btmEq ? OP_MoveGe : OP_MoveGt;
          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
          sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
        }
      }else if( bRev ){
        testOp = OP_Noop;
      }else{
        sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk);
      }

      /* Generate the the top of the loop.  If there is a termination
      ** key we have to test for that key and abort at the top of the
      ** loop.
      */
      start = sqlite3VdbeCurrentAddr(v);
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
        sqlite3VdbeAddOp(v, testOp, iIdxCur, nxt);
        if( (topEq && !bRev) || (!btmEq && bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      if( topLimit | btmLimit ){
        sqlite3VdbeAddOp(v, OP_Column, iIdxCur, nEq);
        sqlite3VdbeAddOp(v, OP_IsNull, 1, cont);

      */
      int start;
      int nEq = pLevel->nEq;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and leave the values of those terms on the stack.
      */
      codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk);
      codeAllEqualityTerms(pParse, pLevel, &wc, notReady);
      nxt = pLevel->nxt;

      /* Generate a single key that will be used to both start and terminate
      ** the search
      */
      buildIndexProbe(v, nEq, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
      ** Then generate code (2) that jumps to "brk" after the cursor is past
      ** Then generate code (2) that jumps to "nxt" after the cursor is past
      ** the last matching element of the table.  The code (1) is executed
      ** once to initialize the search, the code (2) is executed before each
      ** iteration of the scan to see if the scan has finished. */
      if( bRev ){
        /* Scan in reverse order */
        sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk);
        sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, nxt);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk);
        sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, nxt);
        pLevel->op = OP_Prev;
      }else{
        /* Scan in the forward order */
        sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk);
        sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, nxt);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC);
        sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, nxt, "+", P3_STATIC);
        pLevel->op = OP_Next;
      }
      if( !omitTable ){
        sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
      pLevel->p1 = iIdxCur;

  */
  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqlite3VdbeResolveLabel(v, pLevel->cont);
    if( pLevel->op!=OP_Noop ){
      sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqlite3VdbeResolveLabel(v, pLevel->brk);
    if( pLevel->nIn ){
      int *a;
      struct InLoop *pIn;
      int j;
      sqlite3VdbeResolveLabel(v, pLevel->nxt);
      for(j=pLevel->nIn, a=&pLevel->aInLoop[j*2-2]; j>0; j--, a-=2){
        sqlite3VdbeAddOp(v, OP_Next, a[0], a[1]);
        sqlite3VdbeJumpHere(v, a[1]-1);
      for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
        sqlite3VdbeJumpHere(v, pIn->topAddr+1);
        sqlite3VdbeAddOp(v, OP_Next, pIn->iCur, pIn->topAddr);
        sqlite3VdbeJumpHere(v, pIn->topAddr-1);
      }
      sqliteFree(pLevel->aInLoop);
    }
    sqlite3VdbeResolveLabel(v, pLevel->brk);
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0);
      sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
      if( pLevel->iIdxCur>=0 ){
        sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0);
      }

# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clauses.
# This file was created when support for optimizing IS NULL phrases
# was added.  And so the principle purpose of this file is to test
# that IS NULL phrases are correctly optimized.  But you can never
# have too many tests, so some other tests are thrown in as well.
#
# $Id: where4.test,v 1.2 2007/01/25 16:56:08 drh Exp $
# $Id: where4.test,v 1.3 2007/03/28 14:30:09 drh Exp $

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

# Build some test data
#
do_test where4-1.0 {

} {}
do_test where4-4.4 {
  execsql {
    SELECT * FROM test t1 LEFT OUTER JOIN test2 t2 ON t1.col1 = t2.col1
      WHERE t1.col1 IS NULL;
  }
} {}
    


# Ticket #2273.  Problems with IN operators and NULLs.
#
do_test where4-5.1 {
  execsql {
    CREATE TABLE t4(x,y,z,PRIMARY KEY(x,y));
  }
  execsql {
    SELECT *
      FROM t2 LEFT JOIN t4 b1
              LEFT JOIN t4 b2 ON b2.x=b1.x AND b2.y IN (b1.y);
  }
} {1 {} {} {} {} {} {} 2 {} {} {} {} {} {} 3 {} {} {} {} {} {}}
do_test where4-5.2 {
  execsql {
    INSERT INTO t4 VALUES(1,1,11);
    INSERT INTO t4 VALUES(1,2,12);
    INSERT INTO t4 VALUES(1,3,13);
    INSERT INTO t4 VALUES(2,2,22);
    SELECT rowid FROM t4 WHERE x IN (1,9,2,5) AND y IN (1,3,NULL,2) AND z!=13;
  }
} {1 2 4}
do_test where4-5.3 {
  execsql {
    SELECT rowid FROM t4 WHERE x IN (1,9,NULL,2) AND y IN (1,3,2) AND z!=13;
  }
} {1 2 4}
do_test where4-6.1 {
  execsql {
    CREATE TABLE t5(a,b,c,d,e,f,UNIQUE(a,b,c,d,e,f));
    INSERT INTO t5 VALUES(1,1,1,1,1,11111);
    INSERT INTO t5 VALUES(2,2,2,2,2,22222);
    INSERT INTO t5 VALUES(1,2,3,4,5,12345);
    INSERT INTO t5 VALUES(2,3,4,5,6,23456);
  }
  execsql {
    SELECT rowid FROM t5
     WHERE a IN (1,9,2) AND b=2 AND c IN (1,2,3,4) AND d>0
  }
} {3 2}
do_test where4-6.2 {
  execsql {
    SELECT rowid FROM t5
     WHERE a IN (1,NULL,2) AND b=2 AND c IN (1,2,3,4) AND d>0
  }
} {3 2}
do_test where4-7.1 {
  execsql {
    CREATE TABLE t6(y,z,PRIMARY KEY(y,z));
  }
  execsql {
    SELECT * FROM t6 WHERE y=NULL AND z IN ('hello');
  }
} {}

integrity_check {where4-99.0}

finish_test