where.c

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.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.
**
** $Id: where.c,v 1.89.2.2 2004/07/19 19:30:50 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
*/
typedef struct ExprInfo ExprInfo;
struct ExprInfo {
  Expr *p;                /* Pointer to the subexpression */
  u8 indexable;           /* True if this subexprssion is usable by an index */
  short int idxLeft;      /* p->pLeft is a column in this table number. -1 if
                          ** p->pLeft is not the column of any table */
  short int idxRight;     /* p->pRight is a column in this table number. -1 if
                          ** p->pRight is not the column of any table */
  unsigned prereqLeft;    /* Bitmask of tables referenced by p->pLeft */
  unsigned prereqRight;   /* Bitmask of tables referenced by p->pRight */
  unsigned prereqAll;     /* Bitmask of tables referenced by p */
};

/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bitmasks.  The VDBE cursor numbers
** are small integers contained in SrcList_item.iCursor and Expr.iTable
** fields.  For any given WHERE clause, we want to track which cursors
** are being used, so we assign a single bit in a 32-bit word to track
** that cursor.  Then a 32-bit integer is able to show the set of all
** cursors being used.
*/
typedef struct ExprMaskSet ExprMaskSet;
struct ExprMaskSet {
  int n;          /* Number of assigned cursor values */
  int ix[31];     /* Cursor assigned to each bit */
};

/*
** Determine the number of elements in an array.
*/
#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))

/*
** This routine is used to divide the WHERE expression into subexpressions
** separated by the AND operator.
**
** aSlot[] is an array of subexpressions structures.
** There are nSlot spaces left in this array.  This routine attempts to
** split pExpr into subexpressions and fills aSlot[] with those subexpressions.
** The return value is the number of slots filled.
*/
static int exprSplit(int nSlot, ExprInfo *aSlot, Expr *pExpr){
  int cnt = 0;
  if( pExpr==0 || nSlot<1 ) return 0;
  if( nSlot==1 || pExpr->op!=TK_AND ){
    aSlot[0].p = pExpr;
    return 1;
  }
  if( pExpr->pLeft->op!=TK_AND ){
    aSlot[0].p = pExpr->pLeft;
    cnt = 1 + exprSplit(nSlot-1, &aSlot[1], pExpr->pRight);
  }else{
    cnt = exprSplit(nSlot, aSlot, pExpr->pLeft);
    cnt += exprSplit(nSlot-cnt, &aSlot[cnt], pExpr->pRight);
  }
  return cnt;
}

/*
** Initialize an expression mask set
*/
#define initMaskSet(P)  memset(P, 0, sizeof(*P))

/*
** Return the bitmask for the given cursor.  Assign a new bitmask
** if this is the first time the cursor has been seen.
*/
static int getMask(ExprMaskSet *pMaskSet, int iCursor){
  int i;
  for(i=0; i<pMaskSet->n; i++){
    if( pMaskSet->ix[i]==iCursor ) return 1<<i;
  }
  if( i==pMaskSet->n && i<ARRAYSIZE(pMaskSet->ix) ){
    pMaskSet->n++;
    pMaskSet->ix[i] = iCursor;
    return 1<<i;
  }
  return 0;
}

/*
** Destroy an expression mask set
*/
#define freeMaskSet(P)   /* NO-OP */

/*
** This routine walks (recursively) an expression tree and generates
** a bitmask indicating which tables are used in that expression
** tree.
**
** In order for this routine to work, the calling function must have
** previously invoked sqliteExprResolveIds() on the expression.  See
** the header comment on that routine for additional information.
** The sqliteExprResolveIds() routines looks for column names and
** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
** the VDBE cursor number of the table.
*/
static int exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
  unsigned int mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    mask = getMask(pMaskSet, p->iTable);
    if( mask==0 ) mask = -1;
    return mask;
  }
  if( p->pRight ){
    mask = exprTableUsage(pMaskSet, p->pRight);
  }
  if( p->pLeft ){
    mask |= exprTableUsage(pMaskSet, p->pLeft);
  }
  if( p->pList ){
    int i;
    for(i=0; i<p->pList->nExpr; i++){
      mask |= exprTableUsage(pMaskSet, p->pList->a[i].pExpr);
    }
  }
  return mask;
}

