SQLite

Check-in [d6e045f89c]
Login

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

Overview
Comment:Fix the virtual table IN optimizer so that it work even if the virtual table implementation leaves the sqlite3_index_info.aConstraintUsage[].omit flag clear for an equality constraint that it intends to use.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | vtab-IN-opt
Files: files | file ages | folders
SHA1: d6e045f89c5a4b500b1da7ea1224b132909bafc6
User & Date: drh 2012-12-14 15:36:17.947
Context
2012-12-14
15:54
Merge in all the trunk changes that have occurred since this branch was opened. (check-in: 6d507e4de9 user: drh tags: vtab-IN-opt)
15:36
Fix the virtual table IN optimizer so that it work even if the virtual table implementation leaves the sqlite3_index_info.aConstraintUsage[].omit flag clear for an equality constraint that it intends to use. (check-in: d6e045f89c user: drh tags: vtab-IN-opt)
2012-10-16
23:17
Enable optimization of IN operators on constraints to virtual tables. (check-in: aa650746b1 user: drh tags: vtab-IN-opt)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
2189
2190
2191
2192
2193
2194
2195

2196
2197
2198
2199
2200
2201
2202
  Table *pTab = pSrc->pTab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;

  double rCost;

  /* Make sure wsFlags is initialized to some sane value. Otherwise, if the 
  ** malloc in allocateIndexInfo() fails and this function returns leaving
  ** wsFlags in an uninitialized state, the caller may behave unpredictably.
  */
  memset(&p->cost, 0, sizeof(p->cost));







>







2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
  Table *pTab = pSrc->pTab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;
  int bAllowIN;                   /* Allow IN optimizations */
  double rCost;

  /* Make sure wsFlags is initialized to some sane value. Otherwise, if the 
  ** malloc in allocateIndexInfo() fails and this function returns leaving
  ** wsFlags in an uninitialized state, the caller may behave unpredictably.
  */
  memset(&p->cost, 0, sizeof(p->cost));
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
2273
2274
2275
2276
2277
2278


2279






2280
2281
2282



2283
2284
2285
2286
2287
2288
2289
  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  assert( sqlite3GetVTable(pParse->db, pTab) );

  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables to zero.
  **
  ** aConstraint[].usable is true for constraints where the right-hand
  ** side contains only references to tables to the left of the current
  ** table.  In other words, if the constraint is of the form:
  **
  **           column = expr
  **
  ** and we are evaluating a join, then the constraint on column is 
  ** only valid if all tables referenced in expr occur to the left
  ** of the table containing column.
  **
  ** The aConstraints[] array contains entries for all constraints
  ** on the current table.  That way we only have to compute it once
  ** even though we might try to pick the best index multiple times.
  ** For each attempt at picking an index, the order of tables in the
  ** join might be different so we have to recompute the usable flag
  ** each time.
  */





















  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  pUsage = pIdxInfo->aConstraintUsage;
  for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
    j = pIdxCons->iTermOffset;
    pTerm = &pWC->a[j];



    pIdxCons->usable = (pTerm->prereqRight&p->notReady) ? 0 : 1;



  }
  memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  if( pIdxInfo->needToFreeIdxStr ){
    sqlite3_free(pIdxInfo->idxStr);
  }
  pIdxInfo->idxStr = 0;
  pIdxInfo->idxNum = 0;
  pIdxInfo->needToFreeIdxStr = 0;
  pIdxInfo->orderByConsumed = 0;
  /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  nOrderBy = pIdxInfo->nOrderBy;
  if( !p->pOrderBy ){
    pIdxInfo->nOrderBy = 0;
  }

  if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
    return;
  }

  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++){
    if( pUsage[i].argvIndex>0 ){


      p->cost.used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;






    }
  }




  /* If there is an ORDER BY clause, and the selected virtual table index
  ** does not satisfy it, increase the cost of the scan accordingly. This
  ** matches the processing for non-virtual tables in bestBtreeIndex().
  */
  rCost = pIdxInfo->estimatedCost;
  if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){
    rCost += estLog(rCost)*rCost;







|
|
<
<
<
<
<
<
<
<
<
<
<
|
<
<
|
<
|

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
|
|
|
>
>
>
|
>
>
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>
|
>
>
>
>
>
>
|
|
|
>
>
>







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
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  assert( sqlite3GetVTable(pParse->db, pTab) );

  /* Try once or twice.  On the first attempt, allow IN optimizations.
  ** If an IN optimization is accepted, but does not set the











  ** pInfo->aConstrainUsage.omit flag, then it will not work (because it


  ** will allow duplicate rows in the result set) so try again with

  ** IN optimizations disabled.
  */
  for(bAllowIN=1; bAllowIN>=0; bAllowIN--){
    /* Set the aConstraint[].usable fields and initialize all 
    ** output variables to zero.
    **
    ** aConstraint[].usable is true for constraints where the right-hand
    ** side contains only references to tables to the left of the current
    ** table.  In other words, if the constraint is of the form:
    **
    **           column = expr
    **
    ** and we are evaluating a join, then the constraint on column is 
    ** only valid if all tables referenced in expr occur to the left
    ** of the table containing column.
    **
    ** The aConstraints[] array contains entries for all constraints
    ** on the current table.  That way we only have to compute it once
    ** even though we might try to pick the best index multiple times.
    ** For each attempt at picking an index, the order of tables in the
    ** join might be different so we have to recompute the usable flag
    ** each time.
    */
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pUsage = pIdxInfo->aConstraintUsage;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      j = pIdxCons->iTermOffset;
      pTerm = &pWC->a[j];
      if( (pTerm->prereqRight&p->notReady)==0
       && (bAllowIN || pTerm->eOperator!=WO_IN)
      ){
        pIdxCons->usable = 1;
      }else{
        pIdxCons->usable = 0;
      }
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
    if( pIdxInfo->needToFreeIdxStr ){
      sqlite3_free(pIdxInfo->idxStr);
    }
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->needToFreeIdxStr = 0;
    pIdxInfo->orderByConsumed = 0;
    /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
    nOrderBy = pIdxInfo->nOrderBy;
    if( !p->pOrderBy ){
      pIdxInfo->nOrderBy = 0;
    }
  
    if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
      return;
    }
  
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      if( pUsage[i].argvIndex>0 ){
        j = pIdxCons->iTermOffset;
        pTerm = &pWC->a[j];
        p->cost.used |= pTerm->prereqRight;
        if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){
          /* Do not attempt to use an IN constraint if the virtual table
          ** says that the equivalent EQ constraint cannot be safely omitted.
          ** If we do attempt to use such a constraint, some rows might be
          ** repeated in the output. */
          break;
        }
      }
    }
    if( i>=pIdxInfo->nConstraint ) break;
  }
  
  /* If there is an ORDER BY clause, and the selected virtual table index
  ** does not satisfy it, increase the cost of the scan accordingly. This
  ** matches the processing for non-virtual tables in bestBtreeIndex().
  */
  rCost = pIdxInfo->estimatedCost;
  if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){
    rCost += estLog(rCost)*rCost;