/ Check-in [38852f15]
Login

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

Overview
Comment:Enhance the query planner to exploit transitivity of join constraints.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 38852f158ab20bb4d7b264af987ec1538052bec3
User & Date: drh 2013-01-17 17:20:49
References
2014-01-20
19:15 New ticket [1a1a194d] Assertion fault on query of virtual table with cross-column constraints. artifact: ce84c752 user: drh
2013-07-08
18:02 New ticket [d805526e] Incorrect join result or assertion fault due to transitive constraints. artifact: d1fbaa0a user: drh
Context
2013-01-18
03:35
The \xXX escape in the test_regexp.c must be followed by exactly two hex digits. check-in: 82957495 user: drh tags: trunk
2013-01-17
17:20
Enhance the query planner to exploit transitivity of join constraints. check-in: 38852f15 user: drh tags: trunk
17:05
Improved error messages on the RTREE virtual table. Make the "fs" virtual table used for testing available on windows. check-in: c0b90d75 user: drh tags: trunk
16:43
Add the ability to disable transitive constraints using the sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS) interface. Closed-Leaf check-in: 593d67c8 user: drh tags: transitive-constraints
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.
................................................................................
   969    974   #define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
   970    975   #define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
   971    976   #define SQLITE_IdxRealAsInt   0x0010   /* Store REAL as INT in indices */
   972    977   #define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
   973    978   #define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
   974    979   #define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
   975    980   #define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
          981  +#define SQLITE_Transitive     0x0200   /* Transitive constraints */
   976    982   #define SQLITE_AllOpts        0xffff   /* All optimizations */
   977    983   
   978    984   /*
   979    985   ** Macros for testing whether or not optimizations are enabled or disabled.
   980    986   */
   981    987   #ifndef SQLITE_OMIT_BUILTIN_TEST
   982    988   #define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)

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
................................................................................
   625    626   }
   626    627   
   627    628   /*
   628    629   ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
   629    630   ** where X is a reference to the iColumn of table iCur and <op> is one of
   630    631   ** the WO_xx operator codes specified by the op parameter.
   631    632   ** Return a pointer to the term.  Return 0 if not found.
          633  +**
          634  +** The term returned might by Y=<expr> if there is another constraint in
          635  +** the WHERE clause that specifies that X=Y.  Any such constraints will be
          636  +** identified by the WO_EQUIV bit in the pTerm->eOperator field.  The
          637  +** aEquiv[] array holds X and all its equivalents, with each SQL variable
          638  +** taking up two slots in aEquiv[].  The first slot is for the cursor number
          639  +** and the second is for the column number.  There are 22 slots in aEquiv[]
          640  +** so that means we can look for X plus up to 10 other equivalent values.
          641  +** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
          642  +** and ... and A9=A10 and A10=<expr>.
          643  +**
          644  +** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
          645  +** then try for the one with no dependencies on <expr> - in other words where
          646  +** <expr> is a constant expression of some kind.  Only return entries of
          647  +** the form "X <op> Y" where Y is a column in another table if no terms of
          648  +** the form "X <op> <const-expr>" exist.  Other than this priority, if there
          649  +** are two or more terms that match, then the choice of which term to return
          650  +** is arbitrary.
   632    651   */
   633    652   static WhereTerm *findTerm(
   634    653     WhereClause *pWC,     /* The WHERE clause to be searched */
   635    654     int iCur,             /* Cursor number of LHS */
   636    655     int iColumn,          /* Column number of LHS */
   637    656     Bitmask notReady,     /* RHS must not overlap with this mask */
   638    657     u32 op,               /* Mask of WO_xx values describing operator */
   639    658     Index *pIdx           /* Must be compatible with this index, if not NULL */
   640    659   ){
   641         -  WhereTerm *pTerm;
   642         -  int k;
          660  +  WhereTerm *pTerm;            /* Term being examined as possible result */
          661  +  WhereTerm *pResult = 0;      /* The answer to return */
          662  +  WhereClause *pWCOrig = pWC;  /* Original pWC value */
          663  +  int j, k;                    /* Loop counters */
          664  +  Expr *pX;                /* Pointer to an expression */
          665  +  Parse *pParse;           /* Parsing context */
          666  +  int iOrigCol = iColumn;  /* Original value of iColumn */
          667  +  int nEquiv = 2;          /* Number of entires in aEquiv[] */
          668  +  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
          669  +  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */
          670  +
   643    671     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;
          672  +  aEquiv[0] = iCur;
          673  +  aEquiv[1] = iColumn;
          674  +  for(;;){
          675  +    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
          676  +      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
          677  +        if( pTerm->leftCursor==iCur
          678  +          && pTerm->u.leftColumn==iColumn
          679  +        ){
          680  +          if( (pTerm->prereqRight & notReady)==0
          681  +           && (pTerm->eOperator & op & WO_ALL)!=0
          682  +          ){
          683  +            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
          684  +              CollSeq *pColl;
          685  +              char idxaff;
          686  +      
          687  +              pX = pTerm->pExpr;
          688  +              pParse = pWC->pParse;
          689  +              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
          690  +              if( !sqlite3IndexAffinityOk(pX, idxaff) ){
          691  +                continue;
          692  +              }
          693  +      
          694  +              /* Figure out the collation sequence required from an index for
          695  +              ** it to be useful for optimising expression pX. Store this
          696  +              ** value in variable pColl.
          697  +              */
          698  +              assert(pX->pLeft);
          699  +              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
          700  +              if( pColl==0 ) pColl = pParse->db->pDfltColl;
          701  +      
          702  +              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
          703  +                if( NEVER(j>=pIdx->nColumn) ) return 0;
          704  +              }
          705  +              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
          706  +                continue;
          707  +              }
          708  +            }
          709  +            pResult = pTerm;
          710  +            if( pTerm->prereqRight==0 ) goto findTerm_success;
          711  +          }
          712  +          if( (pTerm->eOperator & WO_EQUIV)!=0
          713  +           && nEquiv<ArraySize(aEquiv)
          714  +          ){
          715  +            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
          716  +            assert( pX->op==TK_COLUMN );
          717  +            for(j=0; j<nEquiv; j+=2){
          718  +              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
          719  +            }
          720  +            if( j==nEquiv ){
          721  +              aEquiv[j] = pX->iTable;
          722  +              aEquiv[j+1] = pX->iColumn;
          723  +              nEquiv += 2;
          724  +            }
   672    725             }
   673         -          if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
   674    726           }
   675         -        return pTerm;
   676    727         }
   677    728       }
          729  +    if( iEquiv>=nEquiv ) break;
          730  +    iCur = aEquiv[iEquiv++];
          731  +    iColumn = aEquiv[iEquiv++];
   678    732     }
   679         -  return 0;
          733  +findTerm_success:
          734  +  return pResult;
   680    735   }
   681    736   
   682    737   /* Forward reference */
   683    738   static void exprAnalyze(SrcList*, WhereClause*, int);
   684    739   
   685    740   /*
   686    741   ** Call exprAnalyze on all terms in a WHERE clause.  
................................................................................
   950   1005     ** Compute the set of tables that might satisfy cases 1 or 2.
   951   1006     */
   952   1007     indexable = ~(Bitmask)0;
   953   1008     chngToIN = ~(pWC->vmask);
   954   1009     for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
   955   1010       if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
   956   1011         WhereAndInfo *pAndInfo;
   957         -      assert( pOrTerm->eOperator==0 );
   958   1012         assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
   959   1013         chngToIN = 0;
   960   1014         pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
   961   1015         if( pAndInfo ){
   962   1016           WhereClause *pAndWC;
   963   1017           WhereTerm *pAndTerm;
   964   1018           int j;
................................................................................
   989   1043         Bitmask b;
   990   1044         b = getMask(pMaskSet, pOrTerm->leftCursor);
   991   1045         if( pOrTerm->wtFlags & TERM_VIRTUAL ){
   992   1046           WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
   993   1047           b |= getMask(pMaskSet, pOther->leftCursor);
   994   1048         }
   995   1049         indexable &= b;
   996         -      if( pOrTerm->eOperator!=WO_EQ ){
         1050  +      if( (pOrTerm->eOperator & WO_EQ)==0 ){
   997   1051           chngToIN = 0;
   998   1052         }else{
   999   1053           chngToIN &= b;
  1000   1054         }
  1001   1055       }
  1002   1056     }
  1003   1057   