/*
** Return TRUE if the given operator is one of the operators that is
** allowed for an indexable WHERE clause.  The allowed operators are
** "=", "<", ">", "<=", ">=", and "IN".
*/
static int allowedOp(int op){
  switch( op ){
    case TK_LT:
    case TK_LE:
    case TK_GT:
    case TK_GE:
    case TK_EQ:
    case TK_IN:
      return 1;
    default:
      return 0;
  }
}

/*
** The input to this routine is an ExprInfo structure with only the
** "p" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the ExprInfo
** structure.
*/
static void exprAnalyze(ExprMaskSet *pMaskSet, ExprInfo *pInfo){
  Expr *pExpr = pInfo->p;
  pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
  pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
  pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);
  pInfo->indexable = 0;
  pInfo->idxLeft = -1;
  pInfo->idxRight = -1;
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
      pInfo->idxRight = pExpr->pRight->iTable;
      pInfo->indexable = 1;
    }
    if( pExpr->pLeft->op==TK_COLUMN ){
      pInfo->idxLeft = pExpr->pLeft->iTable;
      pInfo->indexable = 1;
    }
  }
}

/*
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".
**
** This routine attempts to find an index for pTab that generates the
** correct record sequence for the given ORDER BY clause.  The return value
** is a pointer to an index that does the job.  NULL is returned if the
** table has no index that will generate the correct sort order.
**
** If there are two or more indices that generate the correct sort order
** and pPreferredIdx is one of those indices, then return pPreferredIdx.
**
** nEqCol is the number of columns of pPreferredIdx that are used as
** equality constraints.  Any index returned must have exactly this same
** set of columns.  The ORDER BY clause only matches index columns beyond the
** the first nEqCol columns.
**
** All terms of the ORDER BY clause must be either ASC or DESC.  The
** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is
** set to 0 if the ORDER BY clause is all ASC.
*/
static Index *findSortingIndex(
  Table *pTab,            /* The table to be sorted */
  int base,               /* Cursor number for pTab */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  Index *pPreferredIdx,   /* Use this index, if possible and not NULL */
  int nEqCol,             /* Number of index columns used with == constraints */
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
){
  int i, j;
  Index *pMatch;
  Index *pIdx;
  int sortOrder;

  assert( pOrderBy!=0 );
  assert( pOrderBy->nExpr>0 );
  sortOrder = pOrderBy->a[0].sortOrder & SQLITE_SO_DIRMASK;
  for(i=0; i<pOrderBy->nExpr; i++){
    Expr *p;
    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_DIRMASK)!=sortOrder ){
      /* Indices can only be used if all ORDER BY terms are either
      ** DESC or ASC.  Indices cannot be used on a mixture. */
      return 0;
    }
    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_TYPEMASK)!=SQLITE_SO_UNK ){
      /* Do not sort by index if there is a COLLATE clause */
      return 0;
    }
    p = pOrderBy->a[i].pExpr;
    if( p->op!=TK_COLUMN || p->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      return 0;
    }
  }
  
  /* If we get this far, it means the ORDER BY clause consists only of
  ** ascending columns in the left-most table of the FROM clause.  Now
  ** check for a matching index.
  */
  pMatch = 0;
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nExpr = pOrderBy->nExpr;
    if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;
    for(i=j=0; i<nEqCol; i++){
      if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;
      if( j<nExpr && pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] ){ j++; }
    }
    if( i<nEqCol ) continue;
    for(i=0; i+j<nExpr; i++){
      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ) break;
    }
    if( i+j>=nExpr ){
      pMatch = pIdx;
      if( pIdx==pPreferredIdx ) break;
    }
  }
  if( pMatch && pbRev ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
  }
  return pMatch;
}

