This experimental branch attempts to use columns for an index-on-expression

in place of the expression that is being indexed.  This particular check-in
mostly works, but there are still issues.

FossilOrigin-Name: 2e8d4fd4cfd9e82f33c707ba246fe2bb3ca01762cf5ac5905058fbc7adf0abe7

8 files changed, 105 insertions, 0 deletions

diff --git a/src/analyze.c b/src/analyze.c
index 39009899a..8562b9d7f 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -953,6 +953,7 @@ static void analyzeVdbeCommentIndexWithColumnName(
   if( NEVER(i==XN_ROWID) ){
     VdbeComment((v,"%s.rowid",pIdx->zName));
   }else if( i==XN_EXPR ){
+    assert( pIdx->bHasExpr );
     VdbeComment((v,"%s.expr(%d)",pIdx->zName, k));
   }else{
     VdbeComment((v,"%s.%s", pIdx->zName, pIdx->pTable->aCol[i].zCnName));
diff --git a/src/build.c b/src/build.c
index be6b01eb0..502826bfc 100644
--- a/src/build.c
+++ b/src/build.c
@@ -4192,6 +4192,7 @@ void sqlite3CreateIndex(
       j = XN_EXPR;
       pIndex->aiColumn[i] = XN_EXPR;
       pIndex->uniqNotNull = 0;
+      pIndex->bHasExpr = 1;
     }else{
       j = pCExpr->iColumn;
       assert( j<=0x7fff );
diff --git a/src/expr.c b/src/expr.c
index bceb5efb0..3630b47aa 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -4043,6 +4043,26 @@ static int exprCodeInlineFunction(
   return target;
 }
 
+/*
+** Check to see if pExpr is one of the indexed expression on pParse->pIdxExpr.
+** If it is, then resolve the expression by reading from the index and
+** return the register into which the value has been read.  If there is
+** no match, return negative.
+*/
+static SQLITE_NOINLINE int sqlite3ExprIndexLookup(
+  Parse *pParse,   /* The parsing context */
+  Expr *pExpr,     /* The expression to potentially bypass */
+  int target       /* Where to store the result of the expression */
+){
+  IndexExpr *p;
+  for(p=pParse->pIdxExpr; p; p=p->pIENext){
+    if( sqlite3ExprCompare(0, pExpr, p->pExpr, p->iDataCur)!=0 ) continue;
+    sqlite3VdbeAddOp3(pParse->pVdbe, OP_Column, p->iIdxCur, p->iIdxCol, target);
+    return target;
+  }
+  return -1;  /* Not found */
+}
+
 
 /*
 ** Generate code into the current Vdbe to evaluate the given
@@ -4068,6 +4088,14 @@ int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){
   assert( target>0 && target<=pParse->nMem );
   assert( v!=0 );
 
+  if( pParse->pIdxExpr!=0 
+   && pExpr!=0
+   && !ExprHasProperty(pExpr, EP_Leaf)
+   && (r1 = sqlite3ExprIndexLookup(pParse, pExpr, target))>=0
+  ){
+    return r1;
+  }
+
 expr_code_doover:
   if( pExpr==0 ){
     op = TK_NULL;
diff --git a/src/insert.c b/src/insert.c
index 6c71391a1..3e0d696d7 100644
--- a/src/insert.c
+++ b/src/insert.c
@@ -96,6 +96,7 @@ const char *sqlite3IndexAffinityStr(sqlite3 *db, Index *pIdx){
         aff = SQLITE_AFF_INTEGER;
       }else{
         assert( x==XN_EXPR );
+        assert( pIdx->bHasExpr );
         assert( pIdx->aColExpr!=0 );
         aff = sqlite3ExprAffinity(pIdx->aColExpr->a[n].pExpr);
       }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 6f1109f2f..caf7610ad 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1189,6 +1189,7 @@ typedef struct FuncDef FuncDef;
 typedef struct FuncDefHash FuncDefHash;
 typedef struct IdList IdList;
 typedef struct Index Index;
+typedef struct IndexExpr IndexExpr;
 typedef struct IndexSample IndexSample;
 typedef struct KeyClass KeyClass;
 typedef struct KeyInfo KeyInfo;
@@ -2616,6 +2617,7 @@ struct Index {
   unsigned bNoQuery:1;     /* Do not use this index to optimize queries */
   unsigned bAscKeyBug:1;   /* True if the bba7b69f9849b5bf bug applies */
   unsigned bHasVCol:1;     /* Index references one or more VIRTUAL columns */
+  unsigned bHasExpr:1;     /* This is an index on an expression */
 #ifdef SQLITE_ENABLE_STAT4
   int nSample;             /* Number of elements in aSample[] */
   int nSampleCol;          /* Size of IndexSample.anEq[] and so on */
@@ -3564,6 +3566,23 @@ struct TriggerPrg {
 #endif
 
 /*
+** If there is an index on an expression in scope such that the value
+** of the expression pExpr can be read out of the index with cursor iCur
+** at column iCol, then an instance of this object records that fact.
+**
+** A linked list of these objects is attached to Parse and records all
+** expressions that can be short-circuited by extracting a valid from
+** an index.
+*/
+struct IndexExpr {
+  Expr *pExpr;            /* The expression contained in the index */
+  int iDataCur;           /* The data cursor associated with the index */
+  int iIdxCur;            /* The index cursor */
+  int iIdxCol;            /* The column of the index that contains pExpr */
+  IndexExpr *pIENext;     /* Next in a list of all indexed expressions */
+};
+
+/*
 ** An instance of the ParseCleanup object specifies an operation that
 ** should be performed after parsing to deallocation resources obtained
 ** during the parse and which are no longer needed.
@@ -3621,6 +3640,7 @@ struct Parse {
   int nLabelAlloc;     /* Number of slots in aLabel */
   int *aLabel;         /* Space to hold the labels */
   ExprList *pConstExpr;/* Constant expressions */
+  IndexExpr *pIdxExpr; /* List of all expression in active indexes */
   Token constraintName;/* Name of the constraint currently being parsed */
   yDbMask writeMask;   /* Start a write transaction on these databases */
   yDbMask cookieMask;  /* Bitmask of schema verified databases */
diff --git a/src/upsert.c b/src/upsert.c
index fb6c7c0c0..85994020c 100644
--- a/src/upsert.c
+++ b/src/upsert.c
@@ -166,6 +166,7 @@ int sqlite3UpsertAnalyzeTarget(
         if( pIdx->aiColumn[ii]==XN_EXPR ){
           assert( pIdx->aColExpr!=0 );
           assert( pIdx->aColExpr->nExpr>ii );
+          assert( pIdx->bHasExpr );
           pExpr = pIdx->aColExpr->a[ii].pExpr;
           if( pExpr->op!=TK_COLLATE ){
             sCol[0].pLeft = pExpr;
diff --git a/src/where.c b/src/where.c
index b0c0ea7d4..220ea5139 100644
--- a/src/where.c
+++ b/src/where.c
@@ -5384,6 +5384,55 @@ static SQLITE_NOINLINE void whereCheckIfBloomFilterIsUseful(
 }
 
 /*
+** This is an sqlite3ParserAddCleanup() callback that is invoked to
+** free the Parse->pIdxExpr list when the Parse object is destroyed.
+*/
+static void whereIndexExprCleanup(sqlite3 *db, void *pObject){
+  Parse *pParse = (Parse*)pObject;
+  while( pParse->pIdxExpr!=0 ){
+    IndexExpr *p = pParse->pIdxExpr;
+    pParse->pIdxExpr = p->pIENext;
+    sqlite3ExprDelete(db, p->pExpr);
+    sqlite3DbFreeNN(db, p);
+  }
+}
+
+/*
+** The index pIdx is used by a query and contains one or more expressions.
+** In other words pIdx is an index on an expression.  iIdxCur is the cursor
+** number for the index and iDataCur is the cursor number for the corresponding
+** table.
+**
+** This routine adds IndexExpr entries to the Parse->pIdxExpr field for
+** each of the expressions in the index so that the expression code generator
+** will know to replace occurrences of the indexed expression with
+** references to the corresponding column of the index.
+*/
+static SQLITE_NOINLINE void whereAddIndexExpr(
+  Parse *pParse,    /* Add IndexExpr entries to pParse->pIdxExpr */
+  Index *pIdx,      /* The index-on-expression that contains the expressions */
+  int iIdxCur,      /* Cursor number for pIdx */
+  int iDataCur      /* Cursor for the corresponding table */
+){
+  int i;
+  IndexExpr *p;
+  for(i=0; i<pIdx->nColumn; i++){
+    if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
+    p = sqlite3DbMallocRaw(pParse->db, sizeof(IndexExpr));
+    if( p==0 ) break;
+    p->pIENext = pParse->pIdxExpr;
+    p->pExpr = sqlite3ExprDup(pParse->db, pIdx->aColExpr->a[i].pExpr, 0);
+    p->iDataCur = iDataCur;
+    p->iIdxCur = iIdxCur;
+    p->iIdxCol = i;
+    pParse->pIdxExpr = p;
+    if( p->pIENext==0 ){
+      sqlite3ParserAddCleanup(pParse, whereIndexExprCleanup, pParse);
+    }
+  }
+}
+
+/*
 ** Generate the beginning of the loop used for WHERE clause processing.
 ** The return value is a pointer to an opaque structure that contains
 ** information needed to terminate the loop.  Later, the calling routine
@@ -5928,6 +5977,9 @@ WhereInfo *sqlite3WhereBegin(
         op = OP_ReopenIdx;
       }else{
         iIndexCur = pParse->nTab++;
+        if( pIx->bHasExpr ){
+          whereAddIndexExpr(pParse, pIx, iIndexCur, pTabItem->iCursor);
+        }
       }
       pLevel->iIdxCur = iIndexCur;
       assert( pIx!=0 );
diff --git a/src/whereexpr.c b/src/whereexpr.c
index 8c9233ebd..20e569642 100644
--- a/src/whereexpr.c
+++ b/src/whereexpr.c
@@ -989,6 +989,7 @@ static SQLITE_NOINLINE int exprMightBeIndexed2(
     if( pIdx->aColExpr==0 ) continue;
     for(i=0; i<pIdx->nKeyCol; i++){
       if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
+      assert( pIdx->bHasExpr );
       if( sqlite3ExprCompareSkip(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
         aiCurCol[0] = iCur;
         aiCurCol[1] = XN_EXPR;