SQLite

  w.xSelectCallback = sqlite3SelectWalkNoop;
  w.u.pSrcItem = pSrcItem;
  pSrcItem->colUsed = 0;
  sqlite3WalkSelect(&w, pSelect);
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/*
** Assign new cursor numbers to each of the items in pSrc. For each
** new cursor number assigned, set an entry in the aCsrMap[] array 
** to map the old cursor number to the new:
**
**     aCsrMap[iOld] = iNew;
**
** The array is guaranteed by the caller to be large enough for all
** existing cursor numbers in pSrc.
**
** If pSrc contains any sub-selects, call this routine recursively
** on the FROM clause of each such sub-select, with iExcept set to -1.
*/
static void srclistRenumberCursors(
  Parse *pParse,                  /* Parse context */
  int *aCsrMap,                   /* Array to store cursor mappings in */
  SrcList *pSrc,                  /* FROM clause to renumber */
  int iExcept                     /* FROM clause item to skip */
){
  int i;
  struct SrcList_item *pItem;
  for(i=0, pItem=pSrc->a; i<pSrc->nSrc; i++, pItem++){
    if( i!=iExcept ){
      Select *p;
      pItem->iCursor = aCsrMap[pItem->iCursor] = pParse->nTab++;
      for(p=pItem->pSelect; p; p=p->pPrior){
        srclistRenumberCursors(pParse, aCsrMap, p->pSrc, -1);
      }
    }
  }
}

/*
** Expression walker callback used by renumberCursors() to update
** Expr objects to match newly assigned cursor numbers.
*/
static int renumberCursorsCb(Walker *pWalker, Expr *pExpr){
  int *aCsrMap = pWalker->u.aiCol;
  if( pExpr->op==TK_COLUMN && aCsrMap[pExpr->iTable] ){
    pExpr->iTable = aCsrMap[pExpr->iTable];
  }
  return WRC_Continue;
}

