/ Check-in [13171eb5]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Enhance the query planner to exploit transitivity of join constraints in a multi-way join.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | transitive-constraints
Files: files | file ages | folders
SHA1: 13171eb5dc19733276fbfd5515d75b70a9f5f5d7
User & Date: drh 2013-01-16 17:08:58
Context
2013-01-17
00:08
Improved comments explaining the operation of the findTerm() utility routine in where.c. Increase the maximum number of levels of transitivity from 4 to 11. check-in: fe152f8b user: drh tags: transitive-constraints
2013-01-16
17:08
Enhance the query planner to exploit transitivity of join constraints in a multi-way join. check-in: 13171eb5 user: drh tags: transitive-constraints
00:46
Improvements to query planning for joins: Avoid unnecessary calls to "optimal scan" checks in cases where table reordering is not possible. Make sure optimal scan checks are carried out for CROSS JOINs and LEFT JOINs. check-in: d5ebb787 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

   571    571   
   572    572   /*
   573    573   ** A convenience macro that returns the number of elements in
   574    574   ** an array.
   575    575   */
   576    576   #define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))
   577    577   
          578  +/*
          579  +** Determine if the argument is a power of two
          580  +*/
          581  +#define IsPowerOfTwo(X) (((X)&((X)-1))==0)
          582  +
   578    583   /*
   579    584   ** The following value as a destructor means to use sqlite3DbFree().
   580    585   ** The sqlite3DbFree() routine requires two parameters instead of the 
   581    586   ** one parameter that destructors normally want.  So we have to introduce 
   582    587   ** this magic value that the code knows to handle differently.  Any 
   583    588   ** pointer will work here as long as it is distinct from SQLITE_STATIC
   584    589   ** and SQLITE_TRANSIENT.

Changes to src/where.c.

    94     94   typedef struct WhereTerm WhereTerm;
    95     95   struct WhereTerm {
    96     96     Expr *pExpr;            /* Pointer to the subexpression that is this term */
    97     97     int iParent;            /* Disable pWC->a[iParent] when this term disabled */
    98     98     int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
    99     99     union {
   100    100       int leftColumn;         /* Column number of X in "X <op> <expr>" */
   101         -    WhereOrInfo *pOrInfo;   /* Extra information if eOperator==WO_OR */
   102         -    WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
          101  +    WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
          102  +    WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
   103    103     } u;
   104    104     u16 eOperator;          /* A WO_xx value describing <op> */
   105    105     u8 wtFlags;             /* TERM_xxx bit flags.  See below */
   106    106     u8 nChild;              /* Number of children that must disable us */
   107    107     WhereClause *pWC;       /* The clause this term is part of */
   108    108     Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
   109    109     Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
