From cb3d6d14febae2547f1bd4661eab0795dc8e815b Mon Sep 17 00:00:00 2001
From: drh <>
Date: Thu, 22 Jan 2026 19:02:32 +0000
Subject: [PATCH] Enhance the [/info/e33da6d5dc964db8|EXISTS-to-JOIN
 optimization] so that the inserted JOIN terms are not required to be on the
 inner-most loops, as long as all dependencies for the EXISTS-to-JOIN loops
 are in outer loops.  This addresses the performance concern of
 [forum:/forumpost/2026-01-21T19:49:04z|forum post 2026-01-21T19:49:04z]. Test
 cases in TH3.

FossilOrigin-Name: 298d5c8fa6207afb6cdcca3b312a1eeddda0edeb6d840aa5476a7195047a2158
---
 manifest      | 14 +++++++-------
 manifest.uuid |  2 +-
 src/select.c  |  1 -
 src/where.c   | 34 +++++++++++++++++++++++++---------
 4 files changed, 33 insertions(+), 18 deletions(-)

diff --git a/manifest b/manifest
index a99d9f2260..46e191371d 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C For\sthe\s".eqp\sfull"\sshow\sboth\sthe\sQUERY\sPLAN\sand\sthe\sfull\sbyte\scode,\sjust\sas\nit\shas\sin\sthe\spast.
-D 2026-01-22T15:59:45.577
+C Enhance\sthe\s[/info/e33da6d5dc964db8|EXISTS-to-JOIN\soptimization]\sso\sthat\nthe\sinserted\sJOIN\sterms\sare\snot\srequired\sto\sbe\son\sthe\sinner-most\sloops,\nas\slong\sas\sall\sdependencies\sfor\sthe\sEXISTS-to-JOIN\sloops\sare\sin\souter\nloops.\s\sThis\saddresses\sthe\sperformance\sconcern\sof\n[forum:/forumpost/2026-01-21T19:49:04z|forum\spost\s2026-01-21T19:49:04z].\nTest\scases\sin\sTH3.
+D 2026-01-22T19:02:32.952
 F .fossil-settings/binary-glob 61195414528fb3ea9693577e1980230d78a1f8b0a54c78cf1b9b24d0a409ed6a x
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
@@ -738,7 +738,7 @@ F src/printf.c b1b29b5e58e1530d5daeee5963d3c318d8ab2d7e38437580e28755753e0c1ded
 F src/random.c 606b00941a1d7dd09c381d3279a058d771f406c5213c9932bbd93d5587be4b9c
 F src/resolve.c 47aa7fdc9ec4c19b103ac5e79d7887d30119b5675309facf5eed1118391c868b
 F src/rowset.c 8432130e6c344b3401a8874c3cb49fefe6873fec593294de077afea2dce5ec97
-F src/select.c 4d45a04431db072040d6625ee21c1dc483c9b2b64a5ab419f4a4e05aabed1204
+F src/select.c f6ab7ed61778798626c2655d67f43506545d75becb1736c1f0dbc6a2830bf644
 F src/shell.c.in e8818572acd50464bc00426fe0d755e98239f73d531437c3dc7721d1fecb1231
 F src/sqlite.h.in 476f3efeb5dd26ad94dcbce262ca7eb9d042d797a92d624059c67ef37d5b3ab4
 F src/sqlite3.rc 015537e6ac1eec6c7050e17b616c2ffe6f70fca241835a84a4f0d5937383c479
@@ -820,7 +820,7 @@ F src/vxworks.h 9d18819c5235b49c2340a8a4d48195ec5d5afb637b152406de95a9436beeaeab
 F src/wal.c 505a98fbc599a971d92cb90371cf54546c404cd61e04fd093e7b0c8ff978f9b6
 F src/wal.h ba252daaa94f889f4b2c17c027e823d9be47ce39da1d3799886bbd51f0490452
 F src/walker.c d5006d6b005e4ea7302ad390957a8d41ed83faa177e412f89bc5600a7462a014
-F src/where.c 0079b6ba463ae806b99b20cb335729dcce5f3e496b81cccf6441dc11f8c5bf92
+F src/where.c ca89f988b6a97f676178217a919f7d32aea41a4fcd7466c1541882cd79f74e9e
 F src/whereInt.h 8d94cb116c9e06205c3d5ac87af065fc044f8cf08bfdccd94b6ea1c1308e65da
 F src/wherecode.c 71c5c6804b7f882dec8ec858758accae02fcfca13df3cc720f1f258e663ec7c5
 F src/whereexpr.c cadb37fbaa2cb6d1ec1687923c3ac21aed4187d198f4500c00a01abb24c3cb44
