Add logic to the query planner to only use partial indices if the WHERE clause

constrains the search to rows covered by the partial index.  This is just
infrastructure.  The key routine, sqlite3ExprImpliesExpr(), is currently a
no-op so that partial indices will never be used.

FossilOrigin-Name: 8ca3eac111e06a1854f878a74bffe8f20eb47f1b

3 files changed, 38 insertions, 1 deletions

diff --git a/src/expr.c b/src/expr.c
index 2c0419aa2..03258c32c 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -3866,6 +3866,26 @@ int sqlite3ExprListCompare(ExprList *pA, ExprList *pB){
 }
 
 /*
+** Return true if we can prove the pE2 will always be true if pE1 is
+** true.  Return false if we cannot complete the proof or if pE2 might
+** be false.  Examples:
+**
+**     pE1: x==5      pE2: x>0              Result: true
+**     pE1: x>0       pE2: x==5             Result: false
+**     pE1: x!=123    pE2: x IS NOT NULL    Result: true
+**
+** When comparing TK_COLUMN nodes between pE1 and pE2, if pE2 has
+** Expr.iTable<0 then assume a table number given by iTab.
+**
+** When in doubt, return false.  Returning true might give a performance
+** improvement.  Returning false might cause a performance reduction, but
+** it will always give the correct answer and is hence always safe.
+*/
+int sqlite3ExprImpliesExpr(Expr *pE1, Expr *pE2, int iTab){
+  return 0;  /* FIXME: this needs to be worked out */
+}
+
+/*
 ** An instance of the following structure is used by the tree walker
 ** to count references to table columns in the arguments of an 
 ** aggregate function, in order to implement the
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 3d4a57f3a..9d5580f92 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2835,6 +2835,7 @@ int sqlite3RunVacuum(char**, sqlite3*);
 char *sqlite3NameFromToken(sqlite3*, Token*);
 int sqlite3ExprCompare(Expr*, Expr*);
 int sqlite3ExprListCompare(ExprList*, ExprList*);
+int sqlite3ExprImpliesExpr(Expr*, Expr*, int);
 void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
 void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
 int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
diff --git a/src/where.c b/src/where.c
index 9f65d551a..315c4035c 100644
--- a/src/where.c
+++ b/src/where.c
@@ -4503,6 +4503,17 @@ static Bitmask columnsInIndex(Index *pIdx){
   return m;
 }
 
+/* Check to see if a partial index with pPartIndexWhere can be used
+** in the current query.  Return true if it can be and false if not.
+*/
+static int whereUsablePartialIndex(int iTab, WhereClause *pWC, Expr *pWhere){
+  int i;
+  WhereTerm *pTerm;
+  for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
+    if( sqlite3ExprImpliesExpr(pTerm->pExpr, pWhere, iTab) ) return 1;
+  }
+  return 0;
+}
 
 /*
 ** Add all WhereLoop objects for a single table of the join where the table
@@ -4526,11 +4537,13 @@ static int whereLoopAddBtree(
   int b;                      /* A boolean value */
   WhereCost rSize;            /* number of rows in the table */
   WhereCost rLogSize;         /* Logarithm of the number of rows in the table */
+  WhereClause *pWC;           /* The parsed WHERE clause */
   
   pNew = pBuilder->pNew;
   pWInfo = pBuilder->pWInfo;
   pTabList = pWInfo->pTabList;
   pSrc = pTabList->a + pNew->iTab;
+  pWC = pBuilder->pWC;
   assert( !IsVirtual(pSrc->pTab) );
 
   if( pSrc->pIndex ){
@@ -4570,7 +4583,6 @@ static int whereLoopAddBtree(
    && !pSrc->isCorrelated
   ){
     /* Generate auto-index WhereLoops */
-    WhereClause *pWC = pBuilder->pWC;
     WhereTerm *pTerm;
     WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
     for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
@@ -4600,6 +4612,10 @@ static int whereLoopAddBtree(
   /* Loop over all indices
   */
   for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
+    if( pProbe->pPartIdxWhere!=0
+     && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
+      continue;  /* Partial index inappropriate for this query */
+    }
     pNew->u.btree.nEq = 0;
     pNew->nLTerm = 0;
     pNew->iSortIdx = 0;