/ Check-in [a59b5622]
Login

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

Overview
Comment:When estimating the cost of an index scan, factor in the cost savings of being able to use the index to evaluate some WHERE clause terms without having to do a table lookup.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | improved-index-scan
Files: files | file ages | folders
SHA1: a59b5622f7cc6e502d71aabc12c053582cd03609
User & Date: drh 2016-07-27 18:27:02
Context
2016-07-27
19:20
Add test cases and fix a comment. Closed-Leaf check-in: 50f8ea37 user: drh tags: improved-index-scan
18:27
When estimating the cost of an index scan, factor in the cost savings of being able to use the index to evaluate some WHERE clause terms without having to do a table lookup. check-in: a59b5622 user: drh tags: improved-index-scan
2016-07-26
10:46
Ensure that the sqlite3_scrub_backup() extension creates a backup database at least as large as indicated by the database header, even if the last page of the input database is a free-list leaf. check-in: 483994a5 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  3960   3960      && sqlite3ExprCompare(pE1->pLeft, pE2->pLeft, iTab)==0
  3961   3961      && (pE1->op!=TK_ISNULL && pE1->op!=TK_IS)
  3962   3962     ){
  3963   3963       return 1;
  3964   3964     }
  3965   3965     return 0;
  3966   3966   }
         3967  +
         3968  +/*
         3969  +** An instance of the following structure is used by the tree walker
         3970  +** to determine if an expression can be evaluated by reference to the
         3971  +** index only, without having to do a search for the corresponding
         3972  +** table entry.  The IdxCover.pIdx field is the index.  IdxCover.iCur
         3973  +** is the cursor for the table.
         3974  +*/
         3975  +struct IdxCover {
         3976  +  Index *pIdx;     /* The index to be tested for coverage */
         3977  +  int iCur;        /* Cursor number for the table corresponding to the index */
         3978  +};
         3979  +
         3980  +/*
         3981  +** Check to see if there are references to columns in table 
         3982  +** pWalker->u.pIdxCover->iCur can be satisfied using the index
         3983  +** pWalker->u.pIdxCover->pIdx.
         3984  +*/
         3985  +static int exprIdxCover(Walker *pWalker, Expr *pExpr){
         3986  +  if( pExpr->op==TK_COLUMN
         3987  +   && pExpr->iTable==pWalker->u.pIdxCover->iCur
         3988  +   && sqlite3ColumnOfIndex(pWalker->u.pIdxCover->pIdx, pExpr->iColumn)<0
         3989  +  ){
         3990  +    pWalker->eCode = 1;
         3991  +    return WRC_Abort;
         3992  +  }
         3993  +  return WRC_Continue;
         3994  +}
         3995  +
         3996  +/*
         3997  +** Determine if an index on table iCur that contains the columns in
         3998  +** Bitmask m will cover the expression pExpr.  Return true if the index
         3999  +** does cover the expression and false if the expression references
         4000  +** table columns that are not found in the index.
         4001  +**
         4002  +** An index covering an expression means that the expression can be
         4003  +** evaluated using only the index and without having to lookup the
         4004  +** corresponding table entry.
         4005  +*/
         4006  +int sqlite3ExprCoveredByIndex(
         4007  +  Expr *pExpr,        /* The index to be tested */
         4008  +  int iCur,           /* The cursor number for the corresponding table */
         4009  +  Index *pIdx         /* The index that might be used for coverage */
         4010  +){
         4011  +  Walker w;
         4012  +  struct IdxCover xcov;
         4013  +  memset(&w, 0, sizeof(w));
         4014  +  xcov.iCur = iCur;
         4015  +  xcov.pIdx = pIdx;
         4016  +  w.xExprCallback = exprIdxCover;
         4017  +  w.u.pIdxCover = &xcov;
         4018  +  sqlite3WalkExpr(&w, pExpr);
         4019  +  return !w.eCode;
         4020  +}
         4021  +
  3967   4022   
  3968   4023   /*
  3969   4024   ** An instance of the following structure is used by the tree walker
  3970   4025   ** to count references to table columns in the arguments of an 
  3971   4026   ** aggregate function, in order to implement the
  3972   4027   ** sqlite3FunctionThisSrc() routine.
  3973   4028   */