................................................................................
  1040   1094       ** will be recorded in iCursor and iColumn.  There might not be any
  1041   1095       ** such table and column.  Set okToChngToIN if an appropriate table
  1042   1096       ** and column is found but leave okToChngToIN false if not found.
  1043   1097       */
  1044   1098       for(j=0; j<2 && !okToChngToIN; j++){
  1045   1099         pOrTerm = pOrWc->a;
  1046   1100         for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
  1047         -        assert( pOrTerm->eOperator==WO_EQ );
         1101  +        assert( pOrTerm->eOperator & WO_EQ );
  1048   1102           pOrTerm->wtFlags &= ~TERM_OR_OK;
  1049   1103           if( pOrTerm->leftCursor==iCursor ){
  1050   1104             /* This is the 2-bit case and we are on the second iteration and
  1051   1105             ** current term is from the first iteration.  So skip this term. */
  1052   1106             assert( j==1 );
  1053   1107             continue;
  1054   1108           }
................................................................................
  1066   1120           iCursor = pOrTerm->leftCursor;
  1067   1121           break;
  1068   1122         }
  1069   1123         if( i<0 ){
  1070   1124           /* No candidate table+column was found.  This can only occur
  1071   1125           ** on the second iteration */
  1072   1126           assert( j==1 );
  1073         -        assert( (chngToIN&(chngToIN-1))==0 );
         1127  +        assert( IsPowerOfTwo(chngToIN) );
  1074   1128           assert( chngToIN==getMask(pMaskSet, iCursor) );
  1075   1129           break;
  1076   1130         }
  1077   1131         testcase( j==1 );
  1078   1132   
  1079   1133         /* We have found a candidate table and column.  Check to see if that
  1080   1134         ** table and column is common to every term in the OR clause */
  1081   1135         okToChngToIN = 1;
  1082   1136         for(; i>=0 && okToChngToIN; i--, pOrTerm++){
  1083         -        assert( pOrTerm->eOperator==WO_EQ );
         1137  +        assert( pOrTerm->eOperator & WO_EQ );
  1084   1138           if( pOrTerm->leftCursor!=iCursor ){
  1085   1139             pOrTerm->wtFlags &= ~TERM_OR_OK;
  1086   1140           }else if( pOrTerm->u.leftColumn!=iColumn ){
  1087   1141             okToChngToIN = 0;
  1088   1142           }else{
  1089   1143             int affLeft, affRight;
  1090   1144             /* If the right-hand side is also a column, then the affinities
................................................................................
  1112   1166         Expr *pDup;            /* A transient duplicate expression */
  1113   1167         ExprList *pList = 0;   /* The RHS of the IN operator */
  1114   1168         Expr *pLeft = 0;       /* The LHS of the IN operator */
  1115   1169         Expr *pNew;            /* The complete IN operator */
  1116   1170   
  1117   1171         for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
  1118   1172           if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
  1119         -        assert( pOrTerm->eOperator==WO_EQ );
         1173  +        assert( pOrTerm->eOperator & WO_EQ );
  1120   1174           assert( pOrTerm->leftCursor==iCursor );
  1121   1175           assert( pOrTerm->u.leftColumn==iColumn );
  1122   1176           pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
  1123   1177           pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
  1124   1178           pLeft = pOrTerm->pExpr->pLeft;
  1125   1179         }
  1126   1180         assert( pLeft!=0 );
................................................................................
  1141   1195           sqlite3ExprListDelete(db, pList);
  1142   1196         }
  1143   1197         pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
  1144   1198       }
  1145   1199     }
  1146   1200   }
  1147   1201   #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
  1148         -
  1149   1202   
  1150   1203   /*
  1151   1204   ** The input to this routine is an WhereTerm structure with only the
  1152   1205   ** "pExpr" field filled in.  The job of this routine is to analyze the
  1153   1206   ** subexpression and populate all the other fields of the WhereTerm
  1154   1207   ** structure.
  1155   1208   **
................................................................................
  1211   1264       extraRight = x-1;  /* ON clause terms may not be used with an index
  1212   1265                          ** on left table of a LEFT JOIN.  Ticket #3015 */
  1213   1266     }
  1214   1267     pTerm->prereqAll = prereqAll;
  1215   1268     pTerm->leftCursor = -1;
  1216   1269     pTerm->iParent = -1;
  1217   1270     pTerm->eOperator = 0;
  1218         -  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
         1271  +  if( allowedOp(op) ){
  1219   1272       Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
  1220   1273       Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
         1274  +    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
  1221   1275       if( pLeft->op==TK_COLUMN ){
  1222   1276         pTerm->leftCursor = pLeft->iTable;
  1223   1277         pTerm->u.leftColumn = pLeft->iColumn;
  1224         -      pTerm->eOperator = operatorMask(op);
         1278  +      pTerm->eOperator = operatorMask(op) & opMask;
  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( pExpr->op==TK_EQ
         1299  +         && !ExprHasProperty(pExpr, EP_FromJoin)
         1300  +         && OptimizationEnabled(db, SQLITE_Transitive)
         1301  +        ){
         1302  +          pTerm->eOperator |= WO_EQUIV;
         1303  +          eExtraOp = WO_EQUIV;
         1304  +        }
  1243   1305         }else{
  1244   1306           pDup = pExpr;
  1245   1307           pNew = pTerm;
  1246   1308         }
  1247   1309         exprCommute(pParse, pDup);
  1248   1310         pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
  1249   1311         pNew->leftCursor = pLeft->iTable;
  1250   1312         pNew->u.leftColumn = pLeft->iColumn;
  1251   1313         testcase( (prereqLeft | extraRight) != prereqLeft );
  1252   1314         pNew->prereqRight = prereqLeft | extraRight;
  1253   1315         pNew->prereqAll = prereqAll;
  1254         -      pNew->eOperator = operatorMask(pDup->op);
         1316  +      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
  1255   1317       }
  1256   1318     }
  1257   1319   
  1258   1320   #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  1259   1321     /* If a term is the BETWEEN operator, create two new virtual terms
  1260   1322     ** that define the range that the BETWEEN implements.  For example:
  1261   1323     **
