where.c

sqlite-3.4.1,嵌入式数据库.是一个功能强大的开源数据库,给学习和研发以及小型公司的发展带来了全所未有的好处.

/*
** Swap two objects of type T.
*/
#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}

/*
** Commute a comparision operator.  Expressions of the form "X op Y"
** are converted into "Y op X".
*/
static void exprCommute(Expr *pExpr){
  assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
  SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
  SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
  if( pExpr->op>=TK_GT ){
    assert( TK_LT==TK_GT+2 );
    assert( TK_GE==TK_LE+2 );
    assert( TK_GT>TK_EQ );
    assert( TK_GT<TK_LE );
    assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
    pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
  }
}

/*
** Translate from TK_xx operator to WO_xx bitmask.
*/
static int operatorMask(int op){
  int c;
  assert( allowedOp(op) );
  if( op==TK_IN ){
    c = WO_IN;
  }else if( op==TK_ISNULL ){
    c = WO_ISNULL;
  }else{
    c = WO_EQ<<(op-TK_EQ);
  }
  assert( op!=TK_ISNULL || c==WO_ISNULL );
  assert( op!=TK_IN || c==WO_IN );
  assert( op!=TK_EQ || c==WO_EQ );
  assert( op!=TK_LT || c==WO_LT );
  assert( op!=TK_LE || c==WO_LE );
  assert( op!=TK_GT || c==WO_GT );
  assert( op!=TK_GE || c==WO_GE );
  return c;
}

/*
** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
** where X is a reference to the iColumn of table iCur and <op> is one of
** the WO_xx operator codes specified by the op parameter.
** Return a pointer to the term.  Return 0 if not found.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u16 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  WhereTerm *pTerm;
  int k;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & notReady)==0
       && pTerm->leftColumn==iColumn
       && (pTerm->eOperator & op)!=0
    ){
      if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
        Expr *pX = pTerm->pExpr;
        CollSeq *pColl;
        char idxaff;
        int j;
        Parse *pParse = pWC->pParse;

        idxaff = pIdx->pTable->aCol[iColumn].affinity;
        if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;

        /* Figure out the collation sequence required from an index for
        ** it to be useful for optimising expression pX. Store this
        ** value in variable pColl.
        */
        assert(pX->pLeft);
        pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
        if( !pColl ){
          pColl = pParse->db->pDfltColl;
        }

        for(j=0; j<pIdx->nColumn && pIdx->aiColumn[j]!=iColumn; j++){}
        assert( j<pIdx->nColumn );
        if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
      }
      return pTerm;
    }
  }
  return 0;
}

/* Forward reference */
static void exprAnalyze(SrcList*, WhereClause*, int);

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

#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
/*
** Check to see if the given expression is a LIKE or GLOB operator that
** can be optimized using inequality constraints.  Return TRUE if it is
** so and false if not.
**
** In order for the operator to be optimizible, the RHS must be a string
** literal that does not begin with a wildcard.  
*/
static int isLikeOrGlob(
  sqlite3 *db,      /* The database */
  Expr *pExpr,      /* Test this expression */
  int *pnPattern,   /* Number of non-wildcard prefix characters */
  int *pisComplete  /* True if the only wildcard is % in the last character */
){
  const char *z;
  Expr *pRight, *pLeft;
  ExprList *pList;
  int c, cnt;
  int noCase;
  char wc[3];
  CollSeq *pColl;

  if( !sqlite3IsLikeFunction(db, pExpr, &noCase, wc) ){
    return 0;
  }
  pList = pExpr->pList;
  pRight = pList->a[0].pExpr;
  if( pRight->op!=TK_STRING ){
    return 0;
  }
  pLeft = pList->a[1].pExpr;
  if( pLeft->op!=TK_COLUMN ){
    return 0;
  }
  pColl = pLeft->pColl;
  if( pColl==0 ){
    /* TODO: Coverage testing doesn't get this case. Is it actually possible
    ** for an expression of type TK_COLUMN to not have an assigned collation 
    ** sequence at this point?
    */
    pColl = db->pDfltColl;
  }
  if( (pColl->type!=SQLITE_COLL_BINARY || noCase) &&
      (pColl->type!=SQLITE_COLL_NOCASE || !noCase) ){
    return 0;
  }
  sqlite3DequoteExpr(pRight);
  z = (char *)pRight->token.z;
  for(cnt=0; (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2]; cnt++){}
  if( cnt==0 || 255==(u8)z[cnt] ){
    return 0;
  }
  *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;
  *pnPattern = cnt;
  return 1;
}
#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */


#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Check to see if the given expression is of the form
**
**         column MATCH expr
**
** If it is then return TRUE.  If not, return FALSE.
*/
static int isMatchOfColumn(
  Expr *pExpr      /* Test this expression */
){
  ExprList *pList;

  if( pExpr->op!=TK_FUNCTION ){
    return 0;
  }
  if( pExpr->token.n!=5 ||
       sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){
    return 0;
  }
  pList = pExpr->pList;
  if( pList->nExpr!=2 ){
    return 0;
  }
  if( pList->a[1].pExpr->op != TK_COLUMN ){
    return 0;
  }
  return 1;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** If the pBase expression originated in the ON or USING clause of
** a join, then transfer the appropriate markings over to derived.
*/
static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
  pDerived->flags |= pBase->flags & EP_FromJoin;
  pDerived->iRightJoinTable = pBase->iRightJoinTable;
}

#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
/*
** Return TRUE if the given term of an OR clause can be converted
** into an IN clause.  The iCursor and iColumn define the left-hand
** side of the IN clause.
**
** The context is that we have multiple OR-connected equality terms
** like this:
**
**           a=<expr1> OR  a=<expr2> OR b=<expr3>  OR ...
**
** The pOrTerm input to this routine corresponds to a single term of
** this OR clause.  In order for the term to be a condidate for
** conversion to an IN operator, the following must be true:
**
**     *  The left-hand side of the term must be the column which
**        is identified by iCursor and iColumn.
**
**     *  If the right-hand side is also a column, then the affinities
**        of both right and left sides must be such that no type
**        conversions are required on the right.  (Ticket #2249)
**
** If both of these conditions are true, then return true.  Otherwise
** return false.
*/
static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
  int affLeft, affRight;
  assert( pOrTerm->eOperator==WO_EQ );
  if( pOrTerm->leftCursor!=iCursor ){
    return 0;
  }
  if( pOrTerm->leftColumn!=iColumn ){
    return 0;
  }
  affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
  if( affRight==0 ){
    return 1;
  }
  affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
  if( affRight!=affLeft ){
    return 0;
  }
  return 1;
}

/*
** Return true if the given term of an OR clause can be ignored during
** a check to make sure all OR terms are candidates for optimization.
** In other words, return true if a call to the orTermIsOptCandidate()
** above returned false but it is not necessary to disqualify the
** optimization.
**
** Suppose the original OR phrase was this:
**
**           a=4  OR  a=11  OR  a=b
**
** During analysis, the third term gets flipped around and duplicate
** so that we are left with this:
**
**           a=4  OR  a=11  OR  a=b  OR  b=a
**
** Since the last two terms are duplicates, only one of them
** has to qualify in order for the whole phrase to qualify.  When
** this routine is called, we know that pOrTerm did not qualify.
** This routine merely checks to see if pOrTerm has a duplicate that
** might qualify.  If there is a duplicate that has not yet been
** disqualified, then return true.  If there are no duplicates, or
** the duplicate has also been disqualifed, return false.
*/
static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){
  if( pOrTerm->flags & TERM_COPIED ){
    /* This is the original term.  The duplicate is to the left had
    ** has not yet been analyzed and thus has not yet been disqualified. */
    return 1;
  }
  if( (pOrTerm->flags & TERM_VIRTUAL)!=0
     && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){
    /* This is a duplicate term.  The original qualified so this one
    ** does not have to. */
    return 1;
  }
  /* This is either a singleton term or else it is a duplicate for
  ** which the original did not qualify.  Either way we are done for. */
  return 0;
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

/*
** 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.
**
** If the expression is of the form "<expr> <op> X" it gets commuted
** to the standard form of "X <op> <expr>".  If the expression is of
** the form "X <op> Y" where both X and Y are columns, then the original
** expression is unchanged and a new virtual expression of the form
** "Y <op> X" is added to the WHERE clause and analyzed separately.
*/
static void exprAnalyze(
  SrcList *pSrc,            /* the FROM clause */
  WhereClause *pWC,         /* the WHERE clause */
  int idxTerm               /* Index of the term to be analyzed */
){
  WhereTerm *pTerm = &pWC->a[idxTerm];
  ExprMaskSet *pMaskSet = pWC->pMaskSet;
  Expr *pExpr = pTerm->pExpr;
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int nPattern;
  int isComplete;
  int op;

  if( sqlite3MallocFailed() ) return;
  prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
  op = pExpr->op;
  if( op==TK_IN ){
    assert( pExpr->pRight==0 );
    pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)
                          | exprSelectTableUsage(pMaskSet, pExpr->pSelect);
  }else if( op==TK_ISNULL ){
    pTerm->prereqRight = 0;
  }else{
    pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
  }
  prereqAll = exprTableUsage(pMaskSet, pExpr);
  if( ExprHasProperty(pExpr, EP_FromJoin) ){
    prereqAll |= getMask(pMaskSet, pExpr->iRightJoinTable);
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(pExpr);
        if( sqlite3MallocFailed() ){
          sqlite3ExprDelete(pDup);
          return;
        }
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->flags |= TERM_COPIED;
      }else{