SQLite

    }
  }

  whereLoopClear(db, pNew);
  return rc;
}

/* Implementation of the order-by-subquery optimization:
**
** WhereLoop pLoop, which the iLoop-th term of the nested loop, is really
** a subquery or CTE that has an ORDER BY clause.  See if any of the terms
** in the subquery ORDER BY clause will satisfy pOrderBy from the outer
** query.  Mark off all satisfied terms (by setting bits in *pOBSat) and
** return TRUE if they do.  If not, return false.
**
** Example:
**
**    CREATE TABLE t1(a,b,c, PRIMARY KEY(a,b));
**    CREATE TABLE t2(x,y);
**    WITH t3(p,q) AS MATERIALIZED (SELECT x+y, x-y FROM t2 ORDER BY x+y)
**       SELECT * FROM t3 JOIN t1 ON a=q ORDER BY p, b;
**
** The CTE named "t3" comes out in the natural order of "p", so the first
** first them of "ORDER BY p,b" is satisfied by a sequential scan of "t3"
** and sorting only needs to occur on the second term "b".
**
** Limitations:
**
** (1)  The optimization is not applied if the outer ORDER BY contains
**      a COLLATE clause.  The optimization might be applied if the
**      outer ORDER BY uses NULLS FIRST, NULLS LAST, ASC, and/or DESC as
**      long as the subquery ORDER BY does the same.  But if the
**      outer ORDER BY uses COLLATE, even a redundant COLLATE, the
**      optimization is bypassed.
**
** (2)  The subquery ORDER BY terms must exactly match subquery result
**      columns, including any COLLATE annotations.  This routine relies
**      on iOrderByCol to do matching between order by terms and result
**      columns, and iOrderByCol will not be set if the result column
**      and ORDER BY collations differ.
**
** (3)  The subquery and outer ORDER BY can be in opposite directions as
**      long as  the subquery is materialized.  If the subquery is
**      implemented as a co-routine, the sort orders must be in the same
**      direction because there is no way to run a co-routine backwards.
*/
static SQLITE_NOINLINE int wherePathMatchSubqueryOB(
  WhereInfo *pWInfo,      /* The WHERE clause */
  WhereLoop *pLoop,       /* The nested loop term that is a subquery */
  int iLoop,              /* Which level of the nested loop.  0==outermost */
  int iCur,               /* Cursor used by the this loop */

  ExprList *pOrderBy,     /* The ORDER BY clause on the whole query */
  Bitmask *pRevMask,      /* When loops need to go in reverse order */
  Bitmask *pOBSat         /* Which terms of pOrderBy are satisfied so far */
){
  int iOB;                /* Index into pOrderBy->a[] */
  int jSub;               /* Index into pSubOB->a[] */
  u8 rev = 0;             /* True if iOB and jSub sort in opposite directions */
  u8 revIdx = 0;          /* Sort direction for jSub */
  Expr *pOBExpr;          /* Current term of outer ORDER BY */
  ExprList *pSubOB;       /* Complete ORDER BY on the subquery */

  pSubOB = pLoop->u.btree.pOrderBy;
  assert( pSubOB!=0 );
  for(iOB=0; (MASKBIT(iOB) & *pOBSat)!=0; iOB++){}
  for(jSub=0; jSub<pSubOB->nExpr && iOB<pOrderBy->nExpr; jSub++, iOB++){
    if( pSubOB->a[jSub].u.x.iOrderByCol==0 ) break;
    pOBExpr = pOrderBy->a[iOB].pExpr;
    if( pOBExpr->op!=TK_COLUMN && pOBExpr->op!=TK_AGG_COLUMN ) break;
    if( pOBExpr->iTable!=iCur ) break;
    if( pOBExpr->iColumn!=pSubOB->a[jSub].u.x.iOrderByCol-1 ) break;
    if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){
      u8 sfOB = pOrderBy->a[iOB].fg.sortFlags;   /* sortFlags for iOB */
      u8 sfSub = pSubOB->a[jSub].fg.sortFlags;   /* sortFlags for jSub */
      if( (sfSub & KEYINFO_ORDER_BIGNULL) != (sfOB & KEYINFO_ORDER_BIGNULL) ){
        break;
      }
      revIdx = sfSub & KEYINFO_ORDER_DESC;
      if( jSub>0 ){
        if( (rev^revIdx)!=(sfOB & KEYINFO_ORDER_DESC) ){
          break;
        }
      }else{
        rev = revIdx ^ (sfOB & KEYINFO_ORDER_DESC);
        if( rev ){
          if( (pLoop->wsFlags & WHERE_COROUTINE)!=0 ){
            /* Cannot run a co-routine in reverse order */
            break;
          }
          *pRevMask |= MASKBIT(iLoop);
        }
      }
    }
    *pOBSat |= MASKBIT(iOB);
  }
  return jSub>0;
}