................................................................................
  1706   1768     }
  1707   1769     if( pWC->wctrlFlags & WHERE_AND_ONLY ){
  1708   1770       return;
  1709   1771     }
  1710   1772   
  1711   1773     /* Search the WHERE clause terms for a usable WO_OR term. */
  1712   1774     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1713         -    if( pTerm->eOperator==WO_OR 
         1775  +    if( (pTerm->eOperator & WO_OR)!=0
  1714   1776        && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
  1715   1777        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
  1716   1778       ){
  1717   1779         WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
  1718   1780         WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
  1719   1781         WhereTerm *pOrTerm;
  1720   1782         int flags = WHERE_MULTI_OR;
................................................................................
  1727   1789         sBOI.pOrderBy = 0;
  1728   1790         sBOI.pDistinct = 0;
  1729   1791         sBOI.ppIdxInfo = 0;
  1730   1792         for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
  1731   1793           WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
  1732   1794             (pOrTerm - pOrWC->a), (pTerm - pWC->a)
  1733   1795           ));
  1734         -        if( pOrTerm->eOperator==WO_AND ){
         1796  +        if( (pOrTerm->eOperator& WO_AND)!=0 ){
  1735   1797             sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
  1736   1798             bestIndex(&sBOI);
  1737   1799           }else if( pOrTerm->leftCursor==iCur ){
  1738   1800             WhereClause tempWC;
  1739   1801             tempWC.pParse = pWC->pParse;
  1740   1802             tempWC.pMaskSet = pWC->pMaskSet;
  1741   1803             tempWC.pOuter = pWC;
................................................................................
  1788   1850   static int termCanDriveIndex(
  1789   1851     WhereTerm *pTerm,              /* WHERE clause term to check */
  1790   1852     struct SrcList_item *pSrc,     /* Table we are trying to access */
  1791   1853     Bitmask notReady               /* Tables in outer loops of the join */
  1792   1854   ){
  1793   1855     char aff;
  1794   1856     if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  1795         -  if( pTerm->eOperator!=WO_EQ ) return 0;
         1857  +  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  1796   1858     if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  1797   1859     aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  1798   1860     if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  1799   1861     return 1;
  1800   1862   }
  1801   1863   #endif
  1802   1864   
................................................................................
  2050   2112   
  2051   2113     WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
  2052   2114   
  2053   2115     /* Count the number of possible WHERE clause constraints referring
  2054   2116     ** to this virtual table */
  2055   2117     for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  2056   2118       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 );
         2119  +    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
         2120  +    testcase( pTerm->eOperator & WO_IN );
         2121  +    testcase( pTerm->eOperator & WO_ISNULL );
  2060   2122       if( pTerm->eOperator & (WO_ISNULL) ) continue;
  2061   2123       if( pTerm->wtFlags & TERM_VNULL ) continue;
  2062   2124       nTerm++;
  2063   2125     }
  2064   2126   
  2065   2127     /* If the ORDER BY clause contains only columns in the current 
  2066   2128     ** virtual table then allocate space for the aOrderBy part of
................................................................................
  2103   2165     *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  2104   2166     *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
  2105   2167                                                                      pUsage;
  2106   2168   
  2107   2169     for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  2108   2170       u8 op;
  2109   2171       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 );
         2172  +    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
         2173  +    testcase( pTerm->eOperator & WO_IN );
         2174  +    testcase( pTerm->eOperator & WO_ISNULL );
  2113   2175       if( pTerm->eOperator & (WO_ISNULL) ) continue;
  2114   2176       if( pTerm->wtFlags & TERM_VNULL ) continue;
  2115   2177       pIdxCons[j].iColumn = pTerm->u.leftColumn;
  2116   2178       pIdxCons[j].iTermOffset = i;
  2117         -    op = (u8)pTerm->eOperator;
         2179  +    op = (u8)pTerm->eOperator & WO_ALL;
  2118   2180       if( op==WO_IN ) op = WO_EQ;
  2119   2181       pIdxCons[j].op = op;
  2120   2182       /* The direct assignment in the previous line is possible only because
  2121   2183       ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
  2122   2184       ** following asserts verify this fact. */
  2123   2185       assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
  2124   2186       assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