/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.
**
** Consider the term t2.z='ok' in the following queries:
**
**   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
**   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
**   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
**
** The t2.z='ok' is disabled in the in (2) because it did not originate
** in the ON clause.  The term is disabled in (3) because it is not part
** of a LEFT OUTER JOIN.  In (1), the term is not disabled.
**
** Disabling a term causes that term to not be tested in the inner loop
** of the join.  Disabling is an optimization.  We would get the correct
** results if nothing were ever disabled, but joins might run a little
** slower.  The trick is to disable as much as we can without disabling
** too much.  If we disabled in (1), we'd get the wrong answer.
** See ticket #813.
*/
static void disableTerm(WhereLevel *pLevel, Expr **ppExpr){
  Expr *pExpr = *ppExpr;
  if( pLevel->iLeftJoin==0 || ExprHasProperty(pExpr, EP_FromJoin) ){
    *ppExpr = 0;
  }
}

/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an (opaque) structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqliteWhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
**
** If an error occurs, this routine returns NULL.
**
** The basic idea is to do a nested loop, one loop for each table in
** the FROM clause of a select.  (INSERT and UPDATE statements are the
** same as a SELECT with only a single table in the FROM clause.)  For
** example, if the SQL is this:
**
**       SELECT * FROM t1, t2, t3 WHERE ...;
**
** Then the code generated is conceptually like the following:
**
**      foreach row1 in t1 do       \    Code generated
**        foreach row2 in t2 do      |-- by sqliteWhereBegin()
**          foreach row3 in t3 do   /
**            ...
**          end                     \    Code generated
**        end                        |-- by sqliteWhereEnd()
**      end                         /
**
** There are Btree cursors associated with each table.  t1 uses cursor
** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
** And so forth.  This routine generates code to open those VDBE cursors
** and sqliteWhereEnd() generates the code to close them.
**
** If the WHERE clause is empty, the foreach loops must each scan their
** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
** the tables have indices and there are terms in the WHERE clause that
** refer to those indices, a complete table scan can be avoided and the
** code will run much faster.  Most of the work of this routine is checking
** to see if there are indices that can be used to speed up the loop.
**
** Terms of the WHERE clause are also used to limit which rows actually
** make it to the "..." in the middle of the loop.  After each "foreach",
** terms of the WHERE clause that use only terms in that loop and outer
** loops are evaluated and if false a jump is made around all subsequent
** inner loops (or around the "..." if the test occurs within the inner-
** most loop)
**
** OUTER JOINS
**
** An outer join of tables t1 and t2 is conceptally coded as follows:
**
**    foreach row1 in t1 do
**      flag = 0
**      foreach row2 in t2 do
**        start:
**          ...
**          flag = 1
**      end
**      if flag==0 then
**        move the row2 cursor to a null row
**        goto start
**      fi
**    end
**
** ORDER BY CLAUSE PROCESSING
**
** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
** if there is one.  If there is no ORDER BY clause or if this routine
** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
**
** If an index can be used so that the natural output order of the table
** scan is correct for the ORDER BY clause, then that index is used and
** *ppOrderBy is set to NULL.  This is an optimization that prevents an
** unnecessary sort of the result set if an index appropriate for the
** ORDER BY clause already exists.
**
** If the where clause loops cannot be arranged to provide the correct
** output order, then the *ppOrderBy is unchanged.
*/
WhereInfo *sqliteWhereBegin(
  Parse *pParse,       /* The parser context */
  SrcList *pTabList,   /* A list of all tables to be scanned */
  Expr *pWhere,        /* The WHERE clause */
  int pushKey,         /* If TRUE, leave the table key on the stack */
  ExprList **ppOrderBy /* An ORDER BY clause, or NULL */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */
  int haveKey;         /* True if KEY is on the stack */
  ExprMaskSet maskSet; /* The expression mask set */
  int iDirectEq[32];   /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[32];   /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[32];   /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[101]; /* The WHERE clause is divided into these expressions */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.  If the aExpr[]
  ** array fills up, the last entry might point to an expression which
  ** contains additional unfactored AND operators.
  */
  initMaskSet(&maskSet);
  memset(aExpr, 0, sizeof(aExpr));
  nExpr = exprSplit(ARRAYSIZE(aExpr), aExpr, pWhere);