/*
** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
** parameters) to see if it outputs rows in the requested ORDER BY
** (or GROUP BY) without requiring a separate sort operation.  Return N:
**

      obSat |= MASKBIT(i);
    }

    if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
      if( pLoop->wsFlags & WHERE_IPK ){
        if( pLoop->u.btree.pOrderBy
         && OptimizationEnabled(db, SQLITE_OrderBySubq)
         &&  wherePathMatchSubqueryOB(pWInfo,pLoop,iLoop,iCur,
                                     pOrderBy,pRevMask, &obSat)
        ){
          nColumn = 0;
          isOrderDistinct = 0;
        }else{
          nColumn = 1;
        }

# 2024-08-15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# Specifically, it tests cases with order-by-subquery optimization in which
# an ORDER BY in a subquery is used to help resolve an ORDER BY in the
# outer query without having to do an extra sort.
# 

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix orderbyb

db null NULL
do_execsql_test 1.0 {
  CREATE TABLE t1(a TEXT, b TEXT, c INT);
  INSERT INTO t1 VALUES(NULL,NULL,NULL);
  WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7)
    INSERT INTO t1(a,b,c) SELECT char(p,p), char(q,q), n FROM
            (SELECT ((n-1)%4)+0x61 AS p, abs(n*2-9+(n>=5))+0x60 AS q, n FROM c);
  UPDATE t1 SET b=upper(b) WHERE c=1;
  CREATE TABLE t2(k TEXT PRIMARY KEY, v INT) WITHOUT ROWID;
  WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7)
    INSERT INTO t2(k,v) SELECT char(0x60+n,0x60+n), n FROM c;
  WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7)
    INSERT INTO t2(k,v) SELECT char(0x40+n,0x40+n), n FROM c;
  SELECT a,b,c,tx.v AS 'v-a', ty.v AS 'v-b'
    FROM t1 LEFT JOIN t2 AS tx ON tx.k=a
            LEFT JOIN t2 AS ty ON ty.k=b
   ORDER BY c;
} {
  NULL  NULL  NULL  NULL  NULL
  aa    GG    1     1     7
  bb    ee    2     2     5
  cc    cc    3     3     3
  dd    aa    4     4     1
  aa    bb    5     1     2
  bb    dd    6     2     4
  cc    ff    7     3     6
}

do_eqp_execsql_test 1.1 {
  WITH t3(x,y) AS (SELECT a, b FROM t1 ORDER BY a, b LIMIT 8)
    SELECT x, y, v FROM t3 LEFT JOIN t2 ON k=t3.y ORDER BY x, y COLLATE nocase;
} {
  QUERY PLAN
  |--CO-ROUTINE t3
  |  |--SCAN t1
  |  `--USE TEMP B-TREE FOR ORDER BY
  |--SCAN t3
  |--SEARCH t2 USING PRIMARY KEY (k=?) LEFT-JOIN
  `--USE TEMP B-TREE FOR LAST TERM OF ORDER BY
} {
  NULL  NULL  NULL
  aa    bb    2
  aa    GG    7
  bb    dd    4
  bb    ee    5
  cc    cc    3
  cc    ff    6
  dd    aa    1
}

do_eqp_execsql_test 1.2 {
  WITH t3(x,y) AS MATERIALIZED (SELECT a, b COLLATE nocase FROM t1 ORDER BY 1,2)
    SELECT x, y, v FROM t3 LEFT JOIN t2 ON k=t3.y ORDER BY x,y;
} {
  QUERY PLAN
  |--MATERIALIZE t3
  |  |--SCAN t1
  |  `--USE TEMP B-TREE FOR ORDER BY
  |--SCAN t3
  `--SEARCH t2 USING PRIMARY KEY (k=?) LEFT-JOIN
} {
  NULL  NULL  NULL
  aa    bb    2
  aa    GG    7
  bb    dd    4
  bb    ee    5
  cc    cc    3
  cc    ff    6
  dd    aa    1
}


finish_test

  } else {
    if {[string index $res 0]!="/"} {
      set res "/*$res*/"
    }
    uplevel do_execsql_test $name [list "EXPLAIN QUERY PLAN $sql"] [list $res]
  }
}

# Do both an eqp_test and an execsql_test on the same SQL.
#
proc do_eqp_execsql_test {name sql res1 res2} {
  if {[regexp {^\s+QUERY PLAN\n} $res1]} {

    set query_plan [query_plan_graph $sql]

    if {[list {*}$query_plan]==[list {*}$res1]} {
      uplevel [list do_test ${name}a [list set {} ok] ok]
    } else {
      uplevel [list \
        do_test ${name}a [list query_plan_graph $sql] $res1
      ]
    }
  } else {
    if {[string index $res 0]!="/"} {
      set res1 "/*$res1*/"
    }
    uplevel do_execsql_test ${name}a [list "EXPLAIN QUERY PLAN $sql"] [list $res1]
  }
  uplevel do_execsql_test ${name}b [list $sql] [list $res2]
}


#-------------------------------------------------------------------------
#   Usage: do_select_tests PREFIX ?SWITCHES? TESTLIST
#
# Where switches are:
#