................................................................................
  2280   2342       */
  2281   2343       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2282   2344       pUsage = pIdxInfo->aConstraintUsage;
  2283   2345       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2284   2346         j = pIdxCons->iTermOffset;
  2285   2347         pTerm = &pWC->a[j];
  2286   2348         if( (pTerm->prereqRight&p->notReady)==0
  2287         -       && (bAllowIN || pTerm->eOperator!=WO_IN)
         2349  +       && (bAllowIN || (pTerm->eOperator & WO_IN)==0)
  2288   2350         ){
  2289   2351           pIdxCons->usable = 1;
  2290   2352         }else{
  2291   2353           pIdxCons->usable = 0;
  2292   2354         }
  2293   2355       }
  2294   2356       memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
................................................................................
  2312   2374     
  2313   2375       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2314   2376       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2315   2377         if( pUsage[i].argvIndex>0 ){
  2316   2378           j = pIdxCons->iTermOffset;
  2317   2379           pTerm = &pWC->a[j];
  2318   2380           p->cost.used |= pTerm->prereqRight;
  2319         -        if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){
         2381  +        if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
  2320   2382             /* Do not attempt to use an IN constraint if the virtual table
  2321   2383             ** says that the equivalent EQ constraint cannot be safely omitted.
  2322   2384             ** If we do attempt to use such a constraint, some rows might be
  2323   2385             ** repeated in the output. */
  2324   2386             break;
  2325   2387           }
  2326   2388         }