Changes to src/sqliteInt.h.

  3253   3253       NameContext *pNC;                          /* Naming context */
  3254   3254       int n;                                     /* A counter */
  3255   3255       int iCur;                                  /* A cursor number */
  3256   3256       SrcList *pSrcList;                         /* FROM clause */
  3257   3257       struct SrcCount *pSrcCount;                /* Counting column references */
  3258   3258       struct CCurHint *pCCurHint;                /* Used by codeCursorHint() */
  3259   3259       int *aiCol;                                /* array of column indexes */
         3260  +    struct IdxCover *pIdxCover;                /* Check for index coverage */
  3260   3261     } u;
  3261   3262   };
  3262   3263   
  3263   3264   /* Forward declarations */
  3264   3265   int sqlite3WalkExpr(Walker*, Expr*);
  3265   3266   int sqlite3WalkExprList(Walker*, ExprList*);
  3266   3267   int sqlite3WalkSelect(Walker*, Select*);
................................................................................
  3696   3697   int sqlite3RunVacuum(char**, sqlite3*);
  3697   3698   char *sqlite3NameFromToken(sqlite3*, Token*);
  3698   3699   int sqlite3ExprCompare(Expr*, Expr*, int);
  3699   3700   int sqlite3ExprListCompare(ExprList*, ExprList*, int);
  3700   3701   int sqlite3ExprImpliesExpr(Expr*, Expr*, int);
  3701   3702   void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
  3702   3703   void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
         3704  +int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
  3703   3705   int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
  3704   3706   Vdbe *sqlite3GetVdbe(Parse*);
  3705   3707   #ifndef SQLITE_OMIT_BUILTIN_TEST
  3706   3708   void sqlite3PrngSaveState(void);
  3707   3709   void sqlite3PrngRestoreState(void);
  3708   3710   #endif
  3709   3711   void sqlite3RollbackAll(sqlite3*,int);

Changes to src/where.c.

  2771   2771            && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
  2772   2772             )
  2773   2773         ){
  2774   2774           pNew->iSortIdx = b ? iSortIdx : 0;
  2775   2775   
  2776   2776           /* The cost of visiting the index rows is N*K, where K is
  2777   2777           ** between 1.1 and 3.0, depending on the relative sizes of the
  2778         -        ** index and table rows. If this is a non-covering index scan,
  2779         -        ** also add the cost of visiting table rows (N*3.0).  */
         2778  +        ** index and table rows. */
  2780   2779           pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
  2781   2780           if( m!=0 ){
  2782         -          pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16);
         2781  +          /* If this is a non-covering index scan, add in the cost of
         2782  +          ** doing table lookups.  The cost will be 3x the number of
         2783  +          ** lookups.  Take into account WHERE clause terms that can be
         2784  +          ** satisfied using just the index, and that do not require a
         2785  +          ** table lookup. */
         2786  +          LogEst nLookup = rSize + 16;  /* Base cost:  N*3 */
         2787  +          int ii;
         2788  +          int iCur = pSrc->iCursor;
         2789  +          WhereClause *pWC = &pWInfo->sWC;
         2790  +          for(ii=0; ii<pWC->nTerm; ii++){
         2791  +            WhereTerm *pTerm = &pWC->a[ii];
         2792  +            if( !sqlite3ExprCoveredByIndex(pTerm->pExpr, iCur, pProbe) ){
         2793  +              break;
         2794  +            }
         2795  +            /* pTerm can be evaluated using just the index.  So reduce
         2796  +            ** the expected number of table lookups accordingly */
         2797  +            if( pTerm->truthProb<=0 ){
         2798  +              nLookup += pTerm->truthProb;
         2799  +            }else{
         2800  +              nLookup--;
         2801  +              if( pTerm->eOperator & (WO_EQ|WO_IS) ) nLookup -= 19;
         2802  +            }
         2803  +          }
         2804  +          
         2805  +          pNew->rRun = sqlite3LogEstAdd(pNew->rRun, nLookup);
  2783   2806           }
  2784   2807           ApplyCostMultiplier(pNew->rRun, pTab->costMult);
  2785   2808           whereLoopOutputAdjust(pWC, pNew, rSize);
  2786   2809           rc = whereLoopInsert(pBuilder, pNew);
  2787   2810           pNew->nOut = rSize;
  2788   2811           if( rc ) break;
  2789   2812         }