................................................................................
   223    223   #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
   224    224   #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
   225    225   #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
   226    226   #define WO_MATCH  0x040
   227    227   #define WO_ISNULL 0x080
   228    228   #define WO_OR     0x100       /* Two or more OR-connected terms */
   229    229   #define WO_AND    0x200       /* Two or more AND-connected terms */
          230  +#define WO_EQUIV  0x400       /* Of the form A==B, both columns */
   230    231   #define WO_NOOP   0x800       /* This term does not restrict search space */
   231    232   
   232    233   #define WO_ALL    0xfff       /* Mask of all possible WO_* values */
   233    234   #define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */
   234    235   
   235    236   /*
   236    237   ** Value for wsFlags returned by bestIndex() and stored in
................................................................................
   635    636     int iCur,             /* Cursor number of LHS */
   636    637     int iColumn,          /* Column number of LHS */
   637    638     Bitmask notReady,     /* RHS must not overlap with this mask */
   638    639     u32 op,               /* Mask of WO_xx values describing operator */
   639    640     Index *pIdx           /* Must be compatible with this index, if not NULL */
   640    641   ){
   641    642     WhereTerm *pTerm;
   642         -  int k;
          643  +  WhereTerm *pResult = 0;
          644  +  WhereClause *pWCOrig = pWC;
          645  +  int j, k;
          646  +  int aEquiv[8];
          647  +  int nEquiv = 2;
          648  +  int iEquiv = 2;
          649  +  Expr *pX;
          650  +  Parse *pParse;
          651  +
   643    652     assert( iCur>=0 );
   644         -  op &= WO_ALL;
   645         -  for(; pWC; pWC=pWC->pOuter){
   646         -    for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   647         -      if( pTerm->leftCursor==iCur
   648         -         && (pTerm->prereqRight & notReady)==0
   649         -         && pTerm->u.leftColumn==iColumn
   650         -         && (pTerm->eOperator & op)!=0
   651         -      ){
   652         -        if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
   653         -          Expr *pX = pTerm->pExpr;
   654         -          CollSeq *pColl;
   655         -          char idxaff;
   656         -          int j;
   657         -          Parse *pParse = pWC->pParse;
   658         -  
   659         -          idxaff = pIdx->pTable->aCol[iColumn].affinity;
   660         -          if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
   661         -  
   662         -          /* Figure out the collation sequence required from an index for
   663         -          ** it to be useful for optimising expression pX. Store this
   664         -          ** value in variable pColl.
   665         -          */
   666         -          assert(pX->pLeft);
   667         -          pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
   668         -          if( pColl==0 ) pColl = pParse->db->pDfltColl;
   669         -  
   670         -          for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
   671         -            if( NEVER(j>=pIdx->nColumn) ) return 0;
          653  +  aEquiv[0] = iCur;
          654  +  aEquiv[1] = iColumn;
          655  +  for(;;){
          656  +    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
          657  +      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
          658  +        if( pTerm->leftCursor==iCur
          659  +          && pTerm->u.leftColumn==iColumn
          660  +          && (pTerm->eOperator & op & WO_ALL)!=0
          661  +        ){
          662  +          if( (pTerm->prereqRight & notReady)==0 ){
          663  +            if( iColumn>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
          664  +              CollSeq *pColl;
          665  +              char idxaff;
          666  +      
          667  +              pX = pTerm->pExpr;
          668  +              pParse = pWC->pParse;
          669  +              idxaff = pIdx->pTable->aCol[iColumn].affinity;
          670  +              if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
          671  +      
          672  +              /* Figure out the collation sequence required from an index for
          673  +              ** it to be useful for optimising expression pX. Store this
          674  +              ** value in variable pColl.
          675  +              */
          676  +              assert(pX->pLeft);
          677  +              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
          678  +              if( pColl==0 ) pColl = pParse->db->pDfltColl;
          679  +      
          680  +              for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
          681  +                if( NEVER(j>=pIdx->nColumn) ) return 0;
          682  +              }
          683  +              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
          684  +            }
          685  +            pResult = pTerm;
          686  +            if( pTerm->prereqRight==0 ) goto findTerm_success;
          687  +          }
          688  +          if( (op&WO_EQ)!=0
          689  +           && (pTerm->eOperator & WO_EQUIV)!=0
          690  +           && nEquiv<ArraySize(aEquiv)
          691  +          ){
          692  +            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
          693  +            assert( pX->op==TK_COLUMN );
          694  +            for(j=0; j<nEquiv; j+=2){
          695  +              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
          696  +            }
          697  +            if( j==nEquiv ){
          698  +              aEquiv[j] = pX->iTable;
          699  +              aEquiv[j+1] = pX->iColumn;
          700  +              nEquiv += 2;
          701  +            }
   672    702             }
   673         -          if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
   674    703           }
   675         -        return pTerm;
   676    704         }
   677    705       }
          706  +    if( iEquiv>=nEquiv ) break;
          707  +    iCur = aEquiv[iEquiv++];
          708  +    iColumn = aEquiv[iEquiv++];
          709  +    op &= WO_EQ;
   678    710     }
   679         -  return 0;
          711  +findTerm_success:
          712  +  return pResult;
   680    713   }
   681    714   
   682    715   /* Forward reference */
   683    716   static void exprAnalyze(SrcList*, WhereClause*, int);
   684    717   
   685    718   /*
   686    719   ** Call exprAnalyze on all terms in a WHERE clause.  
................................................................................
   989   1022         Bitmask b;
   990   1023         b = getMask(pMaskSet, pOrTerm->leftCursor);
   991   1024         if( pOrTerm->wtFlags & TERM_VIRTUAL ){
   992   1025           WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
   993   1026           b |= getMask(pMaskSet, pOther->leftCursor);
   994   1027         }
   995   1028         indexable &= b;
   996         -      if( pOrTerm->eOperator!=WO_EQ ){
         1029  +      if( (pOrTerm->eOperator & WO_EQ)==0 ){
   997   1030           chngToIN = 0;
   998   1031         }else{
   999   1032           chngToIN &= b;
  1000   1033         }
  1001   1034       }
  1002   1035     }
  1003   1036   
................................................................................
  1040   1073       ** will be recorded in iCursor and iColumn.  There might not be any
  1041   1074       ** such table and column.  Set okToChngToIN if an appropriate table
  1042   1075       ** and column is found but leave okToChngToIN false if not found.
  1043   1076       */
  1044   1077       for(j=0; j<2 && !okToChngToIN; j++){
  1045   1078         pOrTerm = pOrWc->a;
  1046   1079         for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
  1047         -        assert( pOrTerm->eOperator==WO_EQ );
         1080  +        assert( pOrTerm->eOperator & WO_EQ );
  1048   1081           pOrTerm->wtFlags &= ~TERM_OR_OK;
  1049   1082           if( pOrTerm->leftCursor==iCursor ){
  1050   1083             /* This is the 2-bit case and we are on the second iteration and
  1051   1084             ** current term is from the first iteration.  So skip this term. */
  1052   1085             assert( j==1 );
  1053   1086             continue;
  1054   1087           }
................................................................................
  1066   1099           iCursor = pOrTerm->leftCursor;
  1067   1100           break;
  1068   1101         }
  1069   1102         if( i<0 ){
  1070   1103           /* No candidate table+column was found.  This can only occur
  1071   1104           ** on the second iteration */
  1072   1105           assert( j==1 );
  1073         -        assert( (chngToIN&(chngToIN-1))==0 );
         1106  +        assert( IsPowerOfTwo(chngToIN) );
  1074   1107           assert( chngToIN==getMask(pMaskSet, iCursor) );
  1075   1108           break;
  1076   1109         }
  1077   1110         testcase( j==1 );
  1078   1111   
  1079   1112         /* We have found a candidate table and column.  Check to see if that
  1080   1113         ** table and column is common to every term in the OR clause */
  1081   1114         okToChngToIN = 1;
  1082   1115         for(; i>=0 && okToChngToIN; i--, pOrTerm++){
  1083         -        assert( pOrTerm->eOperator==WO_EQ );
         1116  +        assert( pOrTerm->eOperator & WO_EQ );
  1084   1117           if( pOrTerm->leftCursor!=iCursor ){
  1085   1118             pOrTerm->wtFlags &= ~TERM_OR_OK;
  1086   1119           }else if( pOrTerm->u.leftColumn!=iColumn ){
  1087   1120             okToChngToIN = 0;
  1088   1121           }else{
  1089   1122             int affLeft, affRight;
  1090   1123             /* If the right-hand side is also a column, then the affinities
................................................................................
  1112   1145         Expr *pDup;            /* A transient duplicate expression */
  1113   1146         ExprList *pList = 0;   /* The RHS of the IN operator */
  1114   1147         Expr *pLeft = 0;       /* The LHS of the IN operator */
  1115   1148         Expr *pNew;            /* The complete IN operator */
  1116   1149   
  1117   1150         for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
  1118   1151           if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
  1119         -        assert( pOrTerm->eOperator==WO_EQ );
         1152  +        assert( pOrTerm->eOperator & WO_EQ );
  1120   1153           assert( pOrTerm->leftCursor==iCursor );
  1121   1154           assert( pOrTerm->u.leftColumn==iColumn );
  1122   1155           pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
  1123   1156           pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
  1124   1157           pLeft = pOrTerm->pExpr->pLeft;
  1125   1158         }
  1126   1159         assert( pLeft!=0 );
................................................................................
  1142   1175         }
  1143   1176         pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
  1144   1177       }
  1145   1178     }
  1146   1179   }
  1147   1180   #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
  1148   1181   
         1182  +/*
         1183  +** Check to see if pExpr is an expression of the form A==B where both
         1184  +** A and B are columns with the same affinity and collating sequence.
         1185  +** If A and B are equivalent, return true.
         1186  +*/
         1187  +static int isEquivalenceExpr(Parse *pParse, Expr *pExpr){
         1188  +  const CollSeq *pCLeft, *pCRight;
         1189  +  if( pExpr->op!=TK_EQ ) return 0;
         1190  +  if( ExprHasProperty(pExpr, EP_FromJoin) ) return 0;
         1191  +  assert( sqlite3ExprSkipCollate(pExpr->pRight)->op==TK_COLUMN );
         1192  +  assert( sqlite3ExprSkipCollate(pExpr->pLeft)->op==TK_COLUMN );
         1193  +  if( sqlite3ExprAffinity(pExpr->pLeft)!=sqlite3ExprAffinity(pExpr->pRight) ){
         1194  +    return 0;
         1195  +  }
         1196  +  pCLeft = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
         1197  +  if( pCLeft ){
         1198  +    pCRight = sqlite3ExprCollSeq(pParse, pExpr->pRight);
         1199  +    if( pCRight && pCRight!=pCLeft ) return 0;
         1200  +  }
         1201  +  return 1;
         1202  +}
  1149   1203   
  1150   1204   /*
  1151   1205   ** The input to this routine is an WhereTerm structure with only the
  1152   1206   ** "pExpr" field filled in.  The job of this routine is to analyze the
  1153   1207   ** subexpression and populate all the other fields of the WhereTerm
  1154   1208   ** structure.
  1155   1209   **
................................................................................
  1222   1276         pTerm->leftCursor = pLeft->iTable;
  1223   1277         pTerm->u.leftColumn = pLeft->iColumn;
  1224   1278         pTerm->eOperator = operatorMask(op);
  1225   1279       }
  1226   1280       if( pRight && pRight->op==TK_COLUMN ){
  1227   1281         WhereTerm *pNew;
  1228   1282         Expr *pDup;
         1283  +      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
  1229   1284         if( pTerm->leftCursor>=0 ){
  1230   1285           int idxNew;
  1231   1286           pDup = sqlite3ExprDup(db, pExpr, 0);
  1232   1287           if( db->mallocFailed ){
  1233   1288             sqlite3ExprDelete(db, pDup);
  1234   1289             return;
  1235   1290           }
................................................................................
  1236   1291           idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
  1237   1292           if( idxNew==0 ) return;
  1238   1293           pNew = &pWC->a[idxNew];
  1239   1294           pNew->iParent = idxTerm;
  1240   1295           pTerm = &pWC->a[idxTerm];
  1241   1296           pTerm->nChild = 1;
  1242   1297           pTerm->wtFlags |= TERM_COPIED;
         1298  +        if( isEquivalenceExpr(pParse, pExpr) ){
         1299  +          pTerm->eOperator |= WO_EQUIV;
         1300  +          eExtraOp = WO_EQUIV;
         1301  +        }
  1243   1302         }else{
  1244   1303           pDup = pExpr;
  1245   1304           pNew = pTerm;
  1246   1305         }
  1247   1306         exprCommute(pParse, pDup);
  1248   1307         pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
  1249   1308         pNew->leftCursor = pLeft->iTable;
  1250   1309         pNew->u.leftColumn = pLeft->iColumn;
  1251   1310         testcase( (prereqLeft | extraRight) != prereqLeft );
  1252   1311         pNew->prereqRight = prereqLeft | extraRight;
  1253   1312         pNew->prereqAll = prereqAll;
  1254         -      pNew->eOperator = operatorMask(pDup->op);
         1313  +      pNew->eOperator = operatorMask(pDup->op) + eExtraOp;
  1255   1314       }
  1256   1315     }
  1257   1316   
  1258   1317   #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  1259   1318     /* If a term is the BETWEEN operator, create two new virtual terms
  1260   1319     ** that define the range that the BETWEEN implements.  For example:
  1261   1320     **
................................................................................
  1706   1765     }
  1707   1766     if( pWC->wctrlFlags & WHERE_AND_ONLY ){
  1708   1767       return;
  1709   1768     }
  1710   1769   
  1711   1770     /* Search the WHERE clause terms for a usable WO_OR term. */
  1712   1771     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1713         -    if( pTerm->eOperator==WO_OR 
         1772  +    if( (pTerm->eOperator & WO_OR)!=0
  1714   1773        && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
  1715   1774        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
  1716   1775       ){
  1717   1776         WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
  1718   1777         WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
  1719   1778         WhereTerm *pOrTerm;
  1720   1779         int flags = WHERE_MULTI_OR;
................................................................................
  1727   1786         sBOI.pOrderBy = 0;
  1728   1787         sBOI.pDistinct = 0;
  1729   1788         sBOI.ppIdxInfo = 0;
  1730   1789         for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
  1731   1790           WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
  1732   1791             (pOrTerm - pOrWC->a), (pTerm - pWC->a)
  1733   1792           ));
  1734         -        if( pOrTerm->eOperator==WO_AND ){
         1793  +        if( (pOrTerm->eOperator& WO_AND)!=0 ){
  1735   1794             sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
  1736   1795             bestIndex(&sBOI);
  1737   1796           }else if( pOrTerm->leftCursor==iCur ){
  1738   1797             WhereClause tempWC;
  1739   1798             tempWC.pParse = pWC->pParse;
  1740   1799             tempWC.pMaskSet = pWC->pMaskSet;
  1741   1800             tempWC.pOuter = pWC;
................................................................................
  1788   1847   static int termCanDriveIndex(
  1789   1848     WhereTerm *pTerm,              /* WHERE clause term to check */
  1790   1849     struct SrcList_item *pSrc,     /* Table we are trying to access */
  1791   1850     Bitmask notReady               /* Tables in outer loops of the join */
  1792   1851   ){
  1793   1852     char aff;
  1794   1853     if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  1795         -  if( pTerm->eOperator!=WO_EQ ) return 0;
         1854  +  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  1796   1855     if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  1797   1856     aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  1798   1857     if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  1799   1858     return 1;
  1800   1859   }
  1801   1860   #endif
  1802   1861   
................................................................................
  2050   2109   
  2051   2110     WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
  2052   2111   
  2053   2112     /* Count the number of possible WHERE clause constraints referring
  2054   2113     ** to this virtual table */
  2055   2114     for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  2056   2115       if( pTerm->leftCursor != pSrc->iCursor ) continue;
  2057         -    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
  2058         -    testcase( pTerm->eOperator==WO_IN );
  2059         -    testcase( pTerm->eOperator==WO_ISNULL );
         2116  +    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
         2117  +    testcase( pTerm->eOperator & WO_IN );
         2118  +    testcase( pTerm->eOperator & WO_ISNULL );
  2060   2119       if( pTerm->eOperator & (WO_ISNULL) ) continue;
  2061   2120       if( pTerm->wtFlags & TERM_VNULL ) continue;
  2062   2121       nTerm++;
  2063   2122     }
  2064   2123   
  2065   2124     /* If the ORDER BY clause contains only columns in the current 
  2066   2125     ** virtual table then allocate space for the aOrderBy part of
................................................................................
  2103   2162     *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  2104   2163     *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
  2105   2164                                                                      pUsage;
  2106   2165   
  2107   2166     for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  2108   2167       u8 op;
  2109   2168       if( pTerm->leftCursor != pSrc->iCursor ) continue;
  2110         -    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
  2111         -    testcase( pTerm->eOperator==WO_IN );
  2112         -    testcase( pTerm->eOperator==WO_ISNULL );
         2169  +    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
         2170  +    testcase( pTerm->eOperator & WO_IN );
         2171  +    testcase( pTerm->eOperator & WO_ISNULL );
  2113   2172       if( pTerm->eOperator & (WO_ISNULL) ) continue;
  2114   2173       if( pTerm->wtFlags & TERM_VNULL ) continue;
  2115   2174       pIdxCons[j].iColumn = pTerm->u.leftColumn;
  2116   2175       pIdxCons[j].iTermOffset = i;
  2117         -    op = (u8)pTerm->eOperator;
         2176  +    op = (u8)pTerm->eOperator & WO_ALL;
  2118   2177       if( op==WO_IN ) op = WO_EQ;
  2119   2178       pIdxCons[j].op = op;
  2120   2179       /* The direct assignment in the previous line is possible only because
  2121   2180       ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
  2122   2181       ** following asserts verify this fact. */
  2123   2182       assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
  2124   2183       assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
................................................................................
  2280   2339       */
  2281   2340       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2282   2341       pUsage = pIdxInfo->aConstraintUsage;
  2283   2342       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2284   2343         j = pIdxCons->iTermOffset;
  2285   2344         pTerm = &pWC->a[j];
  2286   2345         if( (pTerm->prereqRight&p->notReady)==0
  2287         -       && (bAllowIN || pTerm->eOperator!=WO_IN)
         2346  +       && (bAllowIN || (pTerm->eOperator & WO_IN)==0)
  2288   2347         ){
  2289   2348           pIdxCons->usable = 1;
  2290   2349         }else{
  2291   2350           pIdxCons->usable = 0;
  2292   2351         }
  2293   2352       }
  2294   2353       memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