................................................................................
  2618   2680       tRowcnt iUpper = p->aiRowEst[0];
  2619   2681       tRowcnt a[2];
  2620   2682       u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2621   2683   
  2622   2684       if( pLower ){
  2623   2685         Expr *pExpr = pLower->pExpr->pRight;
  2624   2686         rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2625         -      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
         2687  +      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
  2626   2688         if( rc==SQLITE_OK
  2627   2689          && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
  2628   2690         ){
  2629   2691           iLower = a[0];
  2630         -        if( pLower->eOperator==WO_GT ) iLower += a[1];
         2692  +        if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
  2631   2693         }
  2632   2694         sqlite3ValueFree(pRangeVal);
  2633   2695       }
  2634   2696       if( rc==SQLITE_OK && pUpper ){
  2635   2697         Expr *pExpr = pUpper->pExpr->pRight;
  2636   2698         rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2637         -      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
         2699  +      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
  2638   2700         if( rc==SQLITE_OK
  2639   2701          && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
  2640   2702         ){
  2641   2703           iUpper = a[0];
  2642         -        if( pUpper->eOperator==WO_LE ) iUpper += a[1];
         2704  +        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
  2643   2705         }
  2644   2706         sqlite3ValueFree(pRangeVal);
  2645   2707       }
  2646   2708       if( rc==SQLITE_OK ){
  2647   2709         if( iUpper<=iLower ){
  2648   2710           *pRangeDiv = (double)p->aiRowEst[0];
  2649   2711         }else{
................................................................................
  2943   3005   
  2944   3006       /* If X is the column in the index and ORDER BY clause, check to see
  2945   3007       ** if there are any X= or X IS NULL constraints in the WHERE clause. */
  2946   3008       pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
  2947   3009                              WO_EQ|WO_ISNULL|WO_IN, pIdx);
  2948   3010       if( pConstraint==0 ){
  2949   3011         isEq = 0;
  2950         -    }else if( pConstraint->eOperator==WO_IN ){
         3012  +    }else if( (pConstraint->eOperator & WO_IN)!=0 ){
  2951   3013         /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
  2952   3014         ** because we do not know in what order the values on the RHS of the IN
  2953   3015         ** operator will occur. */
  2954   3016         break;
  2955         -    }else if( pConstraint->eOperator==WO_ISNULL ){
         3017  +    }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
  2956   3018         uniqueNotNull = 0;
  2957   3019         isEq = 1;  /* "X IS NULL" means X has only a single value */
  2958   3020       }else if( pConstraint->prereqRight==0 ){
  2959   3021         isEq = 1;  /* Constraint "X=constant" means X has only a single value */
  2960   3022       }else{
  2961   3023         Expr *pRight = pConstraint->pExpr->pRight;
  2962   3024         if( pRight->op==TK_COLUMN ){
................................................................................
  3361   3423       ** to get a better estimate on the number of rows based on
  3362   3424       ** VALUE and how common that value is according to the histogram.
  3363   3425       */
  3364   3426       if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
  3365   3427        && pFirstTerm!=0 && aiRowEst[1]>1 ){
  3366   3428         assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
  3367   3429         if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
  3368         -        testcase( pFirstTerm->eOperator==WO_EQ );
  3369         -        testcase( pFirstTerm->eOperator==WO_ISNULL );
         3430  +        testcase( pFirstTerm->eOperator & WO_EQ );
         3431  +        testcase( pFirstTerm->eOperator & WO_EQUIV );
         3432  +        testcase( pFirstTerm->eOperator & WO_ISNULL );
  3370   3433           whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
  3371   3434                             &pc.plan.nRow);
  3372   3435         }else if( bInEst==0 ){
  3373         -        assert( pFirstTerm->eOperator==WO_IN );
         3436  +        assert( pFirstTerm->eOperator & WO_IN );
  3374   3437           whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
  3375   3438                          &pc.plan.nRow);
  3376   3439         }
  3377   3440       }
  3378   3441   #endif /* SQLITE_ENABLE_STAT3 */
  3379   3442   
  3380   3443       /* Adjust the number of output rows and downward to reflect rows
................................................................................
  3513   3576               ** set size by a factor of 3.  Indexed range constraints reduce
  3514   3577               ** the search space by a larger factor: 4.  We make indexed range
  3515   3578               ** more selective intentionally because of the subjective 
  3516   3579               ** observation that indexed range constraints really are more
  3517   3580               ** selective in practice, on average. */
  3518   3581               pc.plan.nRow /= 3;
  3519   3582             }
  3520         -        }else if( pTerm->eOperator!=WO_NOOP ){
         3583  +        }else if( (pTerm->eOperator & WO_NOOP)==0 ){
  3521   3584             /* Any other expression lowers the output row count by half */
  3522   3585             pc.plan.nRow /= 2;
  3523   3586           }
  3524   3587         }
  3525   3588         if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3526   3589       }
  3527   3590   
