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

to relax the requirement of having an indexed join constraint.

FossilOrigin-Name: 1c1aef2b7feae29066d0330699ab634ef41f5b60cdcd479a60cb1a5409553138

1 files changed, 78 insertions, 3 deletions

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