/ Check-in [5611130a]
Login

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

Overview
Comment:Adjustments to the WHERE term scanning, to better handle scanning terms of an index.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | index-expr
Files: files | file ages | folders
SHA1: 5611130a595e7f0b6d5f21d76f2755e9c09c7810
User & Date: drh 2015-08-27 15:58:51
Context
2015-08-27
16:07
Merge changes from trunk. check-in: c80e9e8e user: drh tags: index-expr
15:58
Adjustments to the WHERE term scanning, to better handle scanning terms of an index. check-in: 5611130a user: drh tags: index-expr
2015-08-26
18:04
Merge enhancements from trunk. check-in: ec6ddb3d user: drh tags: index-expr
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   269    269     Index *pIdx             /* Must be compatible with this index */
   270    270   ){
   271    271     int j;
   272    272   
   273    273     /* memset(pScan, 0, sizeof(*pScan)); */
   274    274     pScan->pOrigWC = pWC;
   275    275     pScan->pWC = pWC;
          276  +  if( pIdx ){
          277  +    j = iColumn;
          278  +    iColumn = pIdx->aiColumn[j];
          279  +  }
   276    280     if( pIdx && iColumn>=0 ){
   277    281       pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity;
   278         -    for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
   279         -      if( NEVER(j>pIdx->nColumn) ) return 0;
   280         -    }
   281    282       pScan->zCollName = pIdx->azColl[j];
   282    283     }else{
   283    284       pScan->idxaff = 0;
   284    285       pScan->zCollName = 0;
   285    286     }
   286    287     pScan->opMask = opMask;
   287    288     pScan->k = 0;
................................................................................
   293    294   }
   294    295   
   295    296   /*
   296    297   ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
   297    298   ** where X is a reference to the iColumn of table iCur and <op> is one of
   298    299   ** the WO_xx operator codes specified by the op parameter.
   299    300   ** Return a pointer to the term.  Return 0 if not found.
          301  +**
          302  +** If pIdx!=0 then search for terms matching the iColumn-th column of pIdx
          303  +** rather than the iColumn-th column of table iCur.
   300    304   **
   301    305   ** The term returned might by Y=<expr> if there is another constraint in
   302    306   ** the WHERE clause that specifies that X=Y.  Any such constraints will be
   303    307   ** identified by the WO_EQUIV bit in the pTerm->eOperator field.  The
   304    308   ** aEquiv[] array holds X and all its equivalents, with each SQL variable
   305    309   ** taking up two slots in aEquiv[].  The first slot is for the cursor number
   306    310   ** and the second is for the column number.  There are 22 slots in aEquiv[]
................................................................................
   370    374           return i;
   371    375         }
   372    376       }
   373    377     }
   374    378   
   375    379     return -1;
   376    380   }
          381  +
          382  +/*
          383  +** Return TRUE if the iCol-th column of index pIdx is NOT NULL
          384  +*/
          385  +static int indexColumnNotNull(Index *pIdx, int iCol){
          386  +  int j;
          387  +  assert( pIdx!=0 );
          388  +  assert( iCol>=0 && iCol<pIdx->nColumn );
          389  +  j = pIdx->aiColumn[iCol];
          390  +  if( j>=0 ){
          391  +    return pIdx->pTable->aCol[j].notNull;
          392  +  }else if( j==(-1) ){
          393  +    return 1;
          394  +  }else{
          395  +    assert( j==(-2) );
          396  +    return !sqlite3ExprCanBeNull(pIdx->aColExpr->a[iCol].pExpr);
          397  +  }
          398  +}
   377    399   
   378    400   /*
   379    401   ** Return true if the DISTINCT expression-list passed as the third argument
   380    402   ** is redundant.
   381    403   **
   382    404   ** A DISTINCT list is redundant if any subset of the columns in the
   383    405   ** DISTINCT list are collectively unique and individually non-null.
................................................................................
   421    443     **
   422    444     **   3. All of those index columns for which the WHERE clause does not
   423    445     **      contain a "col=X" term are subject to a NOT NULL constraint.
   424    446     */
   425    447     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   426    448       if( !IsUniqueIndex(pIdx) ) continue;
   427    449       for(i=0; i<pIdx->nKeyCol; i++){
   428         -      i16 iCol = pIdx->aiColumn[i];
   429         -      if( 0==sqlite3WhereFindTerm(pWC, iBase, iCol, ~(Bitmask)0, WO_EQ, pIdx) ){
   430         -        int iIdxCol = findIndexCol(pParse, pDistinct, iBase, pIdx, i);
   431         -        if( iIdxCol<0 || pTab->aCol[iCol].notNull==0 ){
   432         -          break;
   433         -        }
          450  +      if( 0==sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask)0, WO_EQ, pIdx) ){
          451  +        if( findIndexCol(pParse, pDistinct, iBase, pIdx, i)<0 ) break;
          452  +        if( indexColumnNotNull(pIdx, i)==0 ) break;
   434    453         }
   435    454       }
   436    455       if( i==pIdx->nKeyCol ){
   437    456         /* This index implies that the DISTINCT qualifier is redundant. */
   438    457         return 1;
   439    458       }
   440    459     }
................................................................................
  2122   2141     WhereScan scan;                 /* Iterator for WHERE terms */
  2123   2142     Bitmask saved_prereq;           /* Original value of pNew->prereq */
  2124   2143     u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
  2125   2144     u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
  2126   2145     u16 saved_nSkip;                /* Original value of pNew->nSkip */
  2127   2146     u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  2128   2147     LogEst saved_nOut;              /* Original value of pNew->nOut */
  2129         -  int iCol;                       /* Index of the column in the table */
  2130   2148     int rc = SQLITE_OK;             /* Return code */
  2131   2149     LogEst rSize;                   /* Number of rows in the table */
  2132   2150     LogEst rLogSize;                /* Logarithm of table size */
  2133   2151     WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */
  2134   2152   
  2135   2153     pNew = pBuilder->pNew;
  2136   2154     if( db->mallocFailed ) return SQLITE_NOMEM;
................................................................................
  2143   2161       opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE;
  2144   2162     }else{
  2145   2163       opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE|WO_ISNULL|WO_IS;
  2146   2164     }
  2147   2165     if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE);
  2148   2166   
  2149   2167     assert( pNew->u.btree.nEq<pProbe->nColumn );
  2150         -  iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  2151   2168   
  2152         -  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  2153         -                        opMask, pProbe);
  2154   2169     saved_nEq = pNew->u.btree.nEq;
  2155   2170     saved_nSkip = pNew->nSkip;
  2156   2171     saved_nLTerm = pNew->nLTerm;
  2157   2172     saved_wsFlags = pNew->wsFlags;
  2158   2173     saved_prereq = pNew->prereq;
  2159   2174     saved_nOut = pNew->nOut;
         2175  +  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq,
         2176  +                        opMask, pProbe);
  2160   2177     pNew->rSetup = 0;
  2161   2178     rSize = pProbe->aiRowLogEst[0];
  2162   2179     rLogSize = estLog(rSize);
  2163   2180     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  2164   2181       u16 eOp = pTerm->eOperator;   /* Shorthand for pTerm->eOperator */
  2165   2182       LogEst rCostIdx;
  2166   2183       LogEst nOutUnadjusted;        /* nOut before IN() and WHERE adjustments */
  2167   2184       int nIn = 0;
  2168   2185   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  2169   2186       int nRecValid = pBuilder->nRecValid;
  2170   2187   #endif
  2171   2188       if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
  2172         -     && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
         2189  +     && indexColumnNotNull(pProbe, saved_nEq)
  2173   2190       ){
  2174   2191         continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */
  2175   2192       }
  2176   2193       if( pTerm->prereqRight & pNew->maskSelf ) continue;
  2177   2194   
  2178   2195       /* Do not allow the upper bound of a LIKE optimization range constraint
  2179   2196       ** to mix with a lower range bound from some other source */
................................................................................
  2202   2219           /* "x IN (value, value, ...)" */
  2203   2220           nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
  2204   2221         }
  2205   2222         assert( nIn>0 );  /* RHS always has 2 or more terms...  The parser
  2206   2223                           ** changes "x IN (?)" into "x=?". */
  2207   2224   
  2208   2225       }else if( eOp & (WO_EQ|WO_IS) ){
         2226  +      int iCol = pProbe->aiColumn[saved_nEq];
  2209   2227         pNew->wsFlags |= WHERE_COLUMN_EQ;
  2210         -      if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1) ){
         2228  +      assert( saved_nEq==pNew->u.btree.nEq );
         2229  +      if( iCol==(-1) || (nInMul==0 && saved_nEq==pProbe->nKeyCol-1) ){
  2211   2230           if( iCol>=0 && pProbe->uniqNotNull==0 ){
  2212   2231             pNew->wsFlags |= WHERE_UNQ_WANTED;
  2213   2232           }else{
  2214   2233             pNew->wsFlags |= WHERE_ONEROW;
  2215   2234           }
  2216   2235         }
  2217   2236       }else if( eOp & WO_ISNULL ){
................................................................................
  2254   2273         ** data, using some other estimate.  */
  2255   2274         whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
  2256   2275       }else{
  2257   2276         int nEq = ++pNew->u.btree.nEq;
  2258   2277         assert( eOp & (WO_ISNULL|WO_EQ|WO_IN|WO_IS) );
  2259   2278   
  2260   2279         assert( pNew->nOut==saved_nOut );
  2261         -      if( pTerm->truthProb<=0 && iCol>=0 ){
         2280  +      if( pTerm->truthProb<=0 && pProbe->aiColumn[saved_nEq]>=0 ){
  2262   2281           assert( (eOp & WO_IN) || nIn==0 );
  2263   2282           testcase( eOp & WO_IN );
  2264   2283           pNew->nOut += pTerm->truthProb;
  2265   2284           pNew->nOut -= nIn;
  2266   2285         }else{
  2267   2286   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  2268   2287           tRowcnt nOut = 0;
................................................................................
  3781   3800         assert( pLoop->aLTermSpace==pLoop->aLTerm );
  3782   3801         if( !IsUniqueIndex(pIdx)
  3783   3802          || pIdx->pPartIdxWhere!=0 
  3784   3803          || pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace) 
  3785   3804         ) continue;
  3786   3805         opMask = pIdx->uniqNotNull ? (WO_EQ|WO_IS) : WO_EQ;
  3787   3806         for(j=0; j<pIdx->nKeyCol; j++){
  3788         -        pTerm = sqlite3WhereFindTerm(pWC, iCur, pIdx->aiColumn[j], 0, opMask, pIdx);
         3807  +        pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx);
  3789   3808           if( pTerm==0 ) break;
  3790   3809           testcase( pTerm->eOperator & WO_IS );
  3791   3810           pLoop->aLTerm[j] = pTerm;
  3792   3811         }
  3793   3812         if( j!=pIdx->nKeyCol ) continue;
  3794   3813         pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED;
  3795   3814         if( pIdx->isCovering || (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){