................................................................................
  4149   4212       **          we reference multiple rows using a "rowid IN (...)"
  4150   4213       **          construct.
  4151   4214       */
  4152   4215       iReleaseReg = sqlite3GetTempReg(pParse);
  4153   4216       pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  4154   4217       assert( pTerm!=0 );
  4155   4218       assert( pTerm->pExpr!=0 );
  4156         -    assert( pTerm->leftCursor==iCur );
  4157   4219       assert( omitTable==0 );
  4158   4220       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  4159   4221       iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
  4160   4222       addrNxt = pLevel->addrNxt;
  4161   4223       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
  4162   4224       sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
  4163   4225       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
................................................................................
  4540   4602       int iRetInit;                             /* Address of regReturn init */
  4541   4603       int untestedTerms = 0;             /* Some terms not completely tested */
  4542   4604       int ii;                            /* Loop counter */
  4543   4605       Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  4544   4606      
  4545   4607       pTerm = pLevel->plan.u.pTerm;
  4546   4608       assert( pTerm!=0 );
  4547         -    assert( pTerm->eOperator==WO_OR );
         4609  +    assert( pTerm->eOperator & WO_OR );
  4548   4610       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  4549   4611       pOrWc = &pTerm->u.pOrInfo->wc;
  4550   4612       pLevel->op = OP_Return;
  4551   4613       pLevel->p1 = regReturn;
  4552   4614   
  4553   4615       /* Set up a new SrcList in pOrTab containing the table being scanned
  4554   4616       ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
................................................................................
  4613   4675         if( pAndExpr ){
  4614   4676           pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
  4615   4677         }
  4616   4678       }
  4617   4679   
  4618   4680       for(ii=0; ii<pOrWc->nTerm; ii++){
  4619   4681         WhereTerm *pOrTerm = &pOrWc->a[ii];
  4620         -      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
         4682  +      if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
  4621   4683           WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
  4622   4684           Expr *pOrExpr = pOrTerm->pExpr;
  4623   4685           if( pAndExpr ){
  4624   4686             pAndExpr->pLeft = pOrExpr;
  4625   4687             pOrExpr = pAndExpr;
  4626   4688           }
  4627   4689           /* Loop through table entries that match term pOrTerm. */