................................................................................
  2312   2371     
  2313   2372       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2314   2373       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2315   2374         if( pUsage[i].argvIndex>0 ){
  2316   2375           j = pIdxCons->iTermOffset;
  2317   2376           pTerm = &pWC->a[j];
  2318   2377           p->cost.used |= pTerm->prereqRight;
  2319         -        if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){
         2378  +        if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
  2320   2379             /* Do not attempt to use an IN constraint if the virtual table
  2321   2380             ** says that the equivalent EQ constraint cannot be safely omitted.
  2322   2381             ** If we do attempt to use such a constraint, some rows might be
  2323   2382             ** repeated in the output. */
  2324   2383             break;
  2325   2384           }
  2326   2385         }
................................................................................
  2618   2677       tRowcnt iUpper = p->aiRowEst[0];
  2619   2678       tRowcnt a[2];
  2620   2679       u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2621   2680   
  2622   2681       if( pLower ){
  2623   2682         Expr *pExpr = pLower->pExpr->pRight;
  2624   2683         rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2625         -      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
         2684  +      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
  2626   2685         if( rc==SQLITE_OK
  2627   2686          && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
  2628   2687         ){
  2629   2688           iLower = a[0];
  2630         -        if( pLower->eOperator==WO_GT ) iLower += a[1];
         2689  +        if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
  2631   2690         }
  2632   2691         sqlite3ValueFree(pRangeVal);
  2633   2692       }
  2634   2693       if( rc==SQLITE_OK && pUpper ){
  2635   2694         Expr *pExpr = pUpper->pExpr->pRight;
  2636   2695         rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2637         -      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
         2696  +      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
  2638   2697         if( rc==SQLITE_OK
  2639   2698          && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
  2640   2699         ){
  2641   2700           iUpper = a[0];
  2642         -        if( pUpper->eOperator==WO_LE ) iUpper += a[1];
         2701  +        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
  2643   2702         }
  2644   2703         sqlite3ValueFree(pRangeVal);
  2645   2704       }
  2646   2705       if( rc==SQLITE_OK ){
  2647   2706         if( iUpper<=iLower ){
  2648   2707           *pRangeDiv = (double)p->aiRowEst[0];
  2649   2708         }else{
................................................................................
  2943   3002   
  2944   3003       /* If X is the column in the index and ORDER BY clause, check to see
  2945   3004       ** if there are any X= or X IS NULL constraints in the WHERE clause. */
  2946   3005       pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
  2947   3006                              WO_EQ|WO_ISNULL|WO_IN, pIdx);
  2948   3007       if( pConstraint==0 ){
  2949   3008         isEq = 0;
  2950         -    }else if( pConstraint->eOperator==WO_IN ){
         3009  +    }else if( (pConstraint->eOperator & WO_IN)!=0 ){
  2951   3010         /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
  2952   3011         ** because we do not know in what order the values on the RHS of the IN
  2953   3012         ** operator will occur. */
  2954   3013         break;
  2955         -    }else if( pConstraint->eOperator==WO_ISNULL ){
         3014  +    }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
  2956   3015         uniqueNotNull = 0;
  2957   3016         isEq = 1;  /* "X IS NULL" means X has only a single value */
  2958   3017       }else if( pConstraint->prereqRight==0 ){
  2959   3018         isEq = 1;  /* Constraint "X=constant" means X has only a single value */
  2960   3019       }else{
  2961   3020         Expr *pRight = pConstraint->pExpr->pRight;
  2962   3021         if( pRight->op==TK_COLUMN ){
................................................................................
  3361   3420       ** to get a better estimate on the number of rows based on
  3362   3421       ** VALUE and how common that value is according to the histogram.
  3363   3422       */
  3364   3423       if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
  3365   3424        && pFirstTerm!=0 && aiRowEst[1]>1 ){
  3366   3425         assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
  3367   3426         if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
  3368         -        testcase( pFirstTerm->eOperator==WO_EQ );
  3369         -        testcase( pFirstTerm->eOperator==WO_ISNULL );
         3427  +        testcase( pFirstTerm->eOperator & WO_EQ );
         3428  +        testcase( pFirstTerm->eOperator & WO_EQUIV );
         3429  +        testcase( pFirstTerm->eOperator & WO_ISNULL );
  3370   3430           whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
  3371   3431                             &pc.plan.nRow);
  3372   3432         }else if( bInEst==0 ){
  3373         -        assert( pFirstTerm->eOperator==WO_IN );
         3433  +        assert( pFirstTerm->eOperator & WO_IN );
  3374   3434           whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
  3375   3435                          &pc.plan.nRow);
  3376   3436         }
  3377   3437       }
  3378   3438   #endif /* SQLITE_ENABLE_STAT3 */
  3379   3439   
  3380   3440       /* Adjust the number of output rows and downward to reflect rows
................................................................................
  3513   3573               ** set size by a factor of 3.  Indexed range constraints reduce
  3514   3574               ** the search space by a larger factor: 4.  We make indexed range
  3515   3575               ** more selective intentionally because of the subjective 
  3516   3576               ** observation that indexed range constraints really are more
  3517   3577               ** selective in practice, on average. */
  3518   3578               pc.plan.nRow /= 3;
  3519   3579             }
  3520         -        }else if( pTerm->eOperator!=WO_NOOP ){
         3580  +        }else if( (pTerm->eOperator & WO_NOOP)==0 ){
  3521   3581             /* Any other expression lowers the output row count by half */
  3522   3582             pc.plan.nRow /= 2;
  3523   3583           }
  3524   3584         }
  3525   3585         if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3526   3586       }
  3527   3587   
