Merge in the exists-to-join optimization that has been modified

to relax the requirement of having an indexed join constraint.

FossilOrigin-Name: 1c1aef2b7feae29066d0330699ab634ef41f5b60cdcd479a60cb1a5409553138

6 files changed, 102 insertions, 7 deletions

diff --git a/src/build.c b/src/build.c
index 5bd3aac3c..526e2ddfe 100644
--- a/src/build.c
+++ b/src/build.c
@@ -5138,14 +5138,17 @@ void sqlite3SrcListIndexedBy(Parse *pParse, SrcList *p, Token *pIndexedBy){
 ** are deleted by this function.
 */
 SrcList *sqlite3SrcListAppendList(Parse *pParse, SrcList *p1, SrcList *p2){
-  assert( p1 && p1->nSrc==1 );
+  assert( p1 );
   if( p2 ){
-    SrcList *pNew = sqlite3SrcListEnlarge(pParse, p1, p2->nSrc, 1);
+    int nOld = p1->nSrc;
+    SrcList *pNew = sqlite3SrcListEnlarge(pParse, p1, p2->nSrc, nOld);
     if( pNew==0 ){
       sqlite3SrcListDelete(pParse->db, p2);
     }else{
       p1 = pNew;
-      memcpy(&p1->a[1], p2->a, p2->nSrc*sizeof(SrcItem));
+      memcpy(&p1->a[nOld], p2->a, p2->nSrc*sizeof(SrcItem));
+      assert( nOld==1 || (p2->nSrc==1 && (p2->a[0].fg.jointype&JT_LTORJ)==0) );
+      assert( p1->nSrc>=2 );
       sqlite3DbFree(pParse->db, p2);
       p1->a[0].fg.jointype |= (JT_LTORJ & p1->a[1].fg.jointype);
     }
diff --git a/src/resolve.c b/src/resolve.c
index 3961a2009..562ca5e00 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -1379,6 +1379,7 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){
         if( nRef!=pNC->nRef ){
           ExprSetProperty(pExpr, EP_VarSelect);
           pExpr->x.pSelect->selFlags |= SF_Correlated;
+          if( pExpr->op==TK_EXISTS ) pParse->bHasExists = 1;
         }
         pNC->ncFlags |= NC_Subquery;
       }
diff --git a/src/select.c b/src/select.c
index d35103cdd..fd99dc91f 100644
--- a/src/select.c
+++ b/src/select.c
@@ -384,7 +384,7 @@ static int tableAndColumnIndex(
   int iEnd,            /* Last member of pSrc->a[] to check */
   const char *zCol,    /* Name of the column we are looking for */
   int *piTab,          /* Write index of pSrc->a[] here */
-  int *piCol,          /* Write index of pSrc->a[*piTab].pTab->aCol[] here */
+  int *piCol,          /* Write index of pSrc->a[*piTab].pSTab->aCol[] here */
   int bIgnoreHidden    /* Ignore hidden columns */
 ){
   int i;               /* For looping over tables in pSrc */
@@ -4658,7 +4658,7 @@ static int flattenSubquery(
   ** complete, since there may still exist Expr.pTab entries that
   ** refer to the subquery even after flattening.  Ticket #3346.
   **
-  ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
+  ** pSubitem->pSTab is always non-NULL by test restrictions and tests above.
   */
   if( ALWAYS(pSubitem->pSTab!=0) ){
     Table *pTabToDel = pSubitem->pSTab;
@@ -5771,7 +5771,7 @@ With *sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){
 ** CTE expression, through routine checks to see if the reference is
 ** a recursive reference to the CTE.
 **
-** If pFrom matches a CTE according to either of these two above, pFrom->pTab
+** If pFrom matches a CTE according to either of these two above, pFrom->pSTab
 ** and other fields are populated accordingly.
 **
 ** Return 0 if no match is found.
@@ -7399,6 +7399,74 @@ static int fromClauseTermCanBeCoroutine(
 }
 
 /*
+** Argument pWhere is the WHERE clause belonging to SELECT statement p. This
+** function attempts to transform expressions of the form:
+**
+**     EXISTS (SELECT ...)
+**
+** into joins. For example, given
+**
+**    CREATE TABLE sailors(sid INTEGER PRIMARY KEY, name TEXT);
+**    CREATE TABLE reserves(sid INT, day DATE, PRIMARY KEY(sid, day));
+**
+**    SELECT name FROM sailors AS S WHERE EXISTS (
+**      SELECT * FROM reserves AS R WHERE S.sid = R.sid AND R.day = '2022-10-25'
+**    );
+**
+** the SELECT statement may be transformed as follows:
+**
+**    SELECT name FROM sailors AS S, reserves AS R
+**      WHERE S.sid = R.sid AND R.day = '2022-10-25';
+*/
+static SQLITE_NOINLINE void existsToJoin(
+  Parse *pParse,
+  Select *p,
+  Expr *pWhere
+){
+  if( pWhere 
+   && !ExprHasProperty(pWhere, EP_OuterON|EP_InnerON) 
+   && p->pSrc->nSrc>0
+   && p->pSrc->nSrc<BMS
+   && pParse->db->mallocFailed==0 
+  ){
+    if( pWhere->op==TK_AND ){
+      Expr *pRight = pWhere->pRight;
+      existsToJoin(pParse, p, pWhere->pLeft);
+      existsToJoin(pParse, p, pRight);
+    }
+    else if( pWhere->op==TK_EXISTS ){
+      Select *pSub = pWhere->x.pSelect;
+      if( pSub->pSrc->nSrc==1 
+       && (pSub->selFlags & (SF_Aggregate|SF_Correlated))==SF_Correlated
+       && pSub->pWhere
+      ){
+        memset(pWhere, 0, sizeof(*pWhere));
+        pWhere->op = TK_INTEGER;
+        pWhere->u.iValue = 1;
+        ExprSetProperty(pWhere, EP_IntValue);
+
+        assert( p->pWhere!=0 );
+        pSub->pSrc->a[0].fg.fromExists = 1;
+        pSub->pSrc->a[0].fg.jointype |= JT_CROSS;
+        p->pSrc = sqlite3SrcListAppendList(pParse, p->pSrc, pSub->pSrc);
+        p->pWhere = sqlite3PExpr(pParse, TK_AND, p->pWhere, pSub->pWhere);
+
+        pSub->pWhere = 0;
+        pSub->pSrc = 0;
+        sqlite3ParserAddCleanup(pParse, sqlite3SelectDeleteGeneric, pSub);
+#if TREETRACE_ENABLED
+        if( sqlite3TreeTrace & 0x100000 ){
+          TREETRACE(0x100000,pParse,p,
+                    ("After EXISTS-to-JOIN optimization:\n"));
+          sqlite3TreeViewSelect(0, p, 0);
+        }
+#endif
+      }
+    }
+  }
+}
+
+/*
 ** Generate byte-code for the SELECT statement given in the p argument. 
 **
 ** The results are returned according to the SelectDest structure.
@@ -7766,6 +7834,13 @@ int sqlite3Select(
   }
 #endif
 
+  /* If there may be an "EXISTS (SELECT ...)" in the WHERE clause, attempt
+  ** to change it into a join.  */
+  if( pParse->bHasExists && OptimizationEnabled(db,SQLITE_ExistsToJoin) ){
+    existsToJoin(pParse, p, p->pWhere);
+    pTabList = p->pSrc;
+  }
+
   /* Do the WHERE-clause constant propagation optimization if this is
   ** a join.  No need to spend time on this operation for non-join queries
   ** as the equivalent optimization will be handled by query planner in
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 36a21d92e..6ae456f59 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1154,6 +1154,7 @@ extern u32 sqlite3TreeTrace;
 **   0x00040000     SELECT tree dump after all code has been generated
 **   0x00080000     NOT NULL strength reduction
 **   0x00100000     Pointers are all shown as zero
+**   0x00200000     EXISTS-to-JOIN optimization
 */
 
 /*
@@ -1926,6 +1927,7 @@ struct sqlite3 {
 #define SQLITE_OnePass        0x08000000 /* Single-pass DELETE and UPDATE */
 #define SQLITE_OrderBySubq    0x10000000 /* ORDER BY in subquery helps outer */
 #define SQLITE_StarQuery      0x20000000 /* Heurists for star queries */
+#define SQLITE_ExistsToJoin   0x40000000 /* The EXISTS-to-JOIN optimization */
 #define SQLITE_AllOpts        0xffffffff /* All optimizations */
 
 /*
@@ -3370,6 +3372,7 @@ struct SrcItem {
     unsigned rowidUsed :1;     /* The ROWID of this table is referenced */
     unsigned fixedSchema :1;   /* Uses u4.pSchema, not u4.zDatabase */
     unsigned hadSchema :1;     /* Had u4.zDatabase before u4.pSchema */
+    unsigned fromExists :1;    /* Comes from WHERE EXISTS(...) */
   } fg;
   int iCursor;      /* The VDBE cursor number used to access this table */
   Bitmask colUsed;  /* Bit N set if column N used. Details above for N>62 */
@@ -3900,6 +3903,7 @@ struct Parse {
   u8 disableLookaside; /* Number of times lookaside has been disabled */
   u8 prepFlags;        /* SQLITE_PREPARE_* flags */
   u8 withinRJSubrtn;   /* Nesting level for RIGHT JOIN body subroutines */
+  u8 bHasExists;       /* Has a correlated "EXISTS (SELECT ....)" expression */
   u8 mSubrtnSig;       /* mini Bloom filter on available SubrtnSig.selId */
   u8 eTriggerOp;       /* TK_UPDATE, TK_INSERT or TK_DELETE */
   u8 bReturning;       /* Coding a RETURNING trigger */
diff --git a/src/where.c b/src/where.c
index 4a0c3988c..69b206a22 100644
--- a/src/where.c
+++ b/src/where.c
@@ -3518,6 +3518,7 @@ static int whereLoopAddBtreeIndex(
    && pProbe->hasStat1!=0
    && OptimizationEnabled(db, SQLITE_SkipScan)
    && pProbe->aiRowLogEst[saved_nEq+1]>=42  /* TUNING: Minimum for skip-scan */
+   && pSrc->fg.fromExists==0
    && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
   ){
     LogEst nIter;
@@ -7397,6 +7398,9 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
         sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2);
       }
 #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
+      if( pTabList->a[pLevel->iFrom].fg.fromExists ){
+        sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);
+      }
       /* The common case: Advance to the next row */
       if( pLevel->addrCont ) sqlite3VdbeResolveLabel(v, pLevel->addrCont);
       sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
diff --git a/src/wherecode.c b/src/wherecode.c
index cc672aa83..9c611001b 100644
--- a/src/wherecode.c
+++ b/src/wherecode.c
@@ -135,6 +135,7 @@ void sqlite3WhereAddExplainText(
 #if defined(SQLITE_DEBUG) && !defined(SQLITE_OMIT_EXPLAIN)
     char *zMsg;                   /* Text to add to EQP output */
 #endif
+    const char *zFormat;
     StrAccum str;                 /* EQP output string */
     char zBuf[100];               /* Initial space for EQP output string */
 
@@ -149,7 +150,14 @@ void sqlite3WhereAddExplainText(
 
     sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
     str.printfFlags = SQLITE_PRINTF_INTERNAL;
-    sqlite3_str_appendf(&str, "%s %S", isSearch ? "SEARCH" : "SCAN", pItem);
+    if( pItem->fg.fromExists ){
+      zFormat = "SINGLETON %S";
+    }else if( isSearch ){
+      zFormat = "SEARCH %S";
+    }else{
+      zFormat = "SCAN %S";
+    }
+    sqlite3_str_appendf(&str, zFormat, pItem);
     if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){
       const char *zFmt = 0;
       Index *pIdx;