Be more aggressive about reusing subqueries that appear on the RHS of IN

operators that have been replicated due to the predicate push-down optimization.

FossilOrigin-Name: 2accf32b6e45a396503c29eecc14a103bcc7b4c313cde921b26b489704060177

3 files changed, 97 insertions, 5 deletions

diff --git a/src/expr.c b/src/expr.c
index 6d67d77f6..9ab190505 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -3422,6 +3422,46 @@ void sqlite3VectorErrorMsg(Parse *pParse, Expr *pExpr){
 
 #ifndef SQLITE_OMIT_SUBQUERY
 /*
+** Scan all previously generated bytecode looking for an OP_BeginSubrtn
+** that is compatible with pExpr.  If found, add the y.sub values
+** to pExpr and return true.  If not found, return false.
+*/
+static int findCompatibleInRhsSubrtn(
+  Parse *pParse,          /* Parsing context */
+  Expr *pExpr,            /* IN operator with RHS that we want to reuse */
+  SubrtnSig *pNewSig      /* Signature for the IN operator */
+){
+  VdbeOp *pOp, *pEnd;
+  SubrtnSig *pSig;
+  Vdbe *v;
+
+  if( pNewSig==0 ) return 0;
+  assert( pExpr->op==TK_IN );
+  assert( !ExprUseYSub(pExpr) );
+  assert( ExprUseXSelect(pExpr) );
+  v = pParse->pVdbe;
+  assert( v!=0 );
+  pOp = sqlite3VdbeGetOp(v, 1);
+  pEnd = sqlite3VdbeGetLastOp(v);
+  for(; pOp<pEnd; pOp++){
+    if( pOp->opcode!=OP_BeginSubrtn ) continue;
+    if( pOp->p4type!=P4_SUBRTNSIG ) continue;
+    pSig = pOp->p4.pSubrtnSig;
+    assert( pSig!=0 );
+    if( pNewSig->selId!=pSig->selId ) continue;
+    if( strcmp(pNewSig->zAff,pSig->zAff)!=0 ) continue;
+    pExpr->y.sub.iAddr = pSig->iAddr;
+    pExpr->y.sub.regReturn = pSig->regReturn;
+    pExpr->iTable = pSig->iTable;
+    ExprSetProperty(pExpr, EP_Subrtn);
+    return 1;
+  }
+  return 0;
+}
+#endif /* SQLITE_OMIT_SUBQUERY */
+
+#ifndef SQLITE_OMIT_SUBQUERY
+/*
 ** Generate code that will construct an ephemeral table containing all terms
 ** in the RHS of an IN operator.  The IN operator can be in either of two
 ** forms:
@@ -3469,11 +3509,30 @@ void sqlite3CodeRhsOfIN(
   ** and reuse it many names.
   */
   if( !ExprHasProperty(pExpr, EP_VarSelect) && pParse->iSelfTab==0 ){
-    /* Reuse of the RHS is allowed */
-    /* If this routine has already been coded, but the previous code
-    ** might not have been invoked yet, so invoke it now as a subroutine.
+    /* Reuse of the RHS is allowed
+    **
+    ** Compute a signature for the RHS of the IN operator to facility
+    ** finding and reusing prior instances of the same IN operator.
+    */
+    SubrtnSig *pSig;
+    if( !ExprUseXSelect(pExpr) ){
+      pSig = 0;
+    }else{
+      assert( pExpr->x.pSelect!=0 );
+      pSig = sqlite3DbMallocRawNN(pParse->db, sizeof(pSig[0]));
+      if( pSig ){
+        pSig->selId = pExpr->x.pSelect->selId;
+        pSig->zAff = exprINAffinity(pParse, pExpr);
+      }
+    }
+
+    /* Check to see if there is a prior materialization of the RHS of
+    ** this IN operator.  If there is, then make use of that prior
+    ** materialization rather than recomputing it.
     */
-    if( ExprHasProperty(pExpr, EP_Subrtn) ){
+    if( ExprHasProperty(pExpr, EP_Subrtn) 
+     || findCompatibleInRhsSubrtn(pParse, pExpr, pSig)
+    ){
       addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
       if( ExprUseXSelect(pExpr) ){
         ExplainQueryPlan((pParse, 0, "REUSE LIST SUBQUERY %d",
@@ -3485,6 +3544,10 @@ void sqlite3CodeRhsOfIN(
       assert( iTab!=pExpr->iTable );
       sqlite3VdbeAddOp2(v, OP_OpenDup, iTab, pExpr->iTable);
       sqlite3VdbeJumpHere(v, addrOnce);
+      if( pSig ){
+        sqlite3DbFree(pParse->db, pSig->zAff);
+        sqlite3DbFree(pParse->db, pSig);
+      }
       return;
     }
 
@@ -3495,7 +3558,12 @@ void sqlite3CodeRhsOfIN(
     pExpr->y.sub.regReturn = ++pParse->nMem;
     pExpr->y.sub.iAddr =
       sqlite3VdbeAddOp2(v, OP_BeginSubrtn, 0, pExpr->y.sub.regReturn) + 1;
-
+    if( pSig ){
+      pSig->iAddr = pExpr->y.sub.iAddr;
+      pSig->regReturn = pExpr->y.sub.regReturn;
+      pSig->iTable = iTab;
+      sqlite3VdbeChangeP4(v, -1, (const char*)pSig, P4_SUBRTNSIG);
+    }
     addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
   }
 
diff --git a/src/vdbe.h b/src/vdbe.h
index 9001ace2e..f40f68d24 100644
--- a/src/vdbe.h
+++ b/src/vdbe.h
@@ -32,6 +32,19 @@ typedef struct Vdbe Vdbe;
 */
 typedef struct sqlite3_value Mem;
 typedef struct SubProgram SubProgram;
+typedef struct SubrtnSig SubrtnSig;
+
+/*
+** A signature for a reusable subroutine that materializes the RHS of
+** an IN operator.
+*/
+struct SubrtnSig {
+  int selId;          /* SELECT-id for the SELECT statement on the RHS */
+  char *zAff;         /* Affinity of the overall IN expression */
+  int iTable;         /* Ephemeral table generated by the subroutine */
+  int iAddr;          /* Subroutine entry address */
+  int regReturn;      /* Register used to hold return address */
+};
 
 /*
 ** A single instruction of the virtual machine has an opcode
@@ -60,6 +73,7 @@ struct VdbeOp {
     u32 *ai;               /* Used when p4type is P4_INTARRAY */
     SubProgram *pProgram;  /* Used when p4type is P4_SUBPROGRAM */
     Table *pTab;           /* Used when p4type is P4_TABLE */
+    SubrtnSig *pSubrtnSig; /* Used when p4type is P4_SUBRTNSIG */
 #ifdef SQLITE_ENABLE_CURSOR_HINTS
     Expr *pExpr;           /* Used when p4type is P4_EXPR */
 #endif
@@ -127,6 +141,7 @@ typedef struct VdbeOpList VdbeOpList;
 #define P4_INTARRAY   (-14) /* P4 is a vector of 32-bit integers */
 #define P4_FUNCCTX    (-15) /* P4 is a pointer to an sqlite3_context object */
 #define P4_TABLEREF   (-16) /* Like P4_TABLE, but reference counted */
+#define P4_SUBRTNSIG  (-17) /* P4 is a SubrtnSig pointer */
 
 /* Error message codes for OP_Halt */
 #define P5_ConstraintNotNull 1
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index 665f6cd17..745d3eaba 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -1413,6 +1413,12 @@ static void freeP4(sqlite3 *db, int p4type, void *p4){
       if( db->pnBytesFreed==0 ) sqlite3DeleteTable(db, (Table*)p4);
       break;
     }
+    case P4_SUBRTNSIG: {
+      SubrtnSig *pSig = (SubrtnSig*)p4;
+      sqlite3DbFree(db, pSig->zAff);
+      sqlite3DbFree(db, pSig);
+      break;
+    }
   }
 }
 
@@ -1992,6 +1998,9 @@ char *sqlite3VdbeDisplayP4(sqlite3 *db, Op *pOp){
       zP4 = pOp->p4.pTab->zName;
       break;
     }
+    case P4_SUBRTNSIG: {
+      break;
+    }
     default: {
       zP4 = pOp->p4.z;
     }