/*
** Assign a new cursor number to each cursor in the FROM clause (Select.pSrc)
** of the SELECT statement passed as the second argument, and to each 
** cursor in the FROM clause of any FROM clause sub-selects, recursively.
** Except, do not assign a new cursor number to the iExcept'th element in
** the FROM clause of (*p). Update all expressions and other references 
** to refer to the new cursor numbers.
**
** Argument aCsrMap is an array that may be used for temporary working
** space. Two guarantees are made by the caller:
**
**   * the array is larger than the largest cursor number used within the
**     select statement passed as an argument, and
**
**   * the array entries for all cursor numbers that do *not* appear in 
**     FROM clauses of the select statement as described above are 
**     initialized to zero.
*/
static void renumberCursors(
  Parse *pParse,                  /* Parse context */
  Select *p,                      /* Select to renumber cursors within */
  int iExcept,                    /* FROM clause item to skip */
  int *aCsrMap                    /* Working space */
){
  Walker w;
  srclistRenumberCursors(pParse, aCsrMap, p->pSrc, iExcept);
  memset(&w, 0, sizeof(w));
  w.u.aiCol = aCsrMap;
  w.xExprCallback = renumberCursorsCb;
  w.xSelectCallback = sqlite3SelectWalkNoop;
  sqlite3WalkSelect(&w, p);
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/*
** This routine attempts to flatten subqueries as a performance optimization.
** This routine returns 1 if it makes changes and 0 if no flattening occurs.
**
** To understand the concept of flattening, consider the following
** query:

**  (17)  If the subquery is a compound select, then
**        (17a) all compound operators must be a UNION ALL, and
**        (17b) no terms within the subquery compound may be aggregate
**              or DISTINCT, and
**        (17c) every term within the subquery compound must have a FROM clause
**        (17d) the outer query may not be
**              (17d1) aggregate, or
**              (17d2) DISTINCT

**        (17e) the subquery may not contain window functions, and
**        (17f) the subquery must not be the RHS of a LEFT JOIN.
**
**        The parent and sub-query may contain WHERE clauses. Subject to
**        rules (11), (13) and (14), they may also contain ORDER BY,
**        LIMIT and OFFSET clauses.  The subquery cannot use any compound
**        operator other than UNION ALL because all the other compound
**        operators have an implied DISTINCT which is disallowed by
**        restriction (4).
**
**        Also, each component of the sub-query must return the same number
**        of result columns. This is actually a requirement for any compound
**        SELECT statement, but all the code here does is make sure that no
**        such (illegal) sub-query is flattened. The caller will detect the
**        syntax error and return a detailed message.
**
**  (18)  If the sub-query is a compound select, then all terms of the
**        ORDER BY clause of the parent must be copies of a term returned
**        by the parent query.
**
**  (19)  If the subquery uses LIMIT then the outer query may not
**        have a WHERE clause.
**
**  (20)  If the sub-query is a compound select, then it must not use
**        an ORDER BY clause.  Ticket #3773.  We could relax this constraint
**        somewhat by saying that the terms of the ORDER BY clause must
**        appear as unmodified result columns in the outer query.  But we
**        have other optimizations in mind to deal with that case.
**
**  (21)  If the subquery uses LIMIT then the outer query may not be
**        DISTINCT.  (See ticket [752e1646fc]).
**
**  (22)  The subquery may not be a recursive CTE.
**

**  (23)  If the outer query is a recursive CTE, then the sub-query may not be
**        a compound query.  This restriction is because transforming the
**        parent to a compound query confuses the code that handles
**        recursive queries in multiSelect().
**
**  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
**        The subquery may not be an aggregate that uses the built-in min() or 
**        or max() functions.  (Without this restriction, a query like:
**        "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily

  int iNewParent = -1;/* Replacement table for iParent */
  int isLeftJoin = 0; /* True if pSub is the right side of a LEFT JOIN */    
  int i;              /* Loop counter */
  Expr *pWhere;                    /* The WHERE clause */
  struct SrcList_item *pSubitem;   /* The subquery */
  sqlite3 *db = pParse->db;
  Walker w;                        /* Walker to persist agginfo data */
  int *aCsrMap = 0;

  /* Check to see if flattening is permitted.  Return 0 if not.
  */
  assert( p!=0 );
  assert( p->pPrior==0 );
  if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
  pSrc = p->pSrc;

  ** that make up the compound SELECT are allowed to be aggregate or distinct
  ** queries.
  */
  if( pSub->pPrior ){
    if( pSub->pOrderBy ){
      return 0;  /* Restriction (20) */
    }
    if( isAgg || (p->selFlags & SF_Distinct)!=0 || isLeftJoin>0 ){
      return 0; /* (17d1), (17d2), or (17f) */
    }
    for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
      testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
      testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
      assert( pSub->pSrc!=0 );
      assert( (pSub->selFlags & SF_Recursive)==0 );
      assert( pSub->pEList->nExpr==pSub1->pEList->nExpr );
      if( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))!=0    /* (17b) */
       || (pSub1->pPrior && pSub1->op!=TK_ALL)                 /* (17a) */
       || pSub1->pSrc->nSrc<1                                  /* (17c) */
#ifndef SQLITE_OMIT_WINDOWFUNC
       || pSub1->pWin                                          /* (17e) */
#endif
      ){
        return 0;
      }
      testcase( pSub1->pSrc->nSrc>1 );
    }

    /* Restriction (18). */
    if( p->pOrderBy ){
      int ii;
      for(ii=0; ii<p->pOrderBy->nExpr; ii++){
        if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;
      }
    }


    /* Restriction (23) */





    if( (p->selFlags & SF_Recursive) ) return 0;

    if( pSrc->nSrc>1 ){
      aCsrMap = sqlite3DbMallocZero(db, pParse->nTab*sizeof(int));
    }
  }

  /***** If we reach this point, flattening is permitted. *****/
  SELECTTRACE(1,pParse,p,("flatten %u.%p from term %d\n",
                   pSub->selId, pSub, iFrom));

  /* Authorize the subquery */
  pParse->zAuthContext = pSubitem->zName;
  TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);
  testcase( i==SQLITE_DENY );
  pParse->zAuthContext = zSavedAuthContext;

  /* Delete the transient structures associated with thesubquery */
  pSub1 = pSubitem->pSelect;
  sqlite3DbFree(db, pSubitem->zDatabase);
  sqlite3DbFree(db, pSubitem->zName);
  sqlite3DbFree(db, pSubitem->zAlias);
  pSubitem->zDatabase = 0;
  pSubitem->zName = 0;
  pSubitem->zAlias = 0;
  pSubitem->pSelect = 0;
  assert( pSubitem->pOn==0 );

  /* If the sub-query is a compound SELECT statement, then (by restrictions
  ** 17 and 18 above) it must be a UNION ALL and the parent query must 
  ** be of the form:
  **
  **     SELECT <expr-list> FROM (<sub-query>) <where-clause> 
  **

  ** We call this the "compound-subquery flattening".
  */
  for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){
    Select *pNew;
    ExprList *pOrderBy = p->pOrderBy;
    Expr *pLimit = p->pLimit;
    Select *pPrior = p->pPrior;
    Table *pItemTab = pSubitem->pTab;
    pSubitem->pTab = 0;
    p->pOrderBy = 0;

    p->pPrior = 0;
    p->pLimit = 0;
    pNew = sqlite3SelectDup(db, p, 0);
    p->pLimit = pLimit;
    p->pOrderBy = pOrderBy;

    p->op = TK_ALL;
    pSubitem->pTab = pItemTab;
    if( pNew==0 ){
      p->pPrior = pPrior;
    }else{
      if( aCsrMap && db->mallocFailed==0 ){
        renumberCursors(pParse, pNew, iFrom, aCsrMap);
      }
      pNew->pPrior = pPrior;
      if( pPrior ) pPrior->pNext = pNew;
      pNew->pNext = p;
      p->pPrior = pNew;
      SELECTTRACE(2,pParse,p,("compound-subquery flattener"
                              " creates %u as peer\n",pNew->selId));
    }






    assert( pSubitem->pSelect==0 );
  }




  sqlite3DbFree(db, aCsrMap);


  if( db->mallocFailed ){

    pSubitem->pSelect = pSub1;
    return 1;
  }

  /* Defer deleting the Table object associated with the
  ** subquery until code generation is
  ** 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.

  ** the FROM clause of the outer query.  Before doing this, remember
  ** the cursor number for the original outer query FROM element in
  ** iParent.  The iParent cursor will never be used.  Subsequent code
  ** will scan expressions looking for iParent references and replace
  ** those references with expressions that resolve to the subquery FROM
  ** elements we are now copying in.
  */
  pSub = pSub1;
  for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){
    int nSubSrc;
    u8 jointype = 0;
    assert( pSub!=0 );
    pSubSrc = pSub->pSrc;     /* FROM clause of subquery */
    nSubSrc = pSubSrc->nSrc;  /* Number of terms in subquery FROM clause */
    pSrc = pParent->pSrc;     /* FROM clause of the outer query */


    if( pParent==p ){
      jointype = pSubitem->fg.jointype;     /* First time through the loop */





    }
    
    /* The subquery uses a single slot of the FROM clause of the outer
    ** query.  If the subquery has more than one element in its FROM clause,
    ** then expand the outer query to make space for it to hold all elements
    ** of the subquery.
    **
    ** Example:
    **

  SELECT * FROM x1, x4
} {
  a 21 a 22 a 23 a 24 a 25 a 302 a 303 a 301
  b 21 b 22 b 23 b 24 b 25 b 302 b 303 b 301
}

do_execsql_test 5.3 {
  SELECT * FROM x1, (SELECT b FROM vvv UNION ALL SELECT c from x3) ORDER BY 1,2;
} {
  a 21 a 22 a 23 a 24 a 25 a 301 a 302 a 303
  b 21 b 22 b 23 b 24 b 25 b 301 b 302 b 303
}

finish_test

# 2020-12-16
#
# 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.  The
# focus of this file is flattening UNION ALL sub-queries.
#

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

do_execsql_test 1.0 {
  CREATE TABLE t1_a(a INTEGER PRIMARY KEY, b TEXT);
  CREATE TABLE t1_b(c INTEGER PRIMARY KEY, d TEXT);
  CREATE TABLE t1_c(e INTEGER PRIMARY KEY, f TEXT);

  INSERT INTO t1_a VALUES(1, 'one'), (4, 'four');
  INSERT INTO t1_b VALUES(2, 'two'), (5, 'five');
  INSERT INTO t1_c VALUES(3, 'three'), (6, 'six');

  CREATE VIEW t1 AS 
    SELECT a, b FROM t1_a   UNION ALL
    SELECT c, d FROM t1_b   UNION ALL
    SELECT e, f FROM t1_c;

  CREATE TABLE i1(x);
  INSERT INTO i1 VALUES(2), (5), (6), (1);
}

do_execsql_test 1.1 {
  SELECT a, b FROM (
    SELECT a, b FROM t1_a   UNION ALL
    SELECT c, d FROM t1_b   UNION ALL
    SELECT e, f FROM t1_c
  ) ORDER BY a
} {
  1 one 2 two 3 three 4 four 5 five 6 six
}

do_execsql_test 1.2 {
  SELECT a, b FROM t1 ORDER BY a
} {
  1 one 2 two 3 three 4 four 5 five 6 six
}

do_execsql_test 1.3 {
  SELECT a, b FROM i1, t1 WHERE a=x ORDER BY a
} {1 one 2 two 5 five 6 six}


#-------------------------------------------------------------------------
reset_db

do_execsql_test 2.1.0 {
  CREATE TABLE t1(x, y);
  INSERT INTO t1 VALUES(1, 'one');
  INSERT INTO t1 VALUES(1, 'ONE');
  INSERT INTO t1 VALUES(2, 'two');
  INSERT INTO t1 VALUES(2, 'TWO');
  INSERT INTO t1 VALUES(3, 'three');
  INSERT INTO t1 VALUES(3, 'THREE');
}

do_execsql_test 2.1.1 {
  WITH s(i) AS (
      SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<3
  )
  SELECT * FROM (
    SELECT 0 AS i UNION ALL SELECT i FROM s UNION ALL SELECT 0
  ), t1 WHERE x=i;
} {
  1 1 one 1 1 ONE 2 2 two 2 2 TWO 3 3 three 3 3 THREE
}

do_catchsql_test 2.1.2 {
  WITH s(i) AS (
      SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<3 UNION ALL SELECT 4
  )
  SELECT * FROM s, t1 WHERE x=i;
} {1 {circular reference: s}}

do_execsql_test 2.2.0 {
  CREATE TABLE t2_a(k INTEGER PRIMARY KEY, v TEXT);
  CREATE TABLE t2_b(k INTEGER PRIMARY KEY, v TEXT);

  CREATE VIEW t2 AS 
    SELECT * FROM t2_a 
    UNION ALL 
    SELECT * FROM t2_b;

  CREATE TRIGGER t2_insert INSTEAD OF INSERT ON t2 BEGIN
    INSERT INTO t2_a SELECT new.k, new.v WHERE (new.k%2)==0;
    INSERT INTO t2_b SELECT new.k, new.v WHERE (new.k%2)==1;
  END;

  INSERT INTO t2 VALUES(5, 'v'), (4, 'iv'), (3, 'iii'), (2, 'ii');
}

do_execsql_test 2.2.1 {
  SELECT * FROM t1, t2 WHERE x=k;
} {
  2 two 2 ii 2 TWO 2 ii 3 three 3 iii 3 THREE 3 iii
}

do_execsql_test 2.2.2 {
  SELECT * FROM t1 LEFT JOIN t2 ON (x=k);
} {
  1 one {} {}
  1 ONE {} {}
  2 two 2 ii 2 TWO 2 ii 3 three 3 iii 3 THREE 3 iii
}

do_execsql_test 2.2.3 {
  SELECT x1.*, x2.* FROM t2 AS x1, t2 AS x2 WHERE x1.k=x2.k+1
} {
  4 iv   3 iii 
  3 iii  2 ii 
  5 v    4 iv
}

do_execsql_test 2.2.4 {
  SELECT * FROM t1, t2 WHERE x=k ORDER BY y;
} {
  3 THREE 3 iii 
  2 TWO 2 ii 
  3 three 3 iii 
  2 two 2 ii
}
do_execsql_test 2.2.5 {
  SELECT * FROM t1, t2 WHERE x=k ORDER BY y||'';
} {
  3 THREE 3 iii 
  2 TWO 2 ii 
  3 three 3 iii 
  2 two 2 ii
}
do_execsql_test 2.2.6 {
  SELECT * FROM t1, t2 WHERE x=k ORDER BY v
} {
  2 two   2 ii
  2 TWO   2 ii 
  3 three 3 iii 
  3 THREE 3 iii 
}
do_execsql_test 2.2.7 {
  SELECT * FROM t1, t2 WHERE x=k ORDER BY v||''
} {
  2 two   2 ii
  2 TWO   2 ii 
  3 three 3 iii 
  3 THREE 3 iii 
}
do_execsql_test 2.2.8 {
  SELECT * FROM t1, t2 WHERE x=k ORDER BY k,v||''
} {
  2 two   2 ii
  2 TWO   2 ii 
  3 three 3 iii 
  3 THREE 3 iii 
}
do_execsql_test 2.2.9a {
  SELECT * FROM t1, t2 ORDER BY +k
} {
  1 one 2 ii 1 ONE 2 ii 2 two 2 ii 
  2 TWO 2 ii 3 three 2 ii 3 THREE 2 ii 
  
  1 one 3 iii 1 ONE 3 iii 2 two 3 iii 
  2 TWO 3 iii 3 three 3 iii 3 THREE 3 iii 

  1 one 4 iv 1 ONE 4 iv 2 two 4 iv 
  2 TWO 4 iv 3 three 4 iv 3 THREE 4 iv 

  1 one 5 v 1 ONE 5 v 2 two 5 v 
  2 TWO 5 v 3 three 5 v 3 THREE 5 v
}

do_execsql_test 2.2.9b {
  SELECT * FROM t1, t2 ORDER BY k
} {
  1 one 2 ii 1 ONE 2 ii 2 two 2 ii 
  2 TWO 2 ii 3 three 2 ii 3 THREE 2 ii 
  
  1 one 3 iii 1 ONE 3 iii 2 two 3 iii 
  2 TWO 3 iii 3 three 3 iii 3 THREE 3 iii 

  1 one 4 iv 1 ONE 4 iv 2 two 4 iv 
  2 TWO 4 iv 3 three 4 iv 3 THREE 4 iv 

  1 one 5 v 1 ONE 5 v 2 two 5 v 
  2 TWO 5 v 3 three 5 v 3 THREE 5 v
}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 3.0 {
  CREATE TABLE t1(c INTEGER PRIMARY KEY, d TEXT);
  INSERT INTO t1 VALUES(1,2);
  CREATE TABLE t3_a(k INTEGER PRIMARY KEY, v TEXT);
  INSERT INTO t3_a VALUES(2,'ii');
  CREATE TABLE t3_b(k INTEGER PRIMARY KEY, v TEXT);
  CREATE VIEW t3 AS
    SELECT * FROM t3_a
    UNION ALL
    SELECT * FROM t3_b;
} {}

do_execsql_test 3.1 {
  SELECT * FROM t1, t3 ORDER BY k;
} {1 2 2 ii}

reset_db
do_execsql_test 4.0 {

  CREATE TABLE t1_a(a INTEGER PRIMARY KEY, b TEXT);
  INSERT INTO t1_a VALUES(123, 't1_a');
  CREATE TABLE t1_b(c INTEGER PRIMARY KEY, d TEXT);

  CREATE VIEW t1 AS
    SELECT a, b FROM t1_a
    UNION ALL
    SELECT c, d FROM t1_b;

  CREATE TABLE t3_a(k INTEGER PRIMARY KEY, v TEXT);
  INSERT INTO t3_a VALUES(456, 't3_a');
  CREATE TABLE t3_b(k INTEGER PRIMARY KEY, v TEXT);

  CREATE VIEW t3 AS
    SELECT * FROM t3_a
    UNION ALL
    SELECT * FROM t3_b;
}

do_execsql_test 4.1 {
  SELECT * FROM t1, t3 ORDER BY k;
} {123 t1_a 456 t3_a}

do_execsql_test 4.2 {
  SELECT * FROM (SELECT * FROM t1, t3) ORDER BY k;
} {123 t1_a 456 t3_a}

finish_test

# 2020-12-16
#
# 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.
#
#***********************************************************************
#

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

do_execsql_test 1.0 {
  CREATE TABLE t1(x,y,z);
  CREATE TABLE t3(x,y,z);
}
faultsim_save_and_close


do_faultsim_test 1 -faults oom-t* -prep {
  faultsim_restore_and_reopen
} -body {
  execsql {
    SELECT * FROM t1, (
      SELECT x FROM t1 UNION ALL SELECT y FROM t1
    ), t3
  }
} -test {
  faultsim_test_result {0 {}}
}

finish_test

  CREATE TABLE t3(a INT PRIMARY KEY, j, k, l, m);
  CREATE VIEW v4 AS SELECT * FROM t2 UNION ALL SELECT * FROM t3;
}
do_eqp_test 110 {
  SELECT * FROM t1, v4 WHERE t1.a=?1 AND v4.a=t1.a;
} {
  QUERY PLAN

  `--COMPOUND QUERY
     |--LEFT-MOST SUBQUERY
     |  |--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?)
     |  `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
     `--UNION ALL
        |--SEARCH TABLE t3 USING INDEX sqlite_autoindex_t3_1 (a=?)

        `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
}

# The scan of the t1 table goes first since that enables the ORDER BY
# sort to be omitted.  This would not be possible without constant
# propagation because without it the t1 table would depend on t3.
#
do_eqp_test 120 {