SQLite

Check-in [b9fc89e432]
Login

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

Overview
Comment:Fix the sqlite3FindInIndex() to ensure that it always uses a prefix of the index and uses no repeated columns. Enhanced comments.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | rowvalue
Files: files | file ages | folders
SHA1: b9fc89e432fbe4e5b41959a42797641907e075e3
User & Date: drh 2016-08-26 21:15:35.199
Context
2016-08-26
22:09
Fix a minor problem in sqlite3FindInIndex() related to rowids being used as part of the index. (check-in: 829f802be7 user: drh tags: rowvalue)
21:15
Fix the sqlite3FindInIndex() to ensure that it always uses a prefix of the index and uses no repeated columns. Enhanced comments. (check-in: b9fc89e432 user: drh tags: rowvalue)
19:54
Add an EXPLAIN QUERY PLAN line for when a index is used to implement an IN operator. (check-in: 171aa833a2 user: drh tags: rowvalue)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/expr.c.
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
  if( pSrc->a[0].pSelect ) return 0;     /* FROM is not a subquery or view */
  pTab = pSrc->a[0].pTab;
  assert( pTab!=0 );
  assert( pTab->pSelect==0 );            /* FROM clause is not a view */
  if( IsVirtual(pTab) ) return 0;        /* FROM clause not a virtual table */
  pEList = p->pEList;
  assert( pEList!=0 );

  /* All SELECT results must be columns. */
  for(i=0; i<pEList->nExpr; i++){
    Expr *pRes = pEList->a[i].pExpr;
    if( pRes->op!=TK_COLUMN ) return 0;
    assert( pRes->iTable==pSrc->a[0].iCursor );  /* Not a correlated subquery */
  }
  return p;







<







1956
1957
1958
1959
1960
1961
1962

1963
1964
1965
1966
1967
1968
1969
  if( pSrc->a[0].pSelect ) return 0;     /* FROM is not a subquery or view */
  pTab = pSrc->a[0].pTab;
  assert( pTab!=0 );
  assert( pTab->pSelect==0 );            /* FROM clause is not a view */
  if( IsVirtual(pTab) ) return 0;        /* FROM clause not a virtual table */
  pEList = p->pEList;
  assert( pEList!=0 );

  /* All SELECT results must be columns. */
  for(i=0; i<pEList->nExpr; i++){
    Expr *pRes = pEList->a[i].pExpr;
    if( pRes->op!=TK_COLUMN ) return 0;
    assert( pRes->iTable==pSrc->a[0].iCursor );  /* Not a correlated subquery */
  }
  return p;
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
    pTab = p->pSrc->a[0].pTab;

    /* Code an OP_Transaction and OP_TableLock for <table>. */
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    sqlite3CodeVerifySchema(pParse, iDb);
    sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

    /* This function is only called from two places. In both cases the vdbe
    ** has already been allocated. So assume sqlite3GetVdbe() is always
    ** successful here.
    */
    assert(v);
    if( nExpr==1 && pEList->a[0].pExpr->iColumn<0 ){
      /* The "x IN (SELECT rowid FROM table)" case */
      int iAddr = sqlite3CodeOnce(pParse);
      VdbeCoverage(v);

      sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
      eType = IN_INDEX_ROWID;







<
<
<
<
|







2145
2146
2147
2148
2149
2150
2151




2152
2153
2154
2155
2156
2157
2158
2159
    pTab = p->pSrc->a[0].pTab;

    /* Code an OP_Transaction and OP_TableLock for <table>. */
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    sqlite3CodeVerifySchema(pParse, iDb);
    sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);





    assert(v);  /* sqlite3GetVdbe() has always been previously called */
    if( nExpr==1 && pEList->a[0].pExpr->iColumn<0 ){
      /* The "x IN (SELECT rowid FROM table)" case */
      int iAddr = sqlite3CodeOnce(pParse);
      VdbeCoverage(v);

      sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
      eType = IN_INDEX_ROWID;
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202


2203





2204
2205
2206
2207
2208
2209
2210
2211

2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226



2227
2228
2229
2230


2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258

2259
2260
2261
2262
2263
2264
2265
            assert( idxaff==SQLITE_AFF_TEXT );
            break;
          default:
            affinity_ok = sqlite3IsNumericAffinity(idxaff);
        }
      }

      /* The collation sequence used by the comparison. If an index is to
      ** be used in place of a temp-table, it must be ordered according
      ** to this collation sequence.  */

      for(pIdx=pTab->pIndex; pIdx && eType==0 && affinity_ok; pIdx=pIdx->pNext){


        if( pIdx->nColumn<nExpr ) continue;





        if( mustBeUnique ){
          if( pIdx->nKeyCol>nExpr
           ||(pIdx->nColumn>nExpr && !IsUniqueIndex(pIdx))
          ){
            continue;
          }
        }


        for(i=0; i<nExpr; i++){
          Expr *pLhs = sqlite3VectorFieldSubexpr(pX->pLeft, i);
          Expr *pRhs = pEList->a[i].pExpr;
          CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs);
          int j;

          assert( pReq!=0 || pRhs->iColumn==XN_ROWID || pParse->nErr );
          for(j=0; j<nExpr; j++){
            if( pIdx->aiColumn[j]!=pRhs->iColumn ) continue;
            assert( pIdx->azColl[j] );
            if( pReq==0 ) continue;
            if( sqlite3StrICmp(pReq->zName, pIdx->azColl[j])!=0 ) continue;
            break;
          }
          if( j==nExpr ) break;



          if( aiMap ) aiMap[i] = j;
        }

        if( i==nExpr ){


          int iAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);
#ifndef SQLITE_OMIT_EXPLAIN
          sqlite3VdbeAddOp4(v, OP_Explain, 0, 0, 0,
            sqlite3MPrintf(db, "USING INDEX %s FOR IN-OPERATOR", pIdx->zName),
            P4_DYNAMIC);
#endif
          sqlite3VdbeAddOp3(v, OP_OpenRead, iTab, pIdx->tnum, iDb);
          sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
          VdbeComment((v, "%s", pIdx->zName));
          assert( IN_INDEX_INDEX_DESC == IN_INDEX_INDEX_ASC+1 );
          eType = IN_INDEX_INDEX_ASC + pIdx->aSortOrder[0];

          if( prRhsHasNull ){
            *prRhsHasNull = ++pParse->nMem;
#ifdef SQLITE_ENABLE_COLUMN_USED_MASK
            i64 mask = (1<<nExpr)-1;
            sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, 
                iTab, 0, 0, (u8*)&mask, P4_INT64);
#endif
            if( nExpr==1 ){
              sqlite3SetHasNullFlag(v, iTab, *prRhsHasNull);
            }
          }
          sqlite3VdbeJumpHere(v, iAddr);
        }
      }
    }
  }


  /* If no preexisting index is available for the IN clause
  ** and IN_INDEX_NOOP is an allowed reply
  ** and the RHS of the IN operator is a list, not a subquery
  ** and the RHS is not constant or has two or fewer terms,
  ** then it is not worth creating an ephemeral table to evaluate
  ** the IN operator so return IN_INDEX_NOOP.







|
<
<
|
|
>
>
|
>
>
>
>
>
|
|
|
|
|
|
|
|
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>
>
|
|
|
|
>
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>







2186
2187
2188
2189
2190
2191
2192
2193


2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
            assert( idxaff==SQLITE_AFF_TEXT );
            break;
          default:
            affinity_ok = sqlite3IsNumericAffinity(idxaff);
        }
      }

      if( affinity_ok ){


        /* Search for an existing index that will work for this IN operator */
        for(pIdx=pTab->pIndex; pIdx && eType==0; pIdx=pIdx->pNext){
          Bitmask colUsed;      /* Columns of the index used */
          Bitmask mCol;         /* Mask for the current column */
          if( pIdx->nColumn<nExpr ) continue;
          /* Maximum nColumn is BMS-2, not BMS-1, so that we can compute
          ** BITMASK(nExpr) without overflowing */
          testcase( pIdx->nColumn==BMS-2 );
          testcase( pIdx->nColumn==BMS-1 );
          if( pIdx->nColumn>=BMS-1 ) continue;
          if( mustBeUnique ){
            if( pIdx->nKeyCol>nExpr
             ||(pIdx->nColumn>nExpr && !IsUniqueIndex(pIdx))
            ){
              continue;  /* This index is not unique over the IN RHS columns */
            }
          }
  
          colUsed = 0;   /* Columns of index used so far */
          for(i=0; i<nExpr; i++){
            Expr *pLhs = sqlite3VectorFieldSubexpr(pX->pLeft, i);
            Expr *pRhs = pEList->a[i].pExpr;
            CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs);
            int j;
  
            assert( pReq!=0 || pRhs->iColumn==XN_ROWID || pParse->nErr );
            for(j=0; j<nExpr; j++){
              if( pIdx->aiColumn[j]!=pRhs->iColumn ) continue;
              assert( pIdx->azColl[j] );
              if( pReq==0 ) continue;
              if( sqlite3StrICmp(pReq->zName, pIdx->azColl[j])!=0 ) continue;
              break;
            }
            if( j==nExpr ) break;
            mCol = MASKBIT(j);
            if( mCol & colUsed ) break; /* Each column used only once */
            colUsed |= mCol;
            if( aiMap ) aiMap[i] = j;
          }
  
          assert( i==nExpr || colUsed!=(MASKBIT(nExpr)-1) );
          if( colUsed==(MASKBIT(nExpr)-1) ){
            /* If we reach this point, that means the index pIdx is usable */
            int iAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);
  #ifndef SQLITE_OMIT_EXPLAIN
            sqlite3VdbeAddOp4(v, OP_Explain, 0, 0, 0,
              sqlite3MPrintf(db, "USING INDEX %s FOR IN-OPERATOR",pIdx->zName),
              P4_DYNAMIC);
  #endif
            sqlite3VdbeAddOp3(v, OP_OpenRead, iTab, pIdx->tnum, iDb);
            sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
            VdbeComment((v, "%s", pIdx->zName));
            assert( IN_INDEX_INDEX_DESC == IN_INDEX_INDEX_ASC+1 );
            eType = IN_INDEX_INDEX_ASC + pIdx->aSortOrder[0];
  
            if( prRhsHasNull ){
              *prRhsHasNull = ++pParse->nMem;
  #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
              i64 mask = (1<<nExpr)-1;
              sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, 
                  iTab, 0, 0, (u8*)&mask, P4_INT64);
  #endif
              if( nExpr==1 ){
                sqlite3SetHasNullFlag(v, iTab, *prRhsHasNull);
              }
            }
            sqlite3VdbeJumpHere(v, iAddr);
          }
        } /* End loop over indexes */
      } /* End if( affinity_ok ) */
    } /* End if not an rowid index */
  } /* End attempt to optimize using an index */

  /* If no preexisting index is available for the IN clause
  ** and IN_INDEX_NOOP is an allowed reply
  ** and the RHS of the IN operator is a list, not a subquery
  ** and the RHS is not constant or has two or fewer terms,
  ** then it is not worth creating an ephemeral table to evaluate
  ** the IN operator so return IN_INDEX_NOOP.