................................................................................
  4149   4209       **          we reference multiple rows using a "rowid IN (...)"
  4150   4210       **          construct.
  4151   4211       */
  4152   4212       iReleaseReg = sqlite3GetTempReg(pParse);
  4153   4213       pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  4154   4214       assert( pTerm!=0 );
  4155   4215       assert( pTerm->pExpr!=0 );
  4156         -    assert( pTerm->leftCursor==iCur );
  4157   4216       assert( omitTable==0 );
  4158   4217       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  4159   4218       iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
  4160   4219       addrNxt = pLevel->addrNxt;
  4161   4220       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
  4162   4221       sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
  4163   4222       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
................................................................................
  4540   4599       int iRetInit;                             /* Address of regReturn init */
  4541   4600       int untestedTerms = 0;             /* Some terms not completely tested */
  4542   4601       int ii;                            /* Loop counter */
  4543   4602       Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  4544   4603      
  4545   4604       pTerm = pLevel->plan.u.pTerm;
  4546   4605       assert( pTerm!=0 );
  4547         -    assert( pTerm->eOperator==WO_OR );
         4606  +    assert( pTerm->eOperator & WO_OR );
  4548   4607       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  4549   4608       pOrWc = &pTerm->u.pOrInfo->wc;
  4550   4609       pLevel->op = OP_Return;
  4551   4610       pLevel->p1 = regReturn;
  4552   4611   
  4553   4612       /* Set up a new SrcList in pOrTab containing the table being scanned
  4554   4613       ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
................................................................................
  4613   4672         if( pAndExpr ){
  4614   4673           pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
  4615   4674         }
  4616   4675       }
  4617   4676   
  4618   4677       for(ii=0; ii<pOrWc->nTerm; ii++){
  4619   4678         WhereTerm *pOrTerm = &pOrWc->a[ii];
  4620         -      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
         4679  +      if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
  4621   4680           WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
  4622   4681           Expr *pOrExpr = pOrTerm->pExpr;
  4623   4682           if( pAndExpr ){
  4624   4683             pAndExpr->pLeft = pOrExpr;
  4625   4684             pOrExpr = pAndExpr;
  4626   4685           }
  4627   4686           /* Loop through table entries that match term pOrTerm. */