@@ -2193,8 +2193,8 @@ F tool/warnings-clang.sh bbf6a1e685e534c92ec2bfba5b1745f34fb6f0bc2a362850723a9ee
 F tool/warnings.sh d924598cf2f55a4ecbc2aeb055c10bd5f48114793e7ba25f9585435da29e7e98
 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f
 F tool/winmain.c 00c8fb88e365c9017db14c73d3c78af62194d9644feaf60e220ab0f411f3604c
-P 2b3b36da9d60c265dceec5964ea51c752d81f41459fb6849c8faea658b253552
-R 9e5a6565e4452411f9695714ff85ba95
+P 756484fcaa7efed0691814f3affeb2449d3301c5c764530f2ec8e290caea567f
+R eaa1f3917dc945edf4c3fa8d74ac8c4b
 U drh
-Z 7ade86c93ca3010bfdd0788463884fbc
+Z 48ecc3b553956c6b2d376be4e206c0f9
 # Remove this line to create a well-formed Fossil manifest.
diff --git a/manifest.uuid b/manifest.uuid
index d6d2621dbe..9a8d37ca03 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-756484fcaa7efed0691814f3affeb2449d3301c5c764530f2ec8e290caea567f
+298d5c8fa6207afb6cdcca3b312a1eeddda0edeb6d840aa5476a7195047a2158
diff --git a/src/select.c b/src/select.c
index 8fff983901..7ae793ed7d 100644
--- a/src/select.c
+++ b/src/select.c
@@ -7485,7 +7485,6 @@ static SQLITE_NOINLINE void existsToJoin(
         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);
         if( pSubWhere ){
           p->pWhere = sqlite3PExpr(pParse, TK_AND, p->pWhere, pSubWhere);
diff --git a/src/where.c b/src/where.c
index 1cee43c06b..24d527bbc3 100644
--- a/src/where.c
+++ b/src/where.c
@@ -4880,6 +4880,17 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
       if( pItem->fg.jointype & JT_LTORJ ) hasRightJoin = 1;
       mPrereq |= mPrior;
       bFirstPastRJ = (pItem->fg.jointype & JT_RIGHT)!=0;
+    }else if( pItem->fg.fromExists ){
+      /* joins that result from the EXISTS-to-JOIN optimization should not
+      ** be moved to the left of any of their dependencies */
+      WhereClause *pWC = &pWInfo->sWC;
+      WhereTerm *pTerm;
+      int i;
+      for(i=pWC->nBase, pTerm=pWC->a; i>0; i--, pTerm++){
+        if( (pNew->maskSelf & pTerm->prereqAll)!=0 ){
+          mPrereq |= (pTerm->prereqAll & (pNew->maskSelf-1));
+        }
+      }
     }else if( !hasRightJoin ){
       mPrereq = 0;
     }
@@ -7432,14 +7443,15 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
       }
 #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
     }
-    if( pTabList->a[pLevel->iFrom].fg.fromExists && i==pWInfo->nLevel-1 ){
-      /* If the EXISTS-to-JOIN optimization was applied, then the EXISTS
-      ** loop(s) will be the inner-most loops of the join. There might be
-      ** multiple EXISTS loops, but they will all be nested, and the join
-      ** order will not have been changed by the query planner.  If the
-      ** inner-most EXISTS loop sees a single successful row, it should
-      ** break out of *all* EXISTS loops.  But only the inner-most of the
-      ** nested EXISTS loops should do this breakout. */
+    if( pTabList->a[pLevel->iFrom].fg.fromExists
+     && (i==pWInfo->nLevel-1
+           || pTabList->a[pWInfo->a[i+1].iFrom].fg.fromExists==0)
+    ){
+      /* This is an EXISTS-to-JOIN optimization which is either the
+      ** inner-most loop, or the inner-most of a group of nested
+      ** EXISTS-to-JOIN optimization loops.  If this loop sees a successful
+      ** row, it should break out of itself as well as other EXISTS-to-JOIN
+      ** loops in which is is directly nested. */
       int nOuter = 0; /* Nr of outer EXISTS that this one is nested within */
       while( nOuter<i ){
         if( !pTabList->a[pLevel[-nOuter-1].iFrom].fg.fromExists ) break;
@@ -7447,7 +7459,11 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
       }
       testcase( nOuter>0 );
       sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel[-nOuter].addrBrk);
-      VdbeComment((v, "EXISTS break"));
+      if( nOuter ){
+        VdbeComment((v, "EXISTS break %d..%d", i-nOuter, i));
+      }else{
+        VdbeComment((v, "EXISTS break %d", i));
+      }
     }
     sqlite3VdbeResolveLabel(v, pLevel->addrCont);
     if( pLevel->op!=OP_Noop ){
-- 
2.47.3