Changes to test/autoindex1.test.

   253    253     CREATE TABLE t5(a, b, c);
   254    254     EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
   255    255   } {
   256    256     0 0 0 {SCAN TABLE t5 (~100000 rows)} 
   257    257     0 0 0 {USE TEMP B-TREE FOR ORDER BY}
   258    258   }
   259    259   
          260  +# The following checks a performance issue reported on the sqlite-dev
          261  +# mailing list on 2013-01-10
          262  +#
          263  +do_execsql_test autoindex1-800 {
          264  +  CREATE TABLE accounts(
          265  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          266  +    account_name TEXT,
          267  +    account_type TEXT,
          268  +    data_set TEXT
          269  +  );
          270  +  CREATE TABLE data(
          271  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          272  +    package_id INTEGER REFERENCES package(_id),
          273  +    mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL,
          274  +    raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL,
          275  +    is_read_only INTEGER NOT NULL DEFAULT 0,
          276  +    is_primary INTEGER NOT NULL DEFAULT 0,
          277  +    is_super_primary INTEGER NOT NULL DEFAULT 0,
          278  +    data_version INTEGER NOT NULL DEFAULT 0,
          279  +    data1 TEXT,
          280  +    data2 TEXT,
          281  +    data3 TEXT,
          282  +    data4 TEXT,
          283  +    data5 TEXT,
          284  +    data6 TEXT,
          285  +    data7 TEXT,
          286  +    data8 TEXT,
          287  +    data9 TEXT,
          288  +    data10 TEXT,
          289  +    data11 TEXT,
          290  +    data12 TEXT,
          291  +    data13 TEXT,
          292  +    data14 TEXT,
          293  +    data15 TEXT,
          294  +    data_sync1 TEXT,
          295  +    data_sync2 TEXT,
          296  +    data_sync3 TEXT,
          297  +    data_sync4 TEXT 
          298  +  );
          299  +  CREATE TABLE mimetypes(
          300  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          301  +    mimetype TEXT NOT NULL
          302  +  );
          303  +  CREATE TABLE raw_contacts(
          304  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          305  +    account_id INTEGER REFERENCES accounts(_id),
          306  +    sourceid TEXT,
          307  +    raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0,
          308  +    version INTEGER NOT NULL DEFAULT 1,
          309  +    dirty INTEGER NOT NULL DEFAULT 0,
          310  +    deleted INTEGER NOT NULL DEFAULT 0,
          311  +    contact_id INTEGER REFERENCES contacts(_id),
          312  +    aggregation_mode INTEGER NOT NULL DEFAULT 0,
          313  +    aggregation_needed INTEGER NOT NULL DEFAULT 1,
          314  +    custom_ringtone TEXT,
          315  +    send_to_voicemail INTEGER NOT NULL DEFAULT 0,
          316  +    times_contacted INTEGER NOT NULL DEFAULT 0,
          317  +    last_time_contacted INTEGER,
          318  +    starred INTEGER NOT NULL DEFAULT 0,
          319  +    display_name TEXT,
          320  +    display_name_alt TEXT,
          321  +    display_name_source INTEGER NOT NULL DEFAULT 0,
          322  +    phonetic_name TEXT,
          323  +    phonetic_name_style TEXT,
          324  +    sort_key TEXT,
          325  +    sort_key_alt TEXT,
          326  +    name_verified INTEGER NOT NULL DEFAULT 0,
          327  +    sync1 TEXT,
          328  +    sync2 TEXT,
          329  +    sync3 TEXT,
          330  +    sync4 TEXT,
          331  +    sync_uid TEXT,
          332  +    sync_version INTEGER NOT NULL DEFAULT 1,
          333  +    has_calendar_event INTEGER NOT NULL DEFAULT 0,
          334  +    modified_time INTEGER,
          335  +    is_restricted INTEGER DEFAULT 0,
          336  +    yp_source TEXT,
          337  +    method_selected INTEGER DEFAULT 0,
          338  +    custom_vibration_type INTEGER DEFAULT 0,
          339  +    custom_ringtone_path TEXT,
          340  +    message_notification TEXT,
          341  +    message_notification_path TEXT
          342  +  );
          343  +  CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1);
          344  +  CREATE INDEX data_raw_contact_id ON data (raw_contact_id);
          345  +  CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype);
          346  +  CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key);
          347  +  CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt);
          348  +  CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id);
          349  +  CREATE INDEX raw_contacts_source_id_account_id_index
          350  +      ON raw_contacts (sourceid, account_id);
          351  +  ANALYZE sqlite_master;
          352  +  INSERT INTO sqlite_stat1
          353  +     VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4');
          354  +  INSERT INTO sqlite_stat1
          355  +     VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4');
          356  +  INSERT INTO sqlite_stat1
          357  +     VALUES('raw_contacts','raw_contacts_source_id_account_id_index',
          358  +            '1600 1600 1600');
          359  +  INSERT INTO sqlite_stat1
          360  +     VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1');
          361  +  INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1');
          362  +  INSERT INTO sqlite_stat1
          363  +     VALUES('data','data_mimetype_data1_index','9819 2455 3');
          364  +  INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7');
          365  +  INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1');
          366  +  DROP TABLE IF EXISTS sqlite_stat3;
          367  +  ANALYZE sqlite_master;
          368  +  
          369  +  EXPLAIN QUERY PLAN
          370  +  SELECT * FROM 
          371  +        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
          372  +             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
          373  +             JOIN accounts ON (raw_contacts.account_id=accounts._id)
          374  +   WHERE mimetype_id=10 AND data14 IS NOT NULL;
          375  +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
          376  +do_execsql_test autoindex1-801 {
          377  +  EXPLAIN QUERY PLAN
          378  +  SELECT * FROM 
          379  +        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
          380  +             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
          381  +             JOIN accounts ON (raw_contacts.account_id=accounts._id)
          382  +   WHERE mimetypes._id=10 AND data14 IS NOT NULL;
          383  +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
   260    384   
   261    385   finish_test

Added test/transitive1.test.

            1  +# 2013 April 17
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this script is testing of transitive WHERE clause constraints
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +do_execsql_test transitive1-100 {
           19  +  CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE);
           20  +  INSERT INTO t1 VALUES('abc','abc','Abc');
           21  +  INSERT INTO t1 VALUES('def','def','def');
           22  +  INSERT INTO t1 VALUES('ghi','ghi','GHI');
           23  +  CREATE INDEX t1a1 ON t1(a);
           24  +  CREATE INDEX t1a2 ON t1(a COLLATE nocase);
           25  +
           26  +  SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF';
           27  +} {def def def}
           28  +do_execsql_test transitive1-110 {
           29  +  SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a;
           30  +} {def def def ghi ghi GHI}
           31  +do_execsql_test transitive1-120 {
           32  +  SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a;
           33  +} {abc abc Abc def def def}
           34  +
           35  +do_execsql_test transitive1-200 {
           36  +  CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT);
           37  +  INSERT INTO t2 VALUES(100,100,100);
           38  +  INSERT INTO t2 VALUES(20,20,20);
           39  +  INSERT INTO t2 VALUES(3,3,3);
           40  +
           41  +  SELECT * FROM t2 WHERE a=b AND c=b AND c=20;
           42  +} {20 20 20}
           43  +do_execsql_test transitive1-210 {
           44  +  SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a;
           45  +} {3 3 3 20 20 20}
           46  +do_execsql_test transitive1-220 {
           47  +  SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a;
           48  +} {20 20 20 100 100 100}
           49  +
           50